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?
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.