差错控制编码(纠错码)

1第八章差错控制编码2●——主要内容§8.1引言§8.2纠错编码的基本原理§8.3线性分组码§8.4循环码§8.5小结3§8.1引言在数字信号传输中，由于噪声的存在及信道特性不理想，都可使信号波形失真，从而在接收端就不可避免的产生错误判决。引起误码原因:(1)信道特性不理想(乘性干扰):引起码间串扰，通常可采用均衡的办法纠正。(2)噪声影响(加性干扰):需借助各种差错控制编码技术来克服。一、基本概念4差错控制编码又称为信道编码(纠错编码)，要求在满足有效性前提下，尽可能提高数字通信的可靠性纠错编码：在要传送的数字信息序列中按一定规则加上一些冗余码元（监督位),使序列按满足一定数学规律的码字传输(编码过程);译码:在接收端,利用这种规律性来鉴别传输过程是否发生错误或纠正错误，恢复原始信息序列。5二、纠错编码的分类按功能分：检错码和纠错码按监督码元与信息码元之间是否存在线性关系分：线性码与非线性码按信息码元与监督码元之间的约束关系不同分：分组码与非分组码如卷积码按信息码元在编码后是否保持原来的信号形式分：系统码与非系统码按纠正差错的类型分：纠正随机错误的码与纠正突发错误的码按码元的取值分：二进制码与多进制码6三、误码的类型随机误码•错码出现是随机的、错码之间统计独立。•由随机噪声引起•存在随机误码的信道称为随机信道突发误码•错码成串集中出现，在很短的时间出现大量错码，而过后又存在较大的无错码位，且差错之间是相关的•例如：脉冲噪声，信道中衰落•存在这种差错的信道称为突发信道7四、差错控制方法（1）前向纠错（FEC）8优点：无需反向信道、译码总延迟恒定，具有恒定的信息传输速率缺点：当纠错能力强时，要增加冗余位；接收可靠性对信道传输条件的恶化很敏感（2）自动要求重发（ARQ）9优点：极低的不可检测概率；编译码简单；对任何信道都有效缺点：需要反向信道；译码延迟不固定；需要缓冲器（3）FEC/ARQ混合系统分为三类：停止等待ARQ、连续ARQ和选择重发ARQ综合利用FEC延迟小，纠错能力强和ARQ传输可靠性高10发端发出同时具有检错和纠错能力的码，收端收到后，检查错误情况：如果错误在纠错能力之内，则自动纠正；若超出纠错能力，但在检错能力之内，则经反向信道要求重发。注意：不同的纠错编码方法，有不同的检错或纠错能力，一般说来，增加监督码元越多，检错或纠错的能力就越强，提高传输可靠性是以降低传输有效性为代价的。11§8.2纠错编码的基本原理简单例子：3位二进制码组（c1c2c3）,其中ci=0或1。此码组有8种不同的组合：000001010011100101110111可分别代表不同的信息含义。若将8种码组都作为有用码组来使用，比如代表8种天气情况：000（晴），001（雷），010（雹），011（阴），100（风），101（云），110（雨），111（雪）12任一码组在传输中若发生一个或多个错码，则将变成另一信息码组这种编码方法就不具有任何抗干扰能力：但如果在8种码组中，规定只准使用其中4种来传输信息，比如，许用码组为：000（晴），011（阴），101（云），110（雨）这种编码接收端有可能检测码组中出现的一位或三位错误，但不能发现两位错码的情况接收端收到禁用码组时，就认为发现了错误13这种方法只能检测错误，但不能纠正错误比如：当接收端收到禁用码组100时，无法判决哪一位码发生了错误000（晴）101（云）110（雨）错一位100要想纠正错误，需要增加多余度，比如，只准使用两个码组14000（晴）111（阴）其他均为禁用码组，则它可检测两个错码或能纠正一个错码。如：接收端接收到禁用码组100，若认为只有一个错码，可纠正，若错码数不超过2个，只能检测错误4种信息完全可以由2位二进制数字来表示，即前两位。可见，第三位完全是多余的，这第三位就作为附加的监督码15一、纠错编码的基本思想发送端按照某种规则在信息序列上附加监督码元，接收端则按照同一规则检查两者间关系码的检错和纠错能力是用信息量的冗余来换取的。添加的冗余越多，码的检错、纠错能力越强，但信道的传输效率下降也越多。以牺牲通信的有效性（信息传输速率）来提高可靠性16二、纠错编码的理论基础理论依据：Shannon信道编码定理定理指出：对于一给定的有干扰信道，若其信道容量为C，只要发送端以低于C的速率R发送信息，则一定存在一种编码方法，使编码错误概率P随着码长n的增加，按指数下降到任意小的值。)(RnEePE（R）称为误差指数，n编码长度，R信息发送速率17三、编码距离与纠错检测的关系码重：二进编码序列V中，包含1的个数为该码组的重量（权），W(v)码距：两个等长码组V1,V2中对应码位上不同二进制码元的个数，也叫汉明距离，d(V1,V2)例：V1＝{11001100}和V2={10010111}重量分别为W1＝4，W2＝5；它们的距离为d(V1,V2)=5。两码组间的汉明距离也等于两码组对应位模二加后所得码组的重量)21()2,1(VVWVVd几个基本概念18最小码距：对于某种编码，所含的全部码组之间的最小距离，成为该码的最小码距，用dmin表示最小码距的大小直接关系着这种编码的检错和纠错能力，它是衡量各种码抗干扰能力大小的标准。码组的最小距离越大，说明码字间的最小差别越大，抗干扰能力越强。最小码距与检错和纠错能力的关系1)如果一个码能检错不多于e个错，则要求1mined2)如果一个码能纠正不多于t个错，则要求12mintd192)如果一个码能纠正不多于t个错，同时可以检e个错误则要求1minted四、编码效率设编码序列长度与所包含的信息位数分别为n,k，则编码效率指一个码组中信息位所占比重：rkknk20编码效率是衡量码性能的一个重要参量，编码效率与抗干扰能力这两个参数是相互矛盾的编码的主要任务就是如何找到一种编码，在满足一定误码率要求的前提下，尽量提高编码效率。五、编码增益描述编码系统对非编码系统性能的改善程度，定义为在给定误码率要求下，非编码系统与编码系统之间所需信噪比的差。编码增益越大越好21§8.3线性分组码一、基本概念分组码将信息码首先分成若干组，然后为每组信码附加若干位监督码元，这种编码称之为“分组码”分组码一般用（n,k）表示，k是信息码的位数，n是码组长度，监督码元位数r=n-k，分组码结构1nc2ncrnc1rc2nc0c码长n=k+rk个信息位r个监督位22注意：在分组码中，监督码仅监督本码组中的信息码元。在非分组码中如卷积码，监督码元除了与本组信息码元有关，还与其它组的信息码元有关线性码码组中监督码元和信息码元之间满足线性变换关系，由一组线性方程（监督方程）构成。线性码是一种代数码。奇偶监督码是最简单的线性码。23二、几种简单的线性分组码1、重复码(n,1)的线性分组码，最小码距为n，当n很大时，编码效率低，纠错能力强，2、奇偶校验码只有一个监督码（校验位）的（n,n-1）的分组码。分为两种：奇数校验码和偶数校验码24奇数校验码：附加一位监督码，使码组中“1”的个数为奇数设码字（vn-1,vn-2,…,v1,v0），v0为监督元，则有：vn-1＋vn-2＋…＋v1＋v0＝1（8-1）在接收端，按上式计算各码元，若结果为0认为有错；否则，无错。如：110100模2加偶数校验码：附加一位监督码，使码组中“1”的个数为偶数，vn-1＋vn-2＋…＋v1＋v0＝0即满足：（8-2）（8-1）与(8-2)叫做监督方程或监督关系式25在接收端，按上式计算各码元，若结果为1认为有错；否则，无错。如：110101注意：只能检测奇数个错误，当错码为奇数个时，由于打乱了码字中”1”个数的奇偶性，故能发现差错。但当错码为偶数个时，因码字中1个数奇偶性保持不变，则无法发现错码。特点：结构简单，易于实现，编码效率高，虽然不理想，但干扰不严重时，且码长不长的情况下仍很有用。263、方阵码也叫二维奇偶校验码（矩阵码、行列监督码），其基本原理与简单的奇偶校验码相似。不同的是每个码元都要受到行和列的两项监督编码方法：将所要传送的码序列编成一个方阵，方阵中每一行为一个码组。每行的最后加上一个监督码元，进行奇偶监督。在每列的最后也加上一个监督码，进行奇偶监督27例：若发送码序列为（1100100111010001110000100111100101011000011000000111……）,求其奇偶监督方阵11001001110010001110000010011110101010110000011000000111001111100经编码后的校验位和信息位一起传输:（11001001110010001110000010011110101010110000011000000111001111100……）28特点：（1）有可能检测偶数个错误，但是不能检测在方阵中构成矩形四个角的错误，因为在行列两个方向均有偶数个错误。（2）适于检测突发错码，能纠正突发错误，如当码组中仅在一行有奇数个错误时，能够确定错误位置，并纠正它。（3）mn(m1)(n1)编码效率信息码元共m行n列294、恒比码（等比码或等重码）每个码组中含“1”和“0”的个数的比例恒定在检测时，计算接收码组中“1”的数目是否正确，能检测出所有奇数个错误，并能部分检测出偶数个错误（成对交换错误检测不出）简单，适用于电传机或其它键盘设备产生的字母和符号例：我国电传机用“5中取3”恒比码表示10个数字30表我国五单位保护电码表数字电码数字电码001101500111101011610101211001711100310110801110411010910011在国际无线电报通信中，广泛采用“7中取3”恒比码。（是一种五中取三码）31四、线性分组码编码原理1、汉明码：能纠正单个随机错误且编码效率较高的线性分组码，其参数：监督位：3m且knm码长：12mn信息位：mm12最小距离：3mind编码效率：1211212mmmmmnk当m很大时，1322、以（7，4）汉明码为例来说明编码原理设码字为a6a5a4a3a2a1a0，信息码元a6、a5、a4、a3来源于待编码的信息序列；监督码元a2、a1、a0的取值应根据信息码元按监督关系式来决定a6+a5+a4+a2=0a6+a5+a3+a1=0a6+a4+a3+a0=0a2=a4+a5+a6a1=a3+a5+a6a0=a3+a4+a6（8-3）每个方程分别为某一个监督码元的奇偶校验方程。通常称这几个线性方程为对应码的一致监督关系式或一致校验方程33信息位监督位信息位监督位a6a5a4a3a2a1a0a6a5a4a3a2a1a00000000100011100010111001100001010110100100011110101100101001101100001010110111010100110011111010001110001111111给定信息位后，根据上式算出各监督位，该编码的所有码组如下表34（1）监督矩阵（奇偶校验矩阵）1·a6+1·a5+1·a4+0·a3+1·a2+0·a1+0·a0=01·a6+1·a5+0·a4+1·a3+0·a2+1·a1+0·a0=01·a6+0·a5+1·a4+1·a3+0·a2+0·a1+1·a0=0a6+a5+a4+a2=0a6+a5+a3+a1=0a6+a4+a3+a0=0上式监督关系式(8-3)可写成350001001101010101100101110123456aaaaaaa写成矩阵形式可记为：H·VT=0T或V·HT=06543210VaaaaaaaO00036r1110100H11010101011001PIH称为线性码监督矩阵r×n阶矩阵监督矩