rresponding output symbol according to the joint probability distribution p(x, y) = p(x)p(y)x), for some source distribution p(x) = px(x). Definition 3.4.2 (Rate-distortion function). Let X be Since we assume that the base of the logarithm in the a discrete memoryless source over alphabet A, and let A mutual information is 2, C is measured in bits. CHAPTER 3.4 Channel protection fundamentals Example 3. The binary symmetric channel (BSC) is scheme is known as minimum distance decoding where a discrete memoryless channel with Ax = Ay = {0,1} and the received word y = yn) is mapped to a channel transition probabilities p(0|1) = p(1 |0) = p and p(0|0) = codeword C = (c1, ..., cn) that has smallest Hamming p(1|1) = 1 - p. When a bit is sent over the BSC, it is distance to y. Here the Hamming distance is defined as either corrupted with probability p or correctly received follows. with probability 1 - p. It is easy to prove that the ca- Definition 3.4.4 (Hamming distance). Let X = (x1, pacity of the BSC is 1 + log + - p) log(1 p) [15]. xn) and y = (y1, ...,yn) be two words of the same length. Example 4. The binary erasure channel (BEC) is a dis- The Hamming distance dH (x,y) between X and y is equal crete memoryless channel with Ax = {0, 1}, Ay = {0, 1, to the number of indices ke {1,2, n} such that Xk # ?} and transition probabilities p(?|0) = p(?|1) = p and Given a BSC with bit error probability p, we have = - p. When a bit is sent over the BEC, it is either erased with probability p or correctly received Pr{Y = YX = = with probability 1 - p. The capacity of the BEC is 1 - p (3.4.1) [15]. We now consider the situation when the symbols If 0<p < 1/2, the probability in (3.4.1) is largest generated by a discrete source U with source alphabet A when dH(c, y) is smallest. Therefore minimum distance are to be sent over a discrete channel with input alphabet decoding and maximum-likelihood decoding are equiv- Ax and output alphabet Ay. To protect the source symbols alent for this channel. against transmission errors, redund