6.441-13 Fano's inequality and the converse to the coding theorem

LECTURE 13 Last time: Strong coding theorem • Revisiting channel and codes• Bound on probability of error• Error exponent • Lecture outline Fano’s Lemma revisited • Fano’s inequality for codewords • Converse to the coding theorem • Reading: Sct. 8.9. � � Fano’s lemmaSuppose we have r.v.s X and Y , Fano’s lemma bounds the error we expect when estimating X from Y We generate an estimator of X that is �=X g(Y ). Probability of error Pe = Pr( �= X)X Indicator function for error E which is 0 when X = X and 1 otherwise. Thus, Pe = P (E = 1)Fano’s lemma:H(E)+ Pe log(|X| − 1) ≥ H(X|Y )We now need to consider the case wherewe are dealing with codewords Want to show that vanishingly small probabiilit of error is not possible if the rate is above capacity � � � �| Fano’s inequality for code wordsAn error occurs when the decoder makes the wrong decision in selecting the message that was transmitted Let M ∈{1, 2,..., 2nR} be the transmitted message and let �M be the estimate of the received message from Yn M is uniformly distributed in {1, 2,..., 2nR}and consecutive message transmissions are IID (thus, we do not make use of a number of messages, but consider a single message transmission) The probability of error for a codebook for transmission of Mis Pe,M = P (M = M)= EY n[P (M = MYn)] Consider an indicator variable E = 1 when an error occurs and E = 0 otherwise � �| | Fano’s inequality for code words H(E,MY )|= H(MY )+ H(EM, Y )||= H(MY )|= H(EY )+ H(ME,Y )||≤ 1+ H(M|E,Y ) Let us consider upper bounding the RHS H(ME,Y )|we are not averaging over codebooks as for the coding theorem, but are considering a specific codebook = H(XE,Y )|= EM,Y [P (M = MY )]H(XE =1,Y ) += MY )])(1 − EM,Y [P (M ��|H(XE =0,Y )|= PeH(XE =1,Y )|≤ PeH(X|E = 1) ≤ Pe log(|M| − 1) Fano’s inequality for code wordsGiven the definition of rate, |M| =2nR, so H(M|E,Y ) ≤ PenR +1 Hence H(MY )|≤ PenR For a given codebook, M determines X, so H(X|Y )= H(M|Y ) ≤ 1+ PenR for a DMC with a given codebook and uniforrml distributed input messages From Fano’s inequality for code wordsto the coding theorem converseWe now want to relate this to mutual informmatio and to capacity Strategy: -will need to have mutual information expreesse as H(M) − H(M|Y ) -rate will need to come in play -try the fact that H(M)= nR for uniformly distributed messages -will need capacity to come into play. We remember that combining the chain rule for entropies and the fact that conditioniin reduces entropy yields the fact that for a DMC I(Xn; Yn) ≤ nC Converse to the channel codingtheoremConsider some sequence of codebooks (2nR, n), indexed by n, such that the maximum probabiilit of error over each codebook goes to 0 as n goes to ∞ Assume (we’ll revisit this later) that the message M is drawn with uniform PMF from {1, 2, . . . , 2nR} Then nR = H(M) Also H(M)= H(MY )+ I(M; Y )|= H(M|Y )+ H(Y ) − H(Y |M) = H(M|Y )+ H(Y ) − H(Y |X) = H(MY )+ I(X; Y )|≤ 1+ PenR + nC Hence R ≤ 1+ PeR + C n Converse to the channel codingtheoremLetting n go to ∞, we obtain that R ≤C (since the maximum probability of error goes to 0 by our assumption) Moreover, we obtain the following boundon error: Pe ≥ 1 − C R − 1 nR Note: -for RC, bound becomes 1 − C for large R n, but 1 − C 1 is always lower bound RR − -as R goes to infinity, bound becomes 1, so is tight bound -RHS of bound does not vary with n in the way we would expect, since the bound increases with n Revisiting the message distributionWe have assumed that we can select the messages to be uniformly distributed This is crucial to get H(M)= nR Does the converse only work when the messaage are uniformly distributed? Let us revisit the consequences of the AEPConsequences of the AEP: the typicalsetDefinition: A� (n) is a typical set with respect to PX(x) if it is the set of sequences in the set of all possible sequences xn n with∈Xprobability: 2−n(H(X)+�) ≤ PXn (xn) ≤ 2−n(H(X)−�) equivalently 1 H(X) − � ≤− n log(PXn (xn)) ≤ H(X)+ � We shall use the typical set to describe a set with characteristics that belong to the majority of elements in that set. Consequences of the AEP: the typicalsetWhy is it typical? The probability of being more than δ away from H(X) goes can be arbitrarily close to 0 as n →∞, hence Pr(A� (n)) ≥ 1 − � We can select � to be arbitrarily small, so that the distribution of messages is arbitraaril close to uniform in the typical set The max of the probability of error must be bounded away from 0 in the typical set for the max of the probability of error to be bounded away from 0 The probability of error is dominated by theprobability of the typical set as we let �> 0MIT OpenCourseWarehttp://ocw.mit.edu 6.441 Information Theory Spring 2010 For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms.