C, k, M, f) such that M < 2lkR' and D(C, k, M, f <D'. representation 00 0 and 11 1, any sequence of two The theorem roughly says that one can reproduce the source symbols can be represented by one bit. source symbols with an average distortion that is smaller The average distortion of the lossy compression than D by spending no more than R(D) bits per source scheme (C, k, M, f) with respect to the source X and the symbol. single-letter distortion measure d is 3.4.2.2 Channel coding D(C,k,M,f) A discrete channel takes at every time unit n a symbol from a finite input alphabet Ax and outputs symbols from where for x = (x1, ...,kk),,(p(x) = II-p(xi). a finite output alphabet Ay. Example 2. In Example 1, suppose that the distortion Let Xn be the random variable that gives the nth input measure d is given by d(x,) = 0 if x = y and d(x,y) symbol of the channel and let Yn be the random variable otherwise. Suppose also that Pr{X = 0} = p(0) p, that gives the nth output symbol of the channel. We say where 0 p < 1/2. Then the average distortion of the that the channel is memoryless if Pr{Yn = y Xn = x} = lossy compression scheme (C, 2, 2, f is p(1 - p). (yy) is independent of n for all ye Ay and Ax, the Let Y be a random variable that is jointly distributed transition probabilities p(y)x) satisfy p(y) and with X according to the joint probability distribution EyeAy P(y|x) = 1, and Pr{Y1 = y1 .,Yn Yn X1=x1, p(x, = p(x)p(y|x) for some conditional probability ,Xn==nn = = all N. distribution p(y)x) = py|x(y|x). As a function of the Definition 3.4.3 (Channel capacity). The capacity of conditional probability distribution PY|X, the average a discrete memoryless channel with input alphabet Ax, distortion when X is reproduced as Y is thus output alphabet Ay, and transition probabilities p(y), Ay, x E Ax is D(PY)X) = p(x)p(y|x)d(x,y). xeA,yeA C = maxI(X;Y), Note that the smallest value that can be taken by D( PYX) is where X is a random variable that gives the input symbol to the channel and Y is a random variable that gives the co