Back to the on-screen lesson · Print

Shannon codes

Rounding each surprise up to a whole number of bits: a code that always exists and always lands within one bit of the entropy.

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.

1. What you will learn

By the end of this lesson you will be able to build a Shannon code by rounding each symbol's surprise up, verify that its lengths satisfy Kraft's inequality and why they must, compute its expected length, prove that it always comes within one bit of the entropy, say when it wastes nothing at all, and use the two halves of the source coding theorem together to say where the best possible code must land before any code is written.

2. What you already have

Kraft's inequality, which decides which lengths are possible, and the source coding theorem's floor at the entropy. This lesson supplies the construction that proves the other half: a code that always exists and always comes close.

3. Shannon length, ceiling, rounding waste

The Shannon length of a symbol is its surprise rounded up, $\lceil \log_2 (1/p) \rceil$, where $\lceil \cdot \rceil$ is the ceiling. The difference between the length and the surprise is the rounding waste, which is zero exactly when the probability is a power of two.

4. Shannon codes

The Shannon code gives symbol $i$ the length $$\ell_i = \left\lceil \log_2 \frac{1}{p_i} \right\rceil,$$ its surprise rounded up to a whole number of bits. These lengths satisfy Kraft, because $2^{-\ell_i} \le p_i$ sums to at most $1$, so a prefix code with them exists (build it shortest first). Since $\ell_i < \log_2(1/p_i) + 1$, the expected length obeys $H \le L < H + 1$. When every $p_i$ is a power of two there is no rounding at all and $L = H$ exactly: the code $0, 10, 110, 111$ for $(\tfrac{1}{2}, \tfrac{1}{4}, \tfrac{1}{8}, \tfrac{1}{8})$ is a Shannon code. For probabilities such as $0.3$ or $0.35$ the ceiling wastes part of a bit; Huffman's algorithm (next lesson) chooses the lengths optimally, but even it cannot beat $H$, and both are within one bit of it. The Shannon code is the existence proof behind the source coding theorem's upper bound, and the same rounding idea, applied to blocks, is what makes the per-symbol cost converge to $H$.

5. Building a Shannon code

Round each surprise up: $\ell_i = \lceil \log_2 (1/p_i) \rceil$. For $p = (0.4, 0.3, 0.2, 0.1)$:

The Kraft sum is $0.6875 \le 1$, so a prefix code with these lengths exists — build it shortest first: $00, 01, 100, 1010$. Kraft always holds for Shannon lengths, because rounding up makes $\ell_i \ge \log_2 (1/p_i)$ and hence $2^{-\ell_i} \le p_i$, whose sum is $1$. The expected length is $L = 2.4$ against $H = 1.846$: the rounding cost $0.554$ bits here, and the theorem's promise is only that it stays under $1$.

The bound $L < H + 1$ is three lines: $\ell_i < \log_2 (1/p_i) + 1$ for every $i$; multiply by $p_i$; sum, and the second term contributes $\sum p_i = 1$.

6. Solving the practice problems

1. Shannon length for probability $p$: $\lceil \log_2 (1/p) \rceil$. For $p = 0.15$, $\log_2 (1/0.15) = 2.74$, so $\ell = 3$. A probability that is exactly a power of two needs no rounding.
2. One symbol of probability $\tfrac{1}{2}$ and $2^j$ of probability $2^{-(j+1)}$: every surprise is already whole, so $L = H = \tfrac{j + 2}{2}$ (the same value as in lesson 1).
3. Guaranteed upper bound from $H$: $H + 1$.
4. Why Shannon lengths admit a prefix code: because $2^{-\ell_i} \le p_i$, so the Kraft sum is at most $\sum p_i = 1$.

Common mistakes

• Rounding to the nearest integer instead of up: $\log_2 (1/0.4) = 1.32$ gives length $2$, not $1$.
• Reporting $\log_2 (1/p)$ itself as the length; codeword lengths are whole numbers of bits.
• Expecting the Shannon code to be optimal: Huffman is usually shorter (lesson 9).

7. Where this usually goes wrong

The first error is rounding the surprise to the nearest whole number rather than up: rounding down would break Kraft's inequality and the lengths would not admit any code. The second is expecting the Shannon code to be optimal; it is within one bit, and Huffman is often strictly better — for $(0.4, 0.3, 0.2, 0.1)$ the Shannon code spends $2.4$ bits against Huffman's $1.9$. The third is reading $L < H + 1$ as $L = H + 1$: the bound is strict and usually slack, and for a dyadic source there is no waste at all.

8. Shannon lengths for a skewed source

1. $p = (0.7, 0.2, 0.1)$: $\log_2 (1/0.7) = 0.51$, $\log_2 5 = 2.32$, $\log_2 10 = 3.32$.

   The surprises.

2. Lengths $1, 3, 4$; Kraft $\tfrac{1}{2} + \tfrac{1}{8} + \tfrac{1}{16} < 1$; $L = 0.7 + 0.6 + 0.4 = 1.7$, within one bit of $H = 1.157$.

   Rounding wasted about half a bit.

9. Proving $L < H + 1$

1. $\ell_i = \lceil \log_2 (1/p_i) \rceil < \log_2 (1/p_i) + 1$ for each $i$.

   A ceiling is less than the number plus one.

2. Multiply by $p_i$ and sum: $L < \sum p_i \log_2 (1/p_i) + \sum p_i = H + 1$.

10. Shannon lengths for $(0.5, 0.3, 0.2)$

1. Surprises $1$, $1.737$, $2.322$.

2. Rounded up: lengths $1, 2, 3$; Kraft sum $\tfrac{1}{2} + \tfrac{1}{4} + \tfrac{1}{8} = \tfrac{7}{8} \le 1$.

3. $L = 0.5 + 0.6 + 0.6 = 1.7$ bits, between $H = 1.485$ and $H + 1 = 2.485$.

   Huffman would give $1.5$ here: lengths $1, 2, 2$.

11. Where the ceiling hurts most

1. A symbol of probability $0.51$ has surprise $0.971$, rounded up to $1$: almost no loss.

2. A symbol of probability $0.26$ has surprise $1.943$, rounded up to $2$: again small.

3. A symbol of probability $0.49$ has surprise $1.029$, rounded up to $2$: nearly a whole bit wasted on a very common symbol. That is why Huffman, which chooses lengths jointly, beats rounding each one separately.

12. Your turn: Shannon length for a symbol of probability $0.15$

1. $\log_2 (1/0.15) = \log_2 6.67 \approx 2.74$.

2. Your turn: work this step out. Its working is at the end of the packet.

   Round up: $\ell = 3$ bits.

13. Guided practice

A source has probabilities $(0.5, 0.3, 0.2)$, in that order. Fill in the Shannon length for each symbol, the Kraft sum of those lengths, and the expected code length in bits.

14. Guided practice

Match each symbol probability to the codeword length the Shannon code gives it.

15. Practice

Build the proof that the Shannon code has expected length $L < H + 1$.

This task has no paper form; do it on a device.

16. Practice

A symbol has probability $0.15$. What codeword length does the Shannon code give it?

Answer:

17. Somewhere new

An engineer must budget for a symbol code before writing one. The source has one symbol of probability $\tfrac{1}{2}$ and $4$ others sharing the rest equally, so its entropy is $2$ bits. Give the set of values the best possible expected length $L^*$ could take, as an interval in bits.

This task has no paper form; do it on a device.

18. Lesson test

Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.

19. Test question

Why do the Shannon lengths $\ell_i = \lceil \log_2 (1/p_i) \rceil$ always admit a prefix code?

• Rounding each surprise upward leaves the inverse-power total no greater than one
• Because the lengths are all equal
• Because rounding up makes the code optimal

20. What you can do now

You can build a Shannon code, show its lengths are usable, and bracket the best code between the entropy and one bit above it. Say in your own words why the surprise has to be rounded up rather than to the nearest whole number. Next: Huffman's algorithm, which finds the best symbol code of all.

Working for the steps left to you

12. Your turn: Shannon length for a symbol of probability $0.15$, step 2