Compression in Practice

The previous chapter, Source Coding and Prefix Codes, ended with three weaknesses of Huffman's code. Each letter costs a whole number of bits, so a binary source with $p = 0.01$, whose entropy is $h(0.01) = 0.0808$ bits, pays 1 bit per letter, 12.4 times its entropy. The probabilities must be known before coding starts. And a code for single letters cannot use the way one letter makes the next more predictable. The same chapter showed that compressed data is fragile, since one flipped bit moved every codeword boundary after it.

Arithmetic coding, range coding and asymmetric numeral systems answer the first weakness by spending fractions of a bit. Adaptive models and the dictionary coders LZ77, LZ78 and LZW answer the other two by learning the source while reading it, and the Burrows–Wheeler transform with move-to-front turns the memory in text into skewed letter counts. A survey of lossy coding follows, and the chapter ends inside a computer's memory system, where compression and fragility meet.

Every number in the chapter is recomputed by ch06_compression_in_practice.py in the python/ folder of the companion repository ecc-book-lab, and the charts are drawn by ch06_charts.py in the same folder.

01.Coding with Intervals

A source emits the letters a, b and c independently, with probabilities 0.7, 0.2 and 0.1. Its entropy is $H(X) = 1.1568$ bits, and Huffman's code, a 0, b 10 and c 11, averages 1.3 bits per letter. The message aabaaa has probability $0.7^5 \times 0.2 = 0.033614$, so it carries $\log_2(1/0.033614) = 4.8948$ bits of information, yet Huffman's code spends 7 bits on it. The waste is rounding, since each a carries $\log_2(1/0.7) = 0.5146$ bits and is charged a whole bit.

Arithmetic coding never charges a letter on its own. It turns the whole message into one interval inside $[0, 1)$. Each letter owns a slice as wide as its probability, a the slice $[0, 0.7)$, b the slice $[0.7, 0.9)$ and c the slice $[0.9, 1)$. The first a keeps $[0, 0.7)$. That interval is split in the same proportions, the second a keeps its first 70 percent, $[0, 0.49)$, and the b keeps the part from 70 to 90 percent of its width, $[0.343, 0.441)$. Table 1 carries the steps to the end of the message, and Figure 1 draws them. To write a step as a formula, fix the order a, b, c and let the cumulative probability $F(s)$ be the total probability of the letters before $s$, so that $F(a) = 0$, $F(b) = 0.7$, $F(c) = 0.9$ and letter $s$ owns $[F(s), F(s) + p(s))$.

The widths multiply, so the final width $w_n = p(x_1)\, p(x_2) \cdots p(x_n)$ is the probability of the message, 0.033614 for aabaaa.

The bits $c_1 c_2 \cdots c_l$ name the fraction $v/2^l$, where $v$ is the integer they spell, and every longer string that begins with them names a number in $[v\,2^{-l}, (v+1)\,2^{-l})$. This is the dyadic interval of the string, the object the previous chapter's section The Kraft Inequality laid end to end. The encoder sends a string whose dyadic interval lies inside the message's interval, so the decoder can identify the message whatever bits follow.

For aabaaa, $l = \lceil 4.8948 \rceil + 1 = 6$ and $v = \lceil 0.343 \times 64 \rceil = \lceil 21.952 \rceil = 22$, which is 010110 in six bits. Its dyadic interval $[0.34375, 0.359375)$ lies inside $[0.343, 0.376614)$. The tag costs 6 bits, one fewer than Huffman's code and 1.1052 bits more than the information in the message.

Proof. Since $v \ge u\, 2^l$, the dyadic interval starts at or above $u$. Since $v < u\, 2^l + 1$, it ends below $u + 2 \cdot 2^{-l} = u + 2^{-(l-1)}$, and $l - 1 = \lceil \log_2(1/w) \rceil$ gives $2^{-(l-1)} \le w$. $\blacksquare$

The decoder reads the tag as $z = 0.34375$, which lies in a's slice $[0, 0.7)$, so the first letter is a. It undoes that narrowing by stretching the slice back over $[0, 1)$, replacing $z$ by $(z - F(s))/p(s)$, and repeats, as Table 2 shows. It must also be told when to stop, by a length sent first or by a letter reserved to end a message.

Proof. For $n = 0$ the empty message owns $[0, 1)$. Within the interval $[u, u + w)$ of a message of $n - 1$ letters, the slice of $s$ runs from $u + w\, F(s)$ to $u + w\, (F(s) + p(s))$, and $F(s) + p(s)$ is $F$ of the next letter, so each slice ends where the next begins and the last ends at $u + w$. The slices tile each parent, and by induction the parents tile $[0, 1)$. $\blacksquare$

So exactly one slice of a first letter contains $z$, the right one, and stretching it carries the message's interval onto the interval of its remaining letters, where the argument repeats.

Proof. A tag that prefixed another would have a dyadic interval containing the other's. But each dyadic interval lies inside its own message's interval, and those intervals are disjoint. $\blacksquare$

02.Why Arithmetic Coding Reaches the Entropy

A tag has length $\lceil \log_2(1/P(x)) \rceil + 1$, less than $\log_2(1/P(x)) + 2$, and averaging this over all messages gives the main result.

Proof. The upper bound is $L_n < \sum_x P(x) \log_2(1/P(x)) + 2$, and with independent letters $\log_2(1/P(x))$ is a sum of $n$ terms $\log_2(1/p(x_k))$, each with expectation $H$. The lower bound holds because the tags are a prefix code for blocks whose entropy is $nH$, and the previous chapter's section The Entropy Lower Bound shows that no prefix code averages less. $\blacksquare$

Huffman's code on blocks of $n$ letters guarantees $H + 1/n$, but it needs a table of $m^n$ codewords, where arithmetic coding computes only the interval of the message sent. Table 3 compares the two for a binary source with $p = 0.1$, whose entropy is $h(0.1) = 0.4690$ bits, and Figure 2 plots them.

For short messages the overhead dominates. At $n = 1$ the letter 0 gets a 2-bit tag and the letter 1 a 5-bit tag, for $0.9 \times 2 + 0.1 \times 5 = 2.3$ bits per letter. The rate is not even monotone, 0.7114 at $n = 6$ and 0.7286 at $n = 7$, because the rounding in the tag length falls differently for each $n$. At $n = 1000$ it is 0.4705, within 0.0015 of the entropy, with no table at all. The source with $p = 0.01$ fares the same, at 0.0823 bits per letter for $n = 1000$ against its entropy of 0.0808 and its bound of 0.0828.

03.Range Coding and Adaptive Models

As described so far, the encoder holds $u_k$ and $w_k$ exactly, and their digits multiply with every letter. A practical coder uses numbers of fixed size, because the leading bits of the tag settle long before the message ends. After aa the interval $[0, 0.49)$ lies inside $[0, 1/2)$, where every number begins with the bit 0, so the encoder emits 0 and doubles the interval to $[0, 0.98)$. The b narrows this to $[0.686, 0.882)$, inside $[1/2, 1)$, so it emits 1 and maps $x$ to $2x - 1$, leaving $[0.372, 0.764)$. The bits 01 begin the tag 010110.

The next three letters leave intervals that straddle $1/2$, down to $[0.372, 0.506456)$, and settle nothing. An interval inside $[1/4, 3/4)$ can shrink this way until it exhausts any fixed precision. Witten, Neal and Cleary [1] resolved this with pending bits. Numbers in $[1/4, 1/2)$ begin 01 and numbers in $[1/2, 3/4)$ begin 10, so the next two bits are certain to differ. The encoder maps $x$ to $2x - 1/2$ and counts a pending bit, and when a bit $b$ settles it emits $b$ followed by one $1 - b$ per pending bit. An interval that fits none of the three cases contains $[1/4, 1/2]$ or $[1/2, 3/4]$, so it is wider than $1/4$ and a register of fixed size keeps enough precision.

Range coding does the same with integers. Start from the range $R = 1000$, with frequencies $f(a) = 7$, $f(b) = 2$ and $f(c) = 1$, total $T = 10$ and cumulative counts $c(a) = 0$, $c(b) = 7$ and $c(c) = 9$. Each letter $s$ updates

For aabaaa the range runs 1000, 700, 490, 98, 68, 47 and 32, and the lower end moves once, to 343 at the b, giving $[343, 375)$ in thousandths. The exact width is 33.614, so truncation cost $\log_2(33.614/32) = 0.0710$ bits.

Truncation never makes slices overlap. The slice of $s$ ends at or before $\text{low} + \lfloor R\,(c(s) + f(s))/T \rfloor$, where the next slice begins, because $\lfloor \alpha \rfloor + \lfloor \beta \rfloor \le \lfloor \alpha + \beta \rfloor$, and the gaps it leaves are unused code space, the source of the 0.0710 bits. To keep $R$ large the coder sends the leading digit once the whole interval shares it. After aaba, $[343, 411)$ holds numbers beginning with 3 and with 4, but every number in $[343, 390)$ after aabaa begins with 3, so that digit goes out and the rest is scaled by 10. Rissanen [2] introduced arithmetic codes that run in finite precision.

The decoder can follow any model it can compute itself, so the model may learn. Start each of $m$ letters with a count of 1, and predict each letter in proportion to its count. For aab with $m = 3$ the predictions are $1/3$, $2/4$ and $1/5$, giving the message probability $1/30$.

The denominators are $m, m + 1, \ldots, n + m - 1$ whatever the letters, and letter $s$ contributes the numerators $1, 2, \ldots, k_s$, so

For aabaaa this is $2!\, 5!\, 1!\, 0!/8! = 1/168$, or 7.3923 bits and a 9-bit tag, against 6 bits with the true model.

Proof. By Equation 5, $P_L(x) = \bigl(\prod_s k_s!/n!\bigr) \big/ \binom{n+m-1}{m-1}$. With $q_s = k_s/n$, the number $\frac{n!}{\prod_s k_s!} \prod_s q_s^{k_s}$ is the probability that $n$ letters drawn with probabilities $q_s$ have exactly the counts $k_s$, so it is at most 1, and $\prod_s k_s!/n! \ge \prod_s q_s^{k_s}$. And $\log_2 \prod_s q_s^{k_s} - \log_2 P(x) = n\, D(Q \,\|\, P) \ge 0$ by Gibbs' inequality from the chapter Information and Entropy. Together these give $P_L(x) \ge P(x)/\binom{n+m-1}{m-1}$. $\blacksquare$

For three letters the price is at most $\log_2 \binom{n+2}{2}$, which is 12.331 bits at $n = 100$ and 18.936 bits at $n = 1000$. Each factor $(n + j)/j$ of the binomial coefficient is at most $n + 1$, so in general the price is at most $(m - 1)\log_2(n + 1)$ bits per message, a share per letter that falls toward zero.

04.Asymmetric Numeral Systems

Arithmetic coding carries two numbers, the lower end and the width. Asymmetric numeral systems, introduced by Duda [3], carry one integer, the state. Appending a decimal digit $d$ to $x$ gives $10x + d$, which multiplies $x$ by about 10 and adds $\log_2 10 = 3.32$ bits, the information in a uniformly random digit. ANS makes the multiplier about $1/p(s)$ for a letter of probability $p(s)$, so each letter adds its own information.

Take $M = 10$, the total of the frequencies 7, 2 and 1, and give a the slots 0 to 6, b the slots 7 and 8, and c the slot 9, writing $f_s$ for the number of slots of $s$ and $c_s$ for its first slot. Every integer belongs to the letter that owns its slot $x \bmod 10$, so the a-integers are 0 to 6, 10 to 16 and so on, as Figure 3 lays out. Pushing $s$ onto the state $x$ moves to the integer numbered $x$, counting from 0, among the integers of $s$. Pushing a onto 10 gives 13, since 0 to 6 are a-integers number 0 to 6, 10 to 12 are numbers 7 to 9, and 13 is number 10. The integers of $s$ have density $f_s/M$, so number $x$ among them lies near $xM/f_s$.

Proof. Write $x = f_s q + r$ with $0 \le r < f_s$, so that $C(s, x) = Mq + c_s + r$. Since $c_s + r < c_s + f_s \le M$, the slot is $c_s + r$, one of the slots of $s$, and $\lfloor C(s, x)/M \rfloor = q$. Then $D(C(s, x)) = f_s q + r = x$. $\blacksquare$

With $q = (x - r)/f_s$, the push is $C(s, x) = \frac{M}{f_s}x + \epsilon$ with $\epsilon = c_s - r\bigl(\frac{M}{f_s} - 1\bigr)$. The first term of $\epsilon$ lies in $[0, M - f_s]$ and the second in $[0, (f_s - 1)(M - f_s)/f_s]$, so $|\epsilon| \le M - f_s$, and dividing by $Mx/f_s$ gives, for $x \ge 1$,

The correction fades as the state grows, so over a long message each letter adds close to $\log_2(1/p(s))$ bits. The decoder pops the most recent letter first, like a stack, so the encoder pushes the message backward. Table 4 encodes aabaaa from the state 10.

The factors approach the ideal $10/7 = 1.4286$ and $10/2 = 5$ as the state grows. The b lands on 117 because the b-integers run 7, 8, 17, 18 and so on, which makes 117 number 22. The six factors multiply to $\log_2 23.4 = 4.5484$ bits, a little under the 4.8948 bits of information, but the final state 234 needs 8 bits, so on a short message the starting state is an overhead, like the 2 bits of arithmetic coding. Decoding starts from 234, whose slot 4 belongs to a, with $D(234) = 7 \times 23 + 4 = 165$, and the states run back through 117, 22, 16 and 13 to 10, popping aabaaa in order.

Left alone the state grows without bound, so a practical coder keeps it in $[10, 100)$ by emitting digits. Before pushing $s$, while $x \ge 10 f_s$, it emits the last digit of $x$ and divides $x$ by 10, rounding down. On aabaaa the first pushes give 13, 16 and 22. Before the b, $22 \ge 20$, so the encoder emits 2, continues from 2 and reaches $C(b, 2) = 17$, then 23 and 32. It sends the state 32 and the digit 2. The decoder pops through 23 and 17 to 2, reads the digit back because $2 < 10$, giving 22, and pops on through 16 and 13 to 10.

Proof. Let $10 \le x < 100$. If $x \ge 10 f_s$, one division gives $\lfloor x/10 \rfloor$, which is at least $f_s$ and below 10. Either way the state $x'$ that is pushed satisfies $f_s \le x' < 10 f_s$, so $q$ lies between 1 and 9 and $C(s, x') = 10q + c_s + r$ lies in $[10, 100)$. A pop returns $x'$, which is below 10 exactly when a digit was emitted, and reading that digit back restores $x$. $\blacksquare$

Nothing here depends on base 10. Choosing $M$ as a power of 2 turns division by $M$ into a shift, and moving 8 bits at a time instead of a decimal digit changes nothing in the proof. The Zstandard format [4] uses a table-driven variant of ANS that its specification calls Finite State Entropy.

05.Dictionary Coding with LZ77

Every coder so far needs a model to supply probabilities. Dictionary coders need none. They replace a string that has occurred before by a pointer to its earlier copy, and the first, described by Ziv and Lempel [5] in 1977, is now called LZ77.

Table 5 parses abcbcbcabcd, numbering positions from 1. The first three letters are new and go as literals. At position 4 the text ahead begins with bcbc, which also begins 2 positions back, so one triple $(2, 4, a)$ covers five letters. At position 9 the text bcd begins with bc, which begins 3, 5 and 7 positions back, and the encoder takes the nearest.

The copy at position 4 is longer than its offset, so it overlaps its own output. The decoder copies one letter at a time, and each copy may read a letter it has just written, as the shading in Figure 4 shows. An offset of 1 therefore codes a run, so aaaaaaab becomes $(0, 0, a)$ and $(1, 6, b)$.

The DEFLATE format [6] uses a window of 32,768 bytes and copies of 3 to 258 bytes. It sends each step as a literal byte or a (length, distance) pair and codes those with Huffman codes, so the prefix codes of the previous chapter sit behind the dictionary.

06.LZ78 and LZW

LZ78 [7] builds an explicit dictionary of phrases instead. Each phrase is the longest phrase already in the dictionary plus one new letter, sent as the pair (number of that phrase, new letter) and then added. The text aababcabcd splits into a, ab, abc and abcd, sent as $(0, a)$, $(1, b)$, $(2, c)$ and $(3, d)$, where phrase 0 is the empty phrase. Phrase $i$ points to one of $i$ earlier phrases, so on a binary source $c$ phrases cost

bits, and a last phrase cut short by the end of the text costs only its pointer.

Ziv and Lempel proved that LZ78 is universal. On any stationary ergodic source, one whose statistics do not change with time and whose long-run averages match its expectations, its bits per letter approach the entropy rate, the limit of $H(X_1, \ldots, X_n)/n$, without the coder being told the source. That proof needs more probability than this Part develops. Figure 5 shows how slowly the approach happens on one sequence from the source with $p = 0.1$, from 0.76 bits per letter after 100 letters to 0.5586 after a million, still 19 percent above the entropy. Over the thirteen lengths plotted, the excess times $\log_2 n$ stays between 1.68 and 2.34, so the excess shrinks roughly like $2/\log_2 n$, far more slowly than the $2/n$ of arithmetic coding with a known model.

Welch's variant LZW [8] drops the explicit letter. Its dictionary starts with every single letter, and each step sends only the number of the longest entry matching the text ahead, then adds that entry followed by the next letter. With a numbered 0 and b numbered 1, Table 6 codes abababa as 0, 1, 2 and 4.

The decoder rebuilds the dictionary one step behind, because each new entry ends with the first letter of the next phrase. It can therefore receive a number it has not yet defined, as with 4 here. That happens only when the encoder sends the entry it has just created, which is the previous phrase followed by its own first letter, so entry 4 is ab followed by a, which is aba. On aaaaaaa the numbers are 0, 2, 3 and 0, and both 2 and 3 are such special cases.

07.Run-Length Coding

A row of a scanned page might hold 12 white pixels, 3 black, 9 white and 2 black. As bits the row is 26 long, but its four runs fit in 16 bits as 4-bit fields, and on two letters the runs alternate, so only the letter of the first run needs to be agreed.

On a memoryless binary source, run-length coding loses nothing. Let 1 have probability $p$, and let $R$ be the gap from one 1 to the next, counting the 1 that ends it. Then $P(R = r) = (1 - p)^{r-1} p$, with mean $E[R] = 1/p$, and

using $E[R - 1] = (1 - p)/p$. A gap covers $1/p$ letters on average, so coding gaps at their entropy costs $h(p)$ bits per letter, the source's own entropy. At $p = 0.1$ a gap carries 4.6900 bits over 10 letters on average, and a Shannon code on gaps, within 1 bit of $H(R)$, spends less than $h(p) + p = 0.5690$ bits per letter, against 1 bit for any code on single letters.

08.The Burrows–Wheeler Transform

Text is not made of runs, but it can be rearranged into something close. The Burrows–Wheeler transform [9] appends an end marker, written $, that sorts before every letter, lists the rotations of the block and sorts them, as Table 7 and Figure 6 do for couscous.

The last column, read downward, is the output. Sorting the rotations sorts the positions of the text by what follows them, and the last column holds the letter just before each position, so letters with the same following context gather. Both rows beginning with ous end in c, because in couscous the letters ous are always preceded by c, and the same happens for the rows beginning with s and with us.

The end marker makes the transform invertible, through a correspondence between the first and last columns.

Proof. The rows that end in a letter $y$ have the form $Wy$, and moving $y$ to the front gives the rows $yW$, which are exactly the rows beginning with $y$, each holding the same occurrence. The rows $Wy$ appear in the sorted order of $W$, since all end in $y$, and so do the rows $yW$, since all begin with $y$. The end marker makes every rotation distinct, so both orders are strict, and the $k$th of one is the $k$th of the other. $\blacksquare$

The last letter of row $i$ precedes the position where row $i$ begins, so the lemma locates the rotation one step earlier. With $C(y)$ the number of letters in the block that sort before $y$, that row is

Row 0 begins with the end marker, so its last letter ends the text. Following LF from row 0, as in Table 8, collects s, u, o, c, s, u, o and c before reaching the marker, and read in reverse these spell couscous.

09.Move-to-Front

The transform's output has the letter counts of couscous, so a code for single letters gains nothing from the rearrangement alone. Move-to-front [10] turns its local repetition into small numbers.

Starting from the list in sorted order, Table 9 codes the output as 3, 0, 1, 2, 0, 4, 0, 4, 0, and every second letter of a run becomes 0. The empirical entropy of a sequence, the entropy of its own letter frequencies, falls from 2.2810 bits per letter to 2.0588. A nine-letter block shows little, but on a long text the output is dominated by zeros, which run-length and arithmetic coding then compress [9].

10.Lossy Coding

Every coder so far is lossless. A sample of sound or the brightness of a pixel is a real number, which takes infinitely many bits to describe exactly, so lossy coding accepts an error in exchange for a finite rate.

Quantization

Round the samples 0.37, $-1.12$, 2.05, 0.61 and $-0.28$ to the nearest multiple of $\Delta = 0.5$. The indices $k = \operatorname{round}(x/\Delta)$ are 1, $-2$, 4, 1 and $-1$, the reconstructions $k\Delta$ are 0.5, $-1$, 2, 0.5 and $-0.5$, and the mean squared error is 0.01886.

When the step is small against the scale on which the density of the samples changes, the error is close to uniform on $[-\Delta/2, \Delta/2)$, so

which is 0.020833 for $\Delta = 0.5$. With $2^b$ levels over a fixed range, each extra bit halves $\Delta$ and divides $D$ by 4, or $10\log_{10} 4 = 6.0206$ decibels. A full-scale signal spread evenly over the range has variance $2^{2b}\Delta^2/12$, so its signal-to-noise ratio is $6.0206\,b$ decibels, 48.16 dB at 8 bits and 96.33 dB at 16 bits.

Transform Coding

Neighboring samples are usually close. Rotate two pixels of brightness 100 and 104 by 45 degrees,

where the identity holds because the cross terms cancel. Here $s = 144.2498$ and $d = -2.8284$, so the sum carries a fraction 0.99962 of the energy 20816. Quantize $s$ with step 4 to 144 and $d$ with step 8 to 0. Both pixels come back as $144/\sqrt{2} = 101.8234$, with squared error 8.0624, the same in both domains, as the identity requires of any error under this linear rotation. Transform coding does this at scale. An orthonormal transform packs the energy of a block into a few coefficients, which are quantized finely, while the rest are quantized coarsely or dropped, as JPEG does on blocks of 8 by 8 pixels with the discrete cosine transform.

The Rate–Distortion Trade

For a Gaussian source of variance $\sigma^2$ under mean squared error,

which is 6.02 dB per bit. A counting sketch, not a proof, shows where this comes from. A block of $n$ samples lies near a sphere of radius $\sqrt{n\sigma^2}$, each reconstruction covers a ball of radius $\sqrt{nD}$, and volumes scale as the $n$th power of the radius, so covering takes about $(\sigma^2/D)^{n/2}$ reconstructions, which is $\frac{1}{2}\log_2(\sigma^2/D)$ bits per sample. Cover and Thomas [11] prove that no code does better and that long blocks achieve it.

A quantizer acting on one sample at a time falls short. With one bit, reconstructing $\pm y$ by sign gives $D = 1 - 2y\, E|X| + y^2$ for unit variance, smallest at $y = E|X| = \sqrt{2/\pi} = 0.7979$, where $D = 1 - 2/\pi = 0.36338$, or $-4.40$ dB against the bound's $-6.02$ dB. Table 10 continues to five bits, where the gap reaches 5.54 dB, because evenly spaced levels must either clip the tails or spread thinly over the middle.

Coding the indices of a fixed-step quantizer with an entropy coder does better, because the rate becomes the entropy $H(K)$ of the index. The differential entropy of a density $f$ is $h(X) = -\int f(x) \log_2 f(x)\, dx$. For a Gaussian, $-\log_2 f(x) = \frac12 \log_2(2\pi\sigma^2) + \frac{x^2}{2\sigma^2}\log_2 e$, and its expectation is $h(X) = \frac{1}{2}\log_2(2\pi e \sigma^2)$, 2.0471 bits at unit variance. With a small step $P(K = k) \approx f(k\Delta)\,\Delta$, so

and with $\log_2 \Delta = \frac12 \log_2(12 D)$ from Equation 13,

The gap settles at $\frac12\log_2(\pi e/6) = 0.2546$ bits, a distortion $\pi e/6 = 1.4233$ times the bound, or 1.5329 dB. Computed exactly, it is 1.88 dB at $\Delta = 1$, 1.62 dB at $\Delta = 0.5$ and 1.56 dB at $\Delta = 0.25$, where the rate is 4.0508 bits, as Figure 7 shows.

11.Compression Inside Memory Systems

Compression also runs between a processor's caches and its main memory. Data moves there in lines of fixed size that must be compressed in a few clock cycles, so the schemes are pattern matchers rather than entropy coders, exploiting lines of zeros, small integers or nearby pointers. A compressed line lets a cache hold more lines, or a memory channel carry more data.

A 32-byte line of eight 4-byte pointers, in hexadecimal 00403A10, 00403A18, 00403A20, 00403A28, 00403A40, 00403A48, 00403A60 and 00403A70, varies only in its last byte. With the first word as a base, the deltas are 0, 8, 16, 24, 48, 56, 80 and 96, each of which fits in a signed byte, so the line takes 12 bytes, a compression ratio of 2.67, as Figure 8 draws. This is base-delta-immediate compression, proposed by Pekhimenko and colleagues [12].

The immediate option handles mixed lines such as 0, 00403A10, 3, 00403A28, 1, 00403A18, C, 00403A40, where no 1-byte or 2-byte delta reaches from the pointers down to the small values. With zero as a second base, the deltas are 0, 0, 3, 24, 1, 8, 12 and 48 under the mask 01010101, where 1 marks the stored base, and the line takes $4 + 8 + 1 = 13$ bytes, a ratio of 2.46. Frequent pattern compression, from Alameldeen and Wood [13], works one word at a time instead, giving each word a short prefix that names a pattern such as all zeros, a small sign-extended value or one repeated byte.

Compression and error correction meet in these lines. Flip bit 4 of the stored base and it becomes 00403A00, so all eight words come back 16 too low. One wrong bit among the 96 stored bits corrupts all 256 bits of the line, where in the uncompressed line it would have damaged one word. The COP design of Palframan, Kim and Lipasti [14] turns this around, storing the check bits of an error-correcting code in the space a compressed line frees.

12.Looking Ahead

The arithmetic code of aabaaa shows the same fragility at the scale of a message. Flipping the first bit of the tag 010110 gives 110110, which decodes to bbaaaa, and flipping the third gives 011110, which decodes to aacaba. Every string of six bits lies in the interval of some message, so neither error is detected. A good compressor removes exactly the redundancy that would have revealed an error.

Protecting compressed data means adding redundancy back, in a form a decoder can use. The source with $p = 0.1$ compresses to $h(0.1) = 0.4690$ bits per letter. The next chapter, Capacity and Shannon's Theorem, shows that a binary symmetric channel, which flips each bit independently with probability 0.1, carries up to $1 - h(0.1) = 0.5310$ bits per use with an error probability as small as desired. Since $0.4690 < 0.5310$, the source can cross that channel at one use per letter with vanishing error, and for lossy coding the condition becomes $R(D) < C$, where $C$ is the capacity. MacKay [15] treats arithmetic and dictionary coding at length, Cover and Thomas [11] give the theory of universal coding and of rate and distortion, and Lin and Costello [16] take up the channel codes of the coming Parts.

13.Worked Examples

14.Exercises

References

1. [1]Witten, Ian H. and Neal, Radford M. and Cleary, John G. (1987). “Arithmetic Coding for Data Compression.” Communications of the ACM, 30(6), pp. 520–540. doi:10.1145/214762.214771
2. [2]Rissanen, Jorma J. (1976). “Generalized Kraft Inequality and Arithmetic Coding.” IBM Journal of Research and Development, 20(3), pp. 198–203. doi:10.1147/rd.203.0198
3. [3]Duda, Jarek (2013). “Asymmetric Numeral Systems: Entropy Coding Combining Speed of Huffman Coding with Compression Rate of Arithmetic Coding.” arXiv:1311.2540. https://arxiv.org/abs/1311.2540
4. [4]Collet, Yann and Kucherawy, Murray S. (2021). “Zstandard Compression and the application/zstd Media Type.” RFC 8878. https://www.rfc-editor.org/rfc/rfc8878
5. [5]Ziv, Jacob and Lempel, Abraham (1977). “A Universal Algorithm for Sequential Data Compression.” IEEE Transactions on Information Theory, 23(3), pp. 337–343. doi:10.1109/TIT.1977.1055714
6. [6]Deutsch, L. Peter (1996). “DEFLATE Compressed Data Format Specification Version 1.3.” RFC 1951. https://www.rfc-editor.org/rfc/rfc1951
7. [7]Ziv, Jacob and Lempel, Abraham (1978). “Compression of Individual Sequences via Variable-Rate Coding.” IEEE Transactions on Information Theory, 24(5), pp. 530–536. doi:10.1109/TIT.1978.1055934
8. [8]Welch, Terry A. (1984). “A Technique for High-Performance Data Compression.” Computer, 17(6), pp. 8–19. doi:10.1109/MC.1984.1659158
9. [9]Burrows, Michael and Wheeler, David J. (1994). “A Block-Sorting Lossless Data Compression Algorithm.” SRC Research Report 124, Digital Systems Research Center. https://web.archive.org/web/20230929095529/https://www.hpl.hp.com/techreports/Compaq-DEC/SRC-RR-124.html
10. [10]Bentley, Jon Louis and Sleator, Daniel D. and Tarjan, Robert E. and Wei, Victor K. (1986). “A Locally Adaptive Data Compression Scheme.” Communications of the ACM, 29(4), pp. 320–330. doi:10.1145/5684.5688
11. [11]Cover, Thomas M. and Thomas, Joy A. (2006). “Elements of Information Theory.” 2nd edition. Wiley-Interscience. doi:10.1002/047174882X
12. [12]Pekhimenko, Gennady and Seshadri, Vivek and Mutlu, Onur and Gibbons, Phillip B. and Kozuch, Michael A. and Mowry, Todd C. (2012). “Base-Delta-Immediate Compression: Practical Data Compression for On-Chip Caches.” In Proceedings of the 21st International Conference on Parallel Architectures and Compilation Techniques (PACT '12), pp. 377–388. doi:10.1145/2370816.2370870
13. [13]Alameldeen, Alaa R. and Wood, David A. (2004). “Adaptive Cache Compression for High-Performance Processors.” In Proceedings of the 31st Annual International Symposium on Computer Architecture (ISCA '04), pp. 212–223. doi:10.1109/ISCA.2004.1310776
14. [14]Palframan, David J. and Kim, Nam Sung and Lipasti, Mikko H. (2015). “COP: To Compress and Protect Main Memory.” In Proceedings of the 42nd Annual International Symposium on Computer Architecture (ISCA '15), pp. 682–693. doi:10.1145/2749469.2750377
15. [15]MacKay, David J. C. (2003). “Information Theory, Inference, and Learning Algorithms.” Cambridge University Press. The author's site offers the whole book free to read on screen. https://www.inference.org.uk/itila/book.html
16. [16]Lin, Shu and Costello, Jr., Daniel J. (2004). “Error Control Coding: Fundamentals and Applications.” 2nd edition. Pearson Prentice Hall.