Questions: Source Coding Theorem

Question 1

A source produces symbols from an alphabet of size 8 with entropy H = 2.5 bits/symbol. A naive fixed-length encoding uses 3 bits per symbol. What does the source coding theorem guarantee about compression?

• A. No code can do better than 3 bits per symbol because the alphabet has 8 symbols
• B. There exist codes achieving average rate arbitrarily close to 2.5 bits per symbol, but no lossless code can go below 2.5
• C. Shannon's theorem guarantees a code achieving exactly 2.5 bits per symbol for every individual sequence
• D. The savings of 0.5 bits per symbol is not achievable because Huffman codes require integer-length codewords

Answer: (B)

The source coding theorem sets the limit at H = 2.5 bits/symbol. Codes like arithmetic coding can get arbitrarily close to this limit for long sequences. Option 3 is wrong because the theorem is about average rate over long sequences, not individual sequences. Option 4 is wrong because while Huffman coding is limited to integer-length codewords (achieving between H and H+1 bits per symbol), arithmetic coding and block Huffman codes can approach H arbitrarily closely.

Question 2

The source coding theorem guarantees that every individual sequence from a source with entropy H can be compressed to exactly H bits per symbol.

• T. True
• F. False

Answer: False

The source coding theorem is an asymptotic, average-case result. It guarantees that the AVERAGE code length per symbol approaches H as the block length grows to infinity. Individual sequences may compress to more or fewer bits. Some sequences (like all-zeros from a biased source) compress much below H; others (rare sequences) require more. What the theorem rules out is an average rate below H — over many sequences drawn from the source, you cannot beat entropy on average.

Question 3

A colleague claims to have developed a lossless compression algorithm that compresses every possible file to a smaller file. Use the source coding theorem (or a counting argument) to explain why this is impossible.

Model answer: If the algorithm maps every n-bit file to a shorter file, then all 2^n possible inputs would map to files of at most n-1 bits. But there are only 2^0 + 2^1 + ... + 2^(n-1) = 2^n - 1 shorter files. By the pigeonhole principle, at least two inputs must map to the same output, making the mapping non-invertible and thus not lossless. More fundamentally, the source coding theorem says the average compressed length cannot be below H, and for a uniform distribution over all n-bit strings, H = n bits — there is no redundancy to exploit. Any compression algorithm that shrinks some files must expand others.

This is one of the most important consequences of information theory: universal compression of all data is impossible. Compression works by exploiting statistical redundancy in the source. Random or already-compressed data has near-maximum entropy and cannot be further compressed. Claims of universal compression algorithms are a reliable indicator of misunderstanding.