Huffman/Run-Level Coding
In MPEG, Huffman coding in combination with Run-Level coding and zig-zag scanning is applied to quantized DCT coefficients. "Run-Level" refers to a run-length of zeros followed by a non-zero level. Huffman coding is also applied to various types of side information.
A Huffman code is an entropy code that is optimum in the sense that it achieves the shortest average possible code word length for a source. This average code word length is >= the entropy of the source.
A typical 8x8 block of quantized DCT coefficients is shown below. Most of the higher order coefficients have been quantized to 0.
12 34 0 54 0 0 0 0
87 0 0 12 0 0 0 0
16 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
After zig-zag scanning the sequence of DCT coefficients to be transmitted looks like:
12 34 87 16 0 0 54 0 0 0 0 0 0 12 0 0 3 0 0 0 .....
The DC coefficient (12) is sent via a separate Huffman table.
After Run-Level parsing, the remaining coefficients and associated runs of zeros are:
34 | 87 | 16 | 0 0 54 | 0 0 0 0 0 0 12 | 0 0 3 | 0 0 0 .....
When examining large amounts of video data encoded in this manner, common run-level sequences have been found. These common sequences are encoded with relatively short code words and are permanently stored in a table in the decoder. A special end of block codeword indicates that all subsequent quantized DCT coefficients in the 8x8 block are 0.
Less common sequences that are not encoded in this manner (because they are not in the Huffman table) are indicated with an escape sequence.
Huffman/Run-Level Coding