Skip to content
Tutorials Center
My learning

Topics

Lesson 13 of 37 ยท Source Coding

Shannon and Shannon-Fano Codes

Build Shannon coding (lengths ceil(-log2 p)) and Shannon-Fano coding (recursive splitting) in Python, compare them to entropy, and learn why Fano is not always optimal.

Two early constructions turn probabilities into prefix codes. Shannon coding picks each length as ceil(-log2 p). Shannon-Fano coding recursively splits the sorted symbols into two groups of nearly equal probability. Both are within one bit of entropy; neither is always optimal, which is why Huffman's later algorithm (Huffman Coding) replaced them. They are still worth building: they make the link between probability and length concrete.

Shannon coding

Algorithm:

  1. Sort symbols by decreasing probability.
  2. Give symbol i the length l_i = ceil(-log2 p_i).
  3. Let F_i = p_1 + ... + p_(i-1) be the cumulative probability before it.
  4. The codeword is the first l_i bits of the binary expansion of F_i.

Because the lengths satisfy Kraft, the construction yields a prefix code. The cumulative-probability trick is the seed of arithmetic coding.

Python Shannon code

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The average length is within one bit of the entropy, as the theory promises, but notice it is not the shortest possible: Shannon coding spends ceil(-log2 p) even when a slightly shorter word would still fit.

Shannon-Fano coding

Shannon-Fano is a top-down idea, devised independently by Shannon and Robert Fano:

  1. Sort symbols by decreasing probability.
  2. Split the list into two parts whose total probabilities are as equal as possible.
  3. Give the first part the bit 0 and the second the bit 1.
  4. Repeat inside each part until every part is a single symbol.
flowchart TD
    A["a .4, b .3, c .15, d .1, e .05"] -- "0" --> B["a .4, b .3 (sum .7 vs .3)"]
    A -- "1" --> C["c .15, d .1, e .05"]

Choose the split point that makes the two sums most equal, then recurse on each side.

Python Shannon-Fano code

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For this source the Shannon-Fano code averages 2.05 bits, noticeably shorter than the Shannon code, and close to the entropy of about 2.01.

Comparing the two

Python Which is shorter across many random sources?

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In these random sources Shannon-Fano is shorter than the Shannon code every time (that is typical, not a theorem), but the last line shows it is not optimal: for a noticeable share of sources Huffman is strictly shorter still.

A dyadic source: both are perfect

If every probability is a power of 1/2, -log2 p is an integer, Shannon coding spends exactly that, and the average length equals the entropy. Shannon-Fano also splits evenly at every step and matches it.

Python Dyadic source

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The two numbers are identical (1.875 bits), so the overhead is exactly zero.

Textbooks sometimes call Shannon-Fano "optimal". It is not. Huffman coding (next chapter) is provably optimal among symbol codes, and in some cases Shannon-Fano is strictly worse. Use Huffman for real work.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What length does Shannon coding give to a symbol with probability 0.3?

    -log2(0.3) = 1.737, and the ceiling is 2.
  2. 2. How does Shannon-Fano build its code?

    It is a top-down splitting algorithm; Huffman is the bottom-up merging one.
  3. 3. For which sources is the Shannon code's average length exactly equal to the entropy?

    Only then is -log2 p an integer for every symbol.
  4. 4. Is Shannon-Fano coding always optimal?

    Huffman is optimal among prefix codes; Shannon-Fano can be strictly worse for some sources.

Summary

  • Shannon code: lengths ceil(-log2 p), codewords from cumulative probabilities; average length < H + 1.
  • Shannon-Fano: recursive splitting into near-equal probability halves; usually shorter, not always optimal.
  • Both are exact for dyadic sources.
  • Huffman coding is the optimal symbol code and the subject of the next chapter.

Next: Huffman Coding