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.

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

Lean formalization

Canonical statementNone

Version 1 · Lean. Finite entropy and finite-group channel infrastructure remain to be shared.

Substantial proofs0 linked

No external Lean proof is registered. Proofs longer than roughly 50 lines or requiring problem-specific infrastructure should live in a dedicated repository and link back to this statement version.

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

Thread key: capacityatlas:finite-group-additive-noise-channel

Find discussionStart discussion

Related problems

AWGN channel with noiseless feedback

Noiseless feedback dramatically improves reliability schemes but leaves the ordinary AWGN capacity unchanged.

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 symmetric channel BSC

Each bit is independently flipped with probability p, giving the canonical finite noisy channel.

Point-to-point Binary Finite alphabet Discrete memoryless Symmetric Capacity Exact
Solved \(C_{\mathrm{BSC}}(p)=1-h_2(p)\)