18.413 Error-Correcting Codes Laboratory, Lecture 3 Notes

18.413: Error­Correcting Codes Lab Lecture 3 3.1 Analysis of repetition code meta­channel When we specialize our interpretation of the output of a channel to the meta channel formed by encoding using the repitition code and transmitting over another channel, we solve a fundamental problem of probability: how to combine the results of independent experiments. That is, let w be a random varible taking values in {0, 1}. Imagine encoding w using the repeat­ 2­times code to (x1 , x2 ) = (w, w), and transmitting x1 and x2 over a memoryless channel (so each transmission is independent). Equivalently, we could assume that x1 is transmitted over one channel and x2 is transmitted over another. Let y1 and y2 be the random variables corresponding to the outputs of the channel, let b1 and b2 be the values actually received, and let p1 = P [x1 = 1|y1 = b1 ] , and p2 = P [x2 = 1|y2 = b2 ] . We would like to know the probability that w = 1 given both y1 and y2 . As before, we will assume that w was uniformly distributed (half chance 0 and half chance 1). I think of each channel transmission as an experiment, and I now want to determine the probability that w was 1 given the results of both experiments. By the theorem from last class, we have P [w = 1|y1 = b1 and y2 = b2 ] = P [y1 = b1 and y2 = b2 |w = 1] P [y1 = b1 and y2 = b2 |w = 1] + P [y1 = b1 and y2 = b2 |w = 0] (3.1) To evaluate this probability, we first note that P [y1 = b1 |w = 1] = P [w = 1|y1 = b1 ] P [y1 = b1 ] /P [w = 1] = p1 P [y1 = b1 ] /P [w = 1] . While we do not necessarily know P [y1 = b1 ], it will turn out not to matter. Since the two channel outputs are independent given w, we have P [y1 = b1 and y2 = b2 |w = 1] = P [y1 = b1 |w = 1] P [y2 = b2 |w = 1] p1 P [y1 = b1 ] p2 P [y2 = b2 ] = . P [w = 1] P [w = 1] 3­1 3­2 Applying P [w = 0|y1 = b1 ] = 1 − P [w = 1|y1 = b1 ], we can also comput P [y1 = b1 and y2 = b2 |w = 0] (1 − p1 )P [y1 = b1 ] (1 − p2 )P [y2 = b2 ] . P [w = 0]2 Combining these equations, and P [w = 0] = P [w = 1] = 1/2, we obtain (3.1) = p1 p2 . p1 p2 + (1 − p1 )(1 − p2 ) In particular, the terms we don’t know cancel! 3.2 Capacity of meta­channel Consider the meta­channel obtained by encoding a bit w via the repeat­2­times code to obtain (x1 , x2 ), and then passing these bits through the BSCp to obtain (y1 , y2 ). We will now compute the capacity of this meta­channel. We begin with the computation of the quantities that appear in the formula for I(w; (y1 , y2 )): P [w = 1|(y1 , y2 ) = (1, 1)] = P [w = 1|(y1 , y2 ) = (1, 0)] = P [w = 1|(y1 , y2 ) = (0, 0)] = P [w = 0|(y1 , y2 ) = (1, 1)] = P [w = 0|(y1 , y2 ) = (1, 0)] = P [w = 0|(y1 , y2 ) = (0, 0)] = (1 − p)2 p2 + (1 − p)2 p(1 − p) = 1/2 p(1 − p) + (1 − p)p p2 p2 + (1 − p)2 ) p2 p2 + (1 − p)2 ) p(1 − p) = 1/2 p(1 − p) + (1 − p)p (1 − p)2 . p2 + (1 − p)2 3­3 To compute the capacity, we must assume that P [w = 1] = P [w = 0] = 1/2, so we have � � P [w = 1|(y1 , y2 ) = (1, 1)] i (w = 1; (y1 , y2 ) = (1, 1)) = log2 , P [w = 1] � � 2(1 − p)2 , = log2 (1 − p)2 + p2 i (w = 1; (y1 , y2 ) = (1, 0)) = 0 � � 2p2 i (w = 1; (y1 , y2 ) = (0, 0)) = log2 , (1 − p)2 + p2 � � 2(1 − p)2 i (w = 0; (y1 , y2 ) = (0, 0)) = log2 , (1 − p)2 + p2 i (w = 0; (y1 , y2 ) = (1, 0)) = 0 � � 2p2 . i (w = 0; (y1 , y2 ) = (1, 1)) = log2 (1 − p)2 + p2 We now compute I(w; y1 , y2 ) by summing over all events: � P [w = a, y1 = b1 , y2 = b2 ] i (w = a; y1 = b1 , y2 = b2 ) I(w; y1 , y2 ) = a,b1 ,b2 � 2 = (1 − p) + p 3.3 2 � � � 1−H p2 (1 − p)2 + p2 �� . Prior, Extrinsic, Posterior and Intrinsic Probabilities It is unsatisfying to have to keep assuming that w is uniformly distributed just because we don’t know how it is distributed. There is a way to avoid having to make this assuption. In the situation in which a variable w is chosen, and then experiments are performed that reveal information about w, such as passing w through a channel, we call the initial probability of w = 1 the prior probability of w = 1, usually written Pprior [w = 1] . In general, when w can take one of many values a1 , . . . , am , the prior distribution is the vector of prior probabilities � prior � P [w = a1 ] , Pprior [w = a2 ] , . . . , Pprior [w = am ] . Our experiments reveal the extrinsic probability of w = 1 given the outcome of the experiment. For example, if y is the output of a channel on input w, and b is the value received, then def Pext [w = 1|y = b] = P [y = b|w = 1] P [y = b|w = 1] + P [y = b|w = 0] is the extrinsic probability of w = 1 given the event y = b. Up to now, we have really been computing extrinsic probabilities. For example, when we derived the interpretation of the output of a channel, we really derived the extrinsic probability. 3­4 If you know the prior probability, then you can combine this knowledge with the extrinsic prob­ ability to achieve the posterior probability: then actual probability of w = 1 given the channel output. Treating the prior and extrinsic probabilities as independent observations, and applying the calculation of the previous section, we obtain Ppost [w = 1|y = b] = Pext [w = 1|y = b] Pprior [w = 1] . Pext [w = 1|y = b] Pprior [w = 1] + Pext [w = 0|y = b] Pprior [w = 0] A useful exercise would be to re­derive the probability that w = 1 given y = b assuming that w is not uniformly distributed, and to observe that one obtains the above formula. We will occasionally also see the term intrinsic probability. This will usually be treated in the same way as the prior, but will be distinguished from the prior in that it will often be determined from previous experiments.