信道编码(上)

第三章信道编码（计划学时18）,本章主要内容,检错、纠错原理2学时差错控制理论1.5学时线性分组码2.5学时循环码3学时循环码的扩展3学时卷积码3学时纠正突发错误的编码3学时,教学目的与要求1.深刻理解信道编码的检、纠错原理。2.熟练掌握建立译码规则的原则和计算错误概率的方法。3.掌握线性分组码、循环码、卷积码等重要的信道编码的原理与方法。（重点）4.了解Shnnon信道编码的内容和意义。,参考文献,1.王新梅：纠错码原理与方法西安电子科技大学出版社（2001年4月修正版）2.袁东风：宽带移动通信中的先进信道编码技术北京邮电大学出版社(2004年3月第一版)3.吴伟陵：信息处理与编码人民邮电出版社（1999年7月第一版）4.曹雪虹：信息论与编码北京邮电大学出版社(2001年8月第一版),第三章信道编码3.1检错、纠错原理,本节的主要内容,检错原理纠错原理汉明重量与最小码距检错纠错能力信道编码的性能指标几种简单的检、纠错码,外语关键词,信道编码：channelcoding检错与纠错：errordetectionandcorrection汉明距离：hammingdistance最小码距：minimumcodedistance重复码：repetitioncode奇偶校验码：parity-checkcode,温旧引新,三大编码：信源编码、信道编码和加密编码信源编码：压缩代码长度的编码。信道编码：为了减少差错而进行的编码。,3.1.1检错原理误码的必然性:在有噪声和损失存在的信道中，输入符号与接收符号不能一一对应，传输错误和判断错误的情况总会存在。误码的不可预知性：误码是随机发生的。接收端并不了解是否发生了误码，更不知晓是哪个码元出现错误。,检错-如何检测有无误码？办法很多。比如双连编码方式把每个0和1都重复一次，再送入信道。接收端一旦发现有违背“双连”规律的码元，就能判断该码元发生了错误。,原因-冗余的作用两个码元当一个用，增加了“冗余”，给误码留下了表达空间，才使码字克服了原先0和1“非此即彼”的情况，。,例1、用2位二进码传输四种天气状况：晴、阴、雨、风,被传信息只有2bit，冗余1bit。码字增加为23=8个，许用码字4个，非法码字4个。任意有1位发生错误时,该许用码将变成非法码。冗余使编码避免了非此即彼，具有了检错能力。,00011011,由于没有冗余,所以非此即彼,错了也不知,晴、阴、雨、风000011101110,例2、改用3位二进制码元传输它们：,思考题：1.信源编码中要压缩掉冗余，信道编码中又要添加进冗余，是不是返工浪费？两种冗余有何不同？2.是不是随便添加冗余,都能克服非此即彼?怎样的许用码才能有检错功能？,3.1.2纠错原理发现错误怎么办？有三种处理方案：（1）重发反馈方式（ARQ）；（2）自动纠错方式（FEC）；（3）混合纠错方式（FEC）；自动纠错的前提：不仅知道有错，还应知道是哪个码元出现错误。,双连码只能检错，不能纠错，因为冗余不够。三连重复码当其中任一码元出错时，还有2位没有错，通过比较就能发现是哪一位错了，从而可以进行纠正。万一三连重复码有两位码元出错时，就会判断失误。因为超出了它的纠错能力。三连重复码的纠错能力是1位，五连重复码的纠错能力是2位，添加的冗余越多，纠错能力就越强，然而传输效率就越低。冗余也是编码具有纠错能力的前提,汉明距离(Hanmingdistance)：定义两个许用码字相同码位上不同玛元的个数叫它们的汉明距离。汉明距离反映了两个码字的差别。双连重复码的汉明距离d=(00,11)=2；三连重复码的汉明距离d=(000,111)=3；双连重复码发生1位错的误码是01或10，与许用码字11或00的汉明距离相同，无法判别误码来自谁。当三连重复码有一位码元出错时，比如000变成001、010或100，误码与000的汉明距离为1，而与111的汉明距离为2，据此就可判定误码来自000；,例3、用5位二进码传输四种天气状况：,晴、阴、雨、风00000010111011011101,被传信息只有2bit，冗余3bit。共25=32个码字，许用码字4个，非法码字28个。当任意发生1位错误时,误码与源码的汉明距离是1位，而误码与其它码字的汉明距离是2位。更多的冗余不仅避免了码字之间非此即彼，而且能够帮助分析误码的可能来源，使编码具有了自动纠错能力。,检错原理：冗余的添入，增加了码字总数，给误码留下了空间，就给判断正确与错误提供了可能。纠错原理：更多冗余的添入，拉大了许用码字之间的汉明距离，就有可能区别误码与各个许用码字之间汉明距离的不同，从而判断误码可能的来源。,检、纠错原理小结,3.1.3汉明重量与最小码距汉明重量(Hammingweight)定义码字中码元1的个数叫做该码字的汉明重量。如：W01011=3；W00000=0；汉明重量与汉明距离的关系：d(u,v)=Wuvu和v是任意两个码字，代表按位模2加(异或)。u和v码元相同的位模2加为0，不同的位模2加为1，Wuv就给出了u和v不同位的个数。,最小汉明距离一种编码有许多个码字，全部两两比较后，可以找出最小的汉明距离d0。例3中：C1=00000；C2=01011；C3=10110；C4=11101；则：d(C1,C2)=3；d(C1,C3)=3；d(C1,C4)=4；d(C2,C3)=4；d(C2,C4)=3；d(C3,C4)=3；因此最小的汉明距离为d0=3（可纠1位错）例2中：C1=000；C2=011；C3=101；C4=110；同样不难求出最小的汉明距离为d0=2（可检错）例1中：C1=00；C2=01；C3=10；C4=11；同样可求出最小的汉明距离为d0=1（非此即彼）,定理：线性群码的最小汉明距离等于非零码字的最小汉明重量d0=Wmin.以例3的5位二进码传输四种天气状况：C1=00000；C2=01011；C3=10110；C4=11101；解释什么是线性码？C4=C2C3；C3=C2C4；C2=C3C4；C1=C2C3C4；任何一个码字都能由其它码字的模2加得到。什么是群码？各码字无论怎样模2加，都不会得到这4个码字之外的东西,这4个码字构成了一个封闭集合。可见它是线性群码，定理条件成立。于是d0=Wmin=3,定理的证明：设u与v之间码距最小，于是：d0=d(u,v)=WuvWmin式中uv是另一许用码字，其重量当然不应小于设定的最小重量Wmin；另一方面，设非零码字c具有最小重量，则：Wmin=Wc=Wc0=d(c,0)d0式中d(c,0)是码字c与全零码字0的距离，它当然不应小于设定的最小汉明距离d0；两式同时考虑，只能有d0=Wmin,逐层深入：,1、没有冗余不行，冗余是检错纠错的前提。2、随意添加一些冗余未必有用。应当通过有计划地添加冗余，使编码者能够恰当地选择许用码字，从而尽量拉大许用码字之间的汉明距离，为检错纠错创造条件。3、仅仅拉大个别码字之间汉明距离是无益的，只有全部码字的汉明距离都大才有意义。为此只须关注最小汉明距离。因此，足够多的冗余只是能够检错纠错的必要条件，而精心选择许用码字使它们的最小汉明距离大于某个数值才是能够检错纠错的充分条件。4、为了求得最小汉明距离，不必一一计算全部码字之间的汉明距离，只须寻找最小码字重量即可。,3.1.4检错、纠错能力检错、纠错能力与最小汉明距离有直接关系设d0为最小汉明距离，e为可检错位数，t为可纠错位数，则：(a)为了发现e个错误码元，要求最小码距d0e+1；(b)为了纠正t个错误码元，要求最小码距d02t+1；(c)为发现e个错码元，同时又能纠正其中t(tt当t=1时，1p，所以矩阵中含3和2p的矩阵元都较大，按最大似然准则选它们作为a*，可确定译码规则为：,F(0)=F(1)=F(2)=F(4)=0F(3)=F(5)=F(6)=F(7)=1,平均错误概率为：,与编码前单符号传输相比，差错率由原来的百分之一降低到万分之三。代价是传输效率为原来的三分之一。,3.2.6信道编码定理,定理：离散无记忆信道X,P(y|x),Y，X是信道编码使用的符号集，Y是接收符号集，P(y|x)为信道传输概率，信道容量为C。当信息传输率RC时，只要编码长度n足够大，总可以在长度为n的编码符号序列中找到M(=2nR)个许用码字和相应的译码规则，组成一个编码，使译码的错误概率PE任意小。逆定理：离散无记忆信道X,P(y|x),Y，P(y|x)为信道传输概率，其信道容量为C。当信息传输率RC时，无论码长n多大，也不可能找到一种编码，使译码错误概率任意小。,信道编码定理及其逆定理，合起来就是香农第二定理。它指出在有噪声干扰信道中高效率高可靠地传输信息是可能的，可靠指错误概率可任意小，高效指传信率可无限接近信道容量。约束条件是传信率不大于信道容量。其办法是使用有足够多冗余进行信道编码。香农第二定理仅指这种编码是存在的，并未给出实现这种编码的途径。,小结：译码规则译码错误概率的定义与计算制定译码规则的准则最大后验概率准则-有最小平的均错误概率最大似然准则-近等概信源的近似准则Shannon信道编码定理,课后复习题思考题：为什么用译码错误概率评判信道编码效果更科学？作业题：教材第114页习题三第9、13题；,第三章信道编码3.3线性分组码,本节的主要内容,线性分组码的基本概念编码方法校验原理纠正多位错的方法纠错能力的讨论,外语关键词：线性分组码：linearblockcodes生成矩阵：generatormatrix一致监督矩阵：parity-checkmatrix校验原理：parity-checktheorem伴随子向量：syndromevector错误格式向量：errorpatternvector纠错能力不等式：errorcorrectingcapabilityinequality,温旧引新,汉明距离：两码字不同码元的个数最小汉明距离=码字最小重量检纠错位数与最小汉明距离的关系：d0e+t+1(tr，HT的秩至多为r，可见，(d0-1)r，即d0r+1又由2t+1d0，可推知：tr/2,2.纠错位数不等式,HT是n行r列的矩阵，所以S=RHT是一行r列的向量，每位只能取0或1，它共有2r个不同的取值，扣除了S=0的一个无错状态，用它来区分不同的错误格式，最多不超过2r-1个。,为了能用伴随子S区分t位以内的所有错误格式，应当有：2r1Cn1+Cn2+Cnt此即纠错能力不等式：2rCn0+Cn1+Cn2+Cnt,另一方面，码长为n的码字，发生一位错码的方式有种，同时发生二位错的方式有种,发生t位错的方式有种。,下面以n=7的线性分组码为例进行讨论：(7,6)码：k=6，r=1，2r=2C70=1，t=0(7,5)码：k=5，r=2，2r=4C70=1，t=0(7,4)码：k=4，r=3,2r=8=C70+C71=1+7=8，t=1(7,3)码：k=3，r=4,2r=16C70+C71=1+7=8，t=1(7,2)码：k=2，r=5,2r=32C70+C71+C72=1+7+21=29，t=2(7,1)码：k=1，r=6，2r=64=C70+C71+C72+C73=1+7+21+35=64，t=3,3.完备码：纠错不等式中，取等号的线性分组码称为完备码。如(7,4)码和(7,1)码。取等号说明冗余得到了最充分的利用，完备码的冗余利用率最高。迄今为止发现的完备码并不多，主要有汉明码、奇连重复码和高莱码。（1）汉明码是能纠正一位错的完备码。满足：2r=1+Cn1=1+n；或：n=2r-1；汉明码可表达为（2r-1,2r-1-r)。r=2时：n=2r-1=3，构成（3,1）汉明码；r=3时：n=2r-1=7，构成（7,4）汉明码;r=4时：n=2r-1=15，构成（15,11）汉明码；,（2）奇连重复码是能纠正多位错的完备码。k=1,n=d0=2t+1,r=n-1；可表达为(n,1)码，它满足纠错能力不等式取等号。例如：三连重复(3,1)码；22=4=1+C31=1+3五连重复(5,1)码；24=16=1+C51+C52=1+5+10;七连重复(7,1)码：26=64=1+C71+C72+C73=1+7+21+35（3）高莱码是能纠正三位错的完备码。高莱码表达为(23,1