Back to the on-screen lesson ·
Rates, codes, error probability; every rate below C is achievable.
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.
A $(M, n)$ code for a channel is a codebook of $M$ input sequences of length $n$, one per message, together with a decoder mapping each output sequence to a message; its rate is $R = \log_2 M / n$ bits per use and its maximal error probability is $\lambda^{(n)} = \max_w P(\text{decoder} \ne w \mid w \text{ sent})$. A rate is achievable if there is a sequence of $(2^{nR}, n)$ codes with $\lambda^{(n)} \to 0$. Shannon's channel coding theorem: every rate $R < C$ is achievable, and (converse) no rate $R > C$ is. So capacity is exactly the speed limit of reliable communication: below it, errors can be made as rare as desired at a fixed positive rate, which repetition coding, whose rate tends to zero, never suggested was possible. The price is block length: reliability at rates near $C$ needs long codes and, in Shannon's proof, decoders too complex to run; the modern codes that approach capacity in practice, turbo, LDPC and polar codes, took fifty years to find.
Another way: picture
Axes: rate $R$ across, error probability up. For each block length $n$ a curve; as $n$ grows the curves drop to zero everywhere left of $C$ and rise to a floor everywhere right of it. Capacity is the cliff.
Another way: steps
An $(M, n)$ code is a codebook of $M$ input sequences of length $n$, one per message, plus a decoder. Its rate is $R = \log_2 M / n$ bits per use — how many message bits ride on each channel use — and its maximal error probability is the worst message's chance of being decoded wrongly. A rate is achievable when a sequence of codes at that rate exists whose error probability tends to $0$ as $n$ grows.
| code | $M$ codewords | length $n$ | rate $R = \log_2 M / n$ | on $\text{BSC}(0.1)$, $C = 0.531$ |
|---|---|---|---|---|
| repetition of $3$ | $2$ | $3$ | $0.333$ | achievable |
| $1000$ bits in $2000$ uses | $2^{1000}$ | $2000$ | $0.5$ | achievable |
| $1000$ bits in $1500$ uses | $2^{1000}$ | $1500$ | $0.667$ | not achievable |
| uncoded | $2^n$ | $n$ | $1$ | not achievable |
Shannon's channel coding theorem is the two-sided statement that the achievable rates are exactly those below capacity: every $R < C$ is achievable, and no $R > C$ is. Read it carefully, because it says less and more than it seems. It does not say a short code at rate $0.5$ is reliable — at $n = 10$ any code errs often; reliability is a limit as $n \to \infty$. It does not hand over a code: the proof shows one exists by averaging over random codebooks. And it does not promise zero errors at any finite length, only that the error can be made as small as you like at a fixed positive rate — which is the surprise, since repetition coding drives the error down only by driving the rate to $0$.
Common mistakes
$1000$ bits in $1500$ uses of $\text{BSC}(0.1)$: $R = 0.667$, $C = 0.531$.
Rate versus capacity.
$R > C$: no code of any length does it reliably; with $2000$ uses, $R = 0.5 < C$, and reliable codes exist.
It does not say a short code at rate $0.5$ is reliable: at $n = 10$ any code errs often. Reliability comes with $n \to \infty$.
Nor does it hand over the code: it proves existence by averaging over random codebooks.
$R = \log_2 2^{60} / 100 = 60/100 = 0.6$ bits per use.
$0.6 > 0.5 = C$.
Above capacity: no code of this rate is reliable, at $n = 100$ or at any length, and the converse (lesson 16) puts a floor under its error probability.
A channel with $C = \tfrac{2}{5} = 0.4$ bits per use must carry $10^6$ bits.
$10^6 / 0.4 = 2.5 \times 10^6$ uses.
Divide bits by bits-per-use; the units leave uses.
Any fewer would need a rate above capacity; any more is comfortable, and long codes get arbitrarily close to this number.
$R = 60/100 = 0.6$ bits per use.
$0.6 > 0.5$: its error probability cannot be made small, however cleverly it is designed.
A code sends $7$ information bits in $9$ uses of a $\text{BSC}(0.1)$, whose capacity is about $0.531$. Is this rate achievable with arbitrarily small error probability (for long codes of the same rate)?
A block code of length $13$ has rate $2/13$ bits per use. How many codewords does it have?
Computed value: answer
A channel has capacity $1/2$ bits per use. In the limit of long codes, what is the smallest number of uses needed to send $17$ information bits reliably?
Computed value: answer
A code sends $5$ information bits in $9$ uses of a $\text{BSC}(0.3)$, whose capacity is about $0.119$. Is this rate achievable with arbitrarily small error probability (for long codes of the same rate)?
Which statement is Shannon's channel coding theorem?
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
A block code of length $33$ has rate $4/33$ bits per use. How many codewords does it have?
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.
9. Your turn: a $(2^{60}, 100)$ code on a channel with $C = 0.5$, step 2