e uniquely decodable. Then The difference I(X;Y)=H(X) - H(XY) is known as the mutual information of the two random variables X and Y. It expresses the amount of information provided by Yon X. Channel protection fundamentals CHAPTER 3.4 3.4.2.1.2 Lossy source coding be a reproducing alphabet. The rate-distortion function Suppose now that the symbols generated by a discrete of the source X with respect to a single-letter distortion measure A x A. R+ is the function memoryless source X over alphabet A are to be reproduced by symbols from a finite alphabet A called the reproducing alphabet. A single-letter distortion measure d: A A R+ measures the distortion d(x, y) when symbol X E A is reproduced as y EA. The distortion be- for all D > Dmin, where the minimum is taken over all tween a word X = (x1, xk) E A and a word y = (y1,..., conditional distributions p(y)x) subject to the constraint yk) E Ak is defined as d(x,y) = . D(pyx) < D. A lossy compression scheme (C, k, M, f) for the Henceforth we assume that the base of the logarithm memoryless source X is given by a block code C of length in the mutual information is 2, SO that R(D) is measured k and size M over the reproducing alphabet A, and in bits. a mapping f from Ak to C. This compression scheme We can now state Shannon's source coding theorem [46]. allows us to represent any sequence of k source symbols Theorem 3.4.2 (Shannon's source coding theorem). Let with [log2 M] bits. Thus the rate of a block code of length X be a discrete memoryless source over alphabet A, and let k and size M is defined to be (log2 M )/k bits per symbol. A be a reproducing alphabet. Let R(D) be the rate- Example 1. Let A = {0, 1}, À = 1}, and C = {00, 11}. distortion function of the source X with respect to a single- Then the mapping f: A2-C given f(00) = 00, f(01) = letter distortion measure d A R+ Then for any D' 00, f(10) = 11, f(11) = 11 defines a lossy compression > D and R' > R(D), there exists a lossy compression scheme scheme (C, 2, 2, f) for the source X. By using the binary (