> For the complete documentation index, see [llms.txt](https://isubasinghe.gitbook.io/isithas-wiki/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://isubasinghe.gitbook.io/isithas-wiki/computer_science/compression/noisy_channel_coding_theorem.md).

# Noisy-channel coding theorem

## Basic idea

Shannon's noisy-channel coding theorem identifies channel capacity as the boundary between reliable and unreliable communication. Coding across long blocks can drive decoding error arbitrarily low below capacity despite noise.

## Key formulas

* For a discrete memoryless channel, $C=\max\_{p(x)}I(X;Y)$ bits per channel use.
* For every rate $R\<C$, there exist codes whose error probability approaches zero as block length grows.
* Rates $R>C$ cannot achieve arbitrarily reliable communication; the strong converse strengthens this toward error probability one for many channels.
* Binary symmetric channel capacity: $C=1-H\_2(p)$, where $p$ is the crossover probability.
* An additive white Gaussian noise channel has capacity $C=B\log\_2(1+S/N)$ bits per second under the standard bandwidth and power model.
* Fano's inequality bounds residual uncertainty after estimation: $H(X\mid\hat X)\le h\_2(P\_e)+P\_e\log(|\mathcal X|-1)$.
* It converts a small decoding error probability into small conditional entropy and is a standard ingredient in converse proofs.

## Resources

<https://en.wikipedia.org/wiki/Noisy-channel_coding_theorem>