CCapacity Atlas
discrete-memoryless-channel

Finite discrete memoryless channel

The general finite memoryless point-to-point channel has a single-letter mutual-information capacity formula.

Point-to-point Finite alphabet Discrete memoryless Capacity Exact Single-letter characterization

Channel and question

Input
\(X\in\mathcal X\), with finite \(\mathcal X\).
Output
\(Y\in\mathcal Y\), with finite \(\mathcal Y\).
Law
A stochastic matrix \(W(y\mid x)\), used independently at each channel use.
Quantity
Shannon capacity \(C(W)\), measured in bits per channel use.

Criterion. Average-error capacity.

  • The channel law is known to encoder and decoder.
  • Average decoding error vanishes with blocklength.

Current status

\[C(W)=\max_{P_X} I(X;Y)\]

The maximum is over distributions on the finite input alphabet.

Known results and bounds for Finite discrete memoryless channel
ResultRelationMethodYear
Lower\(C(W)\ge\max_{P_X}I(X;Y)\)Random coding and typical decoding.1948
Upper\(C(W)\le\max_{P_X}I(X;Y)\)Fano's inequality, the chain rule, and memorylessness.1948

Formal verification

Lean coverageFormally stated

The finite-channel coding theorem is proved locally from a threshold random-coding argument and a weak Fano converse. The proof covers every finite channel, including the repository's empty-input convention.

Claims

  • For every finite channel, operational vanishing-average-error capacity equals single-letter information capacity.
    exact-capacity · exact capacity · solved · Formally proved · v1
Lean declarations (12)

History

  1. Shannon proved the noisy-channel coding theorem.

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

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\)
Binary symmetric channel BSC

Each bit is independently flipped with probability \(p\).

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