Shannon–Fano coding is a technique for constructing a prefix code based on a set of symbols and their probabilities, developed independently by Claude Shannon and Robert Fano in the late 1940s. It is one of the earliest methods for lossless data compression, where variable-length codewords are assigned such that more probable symbols receive shorter codes. While it is suboptimal compared to Huffman coding in terms of average code length, it laid the groundwork for modern entropy encoding and is still used in certain pedagogical contexts and specialized applications.

1 Introduction

1.1 Historical background

The development of Shannon–Fano coding emerged from the foundational work of Claude Shannon and Robert Fano at Bell Laboratories in the late 1940s. Shannon’s 1948 paper *A Mathematical Theory of Communication* introduced the concept of entropy as a measure of information and proposed the idea of variable-length codes to achieve compression. Shortly thereafter, Fano developed a specific algorithm for constructing such codes, which became known as the Shannon–Fano code. The method was one of the first practical implementations of entropy coding, predating the more efficient Huffman coding by a few years. It played a significant role in the early development of information theory and data compression.

1.2 Relationship to Huffman coding

Shannon–Fano coding and Huffman coding are both methods for constructing prefix codes based on symbol probabilities, but they differ in approach and optimality. Huffman coding, developed by David Huffman in 1952, builds the code tree from the bottom up, merging the least probable symbols iteratively, which guarantees the minimum possible average code length for a given probability distribution. In contrast, Shannon–Fano coding uses a top-down recursive splitting of the symbol set, which often results in an average code length that is slightly larger than the entropy bound. While Shannon–Fano is suboptimal, it is conceptually simpler and historically important as a stepping stone to Huffman coding.

1.3 Fundamental concepts: prefix codes and entropy

A prefix code is a set of codewords in which no codeword is a prefix of any other, ensuring unambiguous decodability. Variable-length prefix codes assign shorter codewords to more frequent symbols, achieving compression. The theoretical limit on the average number of bits per symbol for a lossless code is given by the entropy \( H = -\sum p_i \log_2 p_i \), where \( p_i \) are the symbol probabilities. Shannon–Fano coding produces codes whose average length is within one bit of the entropy, but it does not always reach the bound.

2 Algorithm

2.1 Encoding procedure

The Shannon–Fano encoding procedure constructs a binary prefix code by recursively partitioning the set of symbols into two subsets with nearly equal total probabilities. The algorithm proceeds as follows:

  1. Sort the symbols in descending order of probability.
  2. Split the list into two groups such that the sum of probabilities in each group is as close as possible to half of the total probability.
  3. Assign a binary 0 to the first group and a binary 1 to the second group.
  4. Recursively repeat steps 2–3 on each subgroup until all subgroups contain only one symbol.

2.1.1 Recursive splitting of symbol set

The split is performed by finding the point in the sorted list that minimizes the difference between the cumulative probabilities of the left and right halves. This is typically done by scanning from left to right, computing cumulative sums, and choosing the split where the cumulative sum is closest to half the total probability of the current group.

2.1.2 Assigning binary codewords

Each split appends a bit (0 or 1) to the codewords of the symbols in the respective subgroup. The process continues recursively until each symbol has its own leaf node. The final codeword for a symbol is the sequence of bits assigned along the path from the root to that leaf.

2.2 Decoding procedure

Decoding a Shannon–Fano coded bitstream requires the same code tree used during encoding. The decoder starts at the root and reads bits one at a time. For each bit, it moves to the left child (if 0) or right child (if 1). When a leaf node (symbol) is reached, the decoder outputs that symbol and returns to the root. This process continues until the end of the bitstream.

2.3 Example: coding a small alphabet

Consider five symbols with probabilities: A=0.4, B=0.2, C=0.2, D=0.1, E=0.1. Sorted: A(0.4), B(0.2), C(0.2), D(0.1), E(0.1). Total = 1.0. The first split: cumulative sum after A is 0.4, close to 0.5; after A+B is 0.6, also close. The difference for split after A is0.4 – 0.6= 0.2; after A+B is0.6 – 0.4= 0.2; both equal, but typical implementations choose the first split that yields minimal difference. Suppose we split after A (0.4 vs 0.6). Assign 0 to {A} and 1 to {B,C,D,E}.

Now split the right group {B(0.2), C(0.2), D(0.1), E(0.1)} total 0.6. Splitting after B: cumulative 0.2, remaining 0.4, diff 0.2; after B+C: cumulative 0.4, remaining 0.2, diff 0.2. Choose split after B+C (or after B). Assume after B+C: assign 0 to {B,C} and 1 to {D,E}. Then split {B,C}: total 0.4, split after B (0.2/0.2). Assign 0 to {B}, 1 to {C}. Split {D,E}: total 0.2, split after D (0.1/0.1). Assign 0 to {D}, 1 to {E}.

Resulting codewords:

  • A: 0
  • B: 10 0 → 100
  • C: 10 1 → 101
  • D: 11 0 → 110
  • E: 11 1 → 111

Average length = 0.4×1 + 0.2×3 + 0.2×3 + 0.1×3 + 0.1×3 = 0.4 + 0.6 + 0.6 + 0.3 + 0.3 = 2.2 bits/symbol. Entropy ≈ 2.12 bits, so the code is within 0.08 bits of the bound.

3 Properties

3.1 Average code length

The average code length of a Shannon–Fano code is bounded by the entropy \( H \) and \( H+1 \). In practice, for many probability distributions, it is close to the entropy but can exceed the optimal Huffman code length. The exact average length depends on the splitting decisions and the specific probabilities.

3.2 Optimality and limitations

Shannon–Fano coding is not guaranteed to produce the minimal average code length. The recursive splitting may lead to unbalanced trees and longer codewords than necessary. In contrast, Huffman coding always achieves the optimal prefix code. The limitations of Shannon–Fano become apparent in cases where symbol probabilities are not dyadic (i.e., not powers of 1/2) or when the set size is large.

3.2.1 Comparison with Huffman coding

For most probability distributions, Huffman coding yields an equal or shorter average code length than Shannon–Fano. The difference is typically small (less than one bit) but can be significant in pathological cases. Huffman’s bottom-up approach inherently minimizes the weighted path length, while Shannon–Fano’s top-down greedy split may not.

3.2.2 Worst-case scenarios

A worst-case scenario for Shannon–Fano occurs when the probabilities are such that no split can achieve a nearly equal probability partition. For example, with symbols having probabilities 0.9, 0.05, 0.05, the first split results in {0.9} vs {0.05,0.05}, yielding codewords of length 1 for the high-probability symbol and length 2 for the others. Huffman would also produce a similar code, but in other distributions (e.g., 0.49, 0.49, 0.02), Shannon–Fano may assign longer codes to the two frequent symbols than necessary.

4 Applications

4.1 Early data compression systems

Shannon–Fano coding was used in some early data compression systems, such as the Shannon–Fano–Elias coding, and in certain facsimile and image compression prototypes. However, it was soon replaced by more efficient methods like Huffman coding and later arithmetic coding.

4.2 Educational tool for information theory

Because of its conceptual simplicity and ease of manual calculation, Shannon–Fano coding is frequently taught in introductory information theory courses. It serves as a clear demonstration of entropy coding, prefix code construction, and the relationship between probability and code length.

4.3 Variants and improvements

Several variants of Shannon–Fano coding have been proposed, including adaptive versions and modifications that attempt to improve optimality. One such variant is the Shannon–Fano–Elias code, which uses cumulative probabilities to construct a code without splitting, but it may not be a prefix code. Another is the use of Shannon–Fano coding as a fallback in hybrid compression schemes, though modern practice favors arithmetic coding or Huffman coding.

5 See also

5.2 Entropy and information theory topics