Back to the on-screen lesson ·
Why no code averages fewer than $H$ bits per symbol, when equality is possible, and how blocks close the remaining gap.
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 compute the expected length of a symbol code and compare it with the entropy, prove from Kraft's and Gibbs' inequalities that no uniquely decodable code averages fewer than $H$ bits per symbol, name the dyadic case in which equality is possible, say which claims about compression the theorem supports and which it forbids, compute the block-coding bound, and use the theorem to judge a compression claim.
Kraft's inequality, which says which codeword lengths are possible, and Gibbs' inequality, which says no model beats the truth. This lesson puts them together and the answer is the operational meaning of entropy.
The expected length of a code is $L = \sum_i p_i \ell_i$, the average bits per symbol. The source coding theorem brackets the best achievable $L^$ between $H$ and $H + 1$. Block coding* treats $n$ symbols as one super-symbol, which spreads the one-bit overhead over $n$ symbols and drives the cost per symbol down to $H$.
The expected length of a symbol code is $L = \sum_i p_i \ell_i$. Source coding theorem, lower bound: every uniquely decodable code has $L \ge H(X)$. Proof: set $c = \sum_j 2^{-\ell_j} \le 1$ (Kraft, or McMillan) and $q_i = 2^{-\ell_i}/c$, a probability distribution; then $$L - H = \sum_i p_i \log_2 \frac{p_i}{2^{-\ell_i}} = D(p \| q) - \log_2 c \ge 0,$$ with equality only if $c = 1$ and $p_i = 2^{-\ell_i}$, that is, only for dyadic probabilities. Upper bound: the Shannon code (next lesson) has $L < H + 1$. So the optimal length $L^$ satisfies $H \le L^ < H + 1$. The slack of up to one bit per symbol is removed by block coding: treating $n$ symbols as one super-symbol of entropy $nH$ gives a code with $nH \le L_n < nH + 1$, so the cost per symbol tends to $H$. This is the operational meaning of entropy: the minimum average number of bits per symbol of any lossless description.
Another way: picture
A number line of bits per symbol with $H$ marked. Every uniquely decodable code sits at or to the right of $H$; the Shannon code sits within one unit; as blocks grow, the best code slides down toward $H$ but never crosses it.
Another way: steps
Why can no code beat the entropy? Because a set of codeword lengths is a probability distribution in disguise, and coding for the wrong distribution costs a divergence (lesson 4).
| Step | Expression | Why |
|---|---|---|
| set $c$ and $q$ | $c = \sum_j 2^{-\ell_j} \le 1$, $q_i = 2^{-\ell_i}/c$ | Kraft (McMillan); $q$ is a distribution |
| rewrite | $L - H = \sum_i p_i \log_2 \dfrac{p_i}{2^{-\ell_i}}$ | $L = \sum p_i \ell_i$, $H = \sum p_i \log_2 (1/p_i)$ |
| split | $= D(p \| q) - \log_2 c$ | $2^{-\ell_i} = c\, q_i$ |
| bound | $\ge 0$ | Gibbs and $c \le 1$ |
So $L \ge H$, and the excess $L - H = D(p \| q) - \log_2 c$ names exactly what is being wasted: the mismatch between the implied distribution $q_i = 2^{-\ell_i}$ and the truth, plus any unused part of the tree. Equality needs both to vanish: a complete code ($c = 1$) whose lengths satisfy $p_i = 2^{-\ell_i}$, that is, dyadic probabilities and $\ell_i = \log_2 (1/p_i)$ a whole number.
The theorem leaves a gap: $H \le L^ < H + 1$. For a skewed source that one bit is enormous — a coin with $P(\text{heads}) = 0.9$ has $H = 0.469$ bits, yet any symbol code must spend a whole bit per flip, more than twice the entropy. The cure is to code blocks of $n$ symbols as single super-symbols. A memoryless source has $H(X^n) = nH$, so the best block code obeys $nH \le L_n^ < nH + 1$, that is $$H \le \frac{L_n^*}{n} < H + \frac{1}{n}.$$
| block length $n$ | block entropy $nH$ | best length $< nH + 1$ | bits per symbol |
|---|---|---|---|
| $1$ | $0.469$ | $1.469$ | $< 1.469$ |
| $2$ | $0.938$ | $1.938$ | $< 0.969$ |
| $5$ | $2.345$ | $3.345$ | $< 0.669$ |
| $10$ | $4.690$ | $5.690$ | $< 0.569$ |
| $100$ | $46.90$ | $47.90$ | $< 0.479$ |
The price is an alphabet of $|\mathcal{X}|^n$ super-symbols and a delay of $n$ symbols. Arithmetic coding (lesson 11) gets the same effect without ever building that table.
Common mistakes
The first error is treating the bound as something a clever enough code might evade; it holds for every uniquely decodable code, and a compressor that appears to beat it is either lossy or is exploiting structure the entropy calculation did not model. The second is expecting $L = H$ always to be reachable: it needs every probability to be a power of two, and otherwise the best code still wastes a fraction of a bit. The third is forgetting that the one-bit slack is per symbol, so blocking $n$ symbols together reduces it to $1/n$ per symbol — which is why the theorem is an equality in the limit rather than a standing loss.
$p = (0.5, 0.25, 0.125, 0.125)$ has $H = 1.75$. The code $0, 10, 110, 111$ has $L = 0.5 + 0.5 + 0.375 + 0.375 = 1.75$.
Dyadic, so $L = H$ is attainable.
No code can do better, and any code with $L = 1.75$ must use exactly these lengths.
Equality case of Gibbs.
$p = (0.9, 0.1)$, $H = 0.469$. Any symbol code needs at least $1$ bit per flip, more than twice $H$.
One symbol at a time wastes bits.
Blocks of $n = 10$: entropy $4.69$ bits per block, so a code with fewer than $5.69$ bits per block exists, under $0.57$ per flip; larger $n$ approaches $0.469$.
The overhead is under $1/n$ per symbol.
$H = 0.5 \cdot 1 + 0.3 \cdot 1.737 + 0.2 \cdot 2.322 = 1.485$ bits.
$1.4 < 1.485$.
The theorem's floor is the entropy.
No: no uniquely decodable code can average $1.4$ bits. (Blocks of two symbols can average $1.485 + \tfrac{1}{2}$ per pair, that is under $0.99$ per symbol — but never below $1.485$ per symbol.)
$p = (\tfrac{1}{2}, \tfrac{1}{4}, \tfrac{1}{8}, \tfrac{1}{8})$, lengths $1, 2, 3, 3$.
$L = 0.5 + 0.5 + 0.375 + 0.375 = 1.75$; Kraft sum $= 1$, so the code is complete.
$H = 1.75$ too: $L = H$, because every $\ell_i$ equals $\log_2 (1/p_i)$ exactly.
$H = 1.485$ bits.
$1.4 < 1.485$: impossible for any uniquely decodable code.
Symbols with probabilities $\tfrac{1}{2}, \tfrac{1}{4}, \tfrac{1}{4}$ are given codewords of lengths $2, 2, 3$. Fill in the expected code length, the entropy of the source, and the gap between them, in bits.
| Bits | |
|---|---|
| $L$, the expected length | |
| $H$, the entropy | |
| The gap $L - H$ |
Build the proof that every uniquely decodable code has expected length $L \ge H$.
This task has no paper form; do it on a device.
A source has entropy $H = 7/2$ bits per symbol. Can a uniquely decodable symbol code have expected length $2/2$ bits per symbol?
A source has entropy $H$ bits per symbol. Select every statement the source coding theorem supports.
This task has no paper form; do it on a device.
A log file's symbols are independent with the dyadic distribution $(\tfrac{1}{2}, \tfrac{1}{4}, \tfrac{1}{8}, \tfrac{1}{8})$, whose entropy is $1.75$ bits per symbol. Four vendors describe their lossless compressor. Match each claim to its verdict.
| Impossible: below the entropy | Possible, and optimal for this source | Possible, but not optimal | False: only dyadic sources allow it | |
|---|---|---|---|---|
| Averages $1.5$ bits per symbol, losslessly | ||||
| Averages exactly $1.75$ bits per symbol | ||||
| Averages $1.9$ bits per symbol | ||||
| Averages exactly the entropy, for every source whatever |
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
A memoryless source has entropy $5/4$ bits per symbol and is coded in blocks of $2$ symbols. The source coding theorem gives an upper bound on the best expected length per block; what is it, in bits?
Answer:
You can bound any code from below by the entropy and say exactly when the bound is tight. Say in your own words why the codeword lengths of any code can be read as a probability distribution, and what that buys the proof. Next: Shannon codes, which come within one bit of the bound and prove the other half of the theorem.
13. Your turn: can a code for $p = (0.5, 0.3, 0.2)$ average $1.4$ bits?, step 2