CCapacity Atlas
finite-group-additive-noise-channel

Finite-group additive-noise channel

A symbol in a finite group is corrupted by independent additive noise with a known distribution.

Point-to-point Finite alphabet Discrete memoryless Additive noise Symmetric Capacity Exact

Channel and question

Input
\(X\in G\), where \(G\) is a finite group.
Output
\(Y\in G\)
Law
\(Y=X+Z\), with iid noise \(Z\) independent of \(X\).
Quantity
Shannon capacity \(C\), measured in bits per channel use.

Criterion. Average-error capacity.

  • The group operation and noise law are known.
  • Logarithms use base 2.

Current status

\[C=\log_2|G|-H(Z)\]

The uniform input achieves capacity.

Known results and bounds for Finite-group additive-noise channel
ResultRelationMethodYear
Lower\(C\ge\log_2|G|-H(Z)\)Uniform input makes the output uniform.1948
Upper\(C\le\log_2|G|-H(Z)\)Bound output entropy by log alphabet size.1948

Formal verification

Lean coverageFormally stated

Translation equivalences prove that every row has the noise entropy and that uniform input produces uniform output. The operational formula follows from the formal finite-channel coding theorem.

Claims

  • For any finite additive group and noise law, information capacity is log₂|G|-H(Z).
    information-capacity · exact capacity · solved · Formally proved · v1
  • For any finite additive group and noise law, operational capacity is log₂|G|-H(Z).
    operational-capacity · exact capacity · solved · Formally proved · v1
Lean declarations (4)

References

  1. Claude E. Shannon (1948). A Mathematical Theory of Communication. Bell System Technical Journal. DOI 10.1002/j.1538-7305.1948.tb01338.x.
  2. Thomas M. Cover and Joy A. Thomas (2006). Elements of Information Theory. Wiley, second edition. DOI 10.1002/047174882X.

Discussion

Find discussionStart discussion

Related problems

AWGN channel with noiseless feedback

Noiseless output feedback improves reliability without changing AWGN capacity.

Point-to-point Continuous alphabet Gaussian Additive noise Feedback Power constraint Capacity Exact
Solved \(C_{\mathrm{AWGN,fb}}=\frac12\log_2\!\left(1+\frac PN\right)\)
Binary Z-channel Z-channel

One binary symbol is transmitted perfectly while the other can flip in only one direction.

Point-to-point Binary Finite alphabet Discrete memoryless Asymmetric Capacity Exact
Solved \(C_Z(p)=\log_2\!\left(1+(1-p)p^{p/(1-p)}\right)\)
Binary erasure channel BEC

Each transmitted bit is received correctly or replaced by a visible erasure symbol.

Point-to-point Binary Finite alphabet Discrete memoryless Symmetric Erasure Capacity Exact
Solved \(C_{\mathrm{BEC}}(\varepsilon)=1-\varepsilon\)
Binary memory with encoder-known stuck-at defects

Independent stuck-at defects are known noncausally to the encoder but not the decoder.

Point-to-point Binary Finite alphabet Discrete memoryless Noncausal state information Capacity Exact
Solved \(C=1-\delta\)