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 threebit 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

0.2

0.2



Reduced
frame 2

Probability

0.4

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 1152sample 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 psychoacoustical model.
This model determines the tonelike or noiselike 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.