Huffman Coding and Entropy Bound

Huffman Coding & Entropy Bound

Adjust the probability distribution and observe how the Huffman code approaches the entropy bound.

Entropy H(X)

—

bits/symbol

Expected length L

—

bits/symbol

Gap L − H

—

< 1 bit (theorem)

Redundancy R

—

1 − H/log₂|X|

Huffman Tree

Codewords

Entropy vs. Expected Length

Entropy H

Huffman L

Fixed-length