Full search page →

Give common symbols shorter codes

IntermediateIT 03 · Lossless Coding and Universal CompressionInteractive plot

Description

Build a binary prefix code and compare its average length with source entropy.

Try this: Compare P(A) = 0.25 with P(A) = 0.7. Why does the optimal code change in discrete jumps while entropy changes smoothly?

Hints

The chapter section that uses this lab:

Lab · Give common symbols shorter codes

Source entropy
1.357
Expected code length
1.5
Redundancy (bits/symbol)
0.143

No codeword is the prefix of another, so concatenated bits can be decoded without separators. Expected length is Σ p(symbol) × code length = 1.5 bits/symbol. Entropy is 1.357; their gap is 0.143. Spaces in the example only show codeword boundaries.

Try this: Compare P(A) = 0.25 with P(A) = 0.7. Why does the optimal code change in discrete jumps while entropy changes smoothly?

Huffman coding repeatedly merges the two least probable nodes. Ties use alphabetical order. B, C and D each have probability (1−P(A))/3. The expected length assumes this source distribution; the example message has its own symbol counts. Codebook transmission cost is excluded.

Method sources

Open in the Playground →