信息论与编码课件第五章.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第五章 信道编码定理,错误概率与译码规则,错误概率与编码方法,信道编码定理,第五章 作业教材第,141,页,142,页,5.1,，,5.3,信道编码,目的：提高抗干扰能力，使差错率最小。,实质：增加冗余度，扩大信号空间，增大信,号间距离。,重要意义：通过信道编码的方法，可以用不,可靠的信道实现可靠的传输。,信 源,编 码 器,信 源,译 码 器,信 道,编 码 器,信 道,译 码 器,信源,信宿,信道,u,y,x,干扰,编码器：编码函数，完成映射,编码器的输入：,码字分别为：,编码后的信息传输率：码字长为,n,物理意义：每个码元所能携带的最大信息量。,好码：在相同的差错控制（纠错能力）下，,越大，则相应的码越好。,问题：,R,能否无限制提高,?,如何衡量纠错能力？,例：二元对称信道,译码规则对错误概率的影响,译码器,A,译码规则：,接收符号,译码,0,0,1,1,错误概率与译码规则,分析,则在此译码器下，平均错误概率为（设输入为等概）,发出符号,接收符号,译码,正确概率,错误概率,0,0,0,1/3,0,1,1,p,e,(0),=2/3,1,1,1,1/3,1,0,0,p,e,(1),=2/3,译码器,B,译码规则：,分析,则在此译码器下，平均错误概率为（设输入为等概）,接收符号,译码,0,1,1,0,发出符号,接收符号,译码,正确概率,错误概率,0,0,1,p,e,(0),=1/3,0,1,0,p(0)=2/3,1,1,0,p,e,(1),=1/3,1,0,1,p(1)=2/3,结论：错误概率不仅与信道的统计特性有关，而且与译,码规则有关。,我们来定义译码规则,设信道的输入符号集为,X,=,a,i,，,i,=1,，,2,，,，,r,；,输出符号集为,Y,=,b,j,，,j,=1,，,2,，,，,s,。,制定译码规则就是设计一个单值函数,F,（,b,j,），,它对于,每一个输出符号,b,j,确定一个唯一的输入符号,a,i,与其对应。,即,F,（,b,j,）,=,a,i,i,=1,，,2,，,，,r,j,=1,，,2,，,，,s,注：对于同一有噪信道共有,r,s,种,译码规则可供选择。,例,5.1,：,可设计译码准则,译码准则,A,：,译码准则,B,：,译码规则总数为：,r,s,=,27,目标：在,r,s,个规则中找到理想的一个。,原则：使平均错误概率最小。,平均错误概率,P,E,如何计算？,收到符号,b,j,条件下译码正确的条件概率为,平均错误概率,P,E,：,条件错误概率 对输出空间,Y,取统计平均,物理意义：译码后平均收到一个符号所产生的错误的大小,要使,P,E,最小就应该选择,p,F,(,b,j,)|,b,j,为最大,。,最大后验概率准则（最小错误概率准则）,选择译码函数：,译码：将每一个输出符号译成具有最大后验概率的,输入符号，则信道的错误概率此时最小。,分析：,则,最大后验概率准则可另表述为,选择译码函数,使成立,最大似然译码准则,（,最大后验概率准则,特例）,设输入符号的先验概率等概，选择译码函数,使成立,译码：当收到,b,j,后,，译成信道矩阵中第,j,列中最大,的元素所对应的信源符号。,最大后验概率准则,：依赖于先验概率,p,(,a,i,),和信道传递概率,p,(,b,j,|,a,i,),选定译码函数。,最大似然译码准则,：直接从信道矩阵的传递概率中去选定译码函数。,当先验概率,p,(,a,i,),为等概率分布时，最大似然译码准则与最大后验概率准则等价。,平均错误概率,P,E,与译码规则（译码函数）有关。而译码规则又由信道特性来决定。,费诺不等式,H,（,X,|,Y,）,H,（,P,E,）,+,P,E,log(,r,1),重复发送,大数判决规则,信息数据,编码,1,编码,2,000,000000000,000000000,001,000000111,001001001,010,000111000,010010010,011,000111111,011011011,100,111000000,100100100,101,111000111,101101101,110,111111000,110110110,111,111111111,111111111,错误概率与编码方法,编码,1,：将每个码元重复三次,纠正任一位上的错误,设码字记为 由编码方法知,“择多译码”规则的依据,：连续出现两个错误的概率,远远小于出现一个错误的概率。,编码,2,：将每个码字重复三次,纠正任一位上的错误,纠正连续三位和三位以下码元的错误,由编码方法知,例 发送的码字为,0 1 0 0 1 0 0 1 0,干扰后收到为,0 1 1 1 0 0 0 1 0,此时,以上这两种重复码编码后的信息传输率相同为,但纠错能力不同，平均,错误概率,不同。,如何选择编码规则呢？,例：对,4,个等概消息编码,M,=4,第,种,M,=4,第,种,0 0 0,0 1 1,1 0 1,1 1 0,0 0 0,0 0 1,0 1 0,1 0 0,M,=4,第,种,0 0 0,0 1 1,1 0 1,1 1 0,最大似然译码规则下，计算平均错误概率,P,E,=,？,0.01,0.99,0.99,0.01,M,=4,第,种,0 0 0,0 0 1,0 1 0,1 0 0,在选择编码规则时，要使码字之间的最小距离,D,min,越,大越好。,结论：错误概率与编码方法有关。,码,A,码,B,码,C,码,D,码,E,码字,000,111,000,011,101,110,000,001,010,100,00000,01101,10111,11010,000,001,010,011,100,101,110,111,码字长度,n,3,3,3,5,3,消息数,M,2,4,4,4,8,码的最小距离,D,min,3,2,1,3,1,信息传输速率,R,（,比特,/,符号）,1/3,2/3,2/3,2/5,1,错误概率,P,E,（,最大似然译码）,310,-4,210,-2,2.2810,-2,7.810,-4,310,-2,能不能找到一种编码方法使,P,E,相当低（可靠性高），而,R,却保持在一定水平（有效性较高）呢？,定理,5.1,香农第二定理（信道编码定理）,设某信道有,r,个输入符号，,s,个输出符号，信道容量为,C,。,当信息传输率,R,C,时，只要码长,n,足够长，总可以在输入的集合中找到,M,个码字（代表,M,个等可能性的消息）组成的一个码（,M,2,n,(,C-,),，而,是一任意小的正数）和相应的译码规则，使信道输出的错误概率,P,E,任意小。,定理,5.2,（信道编码逆定理）设某信道有,r,个输入，,s,个输出，信道容量为,C,，令,为任意小的正数。若选用码字个数,M=,2,n,(,C+,),，,则无论,n,多大也不能找到一种编码，使译码错误概率任意小。,信道编码定理,译码规则,最小错误概率准则,最大似然译码准则,平均错误概率的计算,编码定理的意义（香农第二定理,）,第五章 小结,