ECOLE POLYTECHNIQUE FEDERALE DE LAUSANNE School of Computer and Communication Sciences Handout 18 Information Theory and Codins Notes on random coding December 12.2005 RANDOM CODING in this note we prove the achievability part of the channel coding theorem for discrete memorvless channels without feedback.The discussion is largely based on chapter 5 of R.G.Gallager,Information Theory and Reliable Communication.Wiley,1968. 1.DISCRETE MEMORYLESS CHANNELS WITHOUT FEEDBACK de pociving for oncthe fumetion and lavior of the t the co ll be completely B:X*×Jy*→R,(,)P(z,-), al ne pa P(,)=P(, which in means that the channel keeps no me channel do es not ave d at c ion P on the right hand side i not an expiit fuction of If a memoryless channel is used without feedback,i.e.,if Pxx)=Pxx) (in words:if the channel inputs do not depend on the past channel outputs)then ()- Px(IT) _Π-1xe,时-) Pxr(ri) _Ixxe-乃x-） Px好() IΠ-1PxX-(arl-)乃Ix(lr) Pxr(i) ´ECOLE POLYTECHNIQUE F´ED´ERALE DE LAUSANNE School of Computer and Communication Sciences Handout 18 Information Theory and Coding Notes on Random Coding December 12, 2003 Random Coding In this note we prove the achievability part of the channel coding theorem for discrete memoryless channels without feedback. The discussion is largely based on chapter 5 of R. G. Gallager, Information Theory and Reliable Communication, Wiley, 1968. 1. Discrete Memoryless Channels Without Feedback Throughout this note we will fix the channel we wish to communicate over. Let X and Y denote the input and output alphabets of this channel. We will assume that the channel is discrete, i.e., that X and Y are finite sets. The behavior of the channel will be completely described by specifying for each k ≥ 1 the function Pk : X k × Yk → R, (x k 1 , yk 1 ) 7→ Pk(yk|x k 1 , yk−1 1 ), which gives the probability of receiving the letter yk at the output at time k, given the past and current inputs to the channel, and the past outputs of the channel. We make the two following assumptions: the channel is memoryless and used without feedback. We will call a channel memoryless if Pk(yk|x k 1 , yk−1 1 ) = P(yk|xk), which in words means that the channel keeps no memory of the past inputs and outputs in determining the output of time k. Also note that the channel does not behave differently at different times: the function P on the right hand side is not an explicit function of k. If a memoryless channel is used without feedback, i.e., if PXk|X k−1 1 ,Y k−1 1 (xk|x k−1 1 , yk−1 1 ) = PXk|X k−1 1 (xk|x k−1 1 ) (in words: if the channel inputs do not depend on the past channel outputs) then PY n 1 |Xn 1 (y n 1 |x n 1 ) = PXn 1 ,Y n 1 (x n 1 , yn 1 ) PXn 1 (x n 1 ) = Qn k=1 PXk,Yk|X k−1 1 ,Y k−1 1 (xk, yk|x k−1 1 , yk−1 1 ) PXn 1 (x n 1 ) = Qn k=1 PXk|X k−1 1 ,Y k−1 1 (xk|x k−1 1 , yk−1 1 )PYk|Xk 1 ,Y k−1 1 (yk|x k 1 , yk−1 1 ) PXn 1 (x n 1 ) = Qn k=1 PXk|X k−1 1 (xk|x k−1 1 )PYk|Xk (yk|xk) PXn 1 (x n 1 ) = Yn k=1 P(yk|xk)