Data Compression 581This is the essence of a compression technique known as run-length encoding (RLE).
RLE works really well but it has a problem. If a data fi le is composed of data that are
predominantly nonrepetitive, RLE actually makes the fi le bigger! So RLE must be made
adaptive so that it is only applied to strings of similar data (where redundancy is high);
when the coder detects continuously changing data (where entropy is high), it simply
reverts back to sending the bytes in an uncompressed form. Evidently it also has to insert
a small information overhead to instruct the decoder when it is (and isn’t) applying the
compression algorithm.
Another lossless compression technique is known as Huffman coding and is suitable for
use with signals in which sample values appear with a known statistical frequency. The
analogy with Morse code is frequently drawn, in which letters that appear frequently
are allocated simple patterns and letters that appear rarely are allocated more complex
patterns. A similar technique, known by the splendid name of the Lempel-Ziv-Welch
(LZW) algorithm, is based on the coding of repeated data chains or patterns. A bit like
Huffman’s coding, LZW sets up a table of common patterns and codes specifi c instances
of patterns in terms of “ pointers, ” which refer to much longer sequences in the table.
The algorithm doesn’t use a predefi ned set of patterns but instead builds up a table of
patterns that it “ sees ” from incoming data. LZW is a very effective technique—even
better than RLE. However, for the really high compression ratios, made necessary by
the transmission and storage of high-quality audio down low bandwidth links, different
approaches are required, based on an understanding of human perception processes.
In principle, the engineering problem presented by low-data rates, and therefore in
reduced digital resolution, is no different to the age-old analogue problems of reduced
dynamic range. In analogue systems, noise reduction systems (either complementary,
i.e., involving encoding and complementary decoding such as Dolby B and dbx1, or
single ended) have been used for many years to enhance the dynamic range of inherently
noisy transmission systems such as analogue tape. All of these analogue systems rely
on a method called “ compansion, ” a word derived from the contraction of compression
and expansion. The dynamic range is deliberately reduced (compressed) in the recording
stage processing and recovered (expanded) in the playback electronics. In some systems
this compansion acts over the whole frequency range (dbx is one such type). Others
work over a selected frequency range (Dolby A, B, C, and SR). We shall see that the
principle of compansion applies in just the same way to digital systems of data reduction.
Furthermore, the distinction made between systems that act across the whole audio