Suppose message 1 is to be sent.The channel input is then c,and the probability of receiving y at the channel output is P(yc).An error will occur if the received sequence is not in D.Since for every y not in D,P(ylc2)>P(ylc),(but there may be y's for which P(ylc2)=P(ylc)and y Di)we have P1=Pylc) Pylc） v:P(ylea)zP(yle.) =>Pylc)1Pyle2≥PyIe) ≤ N y:P(ylea)2P(ylc) s∑Pote%e for any s>0 =∑Pylc)l-Pylc2 The choice s=1/2 gives us P.1≤∑VP(ylc)Pylc2). and by symmetry,the same quantity also upper bounds P.2 For a memoryless channel P(ylCm)=ITP(yelcm.)and we obtain P.m≤∑VP(ylc)Pyle2 =∑.∑VPla)Phle2).VP((.】) -[∑P(le)P(nlcx)[∑VP(l)P(l】 =I∑VP(ek)P(e2) For example,for a binary symmetric channel with crossover probability e,we see that ∑VPa)P)= 1 if Ci=C2.k 2ve(1-e)else, and we obtain Pem≤e(1-ejp where d is the number of places ci and c2 are different (i.e.,d=:c) 4.ERROR PROBABILITY FOR TWO RANDOMLY CHOSEN CODEWORDS Suppose e cod ord sci and ca are chos sen randomly and indepen Suppose message 1 is to be sent. The channel input is then c1, and the probability of receiving y at the channel output is P(y|c1). An error will occur if the received sequence is not in D1. Since for every y not in D1, P(y|c2) ≥ P(y|c1), (but there may be y’s for which P(y|c2) = P(y|c1) and y ∈ D1) we have Pe,1 = X y6∈D1 P(y|c1) ≤ X y: P(y|c2)≥P(y|c1) P(y|c1) = X y P(y|c1)11P(y|c2)≥P(y|c1) ≤ X y:P(y|c2)≥P(y|c1) P(y|c1) P(y|c2) s P(y|c1) s ≤ X y P(y|c1) P(y|c2) s P(y|c1) s for any s ≥ 0 = X y P(y|c1) 1−sP(y|c2) s The choice s = 1/2 gives us Pe,1 ≤ X y p P(y|c1)P(y|c2), and by symmetry, the same quantity also upper bounds Pe,2. For a memoryless channel P(y|cm) = Qn k=1 P(yk|cm,k) and we obtain Pe,m ≤ X y p P(y|c1)P(y|c2) = X y1 · · ·X yn q P(y1|c1,1)P(y1|c2,1). . . q P(yn|c1,nP(yn|c2,n) = hX y1 q P(y1|c1,1)P(y1|c2,1) i . . . hX yn q P(yn|c1,n)P(yn|c2,n) i = Yn k=1 hX y q P(y|c1,k)P(y|c2,k) i . For example, for a binary symmetric channel with crossover probability , we see that X y q P(y|c1,k)P(y|c2,k) = ( 1 if c1,k = c2,k 2 p (1 − ) else, and we obtain Pe,m ≤ [4(1 − )]d/2 where d is the number of places c1 and c2 are different (i.e., d = |{k : c1,k 6= c2,k}|). 4. Error Probability for two randomly chosen codewords Suppose now that the codewords c1 and c2 are chosen randomly and independently each from a distribution Q on X n . Observe that the codewords are random variables C1 and 3