1、第九章 差错控制编码9.1 引言9.2 纠错编码的基本原理9.3 常用的简单编码9.4 线性分组码9.5 循环码9.1 引言由于数字信号在传输过程中受到干扰的影响，使信号码元波形变坏，故传输到接收端后可能发生错误判决。由信道中乘性干扰引起的码间干扰，通常可以采用均衡的办法纠正，而加性干扰的影响则要从其它途径解决。差错控制编码即是减少加性干扰造成错误判决的措施之一。信道编码的主要原理：在传输信息的同时加入信息冗余，通过信息冗余来达到信道差错控制的目的。基本思路：在发送端将被传输的信息附加上一些监督码元，多余的码元与信息码元之间以某种确定的规则相互关联（约束）。接收端按照既定的规则校验信息码元与监
2、督码元之间的关系，一旦传输发生差错，则信息码元与监督码元的关系就受到破坏，从而接收端可以发现错误乃至纠正错误。 错误的类型随机错误：发生的位置是随机的，而且数字序列中前后之间是否发生错误，彼此无关。多数情况下是独立的单个数据发生错误。以随机错误为主的信道称为随机信道 。突发错误：在一些短促的时间区间内错误突发出现，密集成群，而在这些短促的时间区间之间却又存在较长的无错码区间。以这种突发错误为主要错误形式的信道称为突发信道。产生突发错码的主要原因之一是脉冲干扰，而信道中的衰落现象也是产生突发错码的另一主要原因。差错控制方法检错重发法：接收端在收到的信码中检测出（发现）错码时，即设法通知发送端重发
3、，直到正确收到为止。前向纠错法：接收端不仅能在收到的信码中发现有错码，还能够解定错码的位置，纠正错码。反馈校验法：接收端将收到的信码原封不动地转发回发送端，发送端将其与原发送信码比较，如果发现错误，则重发。自动要求重发系统ARQ系统（ Automatic Report reQuest）ARQ系统的三种工作过程差错控制编码分类 在信息码元序列中加入监督码元就称为差错控制编码，也称为纠错编码。不同的编码方法，有不同的检错或纠错能力。一般地，编码中增加的监督码元越多，检（纠）错的能力就越强。差错控制编码原则上是以降低信息传输速率为代价来换取传输可靠性的提高。 分 类： 功能不同分：检错码、纠错码、和
4、纠删码； 信息码元和附加的监督码元之间的检验关系分：线性码和非线性码； 信息码元和监督码元之间的约束方式分：分组码和卷积码； 信息码元在编码后是否保持原来的形式不变分：系统码和非系统码； 纠正错误的类型分：纠正随机错误码和纠正突发错误码； 编码的数学方法分：代数码、几何码和算术码； 实例一： “明天14：0016：00开会” “明天10：0016：00开会” 改：“明天下午14：0016：00开会” “明天下午10：0016：00开会” 改：“明天下午14：0016：00两个小时开会” 9.2 纠错编码的基本原理实例二：000(晴) 001(云) 010(阴) 011(雨) 100(雪) 10
5、1(霜) 110(雾) 111(雹)000(晴) 011(云) 101(阴) 110(雨)000(晴) 111(雨)二 纠错码的基本概念分组码将输入的信息分成不同的组，对各组信息分别独立编码，附加若干监督码的编码集合，为分组码。分组码一般用符号(n,k)表示，其中k是每组二进信息码元的数目，n是编码组的总位数，又称为码组长度（码长），n-k=r为每码组中的监督码元数目，或称监督位数目。分组码是对每段k位长的信息组以一定的规则增加r个监督元，组成长n的码字。在二进制情况下，共有2k个不同的信息组，相应地可得到2k个不同的码字，称为许用码组；其余2n-2k个码字未被选用，称为禁用码组。 an-1
6、an-2 ar ar-1 a0k个信息位r个监督位码长n=k+r在分组码中，码组（码字或码矢）中码元的数目，称为码组的长度（简称码长）；码组中把“1”的数目（即非0的数目）称为码组的重量（简称码重）； 码长、码重和码距 码长、码重和码距 在分组码中，把“1”的数目称为码组的重量，而把两个码组对应位上数字不同的位数称为码组的距离，简称码距，又称汉明(Hamming)距离。某种编码中各个码组间距离的最小值称为最小码距（d0）。三 检错、纠错能力任一(n,k)分组码，若要在码字内： 检测e个随机错误，则要求码的最小距离 ； 纠正t个随机错误，则要求码的最小距离 ； 纠正t个同时检测e( )个随机错误
7、，则要求码的最小距离 ； 10 ed120 tdte 10etd码距与检错和纠错能力的关系四 编码效率编码效率R来衡量有效性：对纠错码的要求：检错和纠错能力尽量强；编码效率尽量高；编码规律尽量简单。 nkR 9.3 常用的几种简单分组码 奇偶监督码二维奇偶监督码恒比码正反码9.3.1 奇偶监督码奇偶监督码可分为奇监督码和偶监督码两种，两者的原理相同。在偶(奇)数监督码中，无论信息位有多少 ，监督位只有一位，它使码组中“1”的个数为偶(奇)数，即满足 an-1 an-2 a0=0(1) 式中a0为监督位，其它为信息位。在接收端，将码组中各码元模2加，若结果为“1”(“0”)就说明存在错码，为“0
8、”(“1”)就认为无错。9.3.2 二维奇偶监督码二维奇偶监督码又称方阵码。它是把奇偶监督码的若干码组排列成矩阵，每一码组写成一行，然后再按列的方向增加第二维监督位。9.3.3 恒比码（等重码或定1码） 在恒比码中，每个码组均含有相同数目的“1”（和“0”）。由于“1”的数目和“0”的数目之比保持恒定，故得此名。这种码在检测时，只要计算接收码组中“1”的数目是否对，就知道有无错误。恒比码的主要优点是简单和适于用来传输电传机或其它键盘设备产生的字母和符号。对于信源来的二进随机数字序列，这种码就不适合使用了。 “5中取3”恒比码：（我国电传通信中用） 阿拉伯数字保护电码国际电码阿拉伯数字保护电码国
9、际电码123450101111001101101101000111111011100110000010100000167890101011110001110100110110110101111000110000011011019.3.4 正反码正反码是一种简单的能够纠正错码的编码。其监督位数目与信息位数目相同，监督码元与信息码元相同（是信息码的重复）或者相反（是信息码的反码），则由信息码中“1”的个数而定。长度为10的正反码具得纠正一位错码的能力，并能检测全部两位以下的错码和大部分两位以上的错码。9.3.5 ISBN国际统一图书编号 国内外出版的图书封底右下角印有诸如ISBN 0-1315-2
10、447-X形式的国际统一图书编号，这种编号也是一种检错码。第一位数字是国家代码，“0”美国及其他英语国家出版物；“7”中国；“1315”代表出版公司；“2447”代表书名编号；“X（罗马字）”校验位。 9.4 线性分组码线性分组码，是指信息位和监督位满足一组线性方程，即其编码规则可用一组线性方程来描述的分组码。线性码有一个重要性质，就是它具有封闭性。即线性码中的任意两个码组之各仍为该码中的一个码组。线性码又称群码。一 基本概念在(n,k)线性分组码中，每一个监督元都是码组中某些信息元按模2和而得到。例（7，4）分组码，设其码字为A=a6 a5 a4 a3 a2 a1 a0，其中前4位是信息元，
11、后3位是监督元，可用下列线性方程组描述该分组码，产生监督元。 346035614562aaaaaaaaaaaa经计算可得（7，4）码的全部码字 。表91 （7，4）码的码字表 序号码 字序号码 字信 息 元监 督 元信 息 元 监 督 元00 0 0 00 0 081 0 0 01 1 110 0 0 10 1 191 0 0 11 0 020 0 1 01 0 1101 0 1 00 1 030 0 1 11 1 0111 0 1 10 0 140 1 0 01 1 0121 1 0 00 0 150 1 0 11 0 1131 1 0 10 1 060 1 1 00 1 1141 1 1
12、01 0 070 1 1 10 0 0151 1 1 11 1 1二 监督矩阵H和生成矩阵G1 监督矩阵H： 设（7，4）汉明码的码字它有三个监督元，可建立三个互相独立的监督关系式： 0123456aaaaaaaA 000034613562456aaaaaaaaaaaa 矩阵形式： 0001001101010101100101110123456aaaaaaaTTAH00THA简记为： 或： 其中 是A的转置， 是 的转置， 是H的转置； 称为（7，4）汉明码的监督矩阵。(n,k)线性分组码的监督矩阵H由r行n列组成，这r行是线性无关的。 TAT00000 TH10011010101011001
13、0111H系统码的监督矩阵可写成如下形式： 称为典型监督矩阵。是r*r的单位矩阵，p是r*k的矩阵。上监督矩阵H有： 100110101010110010111rIpHrpIH 110110110111p2 生成矩阵G：若将监督方程补充为下列方程：346035614562445566aaaaaaaaaaaaaaaaaa345601234561101101101111000010000100001aaaaaaaaaaa其中，TTTaaaaGA3456GaaaaA3456变换为： 1101000101010001100101110001G = 称为生成矩阵。由生成矩阵及信息组可产生出全部码字。G由
14、K行n列组成，每一行是一个码字，K行线性无关。系统码的生成矩阵可写成： 称为典型生成矩阵。由典型生成矩阵得出的码组A中，信息位不变，监督位附加于其后，这种码称为系统码。 TkkPIQIG三 伴随式（校正子）S设发送码组接收码组则发送码组和接收码组之差为：它是传输中产生的错码行矩阵：其中： 0121aaaaAnn0121bbbbBnn)2(模EAB0121eeeeEnniiiiiababe当当, 1, 0可写成： 。令 ，称为伴随式或校正子。由于E为1*n，为n*r矩阵，所以S为1*r的矩阵，即r列的行矩阵： EABTBHS TTTTTEHEHAHHEABHS)(0121ssssSnn按照上述方
15、法构造的纠正单个错误的线性分组码称为汉明码。其特点：码长：信息码位： 监督码位：r=n-k=m；最小码距：d0=3；纠错能力：t=1。 12mn12mkm汉明码的编码效率：汉明码能纠正一个错码，则要求： 2r-1 n 或2r k+r+1汉明码的编码效率等于：K/n=(2r-1-r)/(2r-1)=1-r/(2r-1)=1-r/n可见，汉明码是一种高效码。四 系统码与非系统码设信息位为 ，若编码后的码组为： ，其中， 是监督位，则称这种码为系统码。即系统码经过编码后的码组中前k个是信息位，后n-k是监督位。若不存在上述关系，则称为非系统码。knnnaaa210121aaaaaknknnn01aa
16、knTPQ 0TGH只有系统码才有关系：系统码和非系统码均有：。 9.5 循 环 码一 定义及特点 循环码是一类特殊的线性分组码，特点是循环性。所谓循环码（Cyclic Code）就是任何一个码字循环右移一位后所得到的仍是一个合法码字，也就是说这个码在循环位移运算下具有封闭性。在代数理论中，常用码多项式表示码字。(n,k)循环码的码字，其码多项式（以降幂顺序排列）： 012211)(axaxaxaxAnnnn例1 （7，3）循环码：序号 码 字0123456700001111001100110101010101011010011010010011110001100110例2 （7，3）循环码码
17、组编号信息位监督位码组编号信息位监督位a6a5a4a3a2a1a0a6a5a4a3a2a1a01000000051001011200101116101110030101110711001014011100181110010（7，3）循环码00000000010111100101111001011110010 01011101011100 0111001二 生成多项式及生成矩阵 若一种码的所有码多项式都是多项式g(x)的倍式，则称g(x)为该码的生成多项式。在(n,k)循环码中任意码多项式A(x)都是最低次码倍式。因此，循环码中次数最低的多项式（全0码字除外）就是生成多项式g(x)。可以证明，g
18、(x)是常数项为1的r=n-k次多项式，是xn+1的一个因式。 循环码的生成矩阵常用多项式的形式来表示： )()()()()(21xgxxgxgxxgxxGkk1)(111xgxgxxgrrr其中 例:（7，3）循环码，n=7，k=3，r=4，其生成多项式及生成矩阵分别为： 1)()(2341xxxxAxg1)()()()(23434524562xxxxxxxxxxxxgxxgxgxxG101110001011100010111G三 监督多项式及监督矩阵监督多项式定义：其中，g(x)是常数项为1的r次多项式，是生成多项式；h(x)是常数项为1的k次多项式； 1)()(1111xhxhxxgxx
19、hkkkn监督矩阵H定义： )()()()()(*2*1xhxxhxhxxhxxHknkn1)(12211*xhxhxhxxhkkkk是h(x)的逆多项式； 例：（7，3）循环码， 1)(234xxxxg则： 1)(1)(237xxxgxxh1)(3*xxxh1)(324235346xxxxxxxxxxxxH1101000011010000110100001101H即：四 循环码的编码方法和电路1 循环码的编码方法根据给定的(n,k)值选定生成多项式g(x)，即应在xn+1的因式中选一r=n-k次多项式作为g(x)。设m(x)为信息码多项式，其次数小于k； 12231)(axaxaxaxmkk
20、编码步骤：（1）用xn-k乘m(x)；（2）用g(x)除xn-km(x) ，得到商Q(x)和余式r(x)，即： ，将余式r(x)加于信息位之后作为监督位，得到的多项式必为一码多项式；（3）编出的码组： T(x)= xn-km(x)+r(x) )()()()()(xgxrxQxgxmxkn例：（7，3）码编码器：2 循环码的解码方法 接收端译码的目的是检错和纠错。检错：将接收码组R(x)用原生成多项式g(x)去除，以余式r(x)是否为零判别码组中有无错码。纠错：（1）用生成多项式g(x)除接收码组R(x)，得出余项r(x)；（2）按余式用查表的方法或通过某种运算确定错码位置；（3）纠正错码。 循
21、环码的纠检错能力：已知循环码由g(x)生成，所以g(x)就决定了由它生成的循环码的纠检错能力。循环码有着极强的纠检错能力，在通信和计算机系统中有着广泛的应用。 结论1：若生成多项式g(x)的项数大于1，则由其所生成的循环码能够检测所有的单个错误。结论2：若生成多项式g(x)含有因式(1+x)，则由其生成的循环码能够检测所有奇数个错误。结论3：若码长n不大于g(x)的周期l，则由g(x)所生成的循环码能检测所有单个错误和两个错误，即dmin3，或者说至少能够纠正所有单个错误。所谓多项式的周期，就是使该多项式能够除得尽xl+1的最小正整数l。如果多项式的次数为r，且其周期l=2r-1，则称该多项式
22、为本原多项式。结论4：设g(x)的次数为r，则由g(x)所生成的循环码能够检测长度br的突发错误。 3 常用的循环码国际电报电话咨询委员会（CCITT）推荐的CRC-CCITT，用于8单位国际5号字母表传输时，用生成多项式g(x)= x16+x12+x5+1生成循环码。美国二进制同步系统中采用CRC-16，生成多项式为g(x)= x16+x15+x2+1 ，用于8单位码传输检错；采用CRC-12，生成多项式为g(x)= x12+x11+x3+x2+x+1 ，用于6单位码传输检错。 局域网中广泛应用的CRC-32，生成多项式为g(x)=x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1。
