Huffman Coding

David Huffman in 1954 designed a lossless coding procedure for a frame of values that has the smallest possible average code length. It assigns a single bit to the most probable value and successively more bits to less probable values. The weighted sum of (number of bits for a particular value * probability of that value's occurrence in the frame) yields the average bit size per value needed to transmit the frame. This number is less than or equal to the number of bits if each value was equally probable. An example will help illustrate the advantages of Huffman coding.

Example: Suppose a frame of 10 values has the sequence 2,3,4,3,2,1,0,1,2,2. In the PCM format, each of these values would be converted to a three-bit binary number. The sequence is written as 010,011,100,011,010,001,000,001,010,010. This frame is represented by 30 bits. Now let's use Huffman's procedure. The probability of each of the values is given in the original frame table in order of decreasing probability and increasing number of bits used to represent each value. (Note that the values 3 and 1 have the same probability. Representing 1 with 2 bits and 3 with 2 bits yields an equally valid but different Huffman code. In this example, the same is true for values 4 and 0. Huffman codes are not unique.) The average number of bits per value is then 0.4*1 + 0.2*2 + 0.2*3 + 0.1*4 + 0.1*4 = 2.2 which is less than the 3 in the binary coding with equal probability. For this frame, Huffman coding requires only (10*2.2) = 22 bits to transmit the frame. If instead of this sequence of 10 values, 10 different numbers had appeared only once, the probability for each value would be 0.1 and the average number of bits per value would have been 3.

Let us now construct a (not "the" since the code won't be unique) Huffman code for this frame. This is done by taking the two smallest probabilities, adding them and putting them in the ordered list. This sequence is repeated until the only two entries are in the reduced table.

Original frame
Value	Probability	# of bits
2	0.4	1
3	0.2	2
1	0.2	3
4	0.1	4
0	0.1	4

Reduced
frame 1

Probability

0.4

0.2

Reduced
frame 2

Probability

0.4

0.2

Reduced
frame 3

Probability

0.6

0.4

The last two entries are assigned 0 and 1; which one is a 0 or a 1 is arbitrary. The last two probabilities that were combined are split back up and a 0 or 1 is added to the right of the first bit assigned to the combination. In this example, 0.6 is assigned a 1. The 0.6 came from adding 0.4 and 0.2 so these values are assigned 10 and 11, respectively. The 0.4 assigned the value 10 comes from combining 0.2 and 0.2 and so these values are assigned 100 and 101. And so on.

Reduced frame 3
Probability	code
0.6	1
0.4	0

Reduced frame 2
Probability	code
0.4	0
0.4	10
0.2	11

Reduced frame 1
Probability	code
0.4	0
0.2	11
0.2	100
0.2	101

Original frame
Value	Probability	# of bits	Final code
2	0.4	1	0
3	0.2	2	11
1	0.2	3	100
4	0.1	4	1010
0	0.1	4	1011

The final code sequence for the 22 bits needed to represent the frame would be 0,11,1010,11,0,001,1011,001,0,0.

Huffman coding is used in the final step of creating an MP3 file. The MP3 format uses frames of 1152 sample values. If the sample rate is 44.1kHz, the time that each frame represents is ~26ms. The spectrum of this 1152-sample frame is spectrally analyzed and the frequencies are grouped in 32 channels (critical bands). The masking effects within a band are analyzed based on a psycho-acoustical model. This model determines the tone-like or noise-like nature of the masking in each channel and then decides the effect of each channel on its neighboring bands. The masking information for all of the channels in the frame is recombined into a time varying signal. This signal is numerically different from the original signal but the difference is hardly noticeable aurally. The signal for the frame is then Huffman coded. A sequence of these frames makes up an MP3 file.