Source Coding and Prefix Codes

The previous chapter, Information and Entropy, ended with a source that emits four letters with probabilities $1/2$, $1/4$, $1/8$ and $1/8$, whose entropy is $H(X) = 1.75$ bits, and with the code 0, 10, 110 and 111, whose codewords average exactly 1.75 bits. Its first section, Measuring Surprise, also promised that a long run of fair die rolls, with entropy $\log_2 6 = 2.5850$ bits per roll, can be described with close to 2.585 yes-or-no questions per roll on average. This chapter keeps that promise.

Source coding writes a source's letters as bits, as few per letter as possible on average, so that a receiver still recovers the letters exactly. The chapter asks when codewords can be split back into letters without separators, how short they can be, and how the best code is found, and then codes blocks of letters to close the last gap to the entropy.

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

01.Codes for a Source

Call the letters of the running source a, b, c and d, with probabilities $1/2$, $1/4$, $1/8$ and $1/8$. A code assigns each letter a codeword, a string of bits, and a message is encoded by writing its codewords one after another with nothing between them. The plainest code gives every letter two bits, 00, 01, 10 and 11, and costs 2 bits per letter whatever the probabilities are. Code A, from the end of the previous chapter, assigns a 0, b 10, c 110 and d 111, so the message cabad becomes 1100100111. Like Morse code, it gives the likeliest letter the shortest codeword. Morse code, though, separates its letters with pauses, and a binary code must make its boundaries recoverable from the bits alone.

For code A, $L = \tfrac12 \cdot 1 + \tfrac14 \cdot 2 + \tfrac18 \cdot 3 + \tfrac18 \cdot 3 = 1.75$ bits, equal to the entropy. The two-bit code spends 0.25 bits per letter more. In the previous chapter's section Relative Entropy and Gibbs' Inequality, $D(P \,\|\, Q)$ measured the extra cost of describing a source $P$ with a model $Q$, and for the uniform model $U$, which the two-bit code assumes, $D(P \,\|\, U) = 2 - H(X) = 0.25$ bits, the excess exactly. The section The Entropy Lower Bound explains why.

Code D assigns a 0, b 1, c 01 and d 10, and averages $\tfrac12 \cdot 1 + \tfrac14 \cdot 1 + \tfrac18 \cdot 2 + \tfrac18 \cdot 2 = 1.25$ bits, half a bit below the entropy. The table below lists it with the other codes of the chapter and a Kraft sum that the section The Kraft Inequality explains.

02.When a Code Can Be Decoded

Under code D the bits 0110 have four readings, abba, abd, cba and cd. Nothing in the bits says which was sent, so the half bit saved per letter buys nothing.

Code C hides its failure better. Its four codewords, a 0, b 01, c 100 and d 101, differ, and its lengths are those of code A, yet the bits 0101 split as a followed by d and as b followed by b, as the figure below shows.

Code B assigns a 0, b 01, c 011 and d 111. It is uniquely decodable, but it makes the receiver wait. A 0 followed by six 1s decodes as add, with seven 1s as bdd and with eight as cdd, so the first letter cannot be named until the run of 1s ends. Code B's codewords are code A's written backward, so a stored message read from the right end decodes as code A would, without ambiguity, which proves code B uniquely decodable.

For an arbitrary code, a test that Sardinas and Patterson gave in 1953 settles the question in finitely many steps by following the leftover pieces that appear when one codeword begins another. In code C, the codeword 0 begins 01 and leaves the piece 1, which begins 100 and 101 and leaves the pieces 00 and 01. The piece 01 is itself a codeword, and that coincidence is the ambiguity in the figure. If the pieces run out or repeat without matching a codeword, the code is uniquely decodable. The test is rarely needed, because a simpler kind of code turns out to lose nothing.

03.Prefix Codes and Code Trees

Code A never makes the receiver wait. Reading 1100100111 from the left, the receiver sees 1 and then 11, neither a codeword, then 110, which is c. It emits c, starts over, and recovers cabad with no look-ahead, because no codeword of code A begins another.

The two-bit code and code A are prefix codes. Codes B, C and D are not, since in each of them 0 begins 01. Prefix codes are also called instantaneous codes.

Proof. In a string of codewords of a prefix code, the first codeword matches the first bits of the string. If two different codewords matched, the shorter would be a prefix of the longer, which the prefix condition forbids. So the first letter is fixed by the string. Removing its codeword leaves a shorter string of codewords, and repeating the argument fixes every letter in turn. $\blacksquare$

A prefix code has a picture. From a root draw two branches, labeled 0 and 1, then two more from the end of each, and so on, so that every bit string is a path from the root. Each codeword marks the node where its path ends. The prefix condition says that no codeword lies on the path to another, so every codeword is a leaf, a node with nothing below it, and the depth of each leaf, its number of branches from the root, is the length of its codeword.

Decoding is a walk down the tree, one branch per bit, emitting a letter at each leaf and returning to the root. Code A's tree also has two branches below every node that is not a leaf. Such a tree is called full.

04.The Kraft Inequality

A codeword of length $l$ claims a fraction $2^{-l}$ of the tree, since every path that starts with its bits ends at it. Kraft turned that observation into an exact test for when a set of lengths can belong to a prefix code [1].

Proof that a prefix code satisfies the inequality. Let $l_{\max}$ be the largest length and extend the tree to depth $l_{\max}$, where it has $2^{l_{\max}}$ nodes. A codeword at depth $l_i$ sits above $2^{l_{\max} - l_i}$ of them, the ones whose paths begin with it. No deepest node lies below two codewords, or one codeword would lie on the path to the other, so the codewords claim disjoint sets of deepest nodes and $\sum_i 2^{l_{\max} - l_i} \le 2^{l_{\max}}$. Dividing by $2^{l_{\max}}$ gives the inequality. $\blacksquare$

The lengths 2, 2, 3, 3, 3, 4 and 4, for instance, claim 4, 4, 2, 2, 2, 1 and 1 of the 16 nodes at depth 4, which is all of them, so their Kraft sum is 1.

The converse reads each codeword as a number. A bit string $w$ of length $l$ names the numbers between 0 and 1 whose binary expansion begins with $w$, an interval of width $2^{-l}$, so the string 10 names the numbers from $0.10_2 = 1/2$ up to $0.11_2 = 3/4$. One string is a prefix of another exactly when its interval contains the other's, so codewords whose intervals do not overlap form a prefix code.

Proof that lengths satisfying the inequality have a prefix code. Sort the lengths so that $l_1 \le l_2 \le \cdots \le l_M$, and let $F_i = \sum_{j < i} 2^{-l_j}$, with $F_1 = 0$. Each term of $F_i$ is a whole multiple of $2^{-l_i}$, because $l_j \le l_i$, so the binary expansion of $F_i$ stops within $l_i$ places. Take codeword $i$ to be $F_i$ written with exactly $l_i$ binary places. Its interval runs from $F_i$ to $F_i + 2^{-l_i} = F_{i+1}$, so the intervals sit side by side without overlapping, and the last one ends at $K \le 1$. $\blacksquare$

The top row of the figure below runs the construction on the lengths 2, 2, 3, 3, 3, 4 and 4, whose starting points 0, 4, 8, 10, 12, 14 and 15 sixteenths give the codewords 00, 01, 100, 101, 110, 1110 and 1111. The bottom row uses the lengths 1, 3, 3 and 4, whose Kraft sum is $1/2 + 1/8 + 1/8 + 1/16 = 13/16$, and gives 0, 100, 101 and 1100, leaving $3/16$ of the line unused.

Unused space means a codeword can be shortened. Here 1100 can become 11, giving the prefix code 0, 100, 101 and 11 with a Kraft sum of exactly 1. In general a prefix code with $K < 1$ has a node with only one branch below it, and removing that node shortens every codeword beneath it by one bit. A code worth using has a full tree and $K = 1$.

05.McMillan's Inequality

Code B is uniquely decodable without being a prefix code, so dropping the prefix condition might seem to buy shorter codewords. McMillan proved that it cannot [2].

Raising the Kraft sum $K$ to the power $n$ and multiplying out gives one term for every sequence of $n$ letters, and that term is $2^{-m}$, where $m$ is the length of the sequence's encoding. Collecting the terms by $m$ gives

where $A_m$ counts the $n$-letter sequences whose encoding is $m$ bits long.

Proof. Different sequences give different bit strings, and there are only $2^m$ strings of length $m$, so $A_m \le 2^m$ and each term of the sum in Equation 3 is at most 1. The sum has $n\, l_{\max} - n + 1$ terms, so $K^n \le n(l_{\max} - 1) + 1$ for every $n$. If $K$ exceeded 1, the left side would grow exponentially in $n$ while the right side grows only in proportion to $n$, and for large enough $n$ the inequality would fail. Hence $K \le 1$. $\blacksquare$

For code A and $n = 2$, the 16 pairs of letters encode to lengths from 2 to 6, with $A_m$ equal to 1, 2, 5, 4 and 4, so $K^2 = 1/4 + 2/8 + 5/16 + 4/32 + 4/64 = 1$. Lengths 1, 1 and 2 have $K = 1.25$ and $l_{\max} = 2$, so unique decodability would need $1.25^n \le n + 1$ for every $n$. That holds at $n = 11$, where $1.25^{11} = 11.64$, and fails at $n = 12$, where $1.25^{12} = 14.55$ exceeds 13, so two different messages of 12 letters must share an encoding, whatever bits the codewords use.

06.The Entropy Lower Bound

Entropy turns the limit on the Kraft sum into a limit in bits per letter, which is the first half of Shannon's source coding theorem [3].

The proof reads a code's lengths as a model of the source. With $K = \sum_x 2^{-l(x)}$, the values $Q(x) = 2^{-l(x)}/K$ are positive and add to 1, so they form a distribution, and $l(x) = \log_2 (1/Q(x)) + \log_2 (1/K)$. Averaging over the source and subtracting $H(X) = \sum_x p(x) \log_2 (1/p(x))$ gives

Proof. Gibbs' inequality gives $D(P \,\|\, Q) \ge 0$, with equality only when $Q = P$. McMillan's inequality gives $K \le 1$, so $\log_2(1/K) \ge 0$, with equality only when $K = 1$. Both terms of Equation 4 are therefore non-negative, which proves $L(C) \ge H(X)$, and both vanish exactly when $K = 1$ and $p(x) = 2^{-l(x)}$ for every $x$. $\blacksquare$

The two terms are the two ways a code falls short, unused tree and a wrong model. The two-bit code has $K = 1$, so its whole excess of 0.25 bits is $D(P \,\|\, U)$, while code A has $K = 1$ and $Q = P$, so $L = H(X)$. Code D's 1.25 bits breaks no rule, because code D is not uniquely decodable and its Kraft sum of 1.5 makes $\log_2(1/K)$ negative.

Equality needs every probability to be a power of $1/2$, and such a source is called dyadic. For any other source every uniquely decodable code has $L(C) > H(X)$. The excess $L(C) - H(X)$ is the code's redundancy, and the ratio $H(X)/L(C)$ is its efficiency.

07.Shannon's Code and Fano's Splitting

A letter of probability $p$ would ideally get $\log_2(1/p)$ bits, its surprise in the language of the previous chapter. Codeword lengths are whole numbers, so rounding each surprise up gives Shannon's lengths,

where $\lceil t \rceil$ is the smallest whole number at least as large as $t$.

Proof. Rounding up gives $2^{-l(x)} \le p(x)$, so $K \le 1$ and Kraft's construction supplies a prefix code. Rounding up adds less than 1, so $l(x) < \log_2(1/p(x)) + 1$, and averaging gives $L < H(X) + 1$. The entropy bound gives $L \ge H(X)$. $\blacksquare$

The chapter's second running example has six letters, a to f, with probabilities 0.45, 0.20, 0.10, 0.10, 0.10 and 0.05 and entropy $H(X) = 2.1955$ bits. The surprises, 1.152 bits for a, 2.322 for b, 3.322 for each of c, d and e, and 4.322 for f, round up to 2, 3, 4, 4, 4 and 5, which average 2.95 bits, inside the promised range from 2.1955 to 3.1955.

Shannon's paper built the codewords from cumulative probabilities. With the letters sorted from likeliest to least likely, letter $i$ starts at $F_i$, the total probability of the letters before it, here 0, 0.45, 0.65, 0.75, 0.85 and 0.95, and its codeword is the first $l(x)$ binary places of $F_i$. So a gets 00, b gets 011, since $0.45 = 0.01110011\ldots_2$ in binary, and the others get 1010, 1100, 1101 and 11110. The table below sets the result beside two codes built later in the chapter.

Shannon's code is wasteful. Its Kraft sum is $1/4 + 1/8 + 3/16 + 1/32 = 19/32 = 0.59375$, so $13/32$ of the tree, about 41 percent, goes unused. Of the excess $L - H(X) = 0.7545$ bits, nearly all, 0.7521 bits, is the unused tree $\log_2(1/K)$, while the model mismatch $D(P \,\|\, Q)$ costs about 0.0025 bits. Rounding up wastes most of a bit, worst for a, whose ideal 1.152 bits becomes 2.

Fano's construction works from the top of the tree down. Sort the letters by probability and split the list into two groups whose total probabilities are as nearly equal as possible, the first group's codewords beginning with 0 and the second's with 1, then split each group the same way until every group holds one letter. On the six-letter source the first split puts a, with 0.45, against the other five, with 0.55, a gap of 0.10, where splitting after b would leave 0.65 against 0.35. The five split as b and c, with 0.30, against d, e and f, with 0.25, and later d separates from e and f, which carry 0.15 between them. The codewords a 0, b 100, c 101, d 110, e 1110 and f 1111 average 2.25 bits, 0.70 bits better than Shannon's code.

Shannon's 1948 paper describes the cumulative construction and credits Fano with a substantially similar method found independently, so the name Shannon–Fano code is attached to both, though they produce different codes. The previous chapter's Shannon–Fano code was Shannon's. From here on this book says Shannon's code and Fano's code.

Neither construction is optimal in general. Fano's code matches the best code on this source, but the worked example A Five-Letter Source Where Fano's Code Loses shows it falling short. The best code builds the tree the other way, from the leaves up.

08.Huffman's Algorithm

In 1952 Huffman published an algorithm that builds an optimal prefix code for any source [4]. Fano's method fixes the first bit of every codeword first, and Huffman's fixes the last bits first. The two least likely letters should be the deepest leaves, hanging from the same node, and joining them into one entry leaves a smaller problem of the same kind.

The figure below runs the algorithm on the six-letter source. First e and f merge into ef with 0.15, then c and d into cd with 0.20, which ties with b. The figure places the new entry above b, so b and ef merge next into bef with 0.35, then cd and bef into bcdef with 0.55, and a joins it at the root.

From the root, a gets 0. Inside bcdef, cd takes 10 and bef takes 11, so c is 100, d is 101, b is 110, e is 1110 and f is 1111. The average is $0.45 \cdot 1 + 0.40 \cdot 3 + 0.15 \cdot 4 = 2.25$ bits, a redundancy of 0.0545 bits and an efficiency of 0.976.

The merged probabilities also add to 2.25, and not by accident. Each letter's probability enters the sum once for every merge above its leaf, and there are $l(x)$ such merges, so the sum counts each $p(x)$ exactly $l(x)$ times. On the four-letter source the merges are $1/4$, $1/2$ and $1$, which add to 1.75, and the algorithm returns code A itself.

The tie at 0.20 was a choice. If cd goes below b instead, cd and ef merge into 0.35, b joins that entry, and a joins at the root. That is tree A in the figure below, with a 0, b 10, and c, d, e and f as 1100, 1101, 1110 and 1111, which also averages $0.45 \cdot 1 + 0.20 \cdot 2 + 0.35 \cdot 4 = 2.25$ bits.

Both trees are optimal, as the next section proves, but the variance of the codeword length, $\sum_x p(x) \bigl(l(x) - L\bigr)^2$, is 1.7875 for tree A and 1.3875 for tree B. A link of fixed rate must buffer bursts of long codewords, so tree B, made by placing the merged entry above the tie, needs the smaller buffer.

The figure below sets the lengths of Shannon's code and tree B beside the ideal lengths $\log_2(1/p)$. Huffman's code gives a 1 bit, below its ideal of 1.152, and b 3 bits, above its ideal of 2.322, trading length between letters to keep the average low.

09.Why Huffman's Code Is Optimal

The proof rests on three facts about optimal prefix codes and one identity about merging. The source has $M \ge 2$ letters, all of positive probability, and an optimal code is a prefix code whose average length is the smallest among prefix codes. One exists, because only finitely many sets of lengths give an average below that of any fixed code.

Proof. Swapping the codewords of letters $i$ and $j$ keeps a prefix code and changes its average length by

If $p_i > p_j$ and $l_i > l_j$, the change is negative, so the swap would shorten a code that was supposed to be optimal. Hence $l_i \le l_j$. $\blacksquare$

Proof. If some node has only one branch below it, delete that branch and move everything below it up one level. Every codeword in the moved part loses one bit, the code stays a prefix code, and the average length falls, which contradicts optimality. $\blacksquare$

Proof. In an optimal code, a leaf of greatest depth has a parent with a second branch, by the previous lemma, and that branch ends at a leaf, since nothing lies deeper. So the deepest level holds a pair of sibling leaves. Swap $x$ into one of these positions and $y$ into the other, leaving either in place if it is there already. In each swap, the letter $i$ moved out of the deep position and the least likely letter $j$ moved in have $p_i \ge p_j$ and $l_i \ge l_j$, so by Equation 6 the average length does not increase. The new code is still optimal, with $x$ and $y$ as deepest siblings. $\blacksquare$

The last ingredient is the merging identity. If $x$ and $y$ are siblings in a code $C$, replacing them by a single letter $z$ with $p(z) = p(x) + p(y)$, placed at their parent node, gives a code $C'$ for a source with one letter fewer. The codewords of $x$ and $y$ are one bit longer than that of $z$, so

Proof. The proof is by induction on $M$. With $M = 2$ Huffman's code gives each letter one bit, the least any codeword can have. Suppose the theorem holds for every source of $M - 1$ letters, and let $x$ and $y$ be the two letters of smallest probability that Huffman's algorithm merges first. The algorithm then runs on the merged source of $M - 1$ letters and produces a code $C'_{\mathrm{Huff}}$, optimal there by the induction hypothesis. Splitting the merged leaf back into $x$ and $y$ gives the Huffman code $C_{\mathrm{Huff}}$, with $L(C_{\mathrm{Huff}}) = L(C'_{\mathrm{Huff}}) + p(x) + p(y)$ by Equation 7. By the sibling lemma some optimal code $C$ has $x$ and $y$ as deepest siblings, and merging them gives a code $C'$ for the same merged source, so

$$L(C) = L(C') + p(x) + p(y) \ge L(C'_{\mathrm{Huff}}) + p(x) + p(y) = L(C_{\mathrm{Huff}}).$$

The Huffman code is therefore optimal among prefix codes. A uniquely decodable code meets McMillan's inequality, so Kraft's construction gives a prefix code with the same lengths and the same average, which cannot beat the Huffman code either. $\blacksquare$

Gallager later showed that a prefix code is a Huffman code exactly when the nodes of its tree, root aside, can be listed from largest probability to smallest with each node next to its sibling [5]. Since Huffman's code is at least as short as Shannon's, it also satisfies $H(X) \le L < H(X) + 1$. That bound cannot be improved in general for single letters, as the binary sources of the next section show.

10.Shannon's Source Coding Theorem

A binary source that emits 1 with probability $p = 0.1$ and 0 otherwise has entropy $h(0.1) = 0.4690$ bits, where $h(p)$ is the binary entropy function of the previous chapter. Any code for single letters spends at least 1 bit per letter, more than twice the entropy. The fix is to code several letters at once.

The pairs 00, 01, 10 and 11 have probabilities 0.81, 0.09, 0.09 and 0.01, and Huffman's algorithm merges 0.01 with 0.09 into 0.10, then 0.09 with 0.10 into 0.19, then 0.19 with 0.81. So $L_2 = 0.10 + 0.19 + 1 = 1.29$ bits per pair, or 0.645 bits per letter. Triples cost $L_3 = 1.598$ bits, or 0.5327 per letter, and blocks of four 0.4926 per letter.

The previous chapter's section Joint and Conditional Entropy showed that $n$ independent letters have joint entropy $n H(X)$. The bounds of the last two sections, applied to the source of blocks, then give the average length $L_n$ of an optimal code for blocks of $n$ letters,

Proof. Dividing Equation 8 by $n$ gives $L_n/n \ge H(X)$ for every uniquely decodable code, and $L_n/n < H(X) + 1/n$ for the Huffman code on blocks. Any block length $n > 1/\varepsilon$ makes $1/n < \varepsilon$. $\blacksquare$

The table and the figure below follow the source with $p = 0.1$ from $n = 1$ to $n = 8$. Every rate lies between the entropy and $h(0.1) + 1/n$, but blocks of seven cost 0.4743 bits per letter, more than the 0.4702 of blocks of six, because the theorem bounds the rate without promising that each longer block helps.

The next figure repeats the comparison for every $p$ from 0.01 to 0.5. The gap between single letters and the entropy is widest when $p$ is small, where a whole bit per letter is a large overpayment.

Now the promise from Measuring Surprise can be kept. Huffman's code for one roll of a fair die gives two faces 2 bits and four faces 3 bits, 2.6667 bits per roll against an entropy of 2.5850. For pairs of rolls, 36 equally likely blocks, it gives 28 codewords of 5 bits and 8 of 6 bits, or 2.6111 bits per roll, and for triples it gives 40 codewords of 7 bits and 176 of 8, or 2.6049, as the table below collects. The theorem brings the rate within any margin of 2.585, and the questions of Measuring Surprise are these bits, each one answering whether the path to a block's leaf turns left or right.

The counts follow a rule. For $N$ equally likely letters, let $k = \lfloor \log_2 N \rfloor$ be the largest whole number with $2^k \le N$. Huffman's tree then has $2^{k+1} - N$ leaves at depth $k$ and $2(N - 2^k)$ at depth $k + 1$, as balanced as a tree with $N$ leaves can be. For $N = 216$ this gives $k = 7$ and the counts 40 and 176.

The theorem hides a cost. A code for blocks of $n$ letters needs a codeword for each of the $M^n$ blocks of an $M$-letter alphabet, 256 for the binary source at $n = 8$ and 216 for the die at $n = 3$, so closing the last fraction of a bit makes the table grow exponentially. Arithmetic coding, in the next chapter, reaches the same rates without building the table.

11.Compression and Its Fragility

A source code removes redundancy, the part of the data that a receiver could have predicted. A channel code, the subject of most of this book, adds redundancy back in a form chosen so that a decoder can repair a channel's errors. The redundancy left in raw data has whatever structure the source happened to have, which rarely matches the errors of a channel. Whether compressing first and protecting the result afterward loses anything is the subject of the separation theorem, which the chapter after next, Capacity and Shannon's Theorem, takes up.

Compressed data is also fragile. The word fadedcab, encoded with tree B, is the 22 bits 1111010111101011000110. If the channel flips the third bit, the decoder reads 110 as b, 101 as d, 0 as a, 1111 as f and 0 as a, then d, c, a and b, and delivers nine letters, bdafadcab, instead of eight. The first five are wrong, and the last four, dcab, are right but one place late, because the codeword boundaries line up again from the thirteenth bit on, as the figure below shows.

A two-bit code would have lost a single letter to the same flip, because its codeword boundaries never move. A variable-length code saves bits because its boundaries depend on the data, and the same dependence lets one error move them. Huffman decoders often fall back into step, as this one did, but nothing in the construction guarantees it. Practical compressed formats bound the damage with restart points, places in the stream where decoding can begin afresh, and protect the compressed bits with a channel code.

12.Looking Ahead

Huffman's code is optimal among codes that give each letter its own whole number of bits, and that restriction hurts in three ways. The first is skew. A binary source with $p = 0.01$ has entropy $h(0.01) = 0.0808$ bits, yet single letters cost 1 bit, 12.4 times the entropy, and pairs and triples still cost 0.5150 and 0.3533 bits per letter while the table of blocks grows. The second is the model. Huffman's algorithm needs the probabilities before it starts, the worked example The Cost of a Wrong Model shows what a mistaken guess costs, and real data does not arrive with its probabilities attached. The third is memory. Text, images and program code are not independent letters, and a code for single letters cannot use the way one letter makes the next more predictable.

The next chapter, Compression in Practice, answers each weakness. Arithmetic coding and range coding spend fractions of a bit where a letter deserves them, reaching the entropy without a table of blocks, and asymmetric numeral systems reach the same rates by a different route. The dictionary methods LZ77, LZ78 and LZW learn their model from the data as they read it. Run-length coding and the Burrows–Wheeler transform with move-to-front turn the memory in a source into something a simple code can exploit. That chapter also surveys lossy coding, which gives up exactness in exchange for rate, and the compression used inside memory systems. MacKay [6] and Cover and Thomas [7] treat the source coding of this chapter in depth, and Lin and Costello [8] place it beside the channel codes of the later Parts.

13.Worked Examples

14.Exercises

References

1. [1]Kraft, Leon Gordon (1949). “A Device for Quantizing, Grouping, and Coding Amplitude-Modulated Pulses.” Master's thesis, Massachusetts Institute of Technology. https://dspace.mit.edu/handle/1721.1/12390
2. [2]McMillan, Brockway (1956). “Two Inequalities Implied by Unique Decipherability.” IRE Transactions on Information Theory, 2(4), pp. 115–116. doi:10.1109/TIT.1956.1056818
3. [3]Shannon, Claude E. (1948). “A Mathematical Theory of Communication.” Bell System Technical Journal, 27(3), pp. 379–423. The paper concludes in the October issue, volume 27, number 4, pages 623 to 656. doi:10.1002/j.1538-7305.1948.tb01338.x
4. [4]Huffman, David A. (1952). “A Method for the Construction of Minimum-Redundancy Codes.” Proceedings of the IRE, 40(9), pp. 1098–1101. doi:10.1109/JRPROC.1952.273898
5. [5]Gallager, Robert G. (1978). “Variations on a Theme by Huffman.” IEEE Transactions on Information Theory, 24(6), pp. 668–674. doi:10.1109/TIT.1978.1055959
6. [6]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
7. [7]Cover, Thomas M. and Thomas, Joy A. (2006). “Elements of Information Theory.” 2nd edition. Wiley-Interscience. doi:10.1002/047174882X
8. [8]Lin, Shu and Costello, Jr., Daniel J. (2004). “Error Control Coding: Fundamentals and Applications.” 2nd edition. Pearson Prentice Hall.