Huffman coding
Huffman coding is a lossless entropy-coding method that gives common symbols shorter bit patterns and rare symbols longer ones.
What it is
Huffman coding builds an efficient prefix code. In a prefix code, no complete codeword is the beginning of another codeword. That means a decoder can read a continuous stream of bits and still know where one symbol ends and the next begins.
The useful trick is probability. If a symbol appears often, the code can spend fewer bits on it. If a symbol appears rarely, the code can afford to use more bits. The original data can still be reconstructed exactly, so Huffman coding itself is lossless.
Origin story
David A. Huffman developed the method while he was a graduate student at MIT. His 1952 paper, A Method for the Construction of Minimum-Redundancy Codes, described a practical way to construct an optimal prefix code for a known set of symbol probabilities.
The reason Huffman coding replaced Shannon-Fano coding in many explanations is simple: both use probability, but Huffman's bottom-up tree construction gives the optimum prefix code for the usual minimum average code-length problem.
How it works
- Count, estimate, or model how often each symbol appears.
- Start with the least likely symbols.
- Repeatedly merge the two least likely items into a new branch.
- Read each path through the finished tree as a sequence of 0s and 1s.
The most likely symbols end up closer to the top of the tree, so they receive shorter codes. The least likely symbols sit deeper in the tree, so they receive longer codes.
Rare symbol → longer code
Same meaning → fewer average bits
Where it fits in a codec
Huffman coding is not a complete audio or video codec. It is usually one of the final packing steps after the codec has already done more specialised work.
For example, an audio codec may split sound into frequency bands, estimate what the ear is less likely to notice, quantize the result, and then use entropy coding to store the remaining numbers efficiently. A video codec may predict motion, transform image residuals, quantize coefficients, and then entropy-code the symbols left behind.
In plain English: the codec first makes the data easier to describe. Huffman-style coding then helps write that description using fewer bits.
Huffman, VBR, and ABR
You are right that Huffman coding ties naturally into bitrate behaviour, especially in audio encoders such as MP3. The connection is not that Huffman coding is ABR. The connection is that Huffman coding changes how many bits are needed to describe each block of encoded data.
In MP3-style encoding, a simple passage may produce symbols that can be coded with fewer bits. A complex passage may need more bits after quantization and Huffman coding. That uneven demand is one of the reasons bitrate modes exist:
| Mode | What the encoder is trying to do | How Huffman coding relates |
|---|---|---|
| CBR | Keep the bitrate constant or very predictable. | The encoder may have to quantize harder when the Huffman-coded data would otherwise need too many bits. |
| VBR | Spend more bits where the audio is harder and fewer where it is easier. | The number of Huffman-coded bits helps reveal how expensive a frame is to represent. |
| ABR | Aim for a chosen average bitrate while allowing frame-by-frame variation. | The encoder can vary local bit use while steering the whole file toward the target average. |
Important distinction: in audio tools, ABR usually means average bitrate. In streaming video, ABR often means adaptive bitrate, where the player switches between several prepared streams. Huffman coding is closer to the first meaning because it helps determine how many bits a compressed audio frame needs.
Where it shows up
Modern formats do not all use literal textbook Huffman coding. Some use fixed Huffman tables, some use Huffman-like variable-length codes, and newer video codecs often use arithmetic or range coding instead. The family resemblance is entropy coding: represent likely outcomes cheaply and unlikely outcomes more expensively.
| Area | Typical relationship |
|---|---|
| MP3 | Uses Huffman coding as part of MPEG Layer III's noiseless coding stage after quantization. |
| AAC | Uses Huffman/noiseless coding for quantized spectral data in common AAC profiles. |
| JPEG | Traditionally uses Huffman coding after transform and quantization stages. |
| H.264/AVC | Uses entropy coders such as CAVLC and CABAC rather than simply “Huffman coding”. |
| HEVC/H.265 | Uses CABAC, an arithmetic-coding-based entropy coder. |
| AV1 | Uses modern entropy coding rather than classic Huffman coding. |
Sources and further reading
- David A. Huffman, A Method for the Construction of Minimum-Redundancy Codes, 1952.
- Karlheinz Brandenburg, MP3 and AAC Explained, AES paper.
- LAME documentation on average bitrate mode.
- H.264/AVC entropy-coding material on CAVLC and CABAC.