Shannon-Fano Coding

Shannon-Fano coding is one of the earliest systematic methods for constructing variable-length prefix-free codes. Developed independently by Claude Shannon and Robert Fano, it assigns shorter codewords to more probable symbols using a top-down recursive partitioning of the symbol set. While it does not always achieve the optimal average code length that Huffman coding guarantees, it is conceptually important and historically significant as a precursor to modern entropy coding techniques.

Core Concept Explanation

The Shannon-Fano algorithm proceeds in a top-down recursive fashion. First, symbols are sorted in non-increasing order of probability. The list is then divided into two groups such that the total probability of each group is as nearly equal as possible. The symbols in the upper group are assigned a leading bit of 0 and those in the lower group a leading bit of 1. Each group is then recursively subdivided in the same way until each group contains exactly one symbol. The complete codeword for each symbol is formed by concatenating all the bit assignments made during the recursive splits from root to leaf.

The key idea is that if the two groups have equal total probability, the split is as balanced as possible and the resulting code is as close to entropy as this method can achieve. However, because probability values are continuous and the split must be made at a symbol boundary, perfect balance is rarely achievable. This is where Shannon-Fano differs from Huffman: the greedy bottom-up merging in Huffman coding automatically finds the globally optimal assignment, while the top-down splitting in Shannon-Fano makes locally balanced decisions that can lead to suboptimal results.

Both methods produce prefix-free variable-length codes and both satisfy H(S) <= L < H(S) + 1 for a DMS. However, Huffman coding always achieves the minimum possible L for a prefix-free single-symbol code, while Shannon-Fano may produce a slightly larger L for some source distributions. In practice, for sources with many symbols or probabilities that split cleanly, the two methods often give the same result.

Mathematical Expression

Like all entropy codes, the average codeword length is L = sum_{i=1}^{M} pi * li. The entropy lower bound is H(S) = -sum pi log2(pi). The efficiency is eta = H(S) / L. The redundancy of the code is R = L - H(S) bits/symbol, which represents the extra bits used above the information-theoretic minimum. Shannon-Fano coding guarantees R < 1 bit/symbol, as does Huffman coding, but Shannon-Fano codes can have slightly higher redundancy than Huffman codes for the same source.

The optimal split criterion for each division step is to minimize the absolute difference |P_upper - P_lower|, where P_upper and P_lower are the total probabilities of the two groups. There is no closed-form formula for the codeword lengths of Shannon-Fano codes since they depend on the actual probability values and how cleanly the source can be partitioned at each level.

Practical Understanding

Shannon-Fano coding is no longer used in modern compression systems because Huffman coding achieves strictly equal or better efficiency with similar complexity. However, Shannon-Fano coding is pedagogically valuable because it clearly illustrates the connection between probability and code length: more probable symbols end up higher in the tree and receive shorter paths.

An important practical observation is that when the source has only two symbols, Shannon-Fano and Huffman coding are identical. When there are three or more symbols with non-dyadic probabilities, differences can emerge. For uniform sources where all symbols are equally probable, both methods degenerate to fixed-length coding and achieve optimal compression simultaneously.

Given:
Symbols: {A, B, C, D, E}
Probabilities: p(A)=0.35, p(B)=0.17, p(C)=0.17, p(D)=0.16, p(E)=0.15

Why this formula applies:
Shannon-Fano splits sorted symbols into two groups with nearly equal total probability,
assigning 0 and 1 recursively. Average length L is computed afterward.

Formula:
L = sum pi * li
H(S) = -sum pi * log2(pi)
Efficiency eta = H(S) / L

Shannon-Fano partition:
Sorted: A(0.35), B(0.17), C(0.17), D(0.16), E(0.15)
Split 1: {A,B}=0.52 (code 0), {C,D,E}=0.48 (code 1)
Split 2a: {A}=0.35 (00), {B}=0.17 (01)
Split 2b: {C}=0.17 (10), {D,E}=0.31 (11)
Split 3: {D}=0.16 (110), {E}=0.15 (111)

Codes: A=00(2), B=01(2), C=10(2), D=110(3), E=111(3)

Substitution:
L = 0.35*2 + 0.17*2 + 0.17*2 + 0.16*3 + 0.15*3
  = 0.70 + 0.34 + 0.34 + 0.48 + 0.45

Calculation:
L = 2.31 bits/symbol

H(S) = -(0.35*log2(0.35)+0.17*log2(0.17)+0.17*log2(0.17)+0.16*log2(0.16)+0.15*log2(0.15))
     = -(0.35*(-1.514)+0.17*(-2.557)+0.17*(-2.557)+0.16*(-2.644)+0.15*(-2.737))
     = -(-0.530-0.435-0.435-0.423-0.411)
     = 2.234 bits/symbol

Final Answer: L = 2.31 bits/symbol, H(S) = 2.234 bits/symbol
Efficiency eta = 2.234 / 2.31 = 96.7%
Redundancy R = 2.31 - 2.234 = 0.076 bits/symbol

Exam Tip: GATE may ask to compare Shannon-Fano and Huffman coding for the same source. Both satisfy H(S) <= L < H(S)+1 and produce prefix-free codes, but Huffman is always optimal. A common trap is to assume Shannon-Fano always gives a longer code than Huffman — for many practical distributions they give identical results. Always compute L explicitly for both when comparison is required.

Mechanism: Shannon-Fano vs Huffman Comparison

• Shannon-Fano is top-down: it recursively splits the sorted symbol list into two equally probable groups. Huffman is bottom-up: it greedily merges the two least probable nodes.
• Both produce prefix-free variable-length codes satisfying H(S) <= L < H(S)+1. Only Huffman is provably optimal among prefix-free codes.
• Shannon-Fano coding can produce the same result as Huffman for many sources, particularly when probabilities split cleanly at each partition level.
• The redundancy R = L - H(S) is always less than 1 bit/symbol for both methods but may be larger for Shannon-Fano when partition balance is imperfect.
• Neither method is used in modern systems without modifications. Arithmetic coding, which approaches entropy more closely and handles non-dyadic probabilities better, is preferred in high-performance compressors.

Quick Revision

• Shannon-Fano coding: sort symbols by probability descending, recursively split into two equal-probability groups, assign 0 and 1 to each group.
• Both Shannon-Fano and Huffman produce prefix-free variable-length codes. Huffman is optimal; Shannon-Fano is near-optimal.
• Average length: L = sum pi * li. Bound: H(S) <= L < H(S)+1 for both methods.
• Efficiency: eta = H(S)/L. Redundancy R = L - H(S) < 1 bit/symbol.
• Key distinction: Shannon-Fano makes locally balanced splits (top-down). Huffman makes globally optimal merges (bottom-up).
• Exam trap: Do not state that Shannon-Fano always gives a longer code than Huffman. For many distributions they are identical. The difference only appears for specific probability distributions where local balance does not lead to global optimality.