信道编码(上)

第三章信道编码（计划学时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“非此即彼”的情况，。正误应有别-------许用码字与非法码字两位一组，有00，01，10，11四种方式。00与11是符合双连规律的，称为许用码字。01与10是违背双连规律的，称为非法码字。从而正与有了区别。例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的个数叫做该码字的汉明重量。如：W[01011]=3；W[00000]=0；•汉明重量与汉明距离的关系：d(u,v)=W[u⊕v]u和v是任意两个码字，⊕代表按位模2加(异或)。u和v码元相同的位模2加为0，不同的位模2加为1，W[u⊕v]就给出了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=C2⊕C3；C3=C2⊕C4；C2=C3⊕C4；C1=C2⊕C3⊕C4；任何一个码字都能由其它码字的模2加得到。什么是群码？各码字无论怎样模2加，都不会得到这4个码字之外的东西,这4个码字构成了一个封闭集合。可见它是线性群码，定理条件成立。于是d0=Wmin=3定理的证明：设u与v之间码距最小，于是：d0=d(u,v)=W[u⊕v]≥Wmin式中u⊕v是另一许用码字，其重量当然不应小于设定的最小重量Wmin；另一方面，设非零码字c具有最小重量，则：Wmin=W[c]=W[c⊕0]=d(c,0)≥d0式中d(c,0)是码字c与全零码字0的距离，它当然不应小于设定的最小汉明距离d0；两式同时考虑，只能有d0=Wmin逐层深入：1、没有冗余不行，冗余是检错纠错的前提。2、随意添加一些冗余未必有用。应当通过有计划地添加冗余，使编码者能够恰当地选择许用码字，从而尽量拉大许用码字之间的汉明距离，为检错纠错创造条件。3、仅仅拉大个别码字之间汉明距离是无益的，只有全部码字的汉明距离都大才有意义。为此只须关注最小汉明距离。因此，足够多的冗余只是能够检错纠错的必要条件，而精心选择许用码字使它们的最小汉明距离大于某个数值才是能够检错纠错的充分条件。4、为了求得最小汉明距离，不必一一计算全部码字之间的汉明距离，只须寻找最小码字重量即可。3.1.4检错、纠错能力检错、纠错能力与最小汉明距离有直接关系设d0为最小汉明距离，e为可检错位数，t为可纠错位数，则：(a)为了发现e个错误码元，要求最小码距d0≥e+1；(b)为了纠正t个错误码元，要求最小码距d0≥2t+1；(c)为发现e个错码元，同时又能纠正其中t(te)个错误码元，要求最小码距d0≥e+t+1；eABABABetttt(a)d0≧e+1(b)d0≧2t+1(c)d0≧t+e+1且et纠错、检错能力与最小码矩的关系如果只检错不纠错，则最多检错位数是e=d0-1。如果只纠错不检错，则最多纠错位数是：t=INT[(d0-1)/2]，INT表示取整数如果既纠错又检错，则e和t就不能独立，它们应满足关系式：e+t≤d0-1，而且e必须大于t，[例1]已知汉明距离d0=7,分析检、纠错能力。（1）只检不纠：e=d0-1=6；可检到6位错。（2）只纠不检：t=(d0-1)/2=3；可纠3位错。（3）又检又纠：e与t不独立：e+t≤d0-1，且et当t=1时，1e≤5，1位错已纠，能检出第2—5位错。当t=2时，2e≤4，2位错已纠，能检出第3—4位错。当t=3时，e无解，3位错已纠，3位以上无能力检到。3.1.5信道编码的性能指标编码效率设某种编码的码字长n位，其中信息只有k位，r=n–k为冗余位，最多可纠错t位。则考察编码效率的指标有：（1）信息传输率：η=k/n（2）错位可纠率：δ=t/n（3）冗余利用率：ζ=t/r漏检率把编码检查不出的错误所出现的概率叫做漏检率。差错率把编码不能自动纠正的错误所出现的概率叫做差错率。[例2]讨论双连重复码的编码效率和漏检率。编码效率η=k/n=1/2=0.5假设对称信道，0与1的错误概率均为p，则：漏检率=2位同时出错的概率=p2[例3]讨论三连重复码的编码效率和差错率。编码效率η=k/n=1/3=0.33差错率=3位同时出错的概率+2位出错1位正确的概率=p3+3p2(1-p)[例4]某线性群码由以下16个码字组成：C0(0000000)C1(0001011)C2(0010110)C3(0011101)C4(0100111)C5(0101100)C6(0110001)C7(0111010)C8(1000101)C9(1001110)C10(1010011)C11(1011000)C12(1100010)C13(1101001)C14(1110100)C15(1111111)求最小汉明距离、可纠错位数、编码效率和差错率。解：最小汉明距离:d0=Wmin=3可纠错位数:t=(d0-1)/2=1编码效率：∵m=16k=logm=4n=7∴η=k/n=4/7=0.71差错率=1-(1-p)7-7p(1-p)63.1.6几种简单的检错、纠错码（1）n连重复码n为奇数时，可纠正t=(n-1)/2位错误。错传概率为p时，差错率=n位同时出错的概率+(n-1)位出错1位正确的概率+……+(n+1)/2位出错(n-1)/2位正确的概率=pn+Cn1pn-1(1-p)+……+Cn(n-1)/2p(n+1)/2(1-p)(n-1)/2n为偶数时，可纠正(n/2-1)位错误，还能发现第n/2位出错。漏检率=n位同时出错的概率+(n-1)位出错1位正确的概率+……+(n/2+1)位出错(n/2-1)位正确的概率=pn+Cn1pn-1(1-p)+……+Cn(n/2-1)p(n/2+1)(1-p)(n/2-1)它的编码效率很低，只有η=1/n（2）奇偶校验码k个信息位后面添加1位“奇偶校验位”，其关系为：编码效率它的效率很高，达到：η=（n-1)/n=1-1/n检、纠错能力可查出任何奇数位的错误，却不能发现偶数位的错误，也没有纠错能力。漏检率=Cn2p2(1-p)n-2+Cn4p4(1-p)n-4+……（3）双向监督码为了增加奇偶校验码的检错能力，对列再进行奇偶校验，增加一行“竖直奇偶校验位”，进行双向监督。也称方阵码。信息位监督位110101010010110011111001100001001111000011列监督干扰造成的误码，往往发生在连续若干个码元上。采用上述双向监督，就把行中难以发现的错误，在列中发现。（4）恒比码从n位二进制自然码中挑出１和０的个数之比恒定的一些码字组成许用码集合。五中取三码是从25=32个二进自然码中挑出含3个1，2个0的码字，共1