第5章 信道编码.ppt

,*,第,5,章 信道编码,第,5,章 信道编码,理解,n,次扩展信道的联合渐近均分性,理解香农第二定理,理解线性分组码的纠错原理,掌握汉明码的编码和译码,教学内容和要求,5.1,联合渐近均分性定理,1,、,n,次扩展信道的联合渐进均分性,例,1,二次扩展信道相关符号序列的概率分布特点,二次扩展信源的概率,信源符号序列概率分布特点,二次扩展信道的信道矩阵,二次扩展信宿的概率,信宿符号序列概率分布特点,信源信宿联合符号序列概率分布特点,2,、联合渐进均分性定理,定理,任意给定,0,，当,n,足够大，,n,次扩展信源的典型序列满足,同样的,和,n,，,n,次扩展信宿的典型序列满足,n,次扩展信道的联合典型序列满足,取,n,n,1,，当,n,1,足够大,由大数定理,取,n,n,2,，当,n,2,足够大,由大数定理,取,n,n,3,，当,n,3,足够大,由大数定理,推论,1,推论,2,推论,3,5.2,香农第二定理,1,、平均译码错误概率,最小错误概率准则下的平均译码错误概率,定义,信宿收到,y,j,按最大后验概率判断信源发送,x*,x,i,之一,译码,最小错误概率准则,表示,平均译码错误概率,信宿收到,y,j,的译码错误概率,平均译码错误概率,最大似然准则下的平均译码错误概率,最大似然准则,定义,信宿收到,y,j,按最大转移概率判断信源发送,x*,x,i,之一,译码,表示,信源等概率条件下,最大似然准则等同于最小错误概率准则,平均译码错误概率,2,、香农第二定理,定理,信道的信道容量为,C,，对,n,次扩展信道进行信道编码，对,任意给定的,0,，,只要码率,R C,，当,n,足够大，平均译码错误概率,P,e,C,，,无论,n,多大，平均译码错误概率,P,e,正定理,当,n,足够大，随机产生的码字为等概率的典型序列，数量为,2,nH(X),，,选取其中,2,nR,个作为许用码，其余为禁用码,发生译码错误的两种情况,调整信源概率,P(X),，使,I(X;Y)=C,不失一般性，记,E,1,*,表示第一种情况，,E,i,表示第二种情况,i=2,2,nR,平均译码错误概率,当,n,足够大,5.3,费诺不等式与香农第二定理的逆定理,1,、费诺不等式,n,次扩展信道的损失熵,H(X,n,/Y,n,),与平均译码错误概率,P,e,之间满足,定理,2,、逆定理,对于长度为,n,，数量为,2,nR,的任意码字，如果,R C,，,当,n,足够大，有,香农第二定理表明了平均译码错误概率任意小的信道编码的存在性，明确了信道容量,C,是信道编码的码率上界,香农界,5,.,4,纠错与线性分组码的编码原则,1,、纠错,信道编码,通过在发送端增加冗余使消息出现传输错误时由接收端自动进行纠正,纠错,2,、,n,重复码,例1,信源等概率时的平均译码错误概率,最大似然准则译码,收到,y,1,时,收到,y,2,时,平均译码错误概率,通信系统中一般要求平均译码错误概率的数量级,10,-6,-10,-9,三重复码,消息重复三次,x,1,=0c,1,=000,，,x,2,=1c,2,=111,三次扩展信源的子信源，三次扩展信宿,三次扩展信道的子信道,最大似然准则译码,收到,y,1,=000,时,收到,y,2,=001,时,收到,y,3,=010,时,收到,y,4,=011,时,收到,y,5,=100,时,收到,y,6,=101,时,收到,y,7,=110,时,收到,y,8,=111,时,三重复码,通过在发送端增加冗余使消息出现一位传输错误时由接收端进行纠正,纠错,平均译码错误概率,重复,n,次,n,重复码,n,重复码的码长为原来的,n,倍,编码效率为,1/n,需要找的“好码”,足够小的平均译码错误概率,P,e,较高的编码效率,3,、线性分组码及其编码原则,线性分组码,定义,具有恒定码字长度和消息长度，消息相加后的编码等同于各自编码相加的纠错码,表示,(,n,k,),其中,n,为码字长度，,k,为消息长度，,n-k,为校验长度,例,2,(4,3),偶校验码,码距和最小码距,2,k,个码字构成的码表中，任意两个码字之间的码距,(,汉明距离,),定义,任意两个码字对应位上不同码元的个数,表示,例,3,(4,3),偶校验码中码字,c,2,和,c,3,之间的码距,d,23,2,k,个码字构成的码表中，码字之间的最小码距,定义,所有码字之间码距的最小值,表示,线性分组码的编码原则,例,4,(3,1),线性分组码,三次扩展信源中,8,个可能的码字,8,个可能的码字构成的码表中，任意两个码字之间的码距,如果选取其中,c,1,=000,，,c,8,=111,为许用码，其余为禁用码,三重复码,2,个码字构成的码表中,及信源等概率条件下的平均译码错误概率,在信道,如果选取其中,c,2,=001,，,c,7,=110,为许用码，其余为禁用码,2,个码字构成的码表中,及信源等概率条件下,在信道,x=0c,2,=001,，,x=1c,7,=110,三次扩展信源的子信源，三次扩展信宿,三次扩展信道的子信道,最大似然准则译码,收到,y,1,=000,时,收到,y,2,=001,时,收到,y,3,=010,时,收到,y,4,=011,时,收到,y,5,=100,时,收到,y,6,=101,时,收到,y,7,=110,时,收到,y,8,=111,时,通过在发送端增加冗余使消息出现一位传输错误时由接收端进行纠正,纠错,平均译码错误概率,如果选取其中,c,1,=000,，,c,7,=110,为许用码，其余为禁用码,2,个码字构成的码表中,及信源等概率条件下,在信道,x=0c,1,=000,，,x=1c,7,=110,三次扩展信源的子信源，三次扩展信宿,三次扩展信道的子信道,最大似然准则译码,收到,y,1,=000,时,收到,y,2,=001,时,收到,y,3,=010,时,收到,y,4,=011,时,收到,y,5,=100,时,收到,y,6,=101,时,收到,y,7,=110,时,收到,y,8,=111,时,通过在发送端增加冗余使消息出现一位传输错误时不能完全由接收端进行纠正,平均译码错误概率,线性分组码的编码,选取许用码,线性分组码的编码原则,保证最小码距足够大,线性分组码检错纠错的充要条件,线性分组码,(n,k),检,e,位错并同时纠,t,位错的充要条件,检一位错并同时纠一位错的充要条件,5,.,5,汉明,码,汉明码,最小码距,d,min,=3,的线性分组码,设,(,n,k,),汉明码的码字,为校验位，校验长度为,n-k,其中 为消息位，消息长度为,k,1,、汉明码的编码,编码步骤,构造满秩的,(,n-k)n,校验矩阵,H,r,i,第,i,个接收码字，,1,n,向量,s,i,第,i,个接收码字的误码标志，,1,(n-k),向量,c,i,第,i,个发送码字，,1,n,向量,设满秩的,kn,生成矩阵,G,x,i,第,i,个发送消息，,1,k,向量,由生成矩阵,G,与校验矩阵,H,之间,GH,T,=0,求出,G,即可编码,例1,(3,1),汉明码,构造满秩的,23,校验矩阵,H,所有,2,维非零列向量构成校验矩阵,H,，,如,设满秩的,13,生成矩阵,G,最小码距,(3,1),汉明码,三重复码能检一位错并同时纠一位错,(3,1),汉明码,的码长为原来的,3,倍,编码效率为,1/3,例,2,(7,4),汉明码的编码,构造满秩的,37,校验矩阵,H,所有,3,维非零列向量构成校验矩阵,H,，,如,设满秩的,47,生成矩阵,G,任意两个码字之间的码距,最小码距,(7,4),汉明码能检一位错并同时纠一位错,(7,4),汉明,码的码长为原来的,7/4,倍,编码效率为,4/7,2,、汉明码的译码,译码步骤,检错,误码标志,s,i,当出现一位传输错误,纠错,(,n-k),n,变换,+,模二加,通过,(,n-k),n,变换将误码标志,s,i,变换为形如,1000,，,0100,，,，,0001,，,00,00,的错误图案,e,i,错误图案,e,i,与接收码字,r,i,的模二加,例,3,(7,4),汉明码的译码,检错,误码标志,s,6,纠错,3-7,变换,+,模二加,检错,误码标志,s,6,纠错,3-7,变换,+,模二加,习题：,(P222)6.2(,取,h,1,h,2,h,3,h,4,=0010)(2),，,6.3(2)(3),