IQ) (p.Q) -P Figure 1:Eo(p,Q) Thus,the difficulty in finding good practical codes is not that the good codes are rare,but the difficulty is in find good codes for which there are practical methods to encode and decode The corollary above makes guarantees on P but for a code constructed by random coding the value of P may be much higher than PCan we ensure the existence of codes with small Pmax THEOREM 2.Given a discrete memoryless channel described by P(yl),for any distribution Q on A,any blocklength n and any R>0.there exists a block code of length n and rate at least R with Pe.max <4expf-nE,(R,Q)} Proof.LetM=[2e.We know that there is a code with Mcodewords and satisfies Pae=i7∑Rm≤(M-lPep{-noa,Q} m=l for every p∈0，.Since (M'-1)P≤2PepR≤2enpR we see that for this code Rm-之R.s2om- ' Now.among the l'numbers p P there cannot be more than M'/2 which exceed twice the average value PThus,amon ng these numbers there exist at least [e of them which satisfy Pe.m≤2P.ae≤4exp{-nE,(R,Q)} Keeping only these codewords,and noticing that in the maximum likelihood decoder that onds to this code the d coding sets can only be enla rged,we see that we have constructed a code with the desired properties 5.1.PROPERTIES OF Eo AND Er The value of the existence theorems we just proved depend on whether the bound we have on the probability of error can be made arbitrarily small for a set of rates of interest.Define P(ulr) I(Q)=>Q()P(ulz)in ∑-Q(r)P(r ρI(Q) E0(ρ, Q) ρ Figure 1: E0(ρ, Q) Thus, the difficulty in finding good practical codes is not that the good codes are rare, but the difficulty is in find good codes for which there are practical methods to encode and decode. The corollary above makes guarantees on Pe,ave, but for a code constructed by random coding the value of Pe,max may be much higher than Pe,ave. Can we ensure the existence of codes with small Pe,max? Theorem 2. Given a discrete memoryless channel described by P(y|x), for any distribution Q on X , any blocklength n and any R > 0, there exists a block code of length n and rate at least R with Pe,max ≤ 4 exp −nEr(R, Q) . Proof. Let M0 = d2e nRe. We know that there is a code with M0 codewords and satisfies Pe,ave = 1 M0 X M0 m=1 Pe,m ≤ (M0 − 1)ρ exp −nE0(ρ, Q) for every ρ ∈ [0, 1]. Since (M0 − 1)ρ ≤ 2 ρ e nρR ≤ 2e nρR , we see that for this code Pe,ave = 1 M0 X M0 m=1 Pe,m ≤ 2 exp −nEr(R, Q) . Now, among the M0 numbers Pe,1, . . . , Pe,M0 there cannot be more than M0/2 which exceed twice the average value Pe,ave. Thus, among these M0 numbers there exist at least de nRe of them which satisfy Pe,m ≤ 2Pe,ave ≤ 4 exp −nEr(R, Q) . Keeping only these codewords, and noticing that in the maximum likelihood decoder that corresponds to this code the decoding sets can only be enlarged, we see that we have constructed a code with the desired properties. 5.1. Properties of E0 and Er The value of the existence theorems we just proved depend on whether the bound we have on the probability of error can be made arbitrarily small for a set of rates of interest. Define I(Q) = X x X y Q(x)P(y|x) ln P(y|x) P x0 Q(x 0 )P(y|x 0 ) 7