Back to the on-screen lesson ·
Why random codes work: counting typical output clouds; 2^{nI} codewords fit.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to define block codes, rates and maximal error probability, state Shannon's channel coding theorem in both directions, decide whether a given rate is achievable on a given channel, and compute the number of codewords or channel uses a target implies. You will follow the random coding proof: drawing the codebook at random, decoding by joint typicality, counting output clouds to see why $2^{nC}$ codewords fit, bounding the error with the union bound, and turning an average-error statement into a maximal-error one, which is the argument that makes capacity the speed limit of reliable communication.
Shannon's achievability proof is a counting argument dressed as probability. Fix the capacity-achieving input distribution $p(x)$ and draw every entry of the codebook i.i.d. from it. By the joint AEP, the received $y^n$ is jointly typical with the transmitted codeword with probability near $1$, and it is jointly typical with any particular other codeword with probability about $2^{-nI(X; Y)}$, because only $2^{nH(X \mid Y)}$ of the $2^{nH(X)}$ typical inputs are compatible with a given output. With $2^{nR}$ wrong codewords the chance that one of them fools the decoder is about $2^{n(R - I)}$, which tends to $0$ when $R < I(X; Y) = C$. The joint typicality decoder simply looks for the unique codeword typical with the output. The pictorial version: each codeword produces a cloud of about $2^{nH(Y \mid X)}$ likely outputs inside a space of $2^{nH(Y)}$ typical outputs, so about $2^{n(H(Y) - H(Y \mid X))} = 2^{nC}$ clouds fit without overlapping. Averaging the error over codebooks bounds it, so some codebook is at least that good; expurgating its worst half turns average error into maximal error at a negligible loss of rate.
Another way: picture
Sphere packing: the output space drawn as a large disc, each codeword as a point with a small cloud of likely outputs around it. Codewords are spaced so the clouds do not overlap; the number of clouds that fit is the ratio of the areas, $2^{nH(Y)} / 2^{nH(Y \mid X)}$.
Another way: steps
The achievability proof is a counting argument dressed as probability, and the counting is worth doing before the probability. Fix the capacity-achieving input and look at the space of output sequences.
| count | exponent | on $\text{BSC}(0.1)$ with $n = 1000$ |
|---|---|---|
| typical output sequences | $2^{nH(Y)}$ | $2^{1000}$ |
| outputs likely from one codeword | $2^{nH(Y \mid X)}$ | $2^{469}$ |
| clouds that fit without overlap | $2^{n(H(Y) - H(Y \mid X))} = 2^{nI}$ | $2^{531}$ |
| bits per use | $I$ | $0.531 = C$ |
Each codeword produces a cloud of about $2^{nH(Y \mid X)}$ likely outputs. If the clouds do not overlap the decoder cannot be fooled, and the number that fits into the $2^{nH(Y)}$ typical outputs is their ratio, $2^{nI}$. Taking logarithms and dividing by $n$: $I$ bits per use, and at the best input that is $C$. The picture is called sphere packing, and it is the same arithmetic as the Hamming bound of lesson 21 with probability in place of distance.
Shannon draws every entry of the codebook i.i.d. from the capacity-achieving input distribution. The joint typicality decoder then looks for the unique codeword jointly typical with the received $y^n$, and declares an error if there is none or more than one. Two probabilities finish the proof. The sent codeword is jointly typical with the output with probability near $1$ (the joint AEP). A different, independently drawn codeword is jointly typical with that output with probability about $2^{-nI(X; Y)}$, because only $2^{nH(X \mid Y)}$ of the $2^{nH(X)}$ typical inputs are compatible with a given output. The union bound over the $2^{nR}$ wrong codewords gives $$P(\text{some wrong codeword looks typical}) \lesssim 2^{nR} \cdot 2^{-nI} = 2^{-n(I - R)},$$ which tends to $0$ exactly when $R < I = C$.
Why random rather than constructed? Because averaging is easy and construction is hard. The average error over all codebooks is small, so some codebook is at least as good — and a final trick (throw away the worst half of its codewords) turns a small average error into a small maximal error. The proof therefore tells you a good code exists without telling you which, and finding explicit codes that approach capacity took another fifty years (Reed-Solomon, turbo, LDPC, polar).
Common mistakes
$\text{BSC}(0.1)$, $n = 1000$, fair input: $2^{1000}$ typical outputs; each codeword's cloud has about $2^{469}$ (the outputs with about $100$ flips).
$nH(Y \mid X) = 1000 \cdot h(0.1)$.
$2^{1000} / 2^{469} = 2^{531}$ clouds fit: $531$ bits per $1000$ uses, exactly $nC$.
A wrong codeword is jointly typical with the output with probability at most $2^{-n(I - 3\varepsilon)}$; there are $2^{nR} - 1$ of them.
Joint AEP, third property.
Union bound: $P(\text{some wrong one is typical}) \le 2^{nR} 2^{-n(I - 3\varepsilon)} = 2^{-n(I - R - 3\varepsilon)} \to 0$ if $R < I - 3\varepsilon$.
Then let $\varepsilon \to 0$.
Fair input: $H(Y) = 1$, so $2^{60}$ typical outputs.
$H(Y \mid X) = h(0.2) = 0.722$, so each cloud holds about $2^{43.3}$ outputs.
Clouds that fit: $2^{60 - 43.3} = 2^{16.7}$, that is $\log_2$ of the count $= 16.7$, and $16.7/60 = 0.278 = C$.
$I = 1.25$ bits, $n = 40$: a wrong codeword looks typical with probability about $2^{-50}$.
At rate $R = 1$ there are $2^{40}$ wrong codewords.
Union bound: $2^{40} \cdot 2^{-50} = 2^{-10}$, about one in a thousand — and it shrinks as $2^{-n(I - R)}$ with longer blocks.
Exponent $n(H(Y) - H(Y \mid X)) = 200 \cdot 0.75$.
$2^{150}$ clouds: $150$ bits in $200$ uses, rate $0.75$.
A fair input is sent $n = 40$ times through a $\text{BSC}(0.05)$. About $2^{nH(Y)}$ output sequences are typical and about $2^{nH(Y \mid X)}$ are typical for each codeword. Give $\log_2$ of the number of codewords whose output clouds fit without overlap, to one decimal place.
Computed value: answer
Inputs and outputs of a channel have mutual information $I = 2/4$ bits at the input distribution used for random coding, and the block length is $n = 8$. For a fixed output sequence, the probability that an independently drawn random codeword is jointly typical with it is about $2^{-nI}$. Give $-\log_2$ of that probability.
Computed value: answer
Why does Shannon's proof choose the codebook at random instead of constructing it?
A fair input is sent $n = 20$ times through a $\text{BSC}(0.05)$. About $2^{nH(Y)}$ output sequences are typical and about $2^{nH(Y \mid X)}$ are typical for each codeword. Give $\log_2$ of the number of codewords whose output clouds fit without overlap, to one decimal place.
Computed value: answer
How does the joint typicality decoder in the proof decide which message was sent, and when does it err?
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
Inputs and outputs of a channel have mutual information $I = 2/4$ bits at the input distribution used for random coding, and the block length is $n = 80$. For a fixed output sequence, the probability that an independently drawn random codeword is jointly typical with it is about $2^{-nI}$. Give $-\log_2$ of that probability.
Computed value: answer
You can state and explain the channel coding theorem and see why random codes reach capacity. Next: the converse, proved with Fano, and what feedback and separation add.
10. Your turn: $n = 200$, $H(Y) = 1$, $H(Y \mid X) = 0.25$; how many clouds fit?, step 2