46.03.02 · information-theory / channel-capacity

Shannon's Noisy Channel Coding Theorem: Achievability via Random Coding

shipped3 tiersLean: none

Anchor (Master): Cover & Thomas 2006 Elements of Information Theory 2e (Wiley) §7.4-7.7; Csiszar & Korner 2011 Information Theory: Coding Theorems for Discrete Memoryless Systems 2e (Cambridge) §2.1-2.3; Shannon 1948 A Mathematical Theory of Communication section 13 (the original random coding argument)

Intuition Beginner

You have a noisy channel. You want to send messages reliably. How fast can you go? Shannon answered this in 1948: the maximum reliable rate is the channel capacity $C$ , a single number determined entirely by the channel's noise statistics. Any rate below $C$ is achievable. Any rate above $C$ is not.

The surprise is that the capacity is nonzero at all. A channel that flips 10% of your bits seems like it should corrupt any message beyond recovery. But if you use the channel many times and encode cleverly, the errors average out. You can push through almost $C$ bits of information per use, with errors that vanish as you use the channel more and more.

How do you prove such a thing exists? Shannon's trick was random coding. Instead of designing one clever code, imagine picking codewords at random from a giant hat. Each codeword is a sequence of symbols drawn independently from a fixed distribution. You pick $2^{n R}$ such codewords, each of length $n$ , for a rate of $R$ bits per channel use.

Then you transmit one codeword through the noisy channel. The receiver gets a corrupted version. To decode, the receiver looks for the codeword that is "jointly typical" with the received sequence — meaning the pair looks like it was generated by the joint input-output distribution of the channel. If the rate is below capacity, there is almost surely only one such codeword, and the decoder recovers the message.

The argument works on average over the random codebook. Most random codebooks are good. The probability that a randomly chosen codebook causes a decoding error goes to zero as the block length grows. Therefore, at least one good codebook exists. You do not know which one, but existence is enough.

Visual Beginner

Parameter	Meaning
$n$	Block length (number of channel uses per codeword)
$R$	Rate in bits per channel use
$2^{n R}$	Number of codewords in the codebook
$C$	Channel capacity
$P_{e}$	Probability of decoding error

Figure: A diagram showing a codebook as a tall rectangular array. Each row is a codeword of length $n$ . There are $2^{n R}$ rows. An arrow from row $W$ goes into a "channel" box, which corrupts some symbols, producing a received word $y^{n}$ . A decoder box compares $y^{n}$ to all codewords and outputs the index of the one that is jointly typical. Below the diagram, a graph shows $P_{e}$ versus $R$ : for $R < C$ , the error curve drops exponentially toward zero as $n$ increases; for $R > C$ , the error stays bounded away from zero.

Worked example Beginner

Consider a binary symmetric channel (BSC) with crossover probability $p = 0.1$ . Its capacity is $C = 1 - H (0.1)$ , where $H$ is the binary entropy function.

First compute $H (0.1)$ . This is $- 0.1 lo g_{2} 0.1 - 0.9 lo g_{2} 0.9$ . Working it out: $0.1 \times 3.322 + 0.9 \times 0.152 = 0.332 + 0.137 = 0.469$ bits. So $C = 1 - 0.469 = 0.531$ bits per channel use.

The theorem says: for any rate $R < 0.531$ , you can find codes that achieve error probability as small as you like, provided you use the channel enough times. Let us check $R = 0.5$ , which is safely below capacity.

With $R = 0.5$ and block length $n = 100$ , you have $2^{50}$ codewords. That is about $1 0^{15}$ codewords — far too many to write down, but the random coding argument says they exist. Each codeword has 100 bits. The channel flips about 10 of them.

The decoder receives a 100-bit sequence with roughly 10 errors. It checks which codeword is jointly typical with the received sequence. A jointly typical pair $(X^{n}, Y^{n})$ satisfies two conditions: $X^{n}$ is typical for the input distribution, $Y^{n}$ is typical for the output distribution, and the pair is typical for the joint distribution. For $R = 0.5 < C = 0.531$ , there are few enough codewords that the wrong ones are unlikely to be jointly typical with the received word. The error probability vanishes as $n$ grows.

Check your understanding Beginner

Formal definition Intermediate+

Let $p (y ∣ x)$ be a discrete memoryless channel with input alphabet $X$ and output alphabet $Y$ . Let $C = max_{p (x)} I (X; Y)$ be the channel capacity, and let $p^{*} (x)$ denote a capacity-achieving input distribution.

Definition (Codebook). An $(n, M)$ code for the channel consists of:

An index set $W = {1, 2, \dots, M}$ (the message set).
An encoding function $f : W \to X^{n}$ mapping each message to a codeword $x^{n} (w) = (x_{1} (w), \dots, x_{n} (w))$ .
A decoding function $g : Y^{n} \to W$ mapping each received sequence to a message estimate.

The rate of the code is $R = (lo g_{2} M) / n$ bits per channel use.

Definition (Probability of error). The maximal probability of error for the code is:

P_{e}^{(n)} = w \in W max Pr [g (Y^{n}) \neq = w ∣ X^{n} = f (w)] .

Definition (Achievable rate). A rate $R$ is achievable if there exists a sequence of $(n, 2^{n R})$ codes with $P_{e}^{(n)} \to 0$ as $n \to \infty$ .

Definition (Channel capacity). The channel capacity is the supremum of all achievable rates:

C = sup {R : R is achievable} .

Counterexamples to common slips

The theorem does not say the error is zero. It says the error probability goes to zero as the block length increases. For any finite $n$ , the error is positive. The asymptotic statement is that you can make the error as small as you like by using a long enough code.
Achievability and converse are two separate proofs. The achievability part shows $R < C$ implies reliable codes exist. The converse shows $R > C$ implies reliable codes do not exist. Together they pin down $C$ as the sharp threshold.
Random coding does not produce a usable code. The random coding argument shows existence. It does not give you a specific codebook or a practical decoder. The gap between existence and construction is where coding theory lives.

Key theorem with proof Intermediate+

Theorem (Shannon's noisy channel coding theorem — achievability). For a discrete memoryless channel with capacity $C$ , every rate $R < C$ is achievable. That is, for any $R < C$ , there exists a sequence of $(n, 2^{n R})$ codes with $P_{e}^{(n)} \to 0$ as $n \to \infty$ .

Proof. The proof has four steps: random codebook generation, joint typicality decoding, error analysis, and the existence argument.

Step 1: Random codebook generation. Fix a rate $R < C$ . Fix the capacity-achieving input distribution $p^{*} (x)$ . Generate a codebook $C$ with $M = 2^{n R}$ codewords by drawing each codeword independently: for each message $w \in {1, \dots, M}$ , the codeword $X^{n} (w) = (X_{1} (w), \dots, X_{n} (w))$ is drawn i.i.d. from $p^{*} (x)$ . The $M$ codewords are independent of each other.

Step 2: Joint typicality decoder. After receiving $Y^{n}$ , the decoder declares message $\overset{w}{^}$ if there is a unique $w$ such that $(X^{n} (w), Y^{n})$ is jointly $ϵ$ -typical with respect to the joint distribution $p^{*} (x) p (y ∣ x)$ . If no such $w$ exists or more than one exists, the decoder declares an error.

Recall from 46.02.01 that $(x^{n}, y^{n})$ is jointly $ϵ$ -typical if:

- \frac{1}{n} lo g p^{*} (x^{n}) - H (X) < ϵ, - \frac{1}{n} lo g p (y^{n}) - H (Y) < ϵ,

- \frac{1}{n} lo g p (x^{n}, y^{n}) - H (X, Y) < ϵ .

Step 3: Error analysis. Let $W$ be uniform on ${1, \dots, M}$ and independent of the codebook. By symmetry of the random coding construction, the average error probability is the same for all messages, so:

Pr (error) = Pr (\hat{W} \neq = 1 ∣ W = 1) .

An error occurs if either the transmitted codeword is not jointly typical with the received sequence (event $E_{1}$ ), or some other codeword is jointly typical with the received sequence (event $E_{2, w}$ for wrong codeword $w$ ).

By the joint AEP, $Pr (E_{1}) \to 0$ as $n \to \infty$ .

For the wrong codewords: codeword $X^{n} (w)$ for $w \neq = 1$ is generated independently of $Y^{n}$ (which depends only on $X^{n} (1)$ ). By the joint AEP, the probability that $X^{n} (w)$ is jointly typical with $Y^{n}$ is at most $2^{- n (I (X; Y) - 3 ϵ)}$ . By the union bound:

Pr (w = 2 ⋃ M E_{2, w}) \leq (M - 1) \cdot 2^{- n (I (X; Y) - 3 ϵ)} = 2^{n R} \cdot 2^{- n (I (X; Y) - 3 ϵ)} = 2^{- n (I (X; Y) - R - 3 ϵ)} .

Since $R < C = I (X; Y)$ at the capacity-achieving distribution, we can choose $ϵ$ small enough that $I (X; Y) - R - 3 ϵ > 0$ . Then the union bound probability vanishes exponentially in $n$ .

Step 4: Existence. The average error probability over the random codebook vanishes. Therefore, there exists at least one codebook for which the error probability is at most the average. This codebook gives an $(n, 2^{n R})$ code with $P_{e}^{(n)} \to 0$ . $□$

Bridge. The achievability proof builds toward the converse in 46.03.03, where Fano's inequality shows that rates above $C$ cannot be achieved, completing the full coding theorem. The joint typicality decoder appears again in rate-distortion theory 46.04.01 as the same typicality test used to match source sequences to reproduction codewords. The foundational reason random coding works is that independently generated codewords spread out in the output space so that the probability of two codewords landing in the same typicality region is exponentially small — this is exactly the packing interpretation of capacity. The random coding exponent $E_{r} (R) = max_{s} [E_{0} (s, p^{*}) - s R]$ governing the speed of convergence generalises to the reliability function of the channel. Putting these together, the achievability proof reveals that capacity is not merely an upper bound but a sharp threshold: the boundary between the achievable and the impossible.

Exercises Intermediate+

Exercise (hard, short answer).

Show that the probability of the joint typicality event $Pr {(X^{n}, Y^{n}) \in A_{ϵ}^{(n)}}$ converges to 1 as $n \to \infty$ , where $A_{ϵ}^{(n)}$ is the jointly $ϵ$ -typical set and $(X^{n}, Y^{n})$ is drawn from the joint distribution $p^{*} (x)^{n} p (y ∣ x)^{n}$ .

Hint

Use the law of large numbers on the empirical entropies.

Answer

The pair $(X^{n}, Y^{n})$ consists of $n$ i.i.d. draws from $p^{*} (x, y) = p^{*} (x) p (y ∣ x)$ . The joint typicality conditions require the empirical averages $- \frac{1}{n} lo g p^{*} (X^{n})$ , $- \frac{1}{n} lo g p (Y^{n})$ , and $- \frac{1}{n} lo g p (X^{n}, Y^{n})$ to be within $ϵ$ of $H (X)$ , $H (Y)$ , and $H (X, Y)$ respectively. Each of these is an average of i.i.d. random variables: $- \frac{1}{n} lo g p^{*} (X^{n}) = \frac{1}{n} \sum_{i = 1}^{n} (- lo g p^{*} (X_{i}))$ , and similarly for the others. By the weak law of large numbers, each average converges in probability to its expected value. The intersection of three high-probability events is also high-probability (each event has probability $\geq 1 - δ$ for large $n$ , so the intersection has probability $\geq 1 - 3 δ$ ). Therefore the probability of being jointly typical converges to 1.

Exercise (hard, short answer).

For the binary erasure channel with erasure probability $e$ , capacity is $C = 1 - e$ . The random coding achievability proof uses a uniform input distribution. Sketch the joint typicality decoder for the BEC: what does joint typicality mean when the received word contains erasure symbols?

Answer

On the BEC, the output alphabet is ${0, 1, ?}$ . A jointly typical pair $(x^{n}, y^{n})$ satisfies: (1) the empirical distribution of $x^{n}$ is close to uniform, (2) the empirical distribution of $y^{n}$ is close to the output distribution, and (3) the joint empirical distribution is close to $p (x, y)$ . On the BEC, joint typicality has a simple interpretation: on unerased positions, $y_{i} = x_{i}$ ; on erased positions, $y_{i} = ?$ and $x_{i}$ can be anything. For a wrong codeword $X^{n} (w)$ generated independently of $Y^{n}$ , the unerased positions of $Y^{n}$ are random with respect to $X^{n} (w)$ , so the probability of matching all unerased positions is roughly $2^{- n (1 - e)}$ . The decoder effectively checks agreement on the unerased positions; a wrong codeword matches with probability $\approx 2^{- n (1 - e)}$ , and with $2^{n R}$ codewords the union bound gives $2^{- n (1 - e - R)}$ , which vanishes when $R < 1 - e = C$ .

Exercise (hard, short answer).

The random coding exponent (Gallager's $E_{r} (R)$ ) is defined as $E_{r} (R) = max_{0 \leq s \leq 1} max_{p (x)} [E_{0} (s, p) - s R]$ where $E_{0} (s, p) = - lo g \sum_{y} (\sum_{x} p (x) p (y ∣ x)^{1 - s})^{1/ (1 - s)}$ . Show that $E_{r} (R) > 0$ for $R < C$ and $E_{r} (C) = 0$ .

Hint

Evaluate $E_{0}$ at $s \to 0$ and use $d E_{0} / d s ∣_{s = 0}$ to connect to mutual information.

Answer

At $s = 0$ : $E_{0} (0, p) = - lo g \sum_{y} 1 = - lo g ∣ Y ∣$ ... wait, more carefully: $E_{0} (0, p) = - lo g \sum_{y} (\sum_{x} p (x))^{1} = - lo g \sum_{y} 1 = 0$ since $∣ Y ∣$ terms each equal 1. So $E_{r} (R) \geq E_{0} (0, p) - 0 = 0$ .

Compute $\frac{\partial E _{0}}{\partial s}_{s = 0}$ . By the envelope theorem, $\frac{\partial E _{0}}{\partial s}_{s = 0, p = p^{*}} = I (X; Y) = C$ (this is the mutual information at the capacity-achieving distribution). Therefore for small $s > 0$ : $E_{0} (s, p^{*}) \approx s C + O (s^{2})$ , so $E_{0} (s, p^{*}) - s R \approx s (C - R) + O (s^{2})$ . For $R < C$ , choosing small positive $s$ gives $E_{r} (R) > 0$ . At $R = C$ , $s (C - R) = 0$ and the higher-order terms are non-positive (since $E_{0}$ is concave in $s$ ), giving $E_{r} (C) = 0$ .

Lean formalization Intermediate+

Mathlib has the PMF type for discrete distributions and basic measure-theoretic machinery, but it does not define a channel coding problem. There is no codebook type (a finite collection of codewords), no encoding/decoding function, no probability of error computation, no joint typicality set, and no achievability theorem. The random codebook generation requires product distributions on $X^{n}$ , which Mathlib can express via PMF.bind and Fin vectors, but the typicality condition and its convergence properties are absent. A Codex.InformationTheory.ChannelCoding module would need to define codebooks, decoding functions, error probabilities, and prove the achievability bound via the joint AEP and the union bound. This unit ships without formalization.

Advanced results Master

The random coding exponent

The achievability proof shows that $P_{e}^{(n)} \to 0$ for $R < C$ , but it does not specify the speed. Gallager (1965) sharpened the analysis to show that the error probability decays exponentially:

P_{e}^{(n)} \leq 2^{- n E_{r} (R)},

where the random coding exponent (or Gallager exponent) is:

E_{r} (R) = 0 \leq s \leq 1 max p (x) max [E_{0} (s, p) - s R],

with

E_{0} (s, p) = - lo g_{2} y \in Y \sum (x \in X \sum p (x) p (y ∣ x)^{1 - s})^{1/ (1 - s)} .

The function $E_{r} (R)$ is positive for $R < C$ , zero at $R = C$ , and decreasing in $R$ . It gives a quantitative bound on how fast the error decays as a function of the gap $C - R$ and the channel structure. For the BSC with $p = 0.1$ and $R = 0.5$ , the exponent is approximately $E_{r} (0.5) \approx 0.02$ , giving $P_{e}^{(n)} \leq 2^{- 0.02 n}$ . At $n = 1000$ , this is about $2^{- 20} \approx 1 0^{- 6}$ .

The method of types achievability

An alternative proof of achievability uses the method of types rather than joint typicality. A type (or empirical distribution) of a sequence $x^{n}$ is the distribution $P_{x^{n}}$ that assigns frequency $n_{i} / n$ to symbol $i$ . The type class $T (P)$ is the set of all sequences with empirical distribution $P$ .

The key properties are: (1) the number of types is polynomial in $n$ (at most $(n + 1)^{∣ X ∣ - 1}$ ), (2) each type class has size $∣ T (P) ∣ = 2^{n H (P)} (1 + o (1))$ , and (3) the probability of a type class under distribution $Q$ is $Q^{n} (T (P)) = 2^{- n D (P ∥ Q)} (1 + o (1))$ .

For the achievability proof, the encoder sends codewords drawn uniformly from type classes close to the capacity-achieving type $P^{*}$ . The decoder finds the unique codeword whose joint type with the received sequence is close to the joint distribution $P^{*} \times p (y ∣ x)$ . The error analysis counts the number of type classes that could cause confusion and bounds the probability using the divergence between the true joint type and the confounding type. This gives a stronger bound on the pre-factor (polynomial instead of exponential in $n$ ) at the cost of a slightly more involved counting argument.

Strong converse and the strong coding theorem

The standard achievability proof shows that rates below $C$ are achievable with error probability tending to zero. The strong converse (Wolfowitz, 1957) shows something stronger: for rates above $C$ , the error probability tends to 1 (not merely stays bounded away from zero). Together:

Theorem (Strong converse). For any sequence of $(n, 2^{n R})$ codes with $R > C$ :

P_{e}^{(n)} \to 1 as n \to \infty.

The strong converse is proved using the strong typicality version of the joint AEP and a refinement of Fano's inequality. The key insight is that when $R > C$ , there are more codewords than the typicality regions can accommodate, and most codewords collide, forcing the decoder into errors with overwhelming probability.

The reliability function

The random coding exponent $E_{r} (R)$ is a lower bound on the best achievable error exponent. The reliability function $E (R)$ is the best achievable exponent:

E (R) = - n \to \infty lim \frac{1}{n} lo g P_{e}^{*, (n)} (R),

where $P_{e}^{*, (n)} (R)$ is the minimum error probability over all $(n, 2^{n R})$ codes. The reliability function satisfies $E_{r} (R) \leq E (R) \leq E_{s p} (R)$ , where $E_{s p} (R)$ is the sphere-packing exponent (the best known upper bound on $E (R)$ ). For $R$ close to $C$ , $E_{r} (R) = E (R) = E_{s p} (R)$ , so the reliability function is known exactly near capacity. For low rates, a gap between $E_{r}$ and $E_{s p}$ persists, and the exact reliability function is one of the major open problems in information theory.

Synthesis. Shannon's achievability proof is the foundational result that gives capacity its operational meaning: the maximum $C = max_{p (x)} I (X; Y)$ is the sharp threshold between reliable and unreliable communication. The random coding argument is the central insight — generating codewords independently from the capacity-achieving distribution ensures that wrong codewords are exponentially unlikely to masquerade as the transmitted one, and this is exactly the packing interpretation of the typicality regions. The Gallager exponent refines this to a quantitative bound on the error decay, building toward the reliability function $E (R)$ which remains partially open. The method of types provides an alternative achievability route that appears again in the strong converse and in rate-distortion theory. The achievability proof generalises to continuous channels (AWGN), to channels with memory, and to multiuser settings, putting these together into the information-theoretic framework that underpins all of modern communications.

Full proof set Master

Proposition (Size of the jointly typical set). Let $A_{ϵ}^{(n)}$ be the jointly $ϵ$ -typical set for the distribution $p (x, y) = p^{*} (x) p (y ∣ x)$ . Then:

∣ A_{ϵ}^{(n)} ∣ \leq 2^{n (H (X, Y) + ϵ)} .

Proof. By definition, for any $(x^{n}, y^{n}) \in A_{ϵ}^{(n)}$ :

p (x^{n}, y^{n}) \geq 2^{- n (H (X, Y) + ϵ)} .

Since $p$ is a probability distribution:

1 \geq (x^{n}, y^{n}) \in A_{ϵ}^{(n)} \sum p (x^{n}, y^{n}) \geq ∣ A_{ϵ}^{(n)} ∣ \cdot 2^{- n (H (X, Y) + ϵ)} .

Rearranging: $∣ A_{ϵ}^{(n)} ∣ \leq 2^{n (H (X, Y) + ϵ)}$ . $□$

Proposition (Probability that a wrong codeword is jointly typical). Let $X^{n} (w)$ be drawn from $(p^{*})^{n}$ independently of $Y^{n}$ (which was generated by transmitting $X^{n} (1)$ through the channel). Then for $n$ sufficiently large:

Pr {(X^{n} (w), Y^{n}) \in A_{ϵ}^{(n)}} \leq 2^{- n (I (X; Y) - 3 ϵ)} .

Proof. The joint distribution of $(X^{n} (w), Y^{n})$ factors as $(p^{*})^{n} \times p_{Y ∣ X}^{n}$ when conditioned on $X^{n} (w)$ , but since $X^{n} (w)$ is independent of the transmitted codeword, the pair $(X^{n} (w), Y^{n})$ has the product distribution $p^{*} (x)^{n} \cdot p_{Y} (y)^{n}$ (not the joint distribution $p^{*} (x)^{n} p (y ∣ x)^{n}$ ).

For $(x^{n}, y^{n}) \in A_{ϵ}^{(n)}$ :

p^{*} (x^{n}) \cdot p_{Y} (y^{n}) = p (x^{n}, y^{n}) \cdot \frac{p ^{*} ( x ^{n} ) p _{Y} ( y ^{n} )}{p ( x ^{n} , y ^{n} )} = p (x^{n}, y^{n}) \cdot 2^{- n [\frac{1}{n} l o g \frac{p ( x ^{n} , y ^{n} )}{p ^{*} ( x ^{n} ) p _{Y} ( y ^{n} )}]} .

On the typical set, $\frac{1}{n} lo g \frac{p ( x ^{n} , y ^{n} )}{p ^{*} ( x ^{n} ) p _{Y} ( y ^{n} )}$ is within $ϵ$ of $I (X; Y)$ (since $H (X, Y) - H (X) - H (Y) = - I (X; Y)$ , and each term is within $ϵ$ of its entropy). Therefore:

p^{*} (x^{n}) \cdot p_{Y} (y^{n}) \leq p (x^{n}, y^{n}) \cdot 2^{- n (I (X; Y) - ϵ)} \leq 2^{- n (H (X, Y) - ϵ)} \cdot 2^{- n (I (X; Y) - ϵ)} .

The probability under the product measure is:

A_{ϵ}^{(n)} \sum p^{*} (x^{n}) p_{Y} (y^{n}) \leq ∣ A_{ϵ}^{(n)} ∣ \cdot 2^{- n (H (X, Y) + I (X; Y) - 2 ϵ)} .

Using the size bound $∣ A_{ϵ}^{(n)} ∣ \leq 2^{n (H (X, Y) + ϵ)}$ :

Pr {(X^{n} (w), Y^{n}) \in A_{ϵ}^{(n)}} \leq 2^{n (H (X, Y) + ϵ)} \cdot 2^{- n (H (X, Y) + I (X; Y) - 2 ϵ)} = 2^{- n (I (X; Y) - 3 ϵ)} . □

Connections Master

46.03.01 — Channel capacity $C = max_{p (x)} I (X; Y)$ is defined there; this unit gives it operational meaning via the coding theorem.
46.02.01 — The AEP and joint typicality are the analytical tools that make the random coding proof work; the typicality conditions control both the size of the search space and the probability of confusion.
46.03.03 — The converse of the coding theorem (Fano's inequality) complements this achievability result to give the full theorem.
46.04.01 — Rate-distortion theory has an analogous achievability proof using random codebooks in the source-coding setting.
46.08.01 — LDPC codes are explicit constructions that approach the Shannon limit; the random coding argument shows the limit exists but leaves construction as a separate problem.
46.04.02 — Chernoff information governs error exponents in hypothesis testing; the Gallager exponent $E_{r} (R)$ is the analogous quantity for channel coding.

Historical & philosophical context Master

Claude Shannon proved the noisy channel coding theorem in Part III of his 1948 paper "A Mathematical Theory of Communication" (Bell System Technical Journal 27, 379-423 and 623-656). The achievability proof used a random coding argument that was entirely novel. Shannon generated codewords at random and showed that the average error probability over all possible codes vanishes for rates below capacity, establishing the existence of good codes without constructing any specific one.

The random coding argument was controversial when first presented. Many mathematicians and engineers found it unsatisfying that the proof shows existence without construction. John von Neumann reportedly defended Shannon's approach, pointing out that probabilistic existence proofs are standard in mathematics. The argument is analogous to the probabilistic method in combinatorics (Erdos, 1947): showing that a random structure has a desired property with positive probability proves that such a structure exists.

Robert Gallager refined Shannon's error analysis in his 1965 paper "Simple Derivation of the Coding Theorem and Some Applications" (IEEE Transactions on Information Theory 11, 3-18). Gallager introduced the random coding exponent $E_{r} (R)$ and showed that the error probability decays as $2^{- n E_{r} (R)}$ , giving a quantitative handle on the speed of convergence. Gallager's bound was the foundation for the reliability function analysis developed by the Soviet school (Pinsker, Dobrushin) and by Csiszar and Korner.

The strong converse was proved by Jacob Wolfowitz in 1957 in "The Coding of Messages Subject to Chance Errors" (Illinois Journal of Mathematics 1, 591-606). The strong converse upgraded the converse from "rates above $C$ have bounded error" to "rates above $C$ have error tending to 1," making the coding theorem a sharp threshold.

The gap between existence and construction defined coding theory for the next seven decades. Shannon's proof showed that good codes exist but provided no guidance on how to find them. Constructing explicit codes that approach capacity required the development of algebraic coding theory (Hamming, Reed-Solomon, BCH codes in the 1950s-1960s), concatenated codes (Forney, 1966), and finally iterative decoding (LDPC and turbo codes in the 1990s-2000s). Each of these constructions is an attempt to close the gap between Shannon's existence proof and practical engineering.

Bibliography Master

@article{shannon1948,
  author  = {Shannon, C. E.},
  title   = {A Mathematical Theory of Communication},
  journal = {Bell System Technical Journal},
  volume  = {27},
  pages   = {379--423 and 623--656},
  year    = {1948},
}
@book{cover-thomas2006,
  author    = {Cover, T. M. and Thomas, J. A.},
  title     = {Elements of Information Theory},
  edition   = {2nd},
  publisher = {Wiley},
  year      = {2006},
}
@book{csiszar-korner2011,
  author    = {Csisz{\'a}r, I. and K{\"o}rner, J.},
  title     = {Information Theory: Coding Theorems for Discrete Memoryless Systems},
  edition   = {2nd},
  publisher = {Cambridge University Press},
  year      = {2011},
}
@article{gallager1965,
  author  = {Gallager, R. G.},
  title   = {Simple Derivation of the Coding Theorem and Some Applications},
  journal = {IEEE Transactions on Information Theory},
  volume  = {11},
  pages   = {3--18},
  year    = {1965},
}
@article{wolfowitz1957,
  author  = {Wolfowitz, J.},
  title   = {The Coding of Messages Subject to Chance Errors},
  journal = {Illinois Journal of Mathematics},
  volume  = {1},
  pages   = {591--606},
  year    = {1957},
}
@book{gallager1968,
  author    = {Gallager, R. G.},
  title     = {Information Theory and Reliable Communication},
  publisher = {Wiley},
  year      = {1968},
}

Prerequisites

46.03.01
46.02.01

Tier anchors

beginner: Cover & Thomas 2006 Elements of Information Theory 2e (Wiley) §7.1-7.3 (the big theorem: rates below capacity are achievable, the random coding argument in pictures)
intermediate: Cover & Thomas 2006 Elements of Information Theory 2e (Wiley) §7.4-7.7 (random codebook generation, joint typicality decoder, probability of error analysis, achievability proof)
master: Cover & Thomas 2006 Elements of Information Theory 2e (Wiley) §7.4-7.7; Csiszar & Korner 2011 Information Theory: Coding Theorems for Discrete Memoryless Systems 2e (Cambridge) §2.1-2.3; Shannon 1948 A Mathematical Theory of Communication section 13 (the original random coding argument)

References

Shannon, C. E. — A Mathematical Theory of Communication · Bell System Technical Journal 27 (1948) 379-423 and 623-656; section 13 introduces the random coding argument: generate $2^{n R}$ codewords of length $n$ by drawing each symbol i.i.d. from the capacity-achieving input distribution, then decode by finding the unique codeword jointly typical with the received sequence; the probability of error averaged over the random codebook vanishes as $n \to \infty$ for $R < C$ .
Cover, T. M. & Thomas, J. A. — Elements of Information Theory (2nd ed.) · Wiley (2006). Section 7.4: the channel coding theorem statement, definition of achievable rates. Section 7.5: random codebook generation with i.i.d. symbols from $p^{*} (x)$ , the joint typicality decoder, union bound on error events. Section 7.6: analysis of the probability of error, showing $P_{e}^{(n)} \to 0$ when $R < C = max_{p (x)} I (X; Y)$ . Section 7.7: the converse using Fano inequality.
Csiszar, I. & Korner, J. — Information Theory: Coding Theorems for Discrete Memoryless Systems (2nd ed.) · Cambridge University Press (2011). Section 2.1: the channel coding problem, definition of $(n, M, λ)$ codes. Section 2.2: the random coding achievability bound via the method of types, showing the maximum achievable rate is $C = max_{p (x)} I (X; Y)$ . Section 2.3: strong converse via the packing lemma.

Estimated time

beginner: 15m
intermediate: 50m
master: 90m