Samples from a 16-bit ADC
Compression reduces bandwidth and storage requirements by removing redundancy and irrelevancy. Redundancy occurs when data is sent when it’s not needed. Irrelevancy frequently occurs in audio and video signals because human hearing and vision are imperfect and can be fooled. Audio and video compression algorithms attain compression ratios of up to 20:1 by cleverly reducing redundancy and irrelevancy.
After lowering redundancy and irrelevancy, compression algorithms still have to pack the remaining bits. Bit packing is an encoding process that often generates variable-length tokens. Unlike redundancy and irrelevancy removers, bit packers must be lossless.
Most computer science majors may remember creating a Huffman encoder and decoder during an introductory programming class. Huffman encoders examine the statistics of values in an input data stream and create a mapping of input values to variable-length output tokens. Common input values are mapped to short tokens, while infrequent values are mapped to longer tokens. Huffman encoding exploits input data statistics to pack bits as efficiently as possible.
While Huffman bit packing provides nearly optimal lossless compression, it suffers from a few drawbacks. When input data values aren’t aligned on byte boundaries (for example, compressing samples from a 10-bit analog-to-digital converter or ADC), byte-oriented Huffman encoders generate noise-like statistics. Similarly, when the statistics of input data values change over time, adaptive Huffman coders are required.
Adaptive Huffman coding implementations are quite complicated, especially at rates of 100 MHz or greater in real-time digital signal processing (DSP) applications. To overcome some of the drawbacks of Huffman bit packers, let’s consider three alternative bit packers for real-time DSP.
Most compression algorithms consist of a redundancy remover followed by a bit packer. To illustrate how alternative bit packers operate, the table features a sequence of 20 samples from a 16-bit ADC that we’d like to pack into as few bits as possible.
Without compression, our 20 × 16-bit samples need 320 bits. In the table, the “number of bits” row indicates how many bits are required to represent the value as a twos complement number. For example, Sample 1 with value +12 requires 5 bits: a sign bit (0 = ‘+’) plus 4 magnitude bits (0101 = 5).
Bit packer A will pack all 20 values using the same number of bits. Since sample 20 requires the most bits (14 bits for the value –4201), bit packer A packs the 20 values into 20 × 14 = 280 bits. We also need a “packed word size” field, sent prior to the packed samples, that indicates the next 20 values are each stored in 14 bits.
The “packed word size” requires 4 bits, since the largest packed word is 16 bits. So, bit packer A’s compressed packet size is 280 + 4 = 284 bits, for a compression ratio of 320/284 = 1.127:1. Can we do better than 284 bits? Yes, we can.
Bit packers B and C will pack four successive values using a shared group exponent, as shown in the table. For instance, samples 1 to 4 require 5, 10, 11, and 11 bits per sample, but we’ll send all four values using a group exponent of 11 bits. With this technique, we can send our 20 values using (4 * 11) + (4 * 12) + (4 * 12) + (4 * 13) + (4 * 14) = 248 bits.
But wait. Bit packer B also has to send the exponent bits, which is like sending bit packer A’s “packed word size” with each of bit packer B’s four-sample groups. Exponent bits add 20 bits to our total. Bit packer B’s compressed packet uses 248 + 20 = 268 bits, or 1.19:1 compression. Bit packer C packs bit packer B’s exponents more efficiently. We notice that exponent values change slowly. Instead of sending five slowly changing exponents (11, 12, 12, 13, 14) using 4 bits per exponent, bit packer C encodes the difference between exponents \{11, +1, 0, +1, +1\}.
To get started, we still send the first exponent (11) using 4 bits. Then we send the four differences with this mapping: 0 » 0 \\[1 bit\\], +1 » 100 \\[3 bits\\], –1 » 101, +2 » 1100 \\[4 bits\\], –2 » 1101, etc. Thus, bit packer C sends the five exponents \{11, +1, 0, +1, +1\} using just 4 + 3 + 1 + 3 + 3 = 14 bits. Bit packer C’s compressed packet size is 248 + 14 = 262 bits, or 1.22:1 compression.