Coding for Discrete Sources

Chapter 2 Coding for Discrete Sources 2.1 Introduction A general block diagram of a point-to-point digital communication system was given in Figure 1.1. The source encoder converts the sequence of symbols from the source to a sequence of binary digits, preferably using as few binary digits per symbol as possible. The source decoder performs the inverse operation. Initially, in the spirit of source/channel separation, we ignore the possibility that errors are made in the channel decoder and assume that the source decoder operates on the source encoder output. We first distinguish between three important classes of sources: • Discrete sources The output of a discrete source is a sequence of symbols from a known discrete alphabet X . This alphabet could be the alphanumeric characters, the characters on a computer keyboard, English letters, Chinese characters, the symbols in sheet music (arranged in some systematic fashion), binary digits, etc. The discrete alphabets in this chapter are assumed to contain a finite set of symbols.1 It is often convenient to view the sequence of symbols as occurring at some fixed rate in time, but there is no need to bring time into the picture (for example, the source sequence might reside in a computer file and the encoding can be done off-line). This chapter focuses on source coding and decoding for discrete sources.” Supplementary references for source coding are Chapter 3 of [7] and Chapter 5 of [4]. A more elementary partial treatment is in Sections 4.1-4.3 of [22]. • Analog waveform sources The output of an analog source, in the simplest case, is an analog real waveform, repre­ senting, for example, a speech waveform. The word analog is used to emphasize that the waveform can be arbitrary and is not restricted to taking on amplitudes from some discrete set of values. 1 A set is usually defined to be discrete if it includes either a finite or countably infinite number of members. The countably infinite case does not extend the basic theory of source coding in any important way, but it is occasionally useful in looking at limiting cases, which will be discussed as they arise. 15 Cite as: Robert Gallager, course materials for 6.450 Principles of Digital Communications I, Fall 2006. MIT OpenCourseWare (http://ocw.mit.edu/), Massachusetts Institute of Technology. Downloaded on [DD Month YYYY]. 16 CHAPTER 2. CODING FOR DISCRETE SOURCES It is also useful to consider analog waveform sources with outputs that are complex functions of time; both real and complex waveform sources are discussed later. More generally, the output of an analog source might be an image (represented as an inten­ sity function of horizontal/vertical location) or video (represented as an intensity function of horizontal/vertical location and time). For simplicity, we restrict our attention to analog waveforms, mapping a single real variable, time, into a real or complex-valued intensity. • Discrete-time sources with analog values (analog sequence sources) These sources are halfway between discrete and analog sources. The source output is a sequence of real numbers (or perhaps complex numbers). Encoding such a source is of interest in its own right, but is of interest primarily as a subproblem in encoding analog sources. That is, analog waveform sources are almost invariably encoded by first either sampling the analog waveform or representing it by the coefficients in a series expansion. Either way, the result is a sequence of numbers, which is then encoded. There are many differences between discrete sources and the latter two types of analog sources. The most important is that a discrete source can be, and almost always is, encoded in such a way that the source output can be uniquely retrieved from the encoded string of binary digits. Such codes are called uniquely decodable 2 . On the other hand, for analog sources, there is usually no way to map the source values to a bit sequence such that the source values are uniquely decodable. For example, an infinite number of binary digits is required for the exact specification of an arbitrary real number between 0 and 1. Thus, some sort of quantization is necessary for these analog values, and this introduces distortion. Source encoding for analog sources thus involves a trade-off between the bit rate and the amount of distortion. Analog sequence sources are almost invariably encoded by first quantizing each element of the sequence (or more generally each successive n-tuple of sequence elements) into one of a finite set of symbols. This symbol sequence is a discrete sequence which can then be encoded into a binary sequence. Figure 2.1 summarizes this layered view of analog and discrete source coding. As illustrated, discrete source coding is both an important subject in its own right for encoding text-like sources, but is also the inner layer in the encoding of analog sequences and waveforms. The remainder of this chapter discusses source coding for discrete sources. The following chapter treats source coding for analog sequences and the fourth chapter treats waveform sources. 2.2 Fixed-length codes for discrete sources The simplest approach to encoding a discrete source into binary digits is to create a code C that maps each symbol x of the alphabet X into a distinct codeword C(x), where C(x) is a block of binary digits. Each such block is restricted to have the same block length L, which is why the code is called a fixed-length code. 2 Uniquely-decodable codes are sometimes called noiseless codes in elementary treatments. Uniquely decodable captures both the intuition and the precise meaning far better than noiseless. Unique decodability is defined shortly. Cite as: Robert Gallager, course materials for 6.450 Principles of Digital Communications I, Fall 2006. MIT OpenCourseWare (http://ocw.mit.edu/), Massachusetts Institute of Technology. Downloaded on [DD Month YYYY]. 2.2. FIXED-LENGTH CODES FOR DISCRETE SOURCES input � sampler waveform 17 � discrete � quantizer encoder � analog sequence output waveform � analog filter � table lookup symbol sequence � discrete decoder binary interface binary channel � Figure 2.1: Discrete sources require only the inner layer above, whereas the inner two layers are used for analog sequences and all three layers are used for waveforms sources. For example, if the alphabet X consists of the 7 symbols {a, b, c, d, e, f, g}, then the following fixed-length code of block length L = 3 could be used. C(a) = C(b) = C(c) = C(d) = C(e) = C(f ) = C(g) = 000 001 010 011 100 101 110. The source output, x1 , x2 , . . . , would then be encoded into the encoded output C(x1 )C(x2 ) . . . and thus the encoded output contains L bits per source symbol. For the above example the source sequence bad . . . would be encoded into 001000011 . . . . Note that the output bits are simply run together (or, more technically, concatenated). There are 2L different combinations of values for a block of L bits. Thus, if the number of symbols in the source alphabet, M = |X |, satisfies M ≤ 2L , then a different binary L-tuple may be assigned to each symbol. Assuming that the decoder knows where the beginning of the encoded sequence is, the decoder can segment the sequence into L bit blocks and then decode each block into the corresponding source symbol. In summary, if the source alphabet has size M , then this coding method requires L = log2 M  bits to encode each source symbol, where w denotes the smallest integer greater than or equal to the real number w. Thus log2 M ≤ L < log2 M + 1. The lower bound, log2 M , can be achieved with equality if and only if M is a power of 2. A technique to be used repeatedly is that of first segmenting the sequence of source symbols into successive blocks of n source symbols at a time. Given an alphabet X of M symbols, there are M n possible n-tuples. These M n n-tuples are regarded as the elements of a super-alphabet. Each n-tuple can be encoded rather than encoding the original symbols. Using fixed-length source coding on these n-tuples, each source n-tuple can be encoded into L = log2 M n  bits. Cite as: Robert Gallager, course materials for 6.450 Principles of Digital Communications I, Fall 2006. MIT OpenCourseWare (http://ocw.mit.edu/), Massachusetts Institute of Technology. Downloaded on [DD Month YYYY]. 18 CHAPTER 2. CODING FOR DISCRETE SOURCES The rate L = L/n of encoded bits per original source symbol is then bounded by log2 M n  n log2 M n  L= n L= ≥ < n log2 M = log2 M ; n n(log2 M ) + 1 1 = log2 M + . n n Thus log2 M ≤ L < log2 M + n1 , and by letting n become sufficiently large, the average number of coded bits per source symbol can be made arbitrarily close to log2 M , regardless of whether M is a power of 2. Some remarks: • This simple scheme to make L arbitrarily close to log2 M is of greater theoretical interest than practical interest. As shown later, log2 M is the minimum possible binary rate for uniquely-decodable source coding if the source symbols are independent and equiprobable. Thus this scheme asymptotically approaches this minimum. • This result begins to hint at why measures of information are logarithmic in the alphabet size.3 The logarithm is usually taken to the base 2 in discussions of binary codes. Henceforth log n means “log2 n.” • This method is nonprobabilistic; it takes no account of whether some symbols occur more frequently than others, and it works robustly regardless of the symbol frequencies. But if it is known that some symbols occur more frequently than others, then the rate L of coded bits per source symbol can be reduced by assigning shorter bit sequences to more common symbols in a variable-length source code. This will be our next topic. 2.3 Variable-length codes for discrete sources The motivation for using variable-length encoding on discrete sources is the intuition that data compression can be achieved by mapping more probable symbols into shorter bit sequences, and less likely symbols into longer bit sequences. This intuition was used in the Morse code of old-time telegraphy in which letters were mapped into strings of dots and dashes, using shorter strings for common letters and longer strings for less common letters. A variable-length code C maps each source symbol aj in a source alphabet X = {a1 , . . . , aM } to a binary string C(aj ), called a codeword. The number of bits in C(aj ) is called the length l(aj ) of C(aj ). For example, a variable-length code for the alphabet X = {a, b, c} and its lengths might be given by C(a) = 0 C(b) = 10 C(c) = 11 l(a) = 1 l(b) = 2 l(c) = 2 Successive codewords of a variable-length code are assumed to be transmitted as a continuing sequence of bits, with no demarcations of codeword boundaries (i.e., no commas or spaces). The 3 The notion that information can be viewed as a logarithm of a number of possibilities was first suggested by Hartley [11] in 1927. Cite as: Robert Gallager, course materials for 6.450 Principles of Digital Communications I, Fall 2006. MIT OpenCourseWare (http://ocw.mit.edu/), Massachusetts Institute of Technology. Downloaded on [DD Month YYYY]. 2.3. VARIABLE-LENGTH CODES FOR DISCRETE SOURCES 19 source decoder, given an original starting point, must determine where the codeword boundaries are; this is called parsing. A potential system issue with variable-length coding is the requirement for buffering. If source symbols arrive at a fixed rate and the encoded bit sequence must be transmitted at a fixed bit rate, then a buffer must be provided between input and output. This requires some sort of recognizable ‘fill’ to be transmitted when the buffer is empty and the possibility of lost data when the buffer is full. There are many similar system issues, including occasional errors on the channel, initial synchronization, terminal synchronization, etc. Many of these issues are discussed later, but they are more easily understood after the more fundamental issues are discussed. 2.3.1 Unique decodability The major property that is usually required from any variable-length code is that of unique decodability. This essentially means that for any sequence of source symbols, that sequence can be reconstructed unambiguously from the encoded bit sequence. Here initial synchronization is assumed: the source decoder knows which is the first bit in the coded bit sequence. Note that without initial synchronization, not even a fixed-length code can be uniquely decoded. Clearly, unique decodability requires that C(aj ) =  C(ai ) for each i =  j. More than that, however, it requires that strings4 of encoded symbols be distinguishable. The following definition says this precisely: Definition 2.3.1. A code C for a discrete source is uniquely decodable if, for any string of source symbols, say x1 , x2 , . . . , xn , the concatenation5 of the corresponding codewords, C(x1 )C(x2 ) · · · C(xn ), differs from the concatenation of the codewords C(x1 )C(x2 ) · · · C(xm ) for any other string x1 , x2 , . . . , xm of source symbols. In other words, C is uniquely decodable if all concatenations of codewords are distinct. Remember that there are no commas or spaces between codewords; the source decoder has to determine the codeword boundaries from the received sequence of bits. (If commas were inserted, the code would be ternary rather than binary.) For example, the above code C for the alphabet X = {a, b, c} is soon shown to be uniquely decodable. However, the code C  defined by C  (a) = 0 C  (b) = 1 C  (c) = 01 is not uniquely decodable, even though the codewords are all different. If the source decoder observes 01, it cannot determine whether the source emitted (a b) or (c). Note that the property of unique decodability depends only on the set of codewords and not on the mapping from symbols to codewords. Thus we can refer interchangeably to uniquely­ decodable codes and uniquely-decodable codeword sets. 4 A string of symbols is an n-tuple of symbols for any finite n. A sequence of symbols is an n-tuple in the limit n → ∞, although the word sequence is also used when the length might be either finite or infinite. 5 The concatenation of two strings, say u1 · · · ul and v1 · · · vl� is the combined string u1 · · · ul v1 · · · vl� . Cite as: Robert Gallager, course materials for 6.450 Principles of Digital Communications I, Fall 2006. MIT OpenCourseWare (http://ocw.mit.edu/), Massachusetts Institute of Technology. Downloaded on [DD Month YYYY]. 20 CHAPTER 2. CODING FOR DISCRETE SOURCES 2.3.2 Prefix-free codes for discrete sources Decoding the output from a uniquely-decodable code, and even determining whether it is uniquely decodable, can be quite complicated. However, there is a simple class of uniquely­ decodable codes called prefix-free codes. As shown later, these have the following advantages over other uniquely-decodable codes:6 • If a uniquely-decodable code exists with a certain set of codeword lengths, then a prefix-free code can easily be constructed with the same set of lengths. • The decoder can decode each codeword of a prefix-free code immediately on the arrival of the last bit in that codeword. • Given a probability distribution on the source symbols, it is easy to construct a prefix-free code of minimum expected length. Definition 2.3.2. A prefix of a string y1 · · · yl is any initial substring y1 · · · yl
, l ≤ l of that string. The prefix is proper if l < l. A code is prefix-free if no codeword is a prefix of any other codeword. For example, the code C with codewords 0, 10, and 11 is prefix-free, but the code C  with codewords 0, 1, and 01 is not. Every fixed-length code with distinct codewords is prefix-free. We will now show that every prefix-free code is uniquely decodable. The proof is constructive, and shows how the decoder can uniquely determine the codeword boundaries. Given a prefix-free code C, a corresponding binary code tree can be defined which grows from a root on the left to leaves on the right representing codewords. Each branch is labelled 0 or 1 and each node represents the binary string corresponding to the branch labels from the root to that node. The tree is extended just enough to include each codeword. That is, each node in the tree is either a codeword or proper prefix of a codeword (see Figure 2.2). � 1� �� 1 ���0 �� � � �� 0 �� b 1�� ��� c a→0 b → 11 c → 101 a Figure 2.2: The binary code tree for a prefix-free code. The prefix-free condition ensures that each codeword corresponds to a leaf node (i.e., a node with no adjoining branches going to the right). Each intermediate node (i.e., nodes having one or more adjoining branches going to the right) is a prefix of some codeword reached by traveling right from the intermediate node. 6 With all the advantages of prefix-free codes, it is difficult to understand why the more general class is even discussed. This will become clearer much later. Cite as: Robert Gallager, course materials for 6.450 Principles of Digital Communications I, Fall 2006. MIT OpenCourseWare (http://ocw.mit.edu/), Massachusetts Institute of Technology. Downloaded on [DD Month YYYY]. 2.3. VARIABLE-LENGTH CODES FOR DISCRETE SOURCES 21 The tree of Figure 2.2 has an intermediate node, 10, with only one right-going branch. This shows that the codeword for c could be shortened to 10 without destroying the prefix-free property. This is shown in Figure 2.3. 1 � �� � 1 ���0 �� � � � ��0 � � a b c a→0 b → 11 c → 10 Figure 2.3: A code with shorter lengths than that of Figure 2.2. A prefix-free code will be called full if no new codeword can be added without destroying the prefix-free property. As just seen, a prefix-free code is also full if no codeword can be shortened without destroying the prefix-free property. Thus the code of Figure 2.2 is not full, but that of Figure 2.3 is. To see why the prefix-free condition guarantees unique decodability, consider the tree for the concatenation of two codewords. This is illustrated in Figure 2.4 for the code of Figure 2.3. This new tree has been formed simply by grafting a copy of the original tree onto each of the leaves of the original tree. Each concatenation of two codewords thus lies on a different node of the tree and also differs from each single codeword. One can imagine grafting further trees onto the leaves of Figure 2.4 to obtain a tree representing still more codewords concatenated together. Again all concatenations of code words lie on distinct nodes, and thus correspond to distinct binary strings. �� bb �� �� � �� �� � bc ������ � b ba �� cb � �� �� ��� � �� ���� � cc � �� c � � � ca 1 � � � � �� ab � � 0� � �� � ac � a �� �� �� �� aa aa → 00 ab → 011 ac → 010 ba → 110 bb → 1111 bc → 1110 ca → 100 cb → 1011 cc → 1010 Figure 2.4: Binary code tree for two codewords; upward branches represent 1’s. An alternative way to see that prefix-free codes are uniquely decodable is to look at the codeword parsing problem from the viewpoint of the source decoder. Given the encoded binary string for any strong of source symbols, the source decoder can decode the first symbol simply by reading the string from left to right and following the corresponding path in the code tree until it reaches a leaf, which must correspond to the first codeword by the prefix-free property. After stripping Cite as: Robert Gallager, course materials for 6.450 Principles of Digital Communications I, Fall 2006. MIT OpenCourseWare (http://ocw.mit.edu/), Massachusetts Institute of Technology. Downloaded on [DD Month YYYY]. 22 CHAPTER 2. CODING FOR DISCRETE SOURCES off the first codeword, the remaining binary string is again a string of codewords, so the source decoder can find the second codeword in the same way, and so on ad infinitum. For example, suppose a source decoder for the code of Figure 2.3 decodes the sequence 1010011 · · · . Proceeding through the tree from the left, it finds that 1 is not a codeword, but that 10 is the codeword for c. Thus c is decoded as the first symbol of the source output, leaving the string 10011 · · · . Then c is decoded as the next symbol, leaving 011 · · · , which is decoded into a and then b, and so forth. This proof also shows that prefix-free codes can be decoded with no delay. As soon as the final bit of a codeword is received at the decoder, the codeword can be recognized and decoded without waiting for additional bits. For this reason, prefix-free codes are sometimes called instantaneous codes. It has been shown that all prefix-free codes are uniquely decodable. The converse is not true, as shown by the following code: C(a) = 0 C(b) = 01 C(c) = 011 An encoded sequence for this code can be uniquely parsed by recognizing 0 as the beginning of each new code word. A different type of example is given in Exercise 2.6. With variable-length codes, if there are errors in data transmission, then the source decoder may lose codeword boundary synchronization and may make more than one symbol error. It is therefore important to study the synchronization properties of variable-length codes. For exam­ ple, the prefix-free code {0, 10, 110, 1110, 11110} is instantaneously self-synchronizing, because every 0 occurs at the end of a codeword. The shorter prefix-free code {0, 10, 110, 1110, 1111} is probabilistically self-synchronizing; again, any observed 0 occurs at the end of a codeword, but since there may be a sequence of 1111 codewords of unlimited length, the length of time before resynchronization is a random variable. These questions are not pursued further here. 2.3.3 The Kraft inequality for prefix-free codes The Kraft inequality [17] is a condition determining whether it is possible to construct a prefixfree code for a given discrete source alphabet X = {a1 , . . . , aM } with a given set of codeword lengths {l(aj ); 1 ≤ j ≤ M }. Theorem 2.3.1 (Kraft inequality for prefix-free codes). Every prefix-free code for an al­ phabet X = {a1 , . . . , aM } with codeword lengths {l(aj ); 1 ≤ j ≤ M } satisfies M � 2−l(aj ) ≤ 1. (2.1) j=1 Conversely, if (2.1) is satisfied, then a prefix-free code with lengths {l(aj ); 1 ≤ j ≤ M } exists. Moreover, every full prefix-free code satisfies (2.1) with equality and every non-full prefix-free code satisfies it with strict inequality. For example, this theorem implies that there exists a full prefix-free code with codeword lengths {1, 2, 2} (two such examples have already been given), but there exists no prefix-free code with codeword lengths {1, 1, 2}. Cite as: Robert Gallager, course materials for 6.450 Principles of Digital Communications I, Fall 2006. MIT OpenCourseWare (http://ocw.mit.edu/), Massachusetts Institute of Technology. Downloaded on [DD Month YYYY]. 2.3. VARIABLE-LENGTH CODES FOR DISCRETE SOURCES 23 Before proving the theorem, we show how to represent codewords as base 2 expansions (the base 2 analog of base 10 decimals) in the binary number system. After understanding this representation, the theorem will be almost obvious. The base 2 expansion .y1 y2 · · · yl represents � the rational number lm=1 ym 2−m . For example, .011 represents 1/4 + 1/8. Ordinary decimals with l digits are frequently used to indicate an approximation of a real number to l places of accuracy. Here, same base 2 expansion .y1 y2 · · · yl is viewed as �l in the �l way, the 7 −m −m ‘covering’ the interval [ m=1 ym 2 , + 2−l ). This interval has size 2−l and m=1 ym 2 includes all numbers whose base 2 expansions start with .y1 . . . yl . In this way, any codeword C(aj ) of length l is represented by a rational number in the interval [0, 1) and covers an interval of size 2−l which includes all strings that contain C(aj ) as a prefix (see Figure 2.3). The proof of the theorem follows: 1.0 � Interval [1/2, 1) 1 −→ .1 01 −→ .01 00 −→ .00 � �Interval [1/4, 1/2) � �Interval [0, 1/4) � Figure 2.5: Base 2 expansion numbers and intervals representing codewords. The codewords represented above are (00, 01, and 1). Proof: First, assume that C is a prefix-free code with codeword lengths {l(aj ), 1 ≤ j ≤ M }. For any distinct aj and ai in X , it was shown above that the base 2 expansion corresponding to C(aj ) cannot lie in the interval corresponding to C(ai ) since C(ai ) is not a prefix of C(aj ). Thus the lower end of the interval corresponding to any codeword C(aj ) cannot lie in the interval corresponding to any other codeword. Now, if two of these intervals intersect, then the lower end of one of them must lie in the other, which is impossible. Thus the two intervals must be disjoint and thus the set of all intervals associated with the codewords are disjoint. Since all these intervals are contained in the interval [0, 1) and the size of the interval corresponding to C(aj ) is 2−l(aj ) , (2.1) is established. Next note that if (2.1) is satisfied with strict inequality, then some interval exists in [0, 1) that does not intersect any codeword interval; thus another codeword can be ‘placed’ in this interval and the code is not full. If (2.1) is satisfied with equality, then the intervals fill up [0, 1). In this case no additional code word can be added and the code is full. Finally we show that a prefix-free code can be constructed from any desired set of codeword lengths {l(aj ), 1 ≤ j ≤ M } for which (2.1) is satisfied. Put the set of lengths in nondecreasing order, l1 ≤ l2 ≤ · · · ≤ lM and let u1 , . . . , uM be the real numbers corresponding to the codewords in the construction to be described. The construction is quite simple: u1 = 0, and for all 7 Brackets and parentheses, respectively, are used to indicate closed and open boundaries; thus the interval [a, b) means the set of real numbers u such that a ≤ u < b. Cite as: Robert Gallager, course materials for 6.450 Principles of Digital Communications I, Fall 2006. MIT OpenCourseWare (http://ocw.mit.edu/), Massachusetts Institute of Technology. Downloaded on [DD Month YYYY]. 24 CHAPTER 2. CODING FOR DISCRETE SOURCES j, 1 < j ≤ M , uj = j−1 � 2−li . (2.2) i=1 Each term on the right is an integer multiple of 2−lj , so uj is also an integer multiple of 2−lj . From (2.1), uj < 1, so uj can be represented by a base 2 expansion with lj places. The corresponding codeword of length lj can be added to the code while preserving prefix-freedom (see Figure 2.6). ui 0.001 � 0.001 � � � 0.01 � � 0.01 � � 0.01 � 0.111 0.11 C(5) = 111 C(4) = 110 0.1 C(3) = 10 0.01 C(2) = 01 0 C(1) = 00 Figure 2.6: Construction of codewords for the set of lengths {2, 2, 2, 3, 3}. C(i) is formed from ui by representing ui to li places. Some final remarks on the Kraft inequality: • Just because a code has lengths that satisfy (2.1), it does not follow that the code is prefixfree, or even uniquely decodable. • Exercise 2.11 shows that Theorem 2.3.1 also holds for all uniquely-decodable codes— i.e., there exists a uniquely-decodable code with codeword lengths {l(aj ), 1 ≤ j ≤ M } if and only if (2.1) holds. This will imply that if a uniquely-decodable code exists with a certain set of codeword lengths, then a prefix-free code exists with the same set of lengths. So why use any code other than a prefix-free code? 2.4 Probability models for discrete sources It was shown above that prefix-free codes exist for any set of codeword lengths satisfying the Kraft inequality. When does it desirable to use one of these codes?– i.e., when is the expected number of coded bits per source symbol less than log M and why is the expected number of coded bits per source symbol the primary parameter of importance? This question cannot be answered without a probabilistic model for the source. For example, the M = 4 prefix-free set of codewords {0, 10, 110, 111} has an expected length of 2.25 > 2 = log M if the source symbols are equiprobable, but if the source symbol probabilities are {1/2, 1/4, 1/8, 1/8}, then the expected length is 1.75 < 2. The discrete sources that one meets in applications usually have very complex statistics. For example, consider trying to compress email messages. In typical English text, some letters such Cite as: Robert Gallager, course materials for 6.450 Principles of Digital Communications I, Fall 2006. MIT OpenCourseWare (http://ocw.mit.edu/), Massachusetts Institute of Technology. Downloaded on [DD Month YYYY]. 2.4. PROBABILITY MODELS FOR DISCRETE SOURCES 25 as e and o occur far more frequently than q, x, and z. Moreover, the letters are not independent; for example h is often preceded by t, and q is almost always followed by u. Next, some strings of letters are words, while others are not; those that are not have probability near 0 (if in fact the text is correct English). Over longer intervals, English has grammatical and semantic constraints, and over still longer intervals, such as over multiple email messages, there are still further constraints. It should be clear therefore that trying to find an accurate probabilistic model of a real-world discrete source is not going to be a productive use of our time. An alternative approach, which has turned out to be very productive, is to start out by trying to understand the encoding of “toy” sources with very simple probabilistic models. After studying such toy sources, it will be shown how to generalize to source models with more and more general structure, until, presto, real sources can be largely understood even without good stochastic models. This is a good example of a problem where having the patience to look carefully at simple and perhaps unrealistic models pays off handsomely in the end. The type of toy source that will now be analyzed in some detail is called a discrete memoryless source. 2.4.1 Discrete memoryless sources A discrete memoryless source (DMS) is defined by the following properties: • The source output is an unending sequence, X1 , X2 , X3 , . . . , of randomly selected symbols from a finite set X = {a1 , a2 , . . . , aM }, called the source alphabet. • Each source output X1 , X2 , . . . is selected from X using the same probability mass function (pmf) {pX (a1 ), . . . , pX (aM )}. Assume that pX (aj ) > 0 for all j, 1 ≤ j ≤ M , since there is no reason to assign a code word to a symbol of zero probability and no reason to model a discrete source as containing impossible symbols. • Each source output Xk is statistically independent of the previous outputs X1 , . . . , Xk−1 . The randomly chosen symbols coming out of the source are called random symbols. They are very much like random variables except that they may take on nonnumeric values. Thus, if X denotes the result of a fair coin toss, then it can be modeled as a random symbol that takes values in the set {Heads, Tails} with equal probability. Note that if X is a nonnumeric random symbol, then it makes no sense to talk about its expected value. However, the notion of statistical independence between random symbols is the same as that for random variables, i.e., the event that Xi is any given element of X is independent of the events corresponding to the values of the other random symbols. The word memoryless in the definition refers to the statistical independence between different random symbols, i.e., each variable is chosen with no memory of how the previous random symbols were chosen. In other words, the source symbol sequence is independent and identically distributed (iid).8 In summary, a DMS is a semi-infinite iid sequence of random symbols X1 , X 2 , X 3 , . . . 8 Do not confuse this notion of memorylessness with any non-probabalistic notion in system theory. Cite as: Robert Gallager, course materials for 6.450 Principles of Digital Communications I, Fall 2006. MIT OpenCourseWare (http://ocw.mit.edu/), Massachusetts Institute of Technology. Downloaded on [DD Month YYYY]. 26 CHAPTER 2. CODING FOR DISCRETE SOURCES each drawn from the finite set X , each element of which has positive probability. A sequence of independent tosses of a biased coin is one example of a DMS. The sequence of symbols drawn (with replacement) in a ScrabbleTM game is another. The reason for studying these sources is that they provide the tools for studying more realistic sources. 2.5 Minimum L for prefix-free codes The Kraft inequality determines which sets of codeword lengths are possible for prefix-free codes. Given a discrete memoryless source (DMS), we want to determine what set of codeword lengths can be used to minimize the expected length of a prefix-free code for that DMS. That is, we want to minimize the expected length subject to the Kraft inequality. Suppose a set of lengths l(a1 ), . . . , l(aM ) (subject to the Kraft inequality) is chosen for encoding each symbol into a prefix-free codeword. Define L(X) (or more briefly L) as a random variable representing the codeword length for the randomly selected source symbol. The expected value of L for the given code is then given by L = E[L] = M � l(aj )pX (aj ). j=1 We want to find Lmin , which is defined as the minimum value of L over all sets of codeword lengths satisfying the Kraft inequality. Before finding Lmin , we explain why this quantity is of interest. The number of bits resulting from using the above code to encode a long block X = (X1 , X2 , . . . , Xn ) of symbols is Sn = L(X1 ) + L(X2 ) + · · · + L(Xn ). This is a sum of n iid random variables (rv’s), and the law of large numbers, which is discussed in Section 2.7.1, implies that Sn /n, the number of bits per symbol in this long block, is very close to L with probability very close to 1. In other words, L is essentially the rate (in bits per source symbol) at which bits come out of the source encoder. This motivates the objective of finding Lmin and later of finding codes that achieve the minimum. Before proceeding further, we simplify our notation. We have been carrying along a completely arbitrary finite alphabet X = {a1 , . . . , aM } of size M = |X |, but this problem (along with most source coding problems) involves only the probabilities of the M symbols and not their names. Thus define the source alphabet to be {1, 2, . . . , M }, denote the symbol probabilities by p1 , . . . , pM , and denote the corresponding codeword lengths by l1 , . . . , lM . The expected length of a code is then L= M � l j pj j=1 Mathematically, the problem of finding Lmin is that of minimizing L over all sets of integer lengths l1 , . . . , lM subject to the Kraft inequality:   M �  . (2.3) Lmin = min p l j j �  l1 ,... ,lM : j 2−lj ≤1  j=1 Cite as: Robert Gallager, course materials for 6.450 Principles of Digital Communications I, Fall 2006. MIT OpenCourseWare (http://ocw.mit.edu/), Massachusetts Institute of Technology. Downloaded on [DD Month YYYY]. 2.5. MINIMUM L FOR PREFIX-FREE CODES 2.5.1 27 Lagrange multiplier solution for the minimum L The minimization in (2.3) is over a function of M variables, l1 , . . . , lM , subject to constraints on those variables. Initially, consider a simpler problem � where there are no integer constraint on the lj . This simpler problem is then to minimize j pj lj over all real values of l1 , . . . , lM � subject to j 2−lj ≤ 1. The resulting minimum is called Lmin (noninteger). Since the allowed values for the lengths in this minimization include integer lengths, it is clear that Lmin (noninteger) ≤ Lmin . This noninteger minimization will provide a number of important insights about the problem, so its usefulness extends beyond just providing a lower bound on Lmin . � � Note first that the minimum of j lj pj subject to j 2−lj ≤ 1 must occur when the constraint � is satisfied with equality, for otherwise, one of the lj could be reduced, thus reducing j pj lj � � without violating the constraint. Thus the problem is to minimize j pj lj subject to j 2−lj = 1. Problems of this type are often solved by using a Lagrange multiplier. The idea is to replace the minimization of one function, subject to a constraint on another function, by the minimization of a linear combination of the two functions, in this case the minimization of � � pj l j + λ 2−lj . (2.4) j j If the method works, the expression can be minimized for each choice of λ (called a Lagrange mul­ tiplier ); λ can then be chosen so that the � optimizing choice of l1 , . . . , lM satisfies the constraint. The minimizing value of (2.4) is then j pj lj + λ. This choice of l1 , . . . , lM minimizes the orig­ � −l
 , . . . , l that satisfies the constraint j = 1, inal constrained optimization, since for any l 1 j2 M � �  the expression in (2.4) is j pj lj + λ, which must be greater than or equal to j pj lj + λ. We can attempt9 to minimize (2.4) simply by setting the derivitive with respect to each lj equal to 0. This yields (2.5) pj − λ(ln 2)2−lj = 0; 1 ≤ j ≤ M. � Thus 2−lj = pj /(λ ln 2). Since j pj = 1, λ must be equal to 1/ ln 2 in order to satisfy the � constraint j 2−lj = 1. Then 2−lj = pj , or equivalently lj = − log pj . It will be shown shortly that this stationary point actually achieves a minimum. Substituting this solution into (2.3), Lmin (noninteger) = − M � pj log pj . (2.6) j=1 The quantity on the right side of (2.6) is called the entropy 10 of X, and denoted as H[X]. Thus � H[X] = − pj log pj . j 9 There are well-known rules for when the Lagrange multiplier method works and when it can be solved simply by finding a stationary point. The present problem is so simple, however, that this machinery is unnecessary. 10 Note that X is a random symbol and carries with it all of the accompanying baggage, including a pmf. The entropy H[X] is a numerical function of the random symbol including that pmf; in the same way E[L] is a numerical function of the rv L. Both H[X] and E[L] are expected values of particular rv’s. In distinction, L(X) above is an rv in its own right; it is based on some function l(x) mapping X → R and takes the sample value l(x) for all sample points such that X = x. Cite as: Robert Gallager, course materials for 6.450 Principles of Digital Communications I, Fall 2006. MIT OpenCourseWare (http://ocw.mit.edu/), Massachusetts Institute of Technology. Downloaded on [DD Month YYYY]. 28 CHAPTER 2. CODING FOR DISCRETE SOURCES In summary, the entropy H[X] is a lower bound to L for prefix-free codes and this lower bound is achieved when lj = − log pj for each j. The bound was derived by ignoring the integer constraint, and can be met only if − log pj is an integer for each j; i.e., if each pj is a power of 2. 2.5.2 Entropy bounds on L We now return to the problem of minimizing L with an integer constraint on lengths. The following theorem both establishes the correctness of the previous non-integer optimization and provides an upper bound on Lmin . Theorem 2.5.1 (Entropy bounds for prefix-free codes). Let X be a discrete random symbol with symbol probabilities p1 , . . . , pM . Let Lmin be the minimum expected codeword length over all prefix-free codes for X. Then H[X] ≤ Lmin < H[X] + 1 bit/symbol. (2.7) Furthermore, Lmin = H[X] if and only if each probability pj is an integer power of 2. Proof: It is first shown that H[X] ≤ L for all prefix-free codes. Let l1 , . . . , lM be the codeword lengths of an arbitrary prefix-free code. Then M � H[X] − L = j=1 M M � � 1 2−lj pj log − pj l j = pj log , pj pj j=1 (2.8) j=1 where log 2−lj has been substituted for −lj . We now use the very useful inequality ln u ≤ u − 1, or equivalently log u ≤ (log e)(u − 1), which is illustrated in Figure 2.7. Note that equality holds only at the point u = 1. u−1� � � ln u � � �1 u � � Figure 2.7: The inequality ln u ≤ u − 1. The inequality is strict except at u = 1. Substituting this inequality in (2.8), H[X] − L ≤ (log e) M � j=1 � pj   � M M � � 2−lj − 1 = (log e)  2−lj − pj  ≤ 0, pj j=1 (2.9) j=1 � where the Kraft inequality and j pj = 1 has been used. This establishes the left side of (2.7). The inequality in (2.9) is strict unless 2−lj /pj = 1, or equivalently lj = − log pj , for all j. For integer lj , this can be satisfied with equality if and only if pj is an integer power of 2 for all j. For Cite as: Robert Gallager, course materials for 6.450 Principles of Digital Communications I, Fall 2006. MIT OpenCourseWare (http://ocw.mit.edu/), Massachusetts Institute of Technology. Downloaded on [DD Month YYYY]. 2.5. MINIMUM L FOR PREFIX-FREE CODES 29 arbitrary real values of lj , this proves that (2.5) minimizes (2.3) without the integer constraint, thus verifying (2.6.) To complete the proof, it will be shown that a prefix-free code exists with L < H[X] + 1. Choose the codeword lengths to be lj = − log pj  , where the ceiling notation u denotes the smallest integer less than or equal to u. With this choice, − log pj ≤ lj < − log pj + 1. (2.10) Since the left side of (2.10) is equivalent to 2−lj ≤ pj , the Kraft inequality is satisfied: � � 2−lj ≤ pj = 1. j j Thus a prefix-free code exists with the above lengths. From the right side of (2.10), the expected codeword length of this code is upperbounded by � � L= pj l j < pj (− log pj + 1) = H[X] + 1. j j Since Lmin ≤ L, Lmin < H[X] + 1, completing the proof. Both the proof above and the noninteger minimization in (2.6) suggest that the optimal length of a codeword for a source symbol of probability pj should be approximately − log pj . This is not quite true, because, for example, if M = 2 and p1 = 2−20 , p2 = 1−2−20 , then − log p1 = 20, but the optimal l1 is 1. However, the last part of the above proof shows that if each li is chosen as an integer approximation to − log pi , then L is at worst within one bit of H[X]. For sources with a small number of symbols, the upper bound in the theorem appears to be too loose to have any value. When these same arguments are applied later to long blocks of source symbols, however, the theorem leads directly to the source coding theorem. 2.5.3 Huffman’s algorithm for optimal source codes In the very early days of information theory, a number of heuristic algorithms were suggested for choosing codeword lengths lj to approximate − log pj . Both Claude Shannon and Robert Fano had suggested such heuristic algorithms by 1948. It was conjectured at that time that, since this was an integer optimization problem, its optimal solution would be quite difficult. It was quite a surprise therefore when David Huffman [13] came up with a very simple and straightforward algorithm for constructing optimal (in the sense of minimal L) prefix-free codes. Huffman developed the algorithm in 1950 as a term paper in Robert Fano’s information theory class at MIT. Huffman’s trick, in today’s jargon, was to “think outside the box.” He ignored the Kraft inequal­ ity, and looked at the binary code tree to establish properties that an optimal prefix-free code should have. After discovering a few simple properties, he realized that they led to a simple recursive procedure for constructing an optimal code. Cite as: Robert Gallager, course materials for 6.450 Principles of Digital Communications I, Fall 2006. MIT OpenCourseWare (http://ocw.mit.edu/), Massachusetts Institute of Technology. Downloaded on [DD Month YYYY]. 30 CHAPTER 2. CODING FOR DISCRETE SOURCES 1 �� � ��0 � � C(1) p1 = 0.6 p2 = 0.4 � C(2) With two symbols, the optimal codeword lengths are 1 and 1. � C(2) 1 �� � 1����0 � � � C(3) � � 0 �� � C(1) p1 = 0.6 p2 = 0.3 p3 = 0.1 With three symbols, the optimal lengths are 1, 2, 2. The least likely symbols are assigned words of length 2. Figure 2.8: Some simple optimal codes. The simple examples in Figure 2.8 illustrate some key properties of optimal codes. After stating these properties precisely, the Huffman algorithm will be almost obvious. The property of the length assignments in the three-word example above can be generalized as follows: the longer the codeword, the less probable the corresponding symbol must be. More precisely: Lemma 2.5.1. Optimal codes have the property that if pi > pj , then li ≤ lj . Proof: Assume to the contrary that a code has pi > pj and li > lj . The terms involving symbols i and j in L are pi li + pj lj . If the two code words are interchanged, thus interchanging li and lj , this sum decreases, i.e., (pi li +pj lj ) − (pi lj +pj li ) = (pi − pj )(li − lj ) > 0. Thus L decreases, so any code with pi > pj and li > lj is nonoptimal. An even simpler property of an optimal code is as follows: Lemma 2.5.2. Optimal prefix-free codes have the property that the associated code tree is full. Proof: If the tree is not full, then a codeword length could be reduced (see Figures 2.2 and 2.3). Define the sibling of a codeword as the binary string that differs from the codeword in only the final digit. A sibling in a full code tree can be either a codeword or an intermediate node of the tree. Lemma 2.5.3. Optimal prefix-free codes have the property that, for each of the longest codewords in the code, the sibling of that codeword is another longest codeword. Proof: A sibling of a codeword of maximal length cannot be a prefix of a longer codeword. Since it cannot be an intermediate node of the tree, it must be a codeword. For notational convenience, assume that the M = |X | symbols in the alphabet are ordered so that p1 ≥ p2 ≥ · · · ≥ pM . Cite as: Robert Gallager, course materials for 6.450 Principles of Digital Communications I, Fall 2006. MIT OpenCourseWare (http://ocw.mit.edu/), Massachusetts Institute of Technology. Downloaded on [DD Month YYYY]. 2.5. MINIMUM L FOR PREFIX-FREE CODES 31 Lemma 2.5.4. Let X be a random symbol with a pmf satisfying p1 ≥ p2 ≥ · · · ≥ pM . There is an optimal prefix-free code for X in which the codewords for M − 1 and M are siblings and have maximal length within the code. Proof: There are finitely many codes satisfying the Kraft inequality with equality,11 so consider a particular one that is optimal. If pM < pj for each j < M , then, from Lemma 2.5.1, lM ≥ lj for each and lM has maximal length. If pM = pj for one or more j < M , then lj must be maximal for at least one such j. Then if lM is not maximal, C(j) and C(M ) can be interchanged with no loss of optimality, after which lM is maximal. Now if C(k) is the sibling of C(M ) in this optimal code, then lk also has maximal length. By the argument above, C(M − 1) can then be exchanged with C(k) with no loss of optimality. The Huffman algorithm chooses an optimal code tree by starting with the two least likely symbols, specifically M and M − 1, and constraining them to be siblings in the yet unknown code tree. It makes no difference which sibling ends in 1 and which in 0. How is the rest of the tree to be chosen? If the above pair of siblings is removed from the yet unknown tree, the rest of the tree must contain M − 1 leaves, namely the M − 2 leaves for the original first M − 2 symbols, and the parent node of the removed siblings. The probability pM −1 associated with this new leaf is taken as pM −1 + pM . This tree of M − 1 leaves is viewed as a code for a reduced random symbol X  with a reduced set of probabilities given as p1 , . . . , pM −2 for the original first M − 2 symbols and pM −1 for the new symbol M − 1. To complete the algorithm, an optimal code is constructed for X  . It will be shown that an optimal code for X can be generated by constructing an optimal code for X  , and then grafting siblings onto the leaf corresponding to symbol M − 1. Assuming this fact for the moment, the problem of constructing an optimal M -ary code has been replaced with constructing an optimal M −1-ary code. This can be further reduced by applying the same procedure to the M −1-ary random symbol, and so forth down to a binary symbol for which the optimal code is obvious. The following example in Figures 2.9 to 2.11 will make the entire procedure obvious. It starts with a random symbol X with probabilities {0.4, 0.2, 0.15, 0.15, 0.1} and generates the reduced random symbol X  in Figure 2.9. The subsequent reductions are shown in Figures 2.10 and 2.11. pj 0.4 1 � ��0 �� (0.25)���� symbol 1 0.2 2 0.15 3 0.15 4 0.1 5 The two least likely symbols, 4 and 5 have been combined as siblings. The reduced set of probabilities then becomes {0.4, 0.2, 0.15, 0.25}. Figure 2.9: Step 1 of the Huffman algorithm; finding X  from X . Another example using a different set of probabilities and leading to a different set of codeword lengths is given in Figure 2.12: 11 Exercise 2.10 proves this for those who enjoy such things. Cite as: Robert Gallager, course materials for 6.450 Principles of Digital Communications I, Fall 2006. MIT OpenCourseWare (http://ocw.mit.edu/), Massachusetts Institute of Technology. Downloaded on [DD Month YYYY]. 32 CHAPTER 2. CODING FOR DISCRETE SOURCES pj symbol 0.4 1 � �� 0�� 0.2 2 0.15 3 1 � ��� 0 � 0.15 4 0.1 5 (0.35)���1� (0.25)���� The two least likely symbols in the reduced set, with probabilities 0.15 and 0.2, have been combined as siblings. The reduced set of proba­ bilities then becomes {0.4, 0.35, 0.25}. Figure 2.10: Finding X  from X  . pj � ��� ��� � � �� � �1�� (0.35) ��1� ��� � � � � ��� � 0 � �� 1 � � ���0 ����� � 0 (0.6) ��� �� ��1�� �� 0 (0.25) ��� symbol codeword 0.4 1 1 0.2 2 011 0.15 3 010 0.15 4 001 0.1 5 000 Figure 2.11: The completed Huffman code. The only thing remaining to show that the Huffman algorithm constructs optimal codes is to show that an optimal code for the reduced random symbol X  yields an optimal code for X. Consider Figure 2.13, which shows the code tree for X  corresponding to X in Figure 2.12. Note that Figures 2.12 and 2.13 differ in that C(4) and C(5), each of length 3 in Figure 2.12, have been replaced by a single codeword of length 2 in Figure 2.13. The probability of that single symbol is the sum of the two probabilities in Figure 2.12. Thus the expected codeword length for Figure 2.12 is that for Figure 2.13, increased by p4 + p5 . This accounts for the fact that C(4) and C(5) have lengths one greater than their parent node. In general, comparing the expected length L of any code for X  and the corresponding L of the code generated by extending C  (M − 1) in the code for X  into two siblings for M − 1 and M , it is seen that L = L  + pM −1 + pM . This relationship holds for all codes for X in which C(M − 1) and C(M ) are siblings (which  includes at least one optimal code). This proves that L is minimized by minimizing L , and also shows that Lmin = L min + pM −1 + pM . This completes the proof of the optimality of the Huffman algorithm. It is curious that neither the Huffman algorithm nor its proof of optimality give any indication of the entropy bounds, H[X] ≤ Lmin < H[X] + 1. Similarly, the entropy bounds do not suggest the Huffman algorithm. One is useful in finding an optimal code; the other provides insightful performance bounds. Cite as: Robert Gallager, course materials for 6.450 Principles of Digital Communications I, Fall 2006. MIT OpenCourseWare (http://ocw.mit.edu/), Massachusetts Institute of Technology. Downloaded on [DD Month YYYY]. 2.6. ENTROPY AND FIXED-TO-VARIABLE-LENGTH CODES pj (0.6) 1 � � � 1� � �0 �� � 0 � � (0.4)���1� ��0� � � � �1�� ��� ��� 0 (0.25) � 33 symbol codeword 0.35 1 11 0.2 2 01 0.2 3 00 0.15 4 101 0.1 5 100 Figure 2.12: Completed Huffman code for a different set of probabilities. pj (0.6) 1 � 1�� � 0 � � �� � 0 � � (0.4)���1� ��0� � � � symbol codeword 0.35 1 11 0.2 2 01 0.2 3 00 0.25 4 10 Figure 2.13: Completed reduced Huffman code for Figure 2.12. As an example of the extent to which the optimal lengths approximate − log pj , the source probabilities in Figure 2.11 are {0.40, 0.20, 0.15, 0.15, 0.10}, so − log pj takes the set of values {1.32, 2.32, 2.74, 2.74, 3.32} bits; this approximates the lengths {1, 3, 3, 3, 3} of the optimal code quite well. Similarly, the entropy is H[X] = 2.15 bits/symbol and Lmin = 2.2 bits/symbol, quite close to H[X]. However, it would be difficult to guess these optimal lengths, even in such a simple case, without the algorithm. For the example of Figure 2.12, the source probabilities are {0.35, 0.20, 0.20, 0.15, 0.10}, the values of − log pi are {1.51, 2.32, 2.32, 2.74, 3.32}, and the entropy is H[X] = 2.20. This is not very different from Figure 2.11. However, the Huffman code now has lengths {2, 2, 2, 3, 3} and average length L = 2.25 bits/symbol. (The code of Figure 2.11 has average length L = 2.30 for these source probabilities.) It would be hard to predict these perturbations without carrying out the algorithm. 2.6 Entropy and fixed-to-variable-length codes Entropy is now studied in more detail, both to better understand the entropy bounds and to understand the entropy of n-tuples of successive source letters. The entropy H[X] is a fundamental measure of the randomness of a random symbol X. It has many important properties. The property of greatest interest here is that it is the smallest expected number L of bits per source symbol required to map the sequence of source symbols into a bit sequence in a uniquely decodable way. This will soon be demonstrated by generalizing the variable-length codes of the last few sections to codes in which multiple source symbols are Cite as: Robert Gallager, course materials for 6.450 Principles of Digital Communications I, Fall 2006. MIT OpenCourseWare (http://ocw.mit.edu/), Massachusetts Institute of Technology. Downloaded on [DD Month YYYY]. 34 CHAPTER 2. CODING FOR DISCRETE SOURCES encoded together. First, however, several other properties of entropy are derived. Definition: The entropy of a discrete random symbol12 X with alphabet X is � � 1 =− pX (x) log pX (x) log pX (x). H[X] = pX (x) x∈X (2.11) x∈X Using logarithms to the base 2, the units of H[X] are bits/symbol. If the base of the logarithm is e, then the units of H[X] are called nats/symbol. Conversion is easy; just remember that log y = (ln y)/(ln 2) or ln y = (log y)/(log e), both of which follow from y = eln y = 2log y by taking logarithms. Thus using another base for the logarithm just changes the numerical units of entropy by a scale factor. Note that the entropy H[X] of a discrete random symbol X depends on the probabilities of the different outcomes of X, but not on the names of the outcomes. Thus, for example, the entropy of a random symbol taking the values green, blue, and red with probabilities 0.2, 0.3, 0.5, respectively, is the same as the entropy of a random symbol taking on the values Sunday, Monday, Friday with the same probabilities 0.2, 0.3, 0.5. The entropy H[X] is also called the uncertainty of X, meaning that it is a measure of the randomness of X. Note that entropy is the expected value of the rv log(1/pX (X)). This random variable is called the log pmf rv.13 Thus the entropy is the expected value of the log pmf rv. Some properties of entropy: • For any discrete random symbol X, H[X] ≥ 0. This follows because pX (x) ≤ 1, so log(1/pX (x)) ≥ 0. The result follows from (2.11). • H[X] = 0 if and only if X is deterministic. This follows since pX (x) log(1/pX (x)) = 0 if and only if pX (x) equals 0 or 1. • The entropy of an equiprobable random symbol X with an alphabet X of size M is H[X] = log M . This follows because, if pX (x) = 1/M for all x ∈ X , then � 1 H[X] = log M = log M. M x∈X In this case, the rv − log pX (X) has the constant value log M . • More generally, the entropy H[X] of a random symbol X defined on an alphabet X of size M satisfies H[X] ≤ log M , with equality only in the equiprobable case. To see this, note that � � � � � � 1 1 H[X] − log M = pX (x) log pX (x) log − log M = pX (x) M pX (x) x∈X x∈X � � � 1 ≤ (log e) − 1 = 0, pX (x) M pX (x) x∈X 12 If one wishes to consider discrete random symbols with one or more symbols of zero probability, one can still use this formula by recognizing that limp→0 p log(1/p) = 0 and then defining 0 log 1/0 as 0 in (2.11). Exercise 2.18 illustrates the effect of zero probability symbols in a variable-length prefix code. 13 This rv is often called self information or surprise, or uncertainty. It bears some resemblance to the ordinary meaning of these terms, but historically this has caused much more confusion than enlightenment. Log pmf, on the other hand, emphasizes what is useful here Cite as: Robert Gallager, course materials for 6.450 Principles of Digital Communications I, Fall 2006. MIT OpenCourseWare (http://ocw.mit.edu/), Massachusetts Institute of Technology. Downloaded on [DD Month YYYY]. 2.6. ENTROPY AND FIXED-TO-VARIABLE-LENGTH CODES 35 This uses the inequality log u ≤ (log e)(u−1) (after omitting any terms for which pX (x) = 0). For equality, it is necessary that pX (x) = 1/M for all x ∈ X . In summary, of all random symbols X defined on a given finite alphabet X , the highest entropy occurs in the equiprobable case, namely H[X] = log M , and the lowest occurs in the deterministic case, namely H[X] = 0. This supports the intuition that the entropy of a random symbol X is a measure of its randomness. For any pair of discrete random symbols X and Y , XY is another random symbol. The sample values of XY are the set of all pairs xy, x ∈ X , y ∈ Y and the probability of each sample value xy is pXY (x, y). An important property of entropy is that if X and Y are independent discrete random symbols, then H[XY ] = H[X] + H[Y ]. This follows from: � pXY (x, y) log pXY (x, y) H[XY ] = − X ×Y = − � pX (x)pY (y) (log pX (x) + log pY (y)) = H[X] + H[Y ]. (2.12) X ×Y Extending this to n random symbols, the entropy of a random symbol X n corresponding to a block of n iid outputs from a discrete memoryless source is H[X n ] = nH[X]; i.e., each symbol increments the entropy of the block by H[X] bits. 2.6.1 Fixed-to-variable-length codes Recall that in Section 2.2 the sequence of symbols from the source was segmented into successive blocks of n symbols which were then encoded. Each such block was a discrete random symbol in its own right, and thus could be encoded as in the single-symbol case. It was seen that by making n large, fixed-length codes could be constructed in which the number L of encoded bits per source symbol approached log M as closely as desired. The same approach is now taken for variable-length coding of discrete memoryless sources. A block of n source symbols, X1 , X2 , . . . , Xn has entropy H[X n ] = nH[X]. Such a block is a random symbol in its own right and can be encoded using a variable-length prefix-free code. This provides a fixed-to-variable-length code, mapping n-tuples of source symbols to variablelength binary sequences. It will be shown that the expected number L of encoded bits per source symbol can be made as close to H[X] as desired. Surprisingly, this result is very simple. Let E[L(X n )] be the expected length of a variable-length prefix-free code for X n . Denote the minimum expected length of any prefix-free code for X n by E[L(X n )]min . Theorem 2.5.1 then applies. Using (2.7), H[X n ] ≤ E[L(X n )]min < H[X n ] + 1. (2.13) n Define Lmin,n = E[L(Xn )]min ; i.e., Lmin,n is the minimum number of bits per source symbol over all prefix-free codes for X n . From (2.13), H[X] ≤ Lmin,n < H[X] + 1 . n (2.14) This simple result establishes the following important theorem: Cite as: Robert Gallager, course materials for 6.450 Principles of Digital Communications I, Fall 2006. MIT OpenCourseWare (http://ocw.mit.edu/), Massachusetts Institute of Technology. Downloaded on [DD Month YYYY]. 36 CHAPTER 2. CODING FOR DISCRETE SOURCES Theorem 2.6.1 (Prefix-free source coding theorem). For any discrete memoryless source with entropy H[X], and any integer n ≥ 1, there exists a prefix-free encoding of source n-tuples for which the expected codeword length per source symbol L is at most H[X] + 1/n. Furthermore, no prefix-free encoding of fixed-length source blocks of any length n results in an expected codeword length L less than H[X]. This theorem gives considerable significance to the entropy H[X] of a discrete memoryless source: H[X] is the minimum expected number L of bits per source symbol that can be achieved by fixed-to-variable-length prefix-free codes. There are two potential questions about the significance of the theorem. First, is it possible to find uniquely-decodable codes other than prefix-free codes for which L is less than H[X]? Second, is it possible to further reduce L by using variable-to-variable-length codes? For example, if a binary source has p1 = 10−6 and p0 = 1 − 10−6 , fixed-to-variable-length codes must use remarkably long n-tuples of source symbols to approach the entropy bound. Run-length coding, which is an example of variable-to-variable-length coding, is a more sensible approach in this case: the source is first encoded into a sequence representing the number of source 0’s between each 1, and then this sequence of integers is encoded. This coding technique is further developed in Exercise 2.23. The next section strengthens Theorem 2.6.1, showing that H[X] is indeed a lower bound to L over all uniquely-decodable encoding techniques. 2.7 The AEP and the source coding theorems We first review the weak14 law of large numbers (WLLN) for sequences of iid rv’s. Applying the WLLN to a particular iid sequence, we will establish a form of the remarkable asymptotic equipartition property (AEP). Crudely, the AEP says that, given a very long string of n iid discrete random symbols X1 , . . . , Xn , there exists a “typical set” of sample strings (x1 , . . . , xn ) whose aggregate probabil­ ity is almost 1. There are roughly 2nH[X] typical strings of length n, and each has a probability roughly equal to 2−nH[X] . We will have to be careful about what the words “almost” and “roughly” mean here. The AEP will give us a fundamental understanding not only of source coding for discrete memo­ ryless sources, but also of the probabilistic structure of such sources and the meaning of entropy. The AEP will show us why general types of source encoders, such as variable-to-variable-length encoders, cannot have a strictly smaller expected length per source symbol than the best fixedto-variable-length prefix-free codes for discrete memoryless sources. 14 The word weak is something of a misnomer, since this is one of the most useful results in probability theory. There is also a strong law of large numbers; the difference lies in the limiting behavior of an infinite sequence of rv’s, but this difference is not relevant here. The weak law applies in some cases where the strong law does not, but this also is not relevant here. Cite as: Robert Gallager, course materials for 6.450 Principles of Digital Communications I, Fall 2006. MIT OpenCourseWare (http://ocw.mit.edu/), Massachusetts Institute of Technology. Downloaded on [DD Month YYYY]. 2.7. THE AEP AND THE SOURCE CODING THEOREMS 2.7.1 37 The weak law of large numbers Let Y1 , Y2 , . . . , be a sequence of iid rv’s. Let Y and σY2 be the mean and variance of each Yj . Define the sample average AnY of Y1 , . . . , Yn as SYn n AnY = where SYn = Y1 + · · · + Yn . The sample average AnY is itself an rv, whereas, of course, the mean Y is simply a real number. Since the sum SYn has mean nY and variance nσY2 , the sample average AnY has mean E[AnY ] = Y 2 = σ 2 /n2 = σ 2 /n. It is important to understand that the variance of the sum and variance σA n SYn Y Y increases with n and the variance of the normalized sum (the sample average, AnY ), decreases with n. 2 < ∞ for an rv X , then, Pr{|X − X | ≥ ε} ≤ σ 2 /ε2 The Chebyshev inequality states that if σX X for any ε > 0 (see Exercise 2.3 or any text on probability such as [2] or [24]). Applying this inequality to AnY yields the simplest form of the WLLN: for any ε > 0, Pr{|AnY − Y | ≥ ε} ≤ σY2 . nε2 (2.15) This is illustrated in Figure 2.14. 1 Pr(|A2n Y −Y | < ε) Pr(|AnY −Y | < ε) � � � � �� F 2n (y) � � n AY FAY (y) � � y Y −ε Y Y +ε Figure 2.14: Sketch of the distribution function of the sample average for different n. As n increases, the distribution function approaches a unit step at Y . The closeness to a step within Y ± ε is upperbounded by (2.15). Since the right side of (2.15) approaches 0 with increasing n for any fixed ε > 0, lim Pr{|AnY − Y | ≥ ε} = 0. n→∞ (2.16) For large n, (2.16) says that AnY − Y is small with high probability. It does not say that AnY = Y with high probability (or even nonzero probability), and it does not say that Pr(|AnY − Y | ≥ ε) = 0. As illustrated in Figure 2.14, both a nonzero ε and a nonzero probability are required here, even though they can be made simultaneously as small as desired by increasing n. In summary, the sample average AnY is an rv whose mean Y is independent of n, but whose √ standard deviation σY / n approaches 0 as n → ∞. Therefore the distribution of the sample average becomes concentrated near Y as n increases. The WLLN is simply this concentration property, stated more precisely by either (2.15) or (2.16). Cite as: Robert Gallager, course materials for 6.450 Principles of Digital Communications I, Fall 2006. MIT OpenCourseWare (http://ocw.mit.edu/), Massachusetts Institute of Technology. Downloaded on [DD Month YYYY]. 38 CHAPTER 2. CODING FOR DISCRETE SOURCES The WLLN, in the form of (2.16), applies much more generally than the simple case of iid rv’s. In fact, (2.16) provides the central link between probability models and the real phenomena being modeled. One can observe the outcomes both for the model and reality, but probabilities are assigned only for the model. The WLLN, applied to a sequence of rv’s in the model, and the concentration property (if it exists), applied to the corresponding real phenomenon, provide the basic check on whether the model corresponds reasonably to reality. 2.7.2 The asymptotic equipartition property This section starts with a sequence of iid random symbols and defines a sequence of random variables (rv’s) as functions of those symbols. The WLLN, applied to these rv’s, will permit the classification of sample sequences of symbols as being ‘typical’ or not, and then lead to the results alluded to earlier. Let X1 , X2 , . . . be a sequence of iid discrete random symbols with a common pmf pX (x)>0, x∈X . For each symbol x in the alphabet X , let w(x) = − log pX (x). For each Xk in the sequence, define W (Xk ) to be the rv that takes the value w(x) for Xk = x. Then W (X1 ), W (X2 ), . . . is a sequence of iid discrete rv’s, each with mean � pX (x) log pX (x) = H[X], (2.17) E[W (Xk )] = − x∈X where H[X] is the entropy of the random symbol X. The rv W (Xk ) is the log pmf of Xk and the entropy of Xk is the mean of W (Xk ). The most important property of the log pmf for iid random symbols comes from observing, for example, that for the event X1 = x1 , X2 = x2 , the outcome for W (X1 ) + W (X2 ) is w(x1 ) + w(x2 ) = − log pX (x1 ) − log pX (x2 ) = − log{pX1 X2 (x1 x2 )}. (2.18) In other words, the joint pmf for independent random symbols is the product of the individual pmf’s, and therefore the log of the joint pmf is the sum of the logs of the individual pmf ’s. We can generalize (2.18) to a string of n random symbols, X n = (X1 , . . . , Xn ). For an event X n = x n where x n = (x1 , . . . , xn ), the outcome for the sum W (X1 ) + · · · + W (Xn ) is �n �n w(xk ) = − log pX (xk ) = − log pX n (x n ). (2.19) k=1 k=1 The WLLN can now be applied to the sample average of the log pmfs. Let AnW = − log pX n (X n ) W (X1 ) + · · · + W (Xn ) = n n (2.20) be the sample average of the log pmf. From (2.15), it follows that �� � σ2 � Pr �AnW − E[W (X)] � ≥ ε ≤ W2 . nε Substituting (2.17) and (2.20) into (2.21), � � �� � � − log pX n (X n ) σ2 � � − H[X]� ≥ ε ≤ W2 . Pr � n nε (2.21) (2.22) Cite as: Robert Gallager, course materials for 6.450 Principles of Digital Communications I, Fall 2006. MIT OpenCourseWare (http://ocw.mit.edu/), Massachusetts Institute of Technology. Downloaded on [DD Month YYYY]. 2.7. THE AEP AND THE SOURCE CODING THEOREMS In order to interpret this result, define the typical set Tεn for any ε > 0 as � � � � � � − log pX n (x n ) n n � � Tε = x : � − H[X]� < ε . n 39 (2.23) Thus Tεn is the set of source strings of length n for which the sample average of the log pmf is within ε of its mean H[X]. Eq. (2.22) then states that the aggregrate probability of all strings 2 /(nε2 ). Thus, of length n not in Tεn is at most σW Pr(X n ∈ Tεn ) ≥ 1 − 2 σW . nε2 (2.24) As n increases, the aggregate probability of Tεn approaches 1 for any given ε > 0, so Tεn is certainly a typical set of source strings. This is illustrated in Figure 2.15. 1 Pr(Tε2n ) Pr(Tεn ) � � � � �� F 2n (w) � � n AW FAW (w) � � w H−ε H H+ε Figure 2.15: Sketch of the distribution function of the sample average log pmf. As n increases, the distribution function approaches a unit step at H. The typical set is the set of sample strings of length n for which the sample average log pmf stays within ε of H; as illustrated, its probability approaches 1 as n → ∞. Rewrite (2.23) in the form � � n n n Tε = x : n(H[X] − ε) < − log pX n (x ) < n(H[X] + ε) . Multiplying by −1 and exponentiating, � � Tεn = x n : 2−n(H[X]+ε) < pX n (x n ) < 2−n(H[X]−ε) . (2.25) Eq. (2.25) has the intuitive connotation that the n-strings in Tεn are approximately equiprobable. This is the same kind of approximation that one would use in saying that 10−1001 ≈ 10−1000 ; these numbers differ by a factor of 10, but for such small numbers it makes sense to compare the exponents rather than the numbers themselves. In the same way, the ratio of the upper to lower bound in (2.25) is 22εn , which grows unboundedly with n for fixed ε. However, as seen in (2.23), − n1 log pX n (x n ) is approximately equal to H[X] for all x n ∈ Tεn . This is the important notion, and it does no harm to think of the n-strings in Tεn as being approximately equiprobable. The set of all n-strings of source symbols is thus separated into the typical set Tεn and the complementary atypical set (Tεn )c . The atypical set has aggregate probability no greater than 2 /(nε2 ), and the elements of the typical set are approximately equiprobable (in this peculiar σW sense), each with probability about 2−nH[X] . Cite as: Robert Gallager, course materials for 6.450 Principles of Digital Communications I, Fall 2006. MIT OpenCourseWare (http://ocw.mit.edu/), Massachusetts Institute of Technology. Downloaded on [DD Month YYYY]. 40 CHAPTER 2. CODING FOR DISCRETE SOURCES The typical set Tεn depends on the choice of ε. As ε decreases, the equiprobable approximation (2.25) becomes tighter, but the bound (2.24) on the probability of the typical set is further from 1. As n increases, however, ε can be slowly decreased, thus bringing the probability of the typical set closer to 1 and simultaneously tightening the bounds on equiprobable strings. Let us now estimate the number of elements |Tεn | in the typical set. Since pX n (x n ) > 2−n(H[X]+ε) for each x n ∈ Tεn , � pX n (x n ) > |Tεn | 2−n(H[X]+ε) . 1≥ x n ∈Tεn This implies that |Tεn | < 2n(H[X]+ε) . In other words, since each x n ∈ Tεn contributes at least 2−n(H[X]+ε) to the probability of Tεn , the number of these contributions can be no greater than 2n(H[X]+ε) . 2 /(nε2 ), |T n | can be lower bounded by Conversely, since Pr(Tεn ) ≥ 1 − σW ε 1− 2 � σW ≤ pX n (x n ) < |Tεn |2−n(H[X]−ε) , 2 nε n n x ∈Tε 2 /(nε2 )]2n(H[X]−ε) . In summary, which implies |Tεn | > [1 − σW � 2 � σW 1 − 2 2n(H[X]−ε) < |Tεn | < 2n(H[X]+ε) . nε (2.26) For large n, then, the typical set Tεn has aggregate probability approximately 1 and contains approximately 2nH[X] elements, each of which has probability approximately 2−nH[X] . That is, asymptotically for very large n, the random symbol X n resembles an equiprobable source with alphabet size 2nH[X] . 2 /(nε2 ) in many of the equations above is simply a particular upper bound to The quantity σW the probability of the atypical set. It becomes arbitrarily small as n increases for any fixed ε > 0. Thus it is insightful to simply replace this quantity with a real number δ; for any such 2 /(nε2 ) ≤ δ for large enough n. δ > 0 and any ε > 0, σW This set of results, summarized in the following theorem, is known as the asymptotic equipartition property (AEP). Theorem 2.7.1 (Asymptotic equipartition property). Let Xn be a string of n iid discrete random symbols {Xk ; 1 ≤ k ≤ n} each with entropy H[X]. For all δ > 0 and all sufficiently large n, Pr(Tεn ) ≥ 1 − δ and |Tεn | is bounded by (1 − δ)2n(H[X]−ε) < |Tεn | < 2n(H[X]+ε) . (2.27) Finally, note that the total number of different strings of length n from a source with alphabet size M is M n . For non-equiprobable sources, namely sources with H[X] < log M , the ratio of the number of typical strings to total strings is approximately 2−n(log M −H[X]) , which approaches 0 exponentially with n. Thus, for large n, the great majority of n-strings are atypical. It may be somewhat surprising that this great majority counts for so little in probabilistic terms. As shown in Exercise 2.26, the most probable of the individual sequences are also atypical. There are too few of them, however, to have any significance. We next consider source coding in the light of the AEP. Cite as: Robert Gallager, course materials for 6.450 Principles of Digital Communications I, Fall 2006. MIT OpenCourseWare (http://ocw.mit.edu/), Massachusetts Institute of Technology. Downloaded on [DD Month YYYY]. 2.7. THE AEP AND THE SOURCE CODING THEOREMS 2.7.3 41 Source coding theorems Motivated by the AEP, we can take the approach that an encoder operating on strings of n source symbols need only provide a codeword for each string x n in the typical set Tεn . If a sequence x n occurs that is not in Tεn , then a source coding failure is declared. Since the probability of xn ∈ / Tεn can be made arbitrarily small by choosing n large enough, this situation is tolerable. In this approach, since there are less than 2n(H[X]+ε) strings of length n in Tεn , the number of source codewords that need to be provided is fewer than 2n(H[X]+ε) . Choosing fixed-length codewords of length n(H[X] + ε) is more than sufficient and even allows for an extra codeword, if desired, to indicate that a coding failure has occurred. In bits per source symbol, taking the ceiling function into account, L ≤ H[X] + ε + 1/n. Note that ε > 0 is arbitrary, and for any such ε, Pr{failure} → 0 as n → ∞. This proves the following theorem: Theorem 2.7.2 (Fixed-to-fixed-length source coding theorem). For any discrete mem­ oryless source with entropy H[X], any ε > 0, any δ > 0, and any sufficiently large n, there is a fixed-to-fixed-length source code with Pr{failure} ≤ δ that maps blocks of n source symbols into fixed-length codewords of length L ≤ H[X] + ε + 1/n bits per source symbol. We saw in section 2.2 that the use of fixed-to-fixed-length source coding requires log M bits per source symbol if unique decodability is required (i.e., no failures are allowed), and now we see that this is reduced to arbitrarily little more than H[X] bits per source symbol if arbitrarily rare failures are allowed. This is a good example of a situation where ‘arbitrarily small δ > 0’ and 0 behave very differently. There is also a converse to this theorem following from the other side of the AEP theorem. This says that the error probability approaches 1 for large n if strictly fewer than H[X] bits per source symbol are provided. Theorem 2.7.3 (Converse for fixed-to-fixed-length codes). Let Xn be a string of n iid discrete random symbols {Xk ; 1 ≤ k ≤ n}, with entropy H[X] each. For any ν > 0, let Xn be encoded into fixed-length codewords of length n(H[X] − ν) bits. For every δ > 0 and for all sufficiently large n given δ, Pr{failure} > 1 − δ − 2−νn/2 . (2.28) Proof: Apply the AEP, Theorem 2.7.1, with ε = ν/2. Codewords can be provided for at most 2n(H[X]−ν) typical source n-sequences, and from (2.25) each of these has a probability at most 2−n(H[X]−ν/2) . Thus the aggregate probability of typical sequences for which codewords are provided is at most 2−nν/2 . From the AEP theorem, Pr{Tεn } ≥ 1 − δ is satisfied for large enough n. Codewords15 can be provided for at most a subset of Tεn of probability 2−nν/2 , and the remaining elements of Tεn must all lead to errors, thus yielding (2.28). In going from fixed-length codes of slightly more than H[X] bits per source symbol to codes of slightly less than H[X] bits per source symbol, the probability of failure goes from almost 0 to almost 1, and as n increases, those limits are approached more and more closely. 15 Note that the proof allows codewords to be provided for atypical sequences; it simply says that a large portion of the typical set cannot be encoded. Cite as: Robert Gallager, course materials for 6.450 Principles of Digital Communications I, Fall 2006. MIT OpenCourseWare (http://ocw.mit.edu/), Massachusetts Institute of Technology. Downloaded on [DD Month YYYY]. 42 2.7.4 CHAPTER 2. CODING FOR DISCRETE SOURCES The entropy bound for general classes of codes We have seen that the expected number of encoded bits per source symbol is lower bounded by H[X] for iid sources using either fixed-to-fixed-length or fixed-to-variable-length codes. The details differ in the sense that very improbable sequences are simply dropped in fixed-length schemes but have abnormally long encodings, leading to buffer overflows, in variable-length schemes. We now show that other types of codes, such as variable-to-fixed, variable-to-variable, and even more general codes are also subject to the entropy limit. Rather than describing the highly varied possible nature of these source codes, this will be shown by simply defining certain properties that the associated decoders must have. By doing this, it is also shown that yet undiscovered coding schemes must also be subject to the same limits. The fixed-to-fixed-length converse in the last subsection is the key to this. For any encoder, there must be a decoder that maps the encoded bit sequence back into the source symbol sequence. For prefix-free codes on k-tuples of source symbols, the decoder waits for each variable length codeword to arrive, maps it into the corresponding k-tuple of source symbols, and then starts decoding for the next k-tuple. For fixed-to-fixed-length schemes, the decoder waits for a block of code symbols and then decodes the corresponding block of source symbols. In general, the source produces a non-ending sequence X1 , X2 , . . . of source letters which are encoded into a non-ending sequence of encoded binary digits. The decoder observes this encoded sequence and decodes source symbol Xn when enough bits have arrived to make a decision on it. For any given coding and decoding scheme for a given iid source, define the rv Dn as the number of received bits that permit a decision on X n = X1 , . . . , Xn . This includes the possibility of coders and decoders for which some sample source strings are decodedeincorrectly or postponed infinitely. For these x n , the sample value of Dn is taken to be infinite. It is assumed, however, that all decisions are final in the sense that the decoder cannot decide on a particular x n after observing an initial string of the encoded sequence and then change that decision after observing more of the encoded sequence. What we would like is a scheme in which decoding is correct with high probability and the sample value of the rate, Dn /n, is small with high probability. What the following theorem shows is that for large n, the sample rate can be strictly below the entropy only with vanishingly small probability. This then shows that the entropy lower bounds the data rate in this strong sense. Theorem 2.7.4 (Converse for general coders/decoders for iid sources). Let X∞ be a sequence of discrete random symbols {Xk ; 1 ≤ k ≤ ∞}. For each integer n ≥ 1, let Xn be the first n of those symbols. For any given encoder and decoder, let Dn be the number of received bits at which the decoder can correctly decode Xn . Then for any ν > 0 and δ > 0, and for any sufficiently large n given ν and δ, Pr{Dn ≤ n[H[X] − ν]} < δ + 2−νn/2 . (2.29) Proof: For any sample value x ∞ of the source sequence, let y ∞ denote the encoded sequence. For any given integer n ≥ 1, let m = n[H[X]−ν] . Suppose that x n is decoded upon observation of y j for some j ≤ m. Since decisions are final, there is only one source n-string, namely x n , that can be decoded by time y m is observed. This means that out of the 2m possible initial Cite as: Robert Gallager, course materials for 6.450 Principles of Digital Communications I, Fall 2006. MIT OpenCourseWare (http://ocw.mit.edu/), Massachusetts Institute of Technology. Downloaded on [DD Month YYYY]. 2.8. MARKOV SOURCES 43 m-strings from the encoder, there can be at most16 2m n-strings from the source that be decoded from the observation of the first m encoded outputs. The aggregate probability of any set of 2m source n-strings is bounded in Theorem 2.7.3, and (2.29) simply repeats that bound. 2.8 Markov sources The basic coding results for discrete memoryless sources have now been derived. Many of the results, in particular the Kraft inequality, the entropy bounds on expected length for uniquely­ decodable codes, and the Huffman algorithm, do not depend on the independence of successive source symbols. In this section, these results are extended to sources defined in terms of finite-state Markov chains. The state of the Markov chain17 is used to represent the “memory” of the source. Labels on the transitions between states are used to represent the next symbol out of the source. Thus, for example, the state could be the previous symbol from the source, or could be the previous 300 symbols. It is possible to model as much memory as desired while staying in the regime of finite-state Markov chains. Example 2.8.1. Consider a binary source with outputs X1 , X2 , . . . . Assume that the symbol probabilities for Xm are conditioned on Xk−2 and Xk−1 but are independent of all previous symbols given these past 2 symbols. This pair of previous symbols is modeled by a state Sk−1 . The alphabet of possible states is then the set of binary pairs, S = {[00], [01], [10], [11]}. In Figure 2.16, the states are represented as the nodes of the graph representing the Markov chain, and the source outputs are labels on the graph transitions. Note, for example, that from the state Sk−1 = [01] (representing Xk−2 =0, Xk−1 =1), the output Xk =1 causes a transition to Sk = [11] (representing Xk−1 =1, Xk =1). The chain is assumed to start at time 0 in a state S0 given by some arbitrary pmf. �� ��� 1; 0.1 � [01] [00] 0; 0.9 �� �� � �� � �� �� 1; 0.5 �� 0; 0.5 1; 0.5 ��0; 0.5 �� �� �� � � �� [10] � [11] �� 1; 0.9 �� 0; 0.1 � Figure 2.16: Markov source: Each transition s → s is labeled by the corresponding source output and the transition probability Pr{Sk = s|Sk−1 = s }. Note that this particular source is characterized by long strings of zeros and long strings of ones interspersed with short transition regions. For example, starting in state 00, a representative 16 There are two reasons why the number of decoded n-strings of source symbols by time m can be less than 2m . The first is that the first n source symbols might not be decodable until after the mth encoded bit is received. The second is that multiple m-strings of encoded bits might lead to decoded strings with the same first n source symbols. 17 The basic results about finite-state Markov chains, including those used here, are established in many texts such as [8] and [25] . These results are important in the further study of digital communcation, but are not essential here. Cite as: Robert Gallager, course materials for 6.450 Principles of Digital Communications I, Fall 2006. MIT OpenCourseWare (http://ocw.mit.edu/), Massachusetts Institute of Technology. Downloaded on [DD Month YYYY]. 44 CHAPTER 2. CODING FOR DISCRETE SOURCES output would be 00000000101111111111111011111111010100000000 · · · Note that if sk = [xk−1 xk ] then the next state must be either sk+1 = [xk 0] or sk+1 = [xk 1]; i.e., each state has only two transitions coming out of it. The above example is now generalized to an arbitrary discrete Markov source. Definition 2.8.1. A finite-state Markov chain is a sequence S0 , S1 , . . . of discrete random sym­ bols from a finite alphabet, S. There is a pmf q0 (s), s ∈ S on S0 , and there is a conditional pmf Q(s|s ) such that for all m ≥ 1, all s ∈ S, and all s ∈ S, Pr(Sk =s| Sk−1 =s ) = Pr(Sk =s| Sk−1 =s , . . . , S0 =s0 ) = Q(s| s ). (2.30) There is said to be a transition from s to s, denoted s → s, if Q(s| s ) > 0. Note that (2.30) says, first, that the conditional probability of a state, given the past, depends only on the previous state, and second, that these transition probabilities Q(s|s ) do not change with time. Definition 2.8.2. A Markov source is a sequence of discrete random symbols X1 , X2 , . . . with a common alphabet X which is based on a finite-state Markov chain S0 , S1 , . . . . Each transition (s → s) in the Markov chain is labeled with a symbol from X ; each symbol from X can appear on at most one outgoing transition from each state. Note that the state alphabet S and the source alphabet X are in general different. Since each source symbol appears on at most one transition from each state, the initial state S0 =s0 , combined with the source output, X1 =x1 , X2 =x2 , . . . , uniquely identifies the state sequence, and, of course, the state sequence uniquely specifies the source output sequence. If x ∈ X labels the transition s → s, then the conditional probability of that x is given by P (x| s ) = Q(s| s ). Thus, for example, in the transition [00] → [0]1 in Figure 2.16, Q([01]| [00]) = P (1| [00]). The reason for distinguishing the Markov chain alphabet from the source output alphabet is to allow the state to represent an arbitrary combination of past events rather than just the previous source output. It is this feature that permits Markov source models to reasonably model both simple and complex forms of memory. A state s is accessible from state s in a Markov chain if there is a path in the corresponding graph from s → s, i.e., if Pr(Sk =s| S0 =s ) > 0 for some k > 0. The period of a state s is the greatest common divisor of the set of integers k ≥ 1 for which Pr(Sk =s| S0 =s) > 0. A finite-state Markov chain is ergodic if all states are accessible from all other states and if all states are aperiodic, i.e., have period 1. We will consider only Markov sources for which the Markov chain is ergodic. An important fact about ergodic Markov chains is that the chain has steady-state probabilities q(s) for all s ∈ S, given by the unique solution to the linear equations � q(s )Q(s| s ); s ∈ S (2.31) q(s) = � s
∈S q(s) = 1. s∈S These steady-state probabilities are approached asymptotically from any starting state, i.e., lim Pr(Sk =s| S0 =s ) = q(s) k→∞ for all s, s ∈ S . (2.32) Cite as: Robert Gallager, course materials for 6.450 Principles of Digital Communications I, Fall 2006. MIT OpenCourseWare (http://ocw.mit.edu/), Massachusetts Institute of Technology. Downloaded on [DD Month YYYY]. 2.8. MARKOV SOURCES 2.8.1 45 Coding for Markov sources The simplest approach to coding for Markov sources is that of using a separate prefix-free code for each state in the underlying Markov chain. That is, for each s ∈ S, select a prefix-free code whose lengths l(x, s) are appropriate for the conditional pmf P (x| s) > 0.�The codeword lengths for the code used in state s must of course satisfy the Kraft inequality x 2−l(x,s) ≤ 1. The minimum expected length, Lmin (s) for each such code can be generated by the Huffman algorithm and satisfies H[X| s] ≤ Lmin (s) < H[X| s] + 1. � where, for each s ∈ S, H[X| s] = x −P (x| s) log P (x| s). (2.33) If the initial state S0 is chosen according to the steady-state pmf {q(s); s ∈ S}, then, from (2.31), the Markov chain remains in steady state and the overall expected codeword length is given by H[X| S] ≤ Lmin < H[X| S] + 1, (2.34) where Lmin = � q(s)Lmin (s) and (2.35) s∈S H[X| S] = � q(s)H[X| s]. (2.36) s∈S Assume that the encoder transmits the initial state s0 at time 0. If M  is the number of elements in the state space, then this can be done with log M   bits, but this can be ignored since it is done only at the beginning of transmission and does not affect the long term expected number of bits per source symbol. The encoder then successively encodes each source symbol xk using the code for the state at time k − 1. The decoder, after decoding the initial state s0 , can decode x1 using the code based on state s0 . After determining s1 from s0 and x1 , the decoder can decode x2 using the code based on s1 . The decoder can continue decoding each source symbol, and thus the overall code is uniquely decodable. We next must understand the meaning of the conditional entropy in (2.36). 2.8.2 Conditional entropy It turns out that the conditional entropy H[X| S] plays the same role in coding for Markov sources as the ordinary entropy H[X] plays for the memoryless case. Rewriting (2.36), H[X| S] = �� q(s)P (x| s) log s∈S x∈X 1 . P (x| s) This is the expected value of the rv log[1/P (X| S)]. An important entropy relation, for arbitrary discrete rv’s, is H[XS] = H[S] + H[X| S]. (2.37) Cite as: Robert Gallager, course materials for 6.450 Principles of Digital Communications I, Fall 2006. MIT OpenCourseWare (http://ocw.mit.edu/), Massachusetts Institute of Technology. Downloaded on [DD Month YYYY]. 46 CHAPTER 2. CODING FOR DISCRETE SOURCES To see this, � 1 q(s)P (x| s) s,x � � 1 1 = + q(s)P (x| s) log q(s)P (x| s) log q(s) P (x| s) s,x s,x H[XS] = q(s)P (x| s) log = H[S] + H[X| S]. Exercise 2.19 demonstrates that H[XS] ≤ H[S] + H[X] Comparing this and (2.37), it follows that H[X| S] ≤ H[X]. (2.38) This is an important inequality in information theory. If the entropy H[X] as a measure of mean uncertainty, then the conditional entropy H[X| S] should be viewed as a measure of mean uncer­ tainty after the observation of the outcome of S. If X and S are not statistically independent, then intuition suggests that the observation of S should reduce the mean uncertainty in X; this equation indeed verifies this. Example 2.8.2. Consider Figure 2.16 again. It is clear from symmetry that, in steady state, pX (0) = pX (1) = 1/2. Thus H[X] = 1 bit. Conditional on S=00, X is binary with pmf {0.1, 0.9}, so H[X| [00]] = −0.1 log 0.1 − 0.9 log 0.9 = 0.47 bits. Similarly, H[X| [11]] = 0.47 bits, and H[X| [01]] = H[X| [10]] = 1 bit. The solution to the steady-state equations in (2.31) is q([00]) = q([11]) = 5/12 and q([01]) = q([10]) = 1/12. Thus, the conditional entropy, averaged over the states, is H[X| S] = 0.558 bits. For this example, it is particularly silly to use a different prefix-free code for the source output for each prior state. The problem is that the source is binary, and thus the prefix-free code will have length 1 for each symbol no matter what the state. As with the memoryless case, however, the use of fixed-to-variable-length codes is a solution to these problems of small alphabet sizes and integer constraints on codeword lengths. Let E[L(X n )]min,s be the minimum expected length of a prefix-free code for X n conditional on starting in state s. Then, applying (2.13) to the situation here, H[X n | s] ≤ E[L(X n )]min,s < H[X n | s] + 1. Assume as before that the Markov chain starts in steady state S0 . Thus it remains in steady state at each future time. Furthermore assume that the initial sample state is known at the decoder. Then the sample state continues to be known at each future time. Using a minimum expected length code for each initial sample state, H[X n | S0 ] ≤ E[L(X n )]min,S0 < H[X n | S0 ] + 1. (2.39) Since the Markov source remains in steady state, the average entropy of each source symbol given the state is H(X | S0 ), so intuition suggests (and Exercise 2.32 verifies) that H[X n | S0 ] = nH[X| S0 ]. (2.40) Cite as: Robert Gallager, course materials for 6.450 Principles of Digital Communications I, Fall 2006. MIT OpenCourseWare (http://ocw.mit.edu/), Massachusetts Institute of Technology. Downloaded on [DD Month YYYY]. 2.9. LEMPEL-ZIV UNIVERSAL DATA COMPRESSION 47 Defining Lmin,n = E[L(X n )]min,S0 /n as the minimum expected codeword length per input symbol when starting in steady state, H[X| S0 ] ≤ Lmin,n < H[X| S0 ] + 1/n. (2.41) The asymptotic equipartition property (AEP) also holds for Markov sources. Here, however, there are18 approximately 2nH[X| S] typical strings of length n, each with probability approxi­ mately equal to 2−nH[X| S] . It follows as in the memoryless case that H[X| S] is the minimum possible rate at which source symbols can be encoded subject either to unique decodability or to fixed-to-fixed-length encoding with small probability of failure. The arguments are essentially the same as in the memoryless case. The analysis of Markov sources will not be carried further here, since the additional required ideas are minor modifications of the memoryless case. Curiously, most of our insights and understanding about souce coding come from memoryless sources. At the same time, however, most sources of practical importance can be insightfully modeled as Markov and hardly any can be reasonably modeled as memoryless. In dealing with practical sources, we combine the insights from the memoryless case with modifications suggested by Markov memory. The AEP can be generalized to a still more general class of discrete sources called ergodic sources. These are essentially sources for which sample time averages converge in some proba­ bilistic sense to ensemble averages. We do not have the machinery to define ergodicity, and the additional insight that would arise from studying the AEP for this class would consist primarily of mathematical refinements. 2.9 Lempel-Ziv universal data compression The Lempel-Ziv data compression algorithms differ from the source coding algorithms studied in previous sections in the following ways: • They use variable-to-variable-length codes in which both the number of source symbols encoded and the number of encoded bits per codeword are variable. Moreover, the codes are time-varying. • They do not require prior knowledge of the source statistics, yet over time they adapt so that the average codeword length L per source symbol is minimized in some sense to be discussed later. Such algorithms are called universal. • They have been widely used in practice; they provide a simple approach to understanding universal data compression even though newer schemes now exist. The Lempel-Ziv compression algorithms were developed in 1977-78. The first, LZ77 [37], uses string-matching on a sliding window; the second, LZ78 [38], uses an adaptive dictionary. The LZ78 was algorithm was implemented many years ago in UNIX compress and in many other places. Implementations of LZ77 appeared somewhat later (Stac Stacker, Microsoft Windows) and is still widely used. 18 There are additional details here about whether the typical sequences include the initial state or not, but these differences become unimportant as n becomes large. Cite as: Robert Gallager, course materials for 6.450 Principles of Digital Communications I, Fall 2006. MIT OpenCourseWare (http://ocw.mit.edu/), Massachusetts Institute of Technology. Downloaded on [DD Month YYYY]. 48 CHAPTER 2. CODING FOR DISCRETE SOURCES In this section, the LZ77 algorithm is described. accompanied by a high-level description of why it works. Finally, an approximate analysis of its performance on Markov sources is given, showing that it is effectively optimal.19 In other words, although this algorithm operates in ignorance of the source statistics, it compresses substantially as well as the best algorithm designed to work with those statistics. 2.9.1 The LZ77 algorithm The LZ77 algorithm compresses a sequence x = x1 , x2 , . . . from some given discrete alphabet X of size M = |X |. At this point, no probabilistic model is assumed for the source, so x is simply a sequence of symbols, not a sequence of random symbols. A subsequence (xm , xm+1 , . . . , xn ) of x is represented by x nm . The algorithm keeps the w most recently encoded source symbols in memory. This is called a sliding window of size w. The number w is large, and can be thought of as being in the range of 210 to 220 , say. The parameter w is chosen to be a power of 2. Both complexity and, typically, performance increase with w. Briefly, the algorithm operates as follows. Suppose that at some time the source symbols x P1 have been encoded. The encoder looks for the longest match, say of length n, between the +n +n−u not-yet-encoded n-string x PP +1 and a stored string x PP +1−u starting in the window of length w. The clever algorithmic idea in LZ77 is to encode this string of n symbols simply by encoding the integers n and u; i.e., by pointing to the previous occurrence of this string in the sliding window. If the decoder maintains an identical window, then it can look up the string x PP +n−u +1−u , decode it, and keep up with the encoder. More precisely, the LZ77 algorithm operates as follows: 1. Encode the first w symbols in a fixed-length code without compression, using log M  bits per symbol. (Since wlog M  will be a vanishing fraction of the total number of encoded bits, the efficiency of encoding this preamble is unimportant, at least in theory.) 2. Set the pointer P = w. (This indicates that all symbols up to and including xP have been encoded.) P +n−u 3. Find the largest n ≥ 2 such that x PP +n +1 = x P +1−u for some u in the range 1 ≤ u ≤ w. (Find the longest match between the not-yet-encoded symbols starting at P + 1 and a string of symbols starting in the window; let n be the length of that longest match and u the distance +n back into the window to the start of that match.) The string x PP +1 is encoded by encoding the integers n and u.) Here are two examples of finding this longest match. In the first, the length of the match is n = 3 and the match starts u = 7 symbols before the pointer. In the second, the length of the match is 4 and it starts u = 2 symbols before the pointer. Tis illustrates that that the string and its match can overlap. 19 A proof of this optimality for discrete ergodic sources has been given by Wyner and Ziv [36]. Cite as: Robert Gallager, course materials for 6.450 Principles of Digital Communications I, Fall 2006. MIT OpenCourseWare (http://ocw.mit.edu/), Massachusetts Institute of Technology. Downloaded on [DD Month YYYY]. 2.9. LEMPEL-ZIV UNIVERSAL DATA COMPRESSION 49 w = window � � P Match � a c d b c d a c a b a u=7 � c d b w = window � a b c n =� 3 a d a b a a c b a b a a b d c a··· d c a··· � P Match c b c d a b u=2 � n = 4� � a b a b If no match exists for n ≥ 2, then, independently of whether a match exists for n = 1, set n = 1 and directly encode the single source symbol xP +1 without compression. 4. Encode the integer n into a codeword from the unary-binary code. In the unary-binary code, a positive integer n is encoded into the binary representation of n, preceded by a prefix of log2 n zeroes; i.e., n 1 2 3 4 5 6 7 8 prefix 0 0 00 00 00 00 000 base 2 expansion 1 10 11 100 101 110 111 1000 codeword 1 010 011 00100 00101 00110 00111 0001000 Thus the codewords starting with 0k 1 correspond to the set of 2k integers in the range 2k ≤ n ≤ 2k+1 − 1. This code is prefix-free (picture the corresponding binary tree). It can be seen that the codeword for integer n has length 2 log n + 1; it is seen later that this is negligible compared with the length of the encoding for u. 5. If n > 1, encode the positive integer u ≤ w using a fixed-length code of length log w bits. (At this point the decoder knows n, and can simply count back by u in the previously decoded string to find the appropriate n-tuple, even if there is overlap as above.) 6. Set the pointer P to P + n and go to step (3). (Iterate forever.) 2.9.2 Why LZ77 works The motivation behind LZ77 is information-theoretic. The underlying idea is that if the unknown source happens to be, say, a Markov source of entropy H[X| S], then the AEP says that, for any large n, there are roughly 2nH[X| S] typical source strings of length n. On the other hand, Cite as: Robert Gallager, course materials for 6.450 Principles of Digital Communications I, Fall 2006. MIT OpenCourseWare (http://ocw.mit.edu/), Massachusetts Institute of Technology. Downloaded on [DD Month YYYY]. 50 CHAPTER 2. CODING FOR DISCRETE SOURCES a window of size w contains w source strings of length n, counting duplications. This means that if w  2nH[X| S] , then most typical sequences of length n cannot be found in the window, suggesting that matches of length n are unlikely. Similarly, if w  2nH[X| S] , then it is reasonable to suspect that most typical sequences will be in the window, suggesting that matches of length n or more are likely. The above argument, approximate and vague as it is, suggests that in order to achieve large typical match sizes nt , the window w should be exponentially large, on the order of 2nt H[X| S] , which means log w ; typical match size. (2.42) nt ≈ H[X | S] The encoding for a match requires log w bits for the match location and 2 log nt + 1 for the match size nt . Since nt is proportional to log w, log nt is negligible compared to log w for very large w. Thus, for the typical case, about log w bits are used to encode about nt source symbols. Thus, from (2.42), the required rate, in bits per source symbol, is about L ≈ H[X| S]. The above argument is very imprecise, but the conclusion is that, for very large window size, L is reduced to the value required when the source is known and an optimal fixed-to-variable prefix-free code is used. The imprecision above involves more than simply ignoring the approximation factors in the AEP. A more conceptual issue is that the strings of source symbols that must be encoded are somewhat special since they start at the end of previous matches. The other conceptual difficulty comes from ignoring the duplications of typical sequences within the window. This argument has been made precise by Wyner and Ziv [36]. 2.9.3 Discussion Let us recapitulate the basic ideas behind the LZ77 algorithm: 1. Let Nx be the number of occurrences of symbol x in a window of very large size w. If the source satisfies the WLLN, then the relative frequency Nx /w of appearances of x in the window will satisfy Nx /w ≈ pX (x) with high probability. Similarly, let Nx n be the number of occurrences of x n which start in the window. The relative frequency Nx n /w will then satisfy Nx n /w ≈ pX n (x n ) with high probability for very large w. This association of relative frequencies with probabilities is what makes LZ77 a universal algorithm which needs no prior knowledge of source statistics.20 2. Next, as explained in the previous section, the probability of a typical source string x n for a Markov source is approximately 2−nH[X| S] . If w >> 2nH[X| S] , then, according to the previous item, Nx n ≈ wpX n (x n ) should be large and x n should occur in the window with high probability. Alternatively, if w << 2nH[X| S] , then x n will probably not occur. Consequently the match will usually occur for n ≈ (log w)/H[X| S] as w becomes very large. 3. Finally, it takes about log w bits to point to the best match in the window. The unarybinary code uses 2 log n + 1 bits to encode the length n of the match. For typical n, this is on the order of 2 log(log w/H[X| S]) which is negigible for large enough w compared to log w. 20 As Yogi Berra said, “You can observe a whole lot just by watchin’.” Cite as: Robert Gallager, course materials for 6.450 Principles of Digital Communications I, Fall 2006. MIT OpenCourseWare (http://ocw.mit.edu/), Massachusetts Institute of Technology. Downloaded on [DD Month YYYY]. 2.10. SUMMARY OF DISCRETE SOURCE CODING 51 Consequently, LZ77 requires about log w encoded bits for each group of about (log w)/H[X | S] source symbols, so it nearly achieves the optimal efficiency of L = H[X| S] bits/symbol, as w becomes very large. Discrete sources, as they appear in practice, often can be viewed over different time scales. Over very long time scales, or over the sequences presented to different physical encoders running the same algorithm, there is often very little common structure, sometimes varying from one language to another, or varying from text in a language to data from something else. Over shorter time frames, corresponding to a single file or a single application type, there is often more structure, such as that in similar types of documents from the same language. Here it is more reasonable to view the source output as a finite length segment of, say, the output of an ergodic Markov source. What this means is that universal data compression algorithms must be tested in practice. The fact that they behave optimally for unknown sources that can be modeled to satisfy the AEP is an important guide, but not the whole story. The above view of different time scales also indicates that a larger window need not always improve the performance of the LZ77 algorithm. It suggests that long matches will be more likely in recent portions of the window, so that fixed length encoding of the window position is not the best approach. If shorter codewords are used for more recent matches, then it requires a shorter time for efficient coding to start to occur when the source statistics abruptly change. It also then makes sense to start coding from some arbitrary window known to both encoder and decoder rather than filling the entire window with data before starting to use the LZ77 alogorithm. 2.10 Summary of discrete source coding Discrete source coding is important both for discrete sources such as text and computer files and also as an inner layer for discrete-time analog sequences and fully analog sources. It is essential to focus on the range of possible outputs from the source rather than any one particular output. It is also important to focus on probabilistic models so as to achieve the best compression for the most common outputs with less care for very rare outputs. Even universal coding techniques, such as LZ77, which are designed to work well in the absence of a probability model, require probability models to understand and evaluate how they work. Variable-length source coding is the simplest way to provide good compression for common source outputs at the expense of rare outputs. The necessity to concatenate successive variablelength codewords leads to the non-probabilistic concept of unique decodability. Prefix-free codes provide a simple class of uniquely-decodable codes. Both prefix-free codes and the more general class of uniquely-decodable codes satisfy the Kraft inequality on the number of possible code words of each length. Moreover, for any set of lengths satisfying the Kraft inequality, there is a simple procedure for constructing a prefix-free code with those lengths. Since the expected length, and other important properties of codes, depend only on the codewords lengths (and how they are assigned to source symbols), there is usually little reason to use variable-length codes that are not also prefix free. For a DMS with given probabilities on the symbols of a source code, the entropy is a lower bound on the expected length of uniquely decodable codes. The Huffman algorithm provides a Cite as: Robert Gallager, course materials for 6.450 Principles of Digital Communications I, Fall 2006. MIT OpenCourseWare (http://ocw.mit.edu/), Massachusetts Institute of Technology. Downloaded on [DD Month YYYY]. 52 CHAPTER 2. CODING FOR DISCRETE SOURCES simple procedure for finding an optimal (in the sense of minimum expected codeword length) variable-length prefix-free code. The Huffman algorithm is also useful for deriving properties about optimal variable length source codes (see Exercises 2.12 to 2.18). All the properties of variable-length codes extend immediately to fixed-to-variable-length codes. Here the source output sequence is segmented into blocks of n symbols, each of which is then encoded as a single symbol from the alphabet of source n-tuples. For a DMS the minimum expected codeword length per source symbol then lies between H[U ] and H[U ] + 1/n. Thus prefix-free fixed-to-variable-length codes can approach the entropy bound as closely as desired. One of the disadvantages of fixed-to-variable-length codes is that bits leave the encoder at a variable rate relative to incoming symbols. Thus if the incoming symbols have a fixed rate and the bits must be fed into a channel at a fixed rate (perhaps with some idle periods), then the encoded bits must be queued and there is a positive probability that any finite length queue will overflow. An alternative point of view is to consider fixed-length to fixed-length codes. Here, for a DMS, the set of possible n-tuples of symbols from the source can be partitioned into a typical set and an atypical set. For large n, the AEP says that there are essentially 2nH[U ] typical n-tuples with an aggregate probability approaching 1 with increasing n. Encoding just the typical n-tuples requires about H[U ] bits per symbol, thus approaching the entropy bound without the above queueing problem, but, of course, with occasional errors. As detailed in the text, the AEP can be used to look at the long-term behavior of arbitrary source coding algorithms to show that the entropy bound cannot be exceeded without a failure rate that approaches 1. The above results for discrete memoryless sources extend easily to ergodic Markov sources. The text does not carry out this analysis in detail since readers are not assumed to have the requisite knowledge about Markov chains (see [7] for the detailed analysis). The important thing here is to see that Markov sources can model n-gram statistics for any desired n and thus can model fairly general sources (at the cost of very complex models). From a practical standpoint, universal source codes, such as LZ77 are usually a more reasonable approach to complex and partly unknown sources. Cite as: Robert Gallager, course materials for 6.450 Principles of Digital Communications I, Fall 2006. MIT OpenCourseWare (http://ocw.mit.edu/), Massachusetts Institute of Technology. Downloaded on [DD Month YYYY]. 2.E. EXERCISES 2.E 53 Exercises 2.1. Chapter 1 pointed out that voice waveforms could be converted to binary data by sampling at 8000 times per second and quantizing to 8 bits per sample, yielding 64kb/s. It then said that modern speech coders can yield telephone-quality speech at 6-16 kb/s. If your objective were simply to reproduce the words in speech recognizably without concern for speaker recognition, intonation, etc., make an estimate of how many kb/s would be required. Explain your reasoning. (Note: There is clearly no “correct answer” here; the question is too vague for that. The point of the question is to get used to questioning objectives and approaches.) 2.2. Let V and W be discrete rv’s defined on some probability space with a joint pmf pV W (v, w). (a) Prove that E[V + W ] = E[V ] + E[W ]. Do not assume independence. (b) Prove that if V and W are independent rv’s, then E[V · W ] = E[V ] · E[W ]. c) Assume that V and W are not independent. Find an example where E[V ·W ] = E[V ]·E[W ] and another example where E[V · W ] = E[V ] · E[W ]. 2 be the variances of V and d) Assume that V and W are independent and let σV2 and σW 2 . W respectively. Show that the variance of V + W is given by σV2 +W = σV2 + σW � 2.3. (a) For a nonnegative integer-valued rv N , show that E[N ] = n>0 Pr(N ≥ n). (b) Show, with whatever mathematical care you feel comfortable with, that for an arbitrary �∞ nonnegative rv X that E(X) = 0 Pr(X ≥ a)da. (c) Derive the Markov inequality, which says that for any a ≥ 0 and any nonnegative rv X, Pr(X ≥ a) ≤ E[X] a . Hint: Sketch Pr(X ≥ a) as a function of a and compare the area of the rectangle from 0 to a on the abscissa and 0 to Pr(X ≥ a) with the area corresponding to E[X]. σ2 (d) Derive the Chebyshev inequality, which says that Pr(|Y − E[Y ]| ≥ b) ≤ bY2 for any rv Y with finite mean E[Y ] and finite variance σY2 . Hint: Use part (c) with (Y − E[Y ])2 = X. 2.4. Let X1 , X2 , . . . , Xn , . . . be a sequence of independent identically distributed (iid) analog rv’s with the common probability density function fX (x). Note that Pr{Xn =α} = 0 for all α and that Pr{Xn =Xm } = 0 for m =  n. (a) Find Pr{X1 ≤ X2 }. [Give a numerical answer, not an expression; no computation is required and a one or two line explanation should be adequate.] (b) Find Pr{X1 ≤ X2 ; X1 ≤ X3 } (in other words, find the probability that X1 is the smallest of {X1 , X2 , X3 }). [Again, think— don’t compute.] (c) Let the rv N be the index of the first rv in the sequence to be less than X1 ; that is, Pr{N =n} = Pr{X1 ≤ X2 ; X1 ≤ X3 ; · · · ; X1 ≤ Xn−1 ; X1 > Xn }. Find Pr{N ≥ n} as a function of n. Hint: generalize part (b). (d) Show that E[N ] = ∞. Hint: use part (a) of Exercise 2.3. (e) Now assume that X1 , X2 . . . is a sequence of iid rv’s each drawn from a finite set of values. Explain why you can’t find Pr{X1 ≤ X2 } without knowing the pmf. Explain why E[N ] = ∞. Cite as: Robert Gallager, course materials for 6.450 Principles of Digital Communications I, Fall 2006. MIT OpenCourseWare (http://ocw.mit.edu/), Massachusetts Institute of Technology. Downloaded on [DD Month YYYY]. 54 CHAPTER 2. CODING FOR DISCRETE SOURCES 2.5. Let X1 , X2 , . . . , Xn be a sequence of n binary iid rv’s. Assume that Pr{Xm =1} = Pr{Xm =0} = 12 . Let Z be a parity check on X1 , . . . , Xn ; that is, Z = X1 ⊕ X2 ⊕ · · · ⊕ Xn (where 0 ⊕ 0 = 1 ⊕ 1 = 0 and 0 ⊕ 1 = 1 ⊕ 0 = 1). (a) Is Z independent of X1 ? (Assume n > 1.) (b) Are Z, X1 , . . . , Xn−1 independent? (c) Are Z, X1 , . . . , Xn independent?  12 ? You may take n = 2 here. (d) Is Z independent of X1 if Pr{Xi =1} = 2.6. Define a suffix-free code as a code in which no codeword is a suffix of any other codeword. (a) Show that suffix-free codes are uniquely decodable. Use the definition of unique decod­ ability in Section 2.3.1, rather than the intuitive but vague idea of decodability with initial synchronization. (b) Find an example of a suffix-free code with codeword lengths (1, 2, 2) that is not a prefix-free code. Can a codeword be decoded as soon as its last bit arrives at the decoder? Show that a decoder might have to wait for an arbitrarily long time before decoding (this is why a careful definition of unique decodability is required). (c) Is there a code with codeword lengths (1, 2, 2) that is both prefix-free and suffix-free? Explain. 2.7. The algorithm given in essence by (2.2) for constructing prefix-free codes from a set of codeword lengths uses the assumption that the lengths have been ordered first. Give an example in which the algorithm fails if the lengths are not ordered first. 2.8. Suppose that, for some reason, you wish to encode a source into symbols from a D-ary alphabet (where D is some integer greater than 2) rather than into a binary alphabet. The development of Section 2.3 can be easily extended to the D-ary case, using D-ary trees rather than binary trees to represent prefix-free codes. Generalize the Kraft inequality, (2.1), to the D-ary case and outline why it is still valid. 2.9. Suppose a prefix-free code has symbol probabilities p1 , p2 , . . . , pM and lengths l1 , . . . , lM . Suppose also that the expected length L satisfies L = H[X]. (a) Explain why pi = 2−li for each i. (b) Explain why the sequence of encoded binary digits is a sequence of iid equiprobable binary digits. Hint: Use figure 2.4 to illustrate this phenomenon and explain in words why the result is true in general. Do not attempt a general proof. 2.10. (a) Show that in a code of M codewords satisfying the Kraft inequality with equality, the maximum length is at most M − 1. Explain why this ensures that the number of distinct such codes is finite. (b) Consider the number S(M ) of distinct full code trees with M terminal nodes. Count two trees as being different if the corresponding set of codewords is different. That is, ignore the set of source symbols and the mapping between symbols and codewords. Show � source −1 S(j)S(M − j) where S(1) = 1 by that S(2) = 1 and show that for M > 2, S(M ) = M j=1 convention. Cite as: Robert Gallager, course materials for 6.450 Principles of Digital Communications I, Fall 2006. MIT OpenCourseWare (http://ocw.mit.edu/), Massachusetts Institute of Technology. Downloaded on [DD Month YYYY]. 2.E. EXERCISES 55 2.11. (Proof of the Kraft inequality for uniquely decodable codes) a uniquely de� (a)−lAssume j codable code has lengths l1 , . . . , lM . In order to show that j 2 ≤ 1, demonstrate the following identity for each integer n ≥ 1: n  M M � M M � � �  2−lj  = ··· 2−(lj1 +lj2 +···+ljn ) j=1 j1 =1 j2 =1 jn =1 (b) Show that there is one term on the right for each concatenation of n codewords (i.e., for the encoding of one n-tuple x n ) where lj1 + lj2 + · · · + ljn is the aggregate length of that concatenation. (c) Let Ai be the number of concatenations which have overall length i and show that  n nl M max � �  2−lj  = Ai 2−i j=1 i=1 (d) Using the unique decodability, upper bound each Ai and show that  n M �  2−lj  ≤ nlmax j=1 (e) By taking the nth root and letting n → ∞, demonstrate the Kraft inequality. 2.12. A source with an alphabet size of M = |X | = 4 has symbol probabilities {1/3, 1/3, 2/9, 1/9}. (a) Use the Huffman algorithm to find an optimal prefix-free code for this source. (b) Use the Huffman algorithm to find another optimal prefix-free code with a different set of lengths. (c) Find another prefix-free code that is optimal but cannot result from using the Huffman algorithm. 2.13. An alphabet of M = 4 symbols has probabilities p1 ≥ p2 ≥ p3 ≥ p4 > 0. (a) Show that if p1 = p3 + p4 , then a Huffman code exists with all lengths equal and another exists with a codeword of length 1, one of length 2, and two of length 3. (b) Find the largest value of p1 , say pmax , for which p1 = p3 + p4 is possible. (c) Find the smallest value of p1 , say pmin , for which p1 = p3 + p4 is possible. (d) Show that if p1 > pmax , then every Huffman code has a length 1 codeword. (e) Show that if p1 > pmax , then every optimal prefix-free code has a length 1 codeword. (f) Show that if p1 < pmin , then all codewords have length 2 in every Huffman code. (g) Suppose M > 4. Find the smallest value of pmax such that p1 > pmax guarantees that a Huffman code will have a length 1 codeword. 2.14. Consider a source with M equiprobable symbols. (a) Let k = log M . Show that, for a Huffman code, the only possible codeword lengths are k and k − 1. Cite as: Robert Gallager, course materials for 6.450 Principles of Digital Communications I, Fall 2006. MIT OpenCourseWare (http://ocw.mit.edu/), Massachusetts Institute of Technology. Downloaded on [DD Month YYYY]. 56 CHAPTER 2. CODING FOR DISCRETE SOURCES (b) As a function of M , find how many codewords have length k = log M . What is the expected codeword length L in bits per source symbol? (c) Define y = M/2k . Express L − log M as a function of y. Find the maximum value of this function over 1/2 < y ≤ 1. This illustrates that the entropy bound, L < H[X] + 1 is rather loose in this equiprobable case. 2.15. Let a discrete memoryless source have M symbols with alphabet {1, 2, . . . , M } and ordered probabilities p1 > p2 > · · · > pM > 0. Assume also that p1 < pM −1 + pM . Let l1 , l2 , . . . , lM be the lengths of a prefix-free code of minimum expected length for such a source. (a) Show that l1 ≤ l2 ≤ · · · ≤ lM . (b) Show that if the Huffman algorithm is used to generate the above code, then lM ≤ l1 +1. Hint: Look only at the first two steps of the algorithm. (c) Show that lM ≤ l1 + 1 whether or not the Huffman algorithm is used to generate a minimum expected length prefix-free code. (d) Suppose M = 2k for integer k. Determine l1 , . . . , lM . (e) Suppose 2k < M < 2k+1 for integer k. Determine l1 , . . . , lM . 2.16. (a) Consider extending the Huffman procedure to codes with ternary symbols {0, 1, 2}. Think in terms of codewords as leaves of ternary trees. Assume an alphabet with M = 4 symbols. Note that you cannot draw a full ternary tree with 4 leaves. By starting with a tree of 3 leaves and extending the tree by converting leaves into intermediate nodes, show for what values of M it is possible to have a complete ternary tree. (b) Explain how to generalize the Huffman procedure to ternary symbols, bearing in mind your result in part (a). (c) Use your algorithm for the set of probabilities {0.3, 0.2, 0.2, 0.1, 0.1, 0.1}. 2.17. Let X have M symbols, {1, 2, . . . , M } with ordered probabilities p1 ≥ p2 ≥ · · · ≥ pM > 0. Let X  be the reduced source after the first step of the Huffman algorithm. (a) Express the entropy H[X] for the original source in terms of the entropy H[X  ] of the reduced source as H[X] = H[X  ] + (pM + pM −1 )H(γ), (2.43) where H(γ) is the binary entropy function, H(γ) = −γ log γ − (1−γ) log(1−γ). Find the required value of γ to satisfy (2.43). (b) In the code tree generated by the Huffman algorithm, let v1 denote the intermediate node that is the parent of the leaf nodes for symbols M and M −1. Let q1 = pM + pM −1 be the probability of reaching v1 in the code tree. Similarly, let v2 , v3 , . . . , denote the subsequent intermediate nodes generated by the Huffman algorithm. How many intermediate nodes are there, including the root node of the entire tree? v1 , v2 , . . . , (note (c) Let q1 , q2 , . . . , be the probabilities of reaching the intermediate nodes � that the probability of reaching the root node is 1). Show that L = i qi . Hint: Note that  L = L + q1 . (d) Express H[X] as a sum over the intermediate nodes. The ith term in the sum should involve qi and the binary entropy H(γi ) for some γi to be determined. You may find it helpful Cite as: Robert Gallager, course materials for 6.450 Principles of Digital Communications I, Fall 2006. MIT OpenCourseWare (http://ocw.mit.edu/), Massachusetts Institute of Technology. Downloaded on [DD Month YYYY]. 2.E. EXERCISES 57 to define αi as the probability of moving upward from intermediate node vi , conditional on reaching vi . (Hint: look at part a). (e) Find the conditions (in terms of the probabilities and binary entropies above) under which L = H[X]. (f) Are the formulas for L and H[X] above specific to Huffman codes alone, or do they apply (with the modified intermediate node probabilities and entropies) to arbitrary full prefix-free codes? 2.18. Consider a discrete random symbol X with M +1 symbols for which p1 ≥ p2 ≥ · · · ≥ pM > 0 and pM +1 = 0. Suppose that a prefix-free code is generated for X and that for some reason, this code contains a codeword for M +1 (suppose for example that pM +1 is actaully positive but so small that it is approximated as 0). (a) Find L for the Huffman code including symbol M +1 in terms of L for the Huffman code omitting a codeword for symbol M +1. (b) Suppose now that instead of one symbol of zero probability, there are n such symbols. Repeat part (a) for this case. 2.19. In (2.12), it is shown that if X and Y are independent discrete random symbols, then the entropy for the random symbol XY satisfies H[XY ] = H[X] + H[Y ]. Here we want to show that, without the assumption of independence, we have H[XY ] ≤ H[X] + H[Y ]. (a) Show that H[XY ] − H[X] − H[Y ] = � pXY (x, y) log x∈X ,y∈Y pX (x)pY (y) . pX,Y (x, y) (b) Show that H[XY ] − H[X] − H[Y ] ≤ 0, i.e., that H[XY ] ≤ H[X] + H[Y ]. (c) Let X1 , X2 , . . . , Xn be discrete random symbols, not necessarily independent. Use (b) to show that H[X1 X2 · · · Xn ] ≤ n � H[Xj ]. j=1 2.20. Consider a random symbol X with the symbol alphabet {1, 2, . . . , M } and a pmf {p1 , p2 , . . . , pM }. This exercise derives a relationship called Fano’s inequality between the entropy H[X] and the probability p1 of the first symbol. This relationship is used to prove the converse to the noisy channel coding theorem. Let Y be a random symbol that is 1 if X = 1 and 0 otherwise. For parts (a) through (d), consider M and p1 to be fixed. (a) Express H[Y ] in terms of the binary entropy function, Hb (α) = −α log(α)−(1−α) log(1− α). (b) What is the conditional entropy H[X | Y =1]? (c) Show that H[X | Y =0] ≤ log(M − 1) and show how this bound can be met with equality by appropriate choice of p2 , . . . , pM . Combine this with part (c) to upper bound H[X|Y ]. (d) Find the relationship between H[X] and H[XY ] (e) Use H[Y ] and H[X|Y ] to upper bound H[X] and show that the bound can be met with equality by appropriate choice of p2 , . . . , pM . Cite as: Robert Gallager, course materials for 6.450 Principles of Digital Communications I, Fall 2006. MIT OpenCourseWare (http://ocw.mit.edu/), Massachusetts Institute of Technology. Downloaded on [DD Month YYYY]. 58 CHAPTER 2. CODING FOR DISCRETE SOURCES (f) For the same value of M as before, let p1 , . . . , pM be arbitrary and let pmax be max{p1 , . . . , pM }. Is your upper bound in (d) still valid if you replace p1 by pmax ? Explain. 2.21. A discrete memoryless source emits iid random symbols X1 , X2 , . . . . Each random symbol X has the symbols {a, b, c} with probabilities {0.5, 0.4, 0.1}, respectively. (a) Find the expected length Lmin of the best variable-length prefix-free code for X. (b) Find the expected length Lmin,2 , normalized to bits per symbol, of the best variablelength prefix-free code for X 2 . (c) Is it true that for any DMS, Lmin ≥ Lmin,2 ? Explain. 2.22. For a DMS X with alphabet X = {1, 2, . . . , M }, let Lmin,1 , Lmin,2 , and Lmin,3 be the normalized average lengths, in bits per source symbol, for a Huffman code over X , X 2 and X 3 respectively. Show that Lmin,3 ≤ 23 Lmin,2 + 13 Lmin,1 . 2.23. (Run-Length Coding) Suppose X1 , X2 , . . . , is a sequence of binary random symbols with pX (a) = 0.9 and pX (b) = 0.1. We encode this source by a variable-to-variable-length encoding technique known as run-length coding. The source output is first mapped into intermediate digits by counting the number of occurences of a between each successive b. Thus an intermediate output occurs on each occurence of the symbol b. Since we don’t want the intermediate digits to get too large, however, the intermediate digit 8 is used on the eighth consecutive a and the counting restarts at this point. Thus, outputs appear on each b and on each 8 a’s. For example, the first two lines below illustrate a string of source outputs and the corresponding intermediate outputs. b a a a b a a a a a a a a a a b b a a a a b 0 3 8 2 0 4 0000 0011 1 0010 0000 0100 The final stage of encoding assigns the codeword 1 to the intermediate integer 8, and assigns a 4 bit codeword consisting of 0 followed by the three bit binary representation for each integer 0 to 7. This is illustrated in the third line above. (a) Show why the overall code is uniquely decodable. (b) Find the expected total number of output bits corresponding to each occurrence of the letter b. This total number includes the four bit encoding of the letter b and the one bit encoding for each consecutive string of 8 letter a’s preceding that letter b. (c) By considering a string of 1020 binary symbols into the encoder, show that the number of b’s to occur per input symbol is, with very high probability, very close to 0.1. (d) Combine parts (b) and (c) to find the L, the expected number of output bits per input symbol. 2.24. (a) Suppose a DMS emits h and t with probability 1/2 each. For ε = 0.01, what is Tε5 ? (b) Find Tε1 for Pr(h) = 0.1, Pr(t) = 0.9, and ε = 0.001. 2.25. Consider a DMS with a two symbol alphabet, {a, b} where pX (a) = 2/3 and pX (b) = 1/3. Let X n = X1 , . . . , Xn be a string of random symbols from the source with n = 100, 000. (a) Let W (Xj ) be the log pmf rv for the jth source output, i.e., W (Xj ) = − log 2/3 for Xj = a and − log 1/3 for Xj = b. Find the variance of W (Xj ). Cite as: Robert Gallager, course materials for 6.450 Principles of Digital Communications I, Fall 2006. MIT OpenCourseWare (http://ocw.mit.edu/), Massachusetts Institute of Technology. Downloaded on [DD Month YYYY]. 2.E. EXERCISES 59 (b) For ε = 0.01, evaluate the bound on the probability of the typical set given in (2.24). (c) Let Na be the number of a’s in the string X n = X1 , . . . , Xn . The rv Na is the sum of n iid rv’s. Show what these rv’s are. (d) Express the rv W (X n ) as a function of the rv Na . Note how this depends on n. (e) Express the typical set in terms of bounds on Na (i.e., Tεn = {x n : α < Na < β} and calculate α and β). (f) Find the mean and variance of Na . Approximate Pr{Tεn } by the central limit theorem approximation. The central limit theorem approximation is to evaluate Pr{Tεn } assuming that Na is Gaussian with the mean and variance of the actual Na . One point of this exercise is to illustrate that the Chebyshev inequality used in bounding Pr(Tε ) in the text is very weak (although it is a strict bound, whereas the Gaussian approx­ imation here is relatively accurate but not a bound). Another point is to show that n must be very large for the typical set to look typical. 2.26. For the rv’s in the previous exercise, find Pr{Na = i} for i = 0, 1, 2. Find the probability of each individual string x n for those values of i. Find the particular string x n that has maximum probability over all sample values of X n . What are the next most probable n-strings? Give a brief discussion of why the most probable n-strings are not regarded as typical strings. 2.27. Let X1 , X2 , . . . , be a sequence of iid symbols from a finite alphabet. For any block length n and any small number ε > 0, define the good set of n-tuples xn as the set � � Gnε = xn : pXn (xn ) > 2−n[H[X]+ε] . (a) Explain how Gnε differs from the typical set Tεn . (b) Show that Pr(Gnε ) ≥ 1 − expected here. 2 σW nε2 where W is the log pmf rv for X. Nothing elaborate is (c) Derive an upper bound on the number of elements in Gnε of the form |Gnε | < 2n(H[X]+α) and determine the value of α. (You are expected to find the smallest such α that you can, but not to prove that no smaller value can be used in an upper bound). (d) Let Gnε − Tεn be the set of n-tuples x n that lie in Gεn but not in Tεn . Find an upper bound to |Gnε − Tεn | of the form |Gnε − Tεn | ≤ 2n(H[X]+β) . Again find the smallest β that you can. (e) Find the limit of |Gnε − Tεn |/|Tεn | as n → ∞. 2.28. The typical set Tεn defined in the text is often called a weakly typical set, in contrast to another kind of typical set called a strongly typical set. Assume a discrete memoryless source and let Nj (x n ) be the number of symbols in an n string x n taking on the value j. Then the strongly typical set Sεn is defined as � � Nj (x n ) n n Sε = x : pj (1 − ε) < < pj (1 + ε); for all j ∈ X . n (a) Show that pX n (x n ) = � Nj (x n ) j pj . Cite as: Robert Gallager, course materials for 6.450 Principles of Digital Communications I, Fall 2006. MIT OpenCourseWare (http://ocw.mit.edu/), Massachusetts Institute of Technology. Downloaded on [DD Month YYYY]. 60 CHAPTER 2. CODING FOR DISCRETE SOURCES (b) Show that every x n in Sεn has the property that H[X](1 − ε) < − log pX n (x n ) < H[X](1 + ε) n (c) Show that if x n ∈ Sεn , then x n ∈ Tεn
with ε = H[X]ε, i.e., that Sεn ⊆ Tεn
. (d) Show that for any δ > 0 and all sufficiently large n, / Sεn ) ≤ δ Pr (X n ∈ Hint:Taking �each �letter j separately, 1 ≤ j ≤ M , show that for all sufficiently large n, �� � � Nj δ . Pr � n − pj � ≥ ε ≤ M (e) Show that for all δ > 0 and all suffiently large n, (1 − δ)2n(H[X]−ε) < |Sεn | < 2n(H[X]+ε) . (2.44) Note that parts (d) and (e) constitute the same theorem for the strongly typical set as Theorem 2.7.1 establishes for the weakly typical set. Typically the n required for (2.44) to hold (with the above correspondence between ε and ε) is considerably larger than than that for (2.27) to hold. We will use strong typicality later in proving the noisy channel coding theorem. 2.29. (a) The random variable Dn in Subsection 2.7.4 was defined as the initial string length of encoded bits required to decode the first n symbols of the source input. For the run-length coding example in Exercise 2.23, list the input strings and corresponding encoded output strings that must be inspected to decode the first source letter and from this find the pmf function of D1 . Hint: As many as 8 source letters must be encoded before X1 can be decoded. (b)Find the pmf of D2 . One point of this exercise is to convince you that Dn is a useful rv for proving theorems, but not a rv that is useful for detailed computation. It also shows clearly that Dn can depend on more than the first n source letters. 2.30. The Markov chain S0 , S1 , . . . below starts in steady state at time 0 and has 4 states, S = {1, 2, 3, 4}. The corresponding Markov source X1 , X2 , . . . has a source alphabet X = {a, b, c} of size 3. � ��� b; 1/2 1 � a; 1/2 �� a; 1/2 � � �� 2 �� a; 1 �� 4 � �� c; 1/2 �� � c; 1 3 �� (a) Find the steady-state probabilities {q(s)} of the Markov chain. (b) Find H[X1 ]. (c) Find H[X1 |S0 ]. Cite as: Robert Gallager, course materials for 6.450 Principles of Digital Communications I, Fall 2006. MIT OpenCourseWare (http://ocw.mit.edu/), Massachusetts Institute of Technology. Downloaded on [DD Month YYYY]. 2.E. EXERCISES 61 (d) Describe a uniquely-decodable encoder for which L = H[X1 |S0 ). Assume that the initial state is known to the decoder. Explain why the decoder can track the state after time 0. (e) Suppose you observe the source output without knowing the state. What is the maximum number of source symbols you must observe before knowing the state? 2.31. Let X1 , X2 , . . . , Xn be discrete random symbols. Derive the following chain rule: H[X1 , . . . , Xn ] = H[X1 ] + n � H[Xk |X1 , . . . , Xk−1 ] k=2 Hint: Use the chain rule for n = 2 in (2.37) and ask yourself whether a k tuple of random symbols is itself a random symbol. 2.32. Consider a discrete ergodic Markov chain S0 , S1 , . . . with an arbitrary initial state distribu­ tion. (a) Show that H[S2 |S1 S0 ] = H[S2 |S1 ] (use the basic definition of conditional entropy). (b) Show with the help of Exercise 2.31 that for any n ≥ 2, H[S1 S2 · · · Sn |S0 ] = n � H[Sk |Sk−1 ]. k=1 (c) Simplify this for the case where S0 is in steady state. (d) For a Markov source with outputs X1 X2 · · · , explain why H[X1 · · · Xn |S0 ] = H[S1 · · · Sn |S0 ]. You may restrict this to n = 2 if you desire. (e) Verify (2.40). 2.33. Perform an LZ77 parsing of the string 000111010010101100. Assume a window of length W = 8; the initial window is underlined above. You should parse the rest of the string using the Lempel-Ziv algorithm. 2.34. Suppose that the LZ77 algorithm is used on the binary string x110,000 = 05000 14000 01000 . This notation means 5000 repetitions of 0 followed by 4000 repetitions of 1 followed by 1000 repetitions of 0. Assume a window size w = 1024. (a) Describe how the above string would be encoded. Give the encoded string and describe its substrings. (b) How long is the encoded string? (c) Suppose that the window size is reduced to w = 8. How long would the encoded string be in this case? (Note that such a small window size would only work well for really simple examples like this one.) (d) Create a Markov source model with 2 states that is a reasonably good model for this source output. You are not expected to do anything very elaborate here; just use common sense. (e) Find the entropy in bits per source symbol for your source model. Cite as: Robert Gallager, course materials for 6.450 Principles of Digital Communications I, Fall 2006. MIT OpenCourseWare (http://ocw.mit.edu/), Massachusetts Institute of Technology. Downloaded on [DD Month YYYY]. 62 CHAPTER 2. CODING FOR DISCRETE SOURCES 2.35. (a) Show that if an optimum (in the sense of minimum expected length) prefix-free code is chosen for any given pmf (subject to the condition pi > pj for i < j), the code word lengths satisfy li ≤ lj for all i < j. Use this to show that for all j ≥ 1 lj ≥ log j + 1 (b) The asymptotic efficiency of a prefix-free code for the positive integers is defined to be l limj→∞ logj j . What is the asymptotic efficiency of the unary-binary code? (c) Explain how to construct a prefix-free code for the positive integers where the asymptotic efficiency is 1. Hint: Replace the unary code for the integers n = log j + 1 in the unarybinary code with a code whose length grows more slowly with increasing n. Cite as: Robert Gallager, course materials for 6.450 Principles of Digital Communications I, Fall 2006. MIT OpenCourseWare (http://ocw.mit.edu/), Massachusetts Institute of Technology. Downloaded on [DD Month YYYY].