py of a discrete memoryless and an injective map f : A C (known as an encoder). source). Let X be a discrete memoryless source with source code C is uniquely decodable if for all positive in- alphabet A. The entropy of X is tegers k and all codewords Ci, di, i = 1, k, the equality Ck = di dk implies that Ci = di for all i = 1, H(X) = -() log p(x), ..., k. Here * denotes concatenation. The average codeword length of an encoding scheme (C,f) with respect to a discrete memoryless source X can where the sum is taken over all X E A for which p(x) > be expressed L = Exp(x)|f(x)| Any base of the logarithm can be used in the expres- Shannon's noiseless coding theorem [45] says that the sion for the entropy. When this base is 2, the entropy is entropy of a discrete memoryless source X over alphabet measured in bits. A gives the smallest average number of code symbols The entropy of a discrete memoryless source X (from the alphabet B) needed to losslessly represent one measures the amount of uncertainty in the source. Since source symbol (from the alphabet A), when the base of the entropy is completely defined by the probability the logarithm is B. Before stating the theorem more distribution of X, we speak also of the entropy of the precisely, we must define the extension of a discrete random variable X. source. The kth extension of a source Xn is the source Xk = Given the discrete random variables X, Y1, ,Yn, the (X(n-1)k+1, Xnk) obtained by blocking Xn into blocks of conditional entropy H(X|Y1, Yn) is the average length k. Thus if Xn is a discrete memoryless source taking uncertainty remaining in X after observing Y1, ...,Yn. values inA, then Xn is a discrete memoryless source taking Formally, with H(X|y1,...,Yn) = ...,Yn) values in Ak, where Ak is the set of all words of length k logp(x/y1, ...,yn) we over A. Theorem 3.4.1 (Shannon's noiseless coding theorem). H(X = be a discrete memoryless source. Let Xk be its kth extension. Let Lk be the minimum average codeword length over all encoding schemes for Xk whose codes ar