The channel coding theorem, also known as Shannon’s second theorem or the noisy‑channel coding theorem, is a foundational result in information theory. It was established by Claude Shannon in his seminal 1948 paper “A Mathematical Theory of Communication.” The theorem precisely characterizes the maximum rate at which information can be transmitted over a noisy communication channel with arbitrarily low probability of error. This maximum rate is the channel capacity. The theorem shows that for any rate strictly below capacity, there exists an error‑correcting code that makes the probability of decoding error arbitrarily small; conversely, for any rate above capacity, such reliable transmission is impossible. The theorem thus provides the theoretical limits for both data compression (source coding) and error correction (channel coding), serving as the benchmark for all practical communication systems.
1.1 Historical context
Before Shannon’s work, communication engineers knew that noise limited the accuracy of transmission, but no unified theory existed to quantify these limits. Shannon, building on earlier work by Harry Nyquist and Ralph Hartley, introduced probabilistic models for both sources and channels. His 1948 paper revolutionized the field by showing that reliable communication is possible even over very noisy channels, provided the transmission rate does not exceed a fundamental quantity he called “capacity.” This insight was initially met with skepticism, as it contradicted the prevailing engineering intuition that errors could only be reduced by increasing signal power or decreasing speed. Subsequent research confirmed Shannon’s claims, leading to the development of modern coding theory.
1.2 Role in information theory
The channel coding theorem is one of three cornerstones of information theory, alongside the source coding theorem (which sets the limits of lossless compression) and the rate‑distortion theorem (for lossy compression). Together, these theorems establish the fundamental limits of data handling. The channel coding theorem specifically addresses the trade‑off between transmission rate and reliability. It motivates the design of error‑correcting codes that approach capacity, and it provides a theoretical upper bound that any practical system cannot exceed. The theorem also plays a crucial role in the source–channel separation theorem, which states that optimal performance can be achieved by separating source compression and channel coding.
A rigorous statement of the channel coding theorem requires precise definitions of the communication model.
2.1 Definitions and notation
2.1.1 Discrete memoryless channel
| A discrete memoryless channel (DMC) is defined by an input alphabet \(\mathcal{X}\), an output alphabet \(\mathcal{Y}\), and a transition probability matrix \(P(y | x)\) giving the probability of receiving output \(y\) when input \(x\) is sent. The channel is memoryless in the sense that the output probability depends only on the current input and not on past inputs or outputs. The DMC is the simplest model studied in information theory, yet it captures the essential features of many real channels. |
|---|
2.1.2 Channel capacity
The capacity \(C\) of a DMC is the maximum mutual information between the input and output over all possible input distributions:
\[
| C = \max_{p(x)} I(X;Y) = \max_{p(x)} \sum_{x,y} p(x) P(y | x) \log \frac{P(y | x)}{\sum_{x'} p(x') P(y | x')}. |
|---|
\]
Capacity is measured in bits per channel use and represents the maximum possible transmission rate that can be achieved with arbitrarily small error probability.
2.1.3 Coding rate and block length
A code of block length \(n\) and rate \(R\) is a set of \(M = 2^{nR}\) messages, each mapped to a codeword of length \(n\) over the input alphabet. The encoder selects a codeword for the message, and the decoder, upon observing the channel output of length \(n\), estimates the transmitted message. The rate \(R\) is expressed in bits per channel use.
2.2 Theorem statement
The channel coding theorem can be split into two parts.
2.2.1 Direct part (achievability)
If \(R < C\), then for any \(\epsilon > 0\) there exists a sequence of codes of rate \(R\) and increasing block length \(n\) such that the average probability of decoding error is less than \(\epsilon\). Moreover, for any fixed \(R < C\), there exist codes that achieve arbitrarily high reliability as the block length grows.
2.2.2 Converse part (impossibility)
If \(R > C\), then for any sequence of codes of rate \(R\), the average probability of error is bounded away from zero, and in fact tends to 1 as the block length increases. Hence reliable communication is impossible at rates exceeding the capacity.
The proof of the direct part relies on a random coding argument combined with the concept of joint typicality, while the converse uses the data‑processing inequality and Fano’s inequality.
3.1 Random coding argument
3.1.1 Codebook generation
Instead of constructing a specific code, one considers an ensemble of codes. For a given block length \(n\) and rate \(R\), generate a codebook of \(2^{nR}\) codewords by choosing each symbol independently according to a fixed input distribution \(p(x)\) that achieves capacity. The actual code is drawn at random from this ensemble.
3.1.2 Encoding and decoding
Encoding maps each message to its corresponding codeword. The decoder uses typical set decoding: it looks for the unique codeword that is jointly typical with the received output vector. If no such codeword exists, or more than one exists, an error is declared.
3.2 Joint typicality
3.2.1 Typical sequences
A sequence \(x^n\) is typical with respect to \(p(x)\) if its empirical frequency of each symbol is close to the distribution \(p(x)\). The set of all such sequences, the typical set, contains nearly all probability mass for large \(n\), and its size is approximately \(2^{nH(X)}\).
3.2.2 Joint typical set
A pair \((x^n, y^n)\) is jointly typical with respect to the joint distribution \(p(x,y)\) if the empirical distribution of the pair is close to \(p(x,y)\) and the individual sequences are typical. For any independent pair \((X^n, Y^n)\) drawn from the product distribution \(p(x)p(y)\) (i.e., not necessarily from the channel), the probability that they are jointly typical is about \(2^{-nI(X;Y)}\).
3.3 Error probability analysis
3.3.1 Average over codebooks
Consider a fixed message and its codeword. The decoder makes an error if either the transmitted codeword is not jointly typical with the output (an “encoding error”) or if another codeword is jointly typical with the output (a “confusion error”). The probability of the former can be made arbitrarily small by choosing a large enough \(n\). The probability of the latter is bounded by the number of other codewords times the probability that an independent codeword is jointly typical, which is about \(2^{-n(I(X;Y)-R)}\). Thus, if \(R < I(X;Y) \leq C\), the sum of error probabilities can be made arbitrarily small.
3.3.2 Bounding error events
Averaging the error probability over all random codebooks shows that there exists at least one deterministic codebook with error probability no larger than the average. By optimizing over input distributions, one achieves error arbitrarily small for any \(R < C\).
4.1 Error‑correcting codes
The theorem motivates the design of codes that approach the capacity bound. Several families of codes have been developed.
4.1.1 Linear block codes
Linear block codes, such as Hamming codes and Reed–Solomon codes, map messages to codewords via linear transformations. They have a rich algebraic structure that simplifies encoding and decoding, though they often fall short of capacity.
4.1.2 Convolutional codes
Convolutional codes process data as a continuous stream through shift registers. They are widely used in practice, especially with Viterbi decoding, and can achieve good performance at moderate block lengths.
4.1.3 Modern codes (LDPC, turbo)
Low‑density parity‑check (LDPC) codes and turbo codes are capacity‑approaching codes discovered in the 1990s. They use iterative decoding algorithms (e.g., belief propagation) that perform near the Shannon limit for many channel models. LDPC codes, for instance, are now standard in satellite communications and Wi‑Fi.
4.2 Fundamental limits in communication
The channel coding theorem provides a precise trade‑off among rate, bandwidth, and signal‑to‑noise ratio.
4.2.1 Bandwidth versus signal‑to‑noise ratio
For an additive white Gaussian noise (AWGN) channel of bandwidth \(W\) and signal‑to‑noise ratio \(S/N\), the capacity in bits per second is given by the Shannon–Hartley law:
\[ C = W \log_2\left(1 + \frac{S}{N}\right). \]
This formula shows that capacity increases logarithmically with SNR and linearly with bandwidth.
4.2.2 Power and bandwidth trade‑offs
To increase capacity, one can either increase bandwidth or signal power. However, as bandwidth grows, the noise power also increases (since noise is white), so the capacity tends to a finite limit of about \(1.44\, S/N_0\) (in bits/second), where \(N_0\) is the noise power spectral density. This illustrates the power‑limited and bandwidth‑limited regimes.
5.1 Channels with feedback
When a noiseless feedback channel is available (the transmitter knows what the receiver obtained), capacity does not increase for a DMC, but coding complexity can be reduced. For channels with memory, feedback may increase capacity.
5.2 Continuous and Gaussian channels
5.2.1 AWGN channel capacity
The AWGN channel has real‑valued inputs and outputs, with additive white Gaussian noise of variance \(N_0/2\). Under an average power constraint \(P\), the capacity per channel use is:
\[ C = \frac{1}{2} \log_2\left(1 + \frac{P}{N_0/2}\right) \quad \text{bits per use}. \]
This serves as the baseline for many real‑world channels.
5.2.2 Water‑filling interpretation
For channels with different noise levels at different frequencies (e.g., orthogonal frequency bands), the transmitter should allocate power according to the water‑filling principle: more power is allocated to bands with higher SNR. This strategy achieves the overall capacity.
5.3 Multiple‑access channels
5.3.1 Capacity region
A multiple‑access channel (MAC) has several transmitters sending to a single receiver. The set of achievable rate tuples forms a convex capacity region. For the Gaussian MAC, the region is a pentagon defined by constraints that each user’s rate cannot exceed its single‑user capacity, and the sum rate is bounded by the capacity of the channel with combined power.
5.3.2 Broadcast channels
In a broadcast channel, one transmitter sends to multiple independent receivers. Capacity regions are more complex; the degraded broadcast channel, where the receivers have increasing noise levels, has a known capacity region achieved by superposition coding.
6.1 Source coding theorem (lossless)
The source coding theorem (Shannon’s first theorem) states that the minimum average number of bits needed to represent a source without loss is its entropy. Together with the channel coding theorem, these two results separate the compression and transmission problems.
6.2 Source–channel separation theorem
The source–channel separation theorem asserts that, for a discrete memoryless source and a discrete memoryless channel, it is optimal to compress the source to its entropy rate and then transmit the compressed bits over the channel at a rate below capacity. No joint coding scheme can achieve a lower overall distortion. This theorem justifies the modular design of communication systems.
6.3 Rate–distortion theory
When lossy compression is allowed, rate–distortion theory (Shannon’s third theorem) specifies the minimum rate required to achieve a given distortion, or equivalently, the minimum distortion achievable at a given rate. This is the counterpart for lossy compression, just as the source coding theorem is for lossless compression. The channel coding theorem remains the same for the transmission of the compressed bits.