Huffman Coding - Introduction to Data Compression - page 83

While this reduction in file size is useful, we could have obtained better compression if we
had first removed the structure existing in the form of correlation between the symbols in the
file. Obviously, there is a substantial amount of correlation in this text. For example, Huf is
always followed by fman ! Unfortunately, this correlation is not amenable to simple numerical
models, as was the case for the image files. However, there are other somewhat more complex
techniques that can be used to remove the correlation in text files. We will look more closely
at these in Chapters 5 and 6.

3.8.3 Audio Compression

Another class of data that is very suitable for compression is CD-quality audio data. The
audio signal for each stereo channel is sampled at 44.1 kHz, and each sample is represented
by 16 bits. This means that the amount of data stored on one CD is enormous. If we want to
transmit this data, the amount of channel capacity required would be significant. Compression
is definitely useful in this case. In Table 3.34 we show, for a variety of audio material, the
file size, the entropy, the estimated compressed file size if a Huffman coder is used, and the
resulting compression ratio.
The three segments used in this example represent a wide variety of audio material, from a
symphonic piece by Mozart to a folk rock piece by Cohn. Even though the material is varied,
Huffman coding can lead to some reduction in the capacity required to transmit this material.
Note that we have only provided the estimated compressed file sizes. The estimated file
size in bits was obtained by multiplying the entropy by the number of samples in the file. We
used this approach because the samples of 16-bit audio can take on 65,536 distinct values, and,
therefore, the Huffman coder would require 65,536 distinct (variable-length) codewords. In
most applications, a codebook of this size would not be practical. There is a way of handling
large alphabets, called recursive indexing, that we will describe in Chapter 9. There is also
some recent work [ 11 ] on using a Huffman tree in which leaves represent sets of symbols with
the same probability. The codeword consists of a prefix that specifies the set followed by a
suffix that specifies the symbol within the set. This approach can accommodate relatively large
alphabets.
As with the other applications, we can obtain an increase in compression if we first remove
the structure from the data. Audio data can be modeled numerically. In later chapters we will
examine more sophisticated modeling approaches. For now, let us use the very simple model
that was used in the image-coding example; that is, each sample has the same value as the
previous sample. Using this model, we obtain the difference sequence. The entropy of the
difference sequence is shown in Table 3.35 .

T A B L E 3 . 34 Huffman coding of 16-bit CD-quality audio.

Original Entropy Estimated Compressed Compression

File Name File Size (bytes) (bits) File Size (bytes) Ratio

Mozart 939,862 12.8 725,420 1.30

Cohn 402,442 13.8 349,300 1.15

Mir 884,020 13.7 759,540 1.16