Mathematics.

source coding

Source Coding Theorem

Information Theory35 minDifficulty7 out of 10

You should know: shannon entropy, typical sequences, prefix codes

Overview

Shannon's source coding theorem (noiseless coding theorem) establishes that the minimum average number of bits per symbol needed for lossless compression equals the entropy H(X). Specifically, H(X) bits/symbol is achievable (entropy coding) and no scheme can do better. Huffman codes achieve rates between H and H+1.

Intuition

If a source emits symbols with distribution p, its entropy H(p) tells you the minimum bits per symbol for lossless storage. Symbols that occur rarely need more bits (like Morse code: rare letters get longer codes). Symbols that occur often need fewer bits. The optimal average code length equals H, achieved by assigning -log_2(p_i) bits to symbol i -- but since codeword lengths must be integers, Huffman codes get within 1 bit of H.

Formal Definition

Definition

Source coding theorem: (i) Achievability: for any R > H(X) and epsilon > 0, there exist lossless codes with rate <= R bits/symbol and error probability < epsilon for large blocks. (ii) Converse: no lossless code can achieve average rate < H(X). Huffman: H(X) <= L_{Huffman} < H(X) + 1 where L = sum p_i * l_i. Arithmetic coding: approaches H(X) for long sequences.

H(X)≤L≤H(X)+1(Huffman)H(X) \leq L \leq H(X) + 1 \quad (\text{Huffman})
Huffman code bounds
li=⌈−log⁡2pi⌉ (Shannon-Fano)l_i = \lceil -\log_2 p_i \rceil \text{ (Shannon-Fano)}
Shannon-Fano code lengths
lim⁡n→∞1nLn∗=H(X)(optimal)\lim_{n\to\infty} \frac{1}{n}L_n^* = H(X) \quad (\text{optimal})
Asymptotic optimality

Notation

NotationMeaning
LLAverage codeword length = sum p_i * l_i
H(X)H(X)Shannon entropy = minimum compression rate

Theorems

Theorem 1: Shannon Source Coding Theorem
For an i.i.d. source X with entropy H(X) bits/symbol: (i) For any R > H(X), there exists a lossless block code with rate R bits/symbol and vanishing error. (ii) Any lossless code requires at least H(X) bits per source symbol on average.

Worked Examples

  1. 1

    H = (1/2)*1 + (1/4)*2 + (1/8)*3 + (1/8)*3 = 1.75 bits.

    H=1.75 bitsH = 1.75 \text{ bits}
  2. 2

    Huffman: A='0', B='10', C='110', D='111'. Lengths: 1,2,3,3.

    L=(1/2)(1)+(1/4)(2)+(1/8)(3)+(1/8)(3)=1.75 bitsL = (1/2)(1)+(1/4)(2)+(1/8)(3)+(1/8)(3) = 1.75 \text{ bits}

✓ Answer

H = L = 1.75 bits (Huffman is optimal for this distribution).

Practice Problems

Mediumapplication

Show that no code can achieve average length below H(X) for a distribution with H(X) = 2.3 bits.

Common Mistakes

Common Mistake

Thinking Huffman coding achieves exactly H(X) bits.

Huffman achieves H(X) <= L < H(X)+1. For exactly H(X) bits/symbol, symbol probabilities must be exact powers of 2 (like 1/2, 1/4). Otherwise, there's a fractional-bit gap that arithmetic coding fills.

Quiz

A source has entropy H = 3.7 bits. A Huffman code for this source has average length L satisfying:

Historical Background

Shannon (1948) proved the source coding theorem as part of his foundational work. The theorem answered a fundamental question: how much can information be compressed? The answer, entropy H(X), defined the ultimate limit. Arithmetic coding (1970s) can approach H(X) arbitrarily closely, unlike Huffman which can be up to 1 bit/symbol above H.

  1. 1948

    Shannon proves the source coding theorem in A Mathematical Theory of Communication

    Claude Shannon

  2. 1976

    Pasco and Rissanen develop arithmetic coding, approaching entropy rate closely

    Richard Pasco, Jorma Rissanen

Summary

  • Source coding theorem: min average bits/symbol for lossless compression = H(X).
  • Huffman: H(X) <= L < H(X)+1. Achieves optimum when probabilities are powers of 2.
  • Arithmetic coding approaches H(X) for long sequences.
  • Converse: no uniquely decodable code has L < H(X).

References

  1. BookCover, T.M. and Thomas, J.A. Elements of Information Theory. 2nd ed. Wiley, 2006.