1、1现代通信原理第十一章 差错控制编码和线性分组码2单元概述单元概述 实际信道传输数字信号时，不可避免地会产生误码。差错控制编码的目的是用信道编码的方法检测和纠正误码，降低误比特率。在检错重发控制编码方式中，信道编码只是为了检测误码，而在前向纠错方式中，信道编码用于纠正误码。检错和纠错能力是用信息冗余度即由附加附加在信息中的监督码元来实现的。信息码元与监督码元之间建立某种检验关系，根据建立检验关系的方法不同，可以分为分组码和卷积码。线性分组码中信息码元和监督码元是用现行方程联系起来的，卷积码中它们是以卷积的方式联系起来。码距是确定纠错检错能力的重要度量。3单元学习提纲单元学习提纲（1）前向纠错、
2、检错重发差错控制方法；（2）检错和纠错的基本原理；（3）分组码、卷积码、线性码、系统码的定义；（4）码距的定义，它与检错、纠错能力的关系；（5）线性分组码中监督方程、监督矩阵、生成方程、生成矩阵的含义；4（6）汉明码的特点及构造；（7）循环码的特点及编码方法；（8）纠正一位误码的循环码的一种译码方法；（9）交织码纠正突发错误的原理；（10）卷积码的编码方法，生成多项式与编码器的构造；5（11）卷积码的树状图、网格图的表示；（12）卷积码维持比译码的基本原理和译码过程；（13）纠错编码误比特率性能，编码增益的含义；（14）纠错编码在卫星信道、移动通信等实际通信系统中的应用。6第十一章 差错控制编
3、码和线性分组码 1、概述：数字通信系统是以电子方式传输信息的，接收方收到的数据应当就是发送方发送的数据，但这些电子信息都易受到干扰，太阳黑子活动、电源抖动或施工者用锄头对电缆的碰撞都会对传输产生不可预料的影响。为保证传输数据的完整性，通常采用一定的措施，如利用均衡器纠正信道参数，加大发送功率、扩展信道频带宽度等办法来减少加性干扰。采用上述方法仍难以满足要求时，必须采用差错控制措施，即用来和。7 对于数据传输，人们主要关心的是信息码元的差错概率，即误码率Pe，在中等传输速率（1200/2400波特）下，采用一般的调制方法，对于干线有线载波信道，Pe约为10-410-6的数量级，对于无线短波通信，
4、Pe只有10-210-3的数量级，对于传输速率更高的系统，误码性能还要差。在数据通信中，如计算机与计算机之间的数据传送，Pe要求低于10-9，这就需要加入纠错编码。8从差错控制角度看，信道可以分为三类 1、。误码的出现是随机的，误码之间是统计独立的。如由正态分布白噪声引起的误码（称为）就具有这种性质。2、。误码是成串集中出现的，即在短促的时间区间存在大量误码，在较长的时间区间无误码出现。产生的主要原因是脉冲干扰，信道中的衰落现象也是产生的主要原因。3、。既存在又存在的信道称为混合信道。911.1 差错控制编码的基本概念 1、检错重发方式（ARQ）。2、前向纠错方式（FEC）。3、混合纠错检错方
5、式（HEC）。4、反馈校验方式（IRQ）。11.1.1 差错控制方式1011。采用检错重发方式，发端经编码后发出能够发现错误的码，接收端收到后经检验如果发现传输中有错误，则通过反向信道把这一判断结果反馈给发送端。然后，发送端把信息重发一次，直到接收端确认为止。采用这种差错控制方法，一般在计算机数据通信中应用。检错重发方式分为，如图所示。图中ACK是确认信号，NAK是否认信号。12 ，发对或发错，发送端均要等待接收端的回应。特点是系统简单，时延长。，无ACK信号，当发送端收到NAK信号后，重发错误码组以后的所有码组，特点是系统较为复杂，时延减小。无ACK信号，当发送端收到NAK信号后，重发错误码
6、组，特点是系统复杂，时延最小。1314。发送端经编码发出能纠正错误的码，接收端收到这些码组后，通过译码能发现并纠正误码。前向纠错方式不需要反馈通道，特别适合只能提供单向信道的场合，特点是时延小，实时性好，但系统复杂。但随着编码理论和微电子技术的发展，编译码设备成本下降，加之有单向通信和控制电路简单的优点，在实际应用中日益增多。15。混合纠错检错方式是前向纠错方式和检错重发方式的结合，发送端发出的码不但有一定的纠错能力，对于超出纠错能力的错误要具有检错能力。这种方式在实时性和复杂性方面是前向纠错和检错重发方式的折衷，因而在近年来，在数据通信系统中采用较多。16 反馈校验方式（IRQ）又称回程校验
7、。收端把收到的数据序列全部由反向信道送回发送端，发送端比较发送数据与回送数据，从而发现是否有错误，并把认为错误的数据重新发送，直到发送端没有发现错误为止。不需要纠错、检错的编译器，设备简单。需要反向信道；实时性差；发送端需要一定容量的存储器。IRQ方式仅适用于传输速率较低、数据差错率较低的控制简单的系统中。1711.1.2 差错控制编码的分类 1、按照差错控制编码的不同功能，可以分为（仅能检测误码）、纠错码（仅可以纠正误码）和（兼有纠错和检错功能）。2、按照和附加的之间的检验关系可以分为（信息码元和监督码元满足一组线性方程式）和18 3、按照和之间的约束关系可以分为和。分组码中，码元序列每n位
8、分成一组，其中k个是信息码元，r=n-k个是监督码元，监督码元仅与本组的信息码元有关。卷积码中，编码后序列也编为分组，但监督码元不仅与本组信息码元有关，还与前面码组的信息码元有关。4、按照纠正错误的类型不同，可以分为和。19 5、按照构成差错控制编码的数学方法来分类，可以分为、和。其中代数码建立在近代数学基础上，是目前发展最为完善的编码，其中线性码是是代数码的一个最重要的分支。6、按照每个码元的取值不同，可以分为和2011.1.4 检错和纠错的基本原理 香农著名的信道编码定理指出：对于一个给定的有扰信道，若信道容量为C，只要发送端以低于C的速率R发送信息，则一定存在一种编码方法，使编码错误概率
9、P随着码长n的增加，按指数下降到任意小的值。纠错编码的的基本思想就是在被传送的信息码元中附加一些监督码元，在两者之间建立某种校验关系，当这种校验关系因传输错误而受到破坏时，可以被发现并予以纠正。21以一组二进制码为例 三位二进制码元有8个码组，如果用来表示天气的8种情况000（晴），001（雷），010（雹），011（阴），100（风），101（云），110（雨），111（雪），如果有一个误码，接收端以为是另一条信息，这种编码没有检错和纠错能力。如果这8种码组只用来传送4条信息，即只准使用其中的4种码组000（晴），011（阴），101（云），110（雨），如果有一位误码，不会在接收端产生误判
10、，会检出错误。22 4个状态只用2位二进制码就可以表达，所增加的第3位，就称为监督码元。增加1位监督码元，只能检出1位误码，对于上例，如果有2位误码，将发生误判。如将000（晴）误传成101（云）。要抗多位误码，就要增加监督码元的个数，即增加冗余度。23码距与检错和纠错能力 定义：1、：码组中非零码元的个数。如001，码重为1；011，码重为2。2、：两个码组中对应码位上具有的不同二进制码元的个数定义为两个码组的距离（汉明距，简称码距），如111和000，码距为3，111和100码距为2，111和110码距为1。3、：对于许用的n个码组，各码组之间最小的码距称为最小码距。2425 对于如图所示
11、的3位二进制码，如果8个码组可用，（000，001，010，011，100，101，110，111），各点之间最小相差1个边长，最小码距为1。如果只有4个码组可用，选（010，111，100，001）或（110，011，000，101），各点之间相差2个边长，最小码距为2。如果只有2个码组可用，分别选（111，000）（100，011）（110，001）（101，010），各点之间相差3个边长，最小码距为3。26码距与检错和纠错能力 如上所述，一种编码的最小码距直接关系到这种码的检错和纠错能力，因此最小码距是信道编码的一个重要参数。在一般情况下，对于分组码有如下结论：（1）在一个码组内检测个e
12、误码，要求最小码距 dmin=e+1（2）在一个码组内纠正个t误码，要求最小码距 dmin=2t+1（3）在一个码组内纠正t个误码，同时检测e个(e=t)误码（当误码数大于t时就不能纠错，只能检测e个误码），要求最小码距 dmin=t+e+12711.1.5 几种实用的简单检错码 1、奇偶监督码 这是一种最简单的检错码，又称奇偶校验码，在计算机数据通信中得到广泛应用。七单位国际5层字母表、美国信息交换码ASCII字母表中都用7比特码组表示128种字符，如字符A的编码为1000001。为了检查字符传输过程中是否有误，常在7比特码组后码组后加1位作为奇偶校验位。使得8位码组（一个字节）中的“1”的
13、个数为奇数或偶数，如果为奇数，称为奇校验码；偶数时，称为偶校验码。编码规则是：首先将要传送的信息分成组，然后将各位二进制信息加监督位用模2和。选择正确的监督位，使模2和为“0”（偶校验），为“1”（奇校验）。28 2、水平奇偶监督码 将经过奇偶监督编码的码元按行排成方阵，但传送时则按列进行的顺序传送。接收端仍将码元排成发送时的方形阵式，然后再进行奇偶校验。如：发送时按顺序传送11101110011000010101。以此来抗突发性错误。29 3、水平垂直奇偶校验码 在水平奇偶监督码的基础上，对方阵中的每一列也进行奇偶校验。发送时按列序顺次传送，接收端恢复成方阵后进行奇偶校验，如：传送顺序为11
14、1010110011100001101011，它能发现某一行或某一列上所有奇数个误码。30 4、群计数码 监督码组中“1”的个数构成所谓群计数码。例如一个码组的信息码元为1010111，其中有5个“1”，用二进制表示为101，将它作为监督码元附加在信息码元之后，传输码组为1010111101。为了提高检突发错误的能力，也可以仿照水平奇偶方法，将信息排成方阵，按列发送。31 5、恒比码 在恒比码中，每个码组中“1”（或“0”）的个数相同，因而称为等重码。检测时，只要计算每个码组中“1”的数目是否对，就能判断有无错误。我国电传机传输汉字电码的通信中，广泛采用五单位数字保护电码。每个码组长度为5，共
15、有25=32种组合，其中“1”的个数为3的编码正好10个，分别代表阿拉伯数字（110）。1-01011；2-11001；3-10110；4-11010；5-00111；6-10101；7-11100；8-01110；9-10011；10-01101。在国际ARQ电报通信系统中，它采用3个“1”、4个“0”的恒比码，7中取3共有35个许用码组，分别代表26个字母及其它符号。3211.2.5 汉明（Hamming)码 汉明码是1950年由美国贝尔实验室汉明提出来的，是第一个设计用来纠正错误的线性分组码，汉明码被广泛用于数字通信和数据存储系统中。对于奇偶校验的偶校验，我们用下式作为作为021.aaa
16、Snn 在接收端译码时，若S=0，就认为无错。若S=1，就认为有错。这里称S为校正子（校验子），又称伴随式。33汉明（Hamming)码 在上例中，由于只有一位监督码元，一个监督方程，所以只能检错，无法纠错。汉明码（n,k)是一种可用于纠单个随机错误的循环编码。一般汉明码的参数如下：码长 n=2r-1 信息位 k=2r-1-r 监督位 r=n-k，r是不小于3的任意正整数。（因为要纠t位错误，dmin大于2t+1)最小汉明距离 d=3 下表是的一般汉明码结构。34码字长度n 信息位k 校验位r74315114312656357635（7，4）汉明码举例 对于（7，4）汉明码，码元为a6,a5,
17、a4,a3,a2,a1,a0 假设有三个相应的监督方程，在接收端根据校正子的能纠正某一位的错误。034631356224561aaaaSaaaaSaaaaSS1 S2 S3 错码位置001a0010a1100a2011a3101a4110a5111a6000无错36（7，4）汉明码举例 如果传送a6,a5,a4,a3共4位数据，要求能自动纠正单个误码，须增加3位监督码a2,a1,a0。监督码的计算方程见下式。346035614562aaaaaaaaaaaa 7位数据按a6,a5,a1,a0的顺序一起发送，在接收端按校正子（伴随式）的组合来判断在哪一位出现了错误，并实时纠正（将相应位取非）。37
18、（7，4）汉明码的编码器和译码器（1）38（7，4）汉明码的编码器（2）+Z-1Z-1Z-1+1xx2x3s1s2（1）S1接通，S2掷向下端，输出数据位a6,a5,a4,a3的同时，反馈移位寄存器串行接收数据，延时等待推出监督位。（2）4位数据发完后，断开S1，将S2掷向上端，开始送监督位。（3）3位监督位送完后，开关又掷回原位。（4）设监督位为n，反馈移位寄存器由n位的本原多项式设计。39（15，11）汉明码举例 对于（15，11）汉明码，码为a14,a13,a12.,a3,a2,a1,a0 假设有四个相应的监督方程，在接收端根据校正子的能纠正某一位的错误04571011121441468
19、10111314325691012131423789111213141aaaaaaaaSaaaaaaaaSaaaaaaaaSaaaaaaaaSS1 S2 S3 s4错码位置0001a00010a10100a21000a30011a40101a50110a61001a71010a81100a90111a101011a111101a121110a131111a140000无错40（15，11）汉明码举例 同理，如果传送a14,a13.a5,a4共11位数据，要求能自动纠正单个误码，须增加4位监督码a3,a2,a1,a0。监督码的计算方程见下式。457101112140468101113141569
20、101213142789111213143aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa 15位数据按a14,a13,a1,a0的顺序一起发送，在接收端按校正子（伴随式）的组合来判断在哪一位出现了错误，并实时纠正（将相应位取非）。4111.2 线性分组码 线性分组码定义：分组码中和监督码元是用线性方程联系起来的一种差错控制码。汉明码是线性分组码的一种，能纠一位误码。线性分组码有三个重要的运算式：监督矩阵、生成矩阵和校正子。42(11.2.2)1、从上节汉明码的例子可以看出，线性分组码的监督方程可以用矩阵形式来表达（无误码时，下式成立）：式中的系数矩阵称为，用H表示。如果用虚线
21、分为两部分，左边为P矩阵，是一个r*k阶矩阵；右边为Ir矩阵，是一个r*r阶单位方阵。0000123456100110101010110010111aaaaaaa431、设发送序列为A，则监督方程也可以写为：0000123456OaaaaaaaAOHAT其中44(11.2.3)2、生成矩阵 已知监督方程和信号码元时可以按下式算出监督码元，式中用的是P矩阵。或者用下式来计算，式中的矩阵是P的转置矩阵，称为Q矩阵。3456110110110111012aaaaaaa1101010111113456012aaaaaaa452、生成矩阵 在Q的左边加一个k*k阶单位方阵，就生成一个新的矩阵G。1101
22、000101010001100101110001G 这个新矩阵G称为生成矩阵，因为可由它产生整个码组A。GaaaaA345646(11.2.4)校正子 设发送码组A为一n列的行矩阵，矩阵中n个元素就是码组中的n个码元。发送码组在传输过程中出现了误码，接收端收到了B矩阵，也是一n列的行矩阵。设收发码组之差E=B-A（模2），称为。校正子S可以根据接收序列和H矩阵来计算。TTTTTEHEHOEHAHHEABHS)(可见校正子只与错误图样有关，与发送序列无关，是一个信道参数。47校正子 如果不出现误码，校正子S=0。如果有误码，通过计算校正子S来指示误码的位置和纠正误码。设发送的序列A=000101
23、1 错误图样E=0001000 接收到的序列B=0000011，校正子可以由下式计算得到：1000100011101010111111100000THBS=(0 1 1)指示a3有错误。4811.3 循环码 循环码是线性分组码中的一类，是以现代代数理论作为基础建立起来的。循环码的编码和译码设备相对简单 循环码的检错和纠错能力较强。49循环码的循环特性 循环码与其它线性分组码一样，设总长度为n，前k位是信息位，后r位是监督位。(r=n-k)循环码中任意一许用码组经过循环移位后(将最右端的码元移至左端)，所得到的码组仍是许用码组。如表所示。a6a5a4a3a2a1a0100000002001011
24、1301011104011100151001011610111007110010181110010码组编号信息位监督位50循环码的循环特性一般来说，若（an-1,an-2,a0)是循环码的码组，则（an-2,an-3,a0,an-1)（an-3,an-4,an-1,an-2)（a0,an-1,a2,a1)也是该循环码的码组。51循环码的循环特性 码组（an-1,an-2,a1,a0)也可以用一个多项式来表示 A(X)=an-1xn-1+an-2xn-2+a1x+a0 对于一个（7，3）循环码，任一码组可以表示为 A(X)=a6x6+a5x5+a4x4+a3x3+a2x2+a1x+a0 式中a6
25、,a5,a1,a0是编码，x只是码元位置的标记。52循环码的循环特性 对于一个循环码组，可以用下列码多项式来分别表示。A（X）=an-1xn-1+an-2xn-2+a1x+a0 A（X）=an-2xn-1+an-3xn-2+a1x2+a0 x+an-1 Ai（X）=an-i-1xn-1+an-i-2xn-2+a0 xi+an-1xi-1+an-i 我们来看下式：53循环码的循环特性 式中采用模2加减，所以加法与减法是等效的。若被除式是xA（X）（许用码组），除式是xn+1（已知多项式），余式是A（X）（循环移一位的许用码组）。若被除式是xiA（X）（许用码组），除式是xn+1（已知多项式），余
26、式是Ai（X）（循环移i位的许用码组）。54循环码的循环特性例如某循环码1100101，则A(X)=X6+X5+X2+1,XA(X)=X7+X6+X3+X,11113673677XXXXXXXXX余数余数构成的码是1001011，正好是循环一位的结果。55循环码的循环特性例如某循环码1100101，则A(X)=X6+X5+X2+X1,X2A(X)=X8+X7+X4+X2,1111247247824787XXXXXXXXXXXXXXXX余数构成的码是0010111，正好是循环两位的结果。56由此得到一个重要结论 57首先要找到第一个许用码组A（x）在循环码中，有一个许用码组比较特殊，就是全0码，
27、即信息位全0时，监督位也取全0，通过这一点可以找出另一个许用码组。结论：假若第k位不为1，将造成信息位全为零，而监督位不为0的情况，若第n位不为1，右移一位后，将使信息位全为0，而监督位不为0。58循环码的生成多项式g（x）这一个前k-1位为0，第k位和第n位为1的许用码组可以用一个码多项式g(x)来标识，称为循环码的生成多项式。（1）g(x)是一个能除尽xn+1的n-k阶多项式。（2）要寻找生成多项式，必须对xn+1进行因式分解，这需要计算机来完成。（3）在一些参考书上有因式分解的表格可以选用。59循环码的监督多项式h（x）设多项式h(x)满足下式：h(x)g(x)=xn+1 就称h(x)为
28、监督多项式。60X7+1因式分解构成的循环码生成多项式(n,k)dg(x)h(x)(7,6)2x+1(x3+x+1)(x3+x2+x1)(7,4)3x3+x2+1(x3+x+1)(x+1)(7,3)4(x3+x+1)(x+1)x3+x2+1(7,1)7(x3+x+1)(x3+x2+x1)x+1表中x3是x的三次方，x2是x的二次方。61由生成多项式得到生成矩阵根据生成多项式可以求出生成矩阵G（x）)()(.)()()(21xgxgxxgxxgxXGkk62根据生成矩阵可以由信息码组求出传输码组)()(.)()().()(2100112211xgxgxxgxxgxxmxmxmxmxAkkkkkk
29、63X7+1因式分解后构成的循环码特例 因式分解x7+1=(x+1)(x3+x+1)(x3+x2+1)。（1）若取x+1为生成多项式，这是一种（7，6）码，有6个信息位，1个纠错位，这是一种偶校验码。（2）若取(x3+x2+1)为生成多项式，这是由本原多项式构成的（7，4）的汉明码。（能纠1位错码）。（3）若取(x3+x+1)(x3+x2+1)为生成多项式，只有1位信息位，构成的是全1码或全0码。64例题一 对于一（7，3）循环码，其 g(x)=(x3+x2+1)(x+1)=x4+x2+x+1 生成矩阵G（X）便可写成1000000000)()()()(2423523462xxxxxxxxxx
30、xxgxxgxgxXG65例题一111010001110100011101G 这不是典型的生成矩阵形式，若将第一列加上第三列，则如下生成矩阵形式。111010001110101101001G66例题一假设信息码是111，生成序列为A（X）0100111111010001110101101001111)(XA假设信息码是110，生成序列为A（X）1010011111010001110101101001011)(XA和循环的结果一致。67例题一 其它信息码的编码结果见下表a6a5a4a3a2a1a010000000200101113010111040111001510010116101110071
31、10010181110010码组编号信息位监督位68循环码编码器 循环码的编码电路，用硬件实现，可以采用除法电路。对于生成多项式为g(x)=x4+x2+x+1的编码器，其硬件电路如图所示：69循环码编码器 （1）首先将xn+1（x7+1）多项式展开，取最高幂为xn-k（x4）的一个组合项为g(x)。（2）对应g(x)有4级移位寄存器D1，D2，D3，D4，g(x)多项式系数是1还是0表示该位上有无反馈线。（3）当信息位输入时，控制器使Q1和Q3为正，Q2为0，开通门1和门3，此时电路除输出信息码之外，还送到除法电路进行运算。（4）当信息位传完之后，控制电路将Q2为正，Q1、Q3为0，开通门2，
32、使寄存器中的除法余项（监督码元）依此输出。70反馈输出D1D2D3D4FA00000001111011110011101010100010100000101100001000000011移位寄存器输入M举输入信息码110为例,输出码为1100101。71循环码的解码器 接收端解码的要求有两种：检错和纠错。达到的移码原理十分简单。由于任一码组多项式都能被生成多项式整除，所以接收端可以将接收码组R(x)用原生成多项式g(x)去除。（1）若能除尽，传输中未发生错误。（2）若除不尽，传输中发生了错误。72循环码的解码器 解码器的主要部分是一个除法器和缓冲移位寄存器。前11拍输出信码到缓冲寄存器里等待输
33、出。第15拍到来时，若除法器的结果RE(x)等于0,说明没有误码，可以打开与门让信码输出。第15拍到来时，若除法器的结果RE(x)不等于0,说明有误码，删除移位寄存器内容，并发出重发指令73循环码的解码器在接收端为而采用的解码方法要复杂的多。对于(7,3)循环码，码距等于3，只能检2位误码和纠1位误码。（7,3）循环码生成多项式是的x3+x2+1，相应的移码器如图所示。74循环码的解码器 根据第7拍到来时，除法器中移位寄存器的状态可以判断误码的位置。D2D1D01001010 x1001x2110 x3011x4111x5101x6移位寄存器状态差错位置75自测题自测题 （1）比较前向纠错（F
34、EC）、检错重发（ARQ）和混合纠错这三种差错控制编码方式的优缺点。（2）对于一个码长为31的线性码，若允许纠正2个错误，至少需要多少位监督码元？（3）（23，12）格雷码能纠正3个随机错误，证明它是完备码。（4）已知循环码生成多项式为D4+D2+D+1，输入信息码元为101010，求编码后的系统码码组。N=?（5）分组码和卷积码的区别是什么？76（6）循环码主要特点是什么？如何实现编码？（7）已知分组码（63，51），说明它的含义，并估计它可能具有的纠错能力。（8）什么是交织码？它的主要性能是什么？（9）已知卷积码（3，2，7），说明它的含义。（10）已知卷积码（2，1，7）生成多项式的八进制表示为（133）8，画出它的编码器方框图。（11）已知码率为1/2的卷积码，其生成多项式为G1（D）=1，G2（D）=1+D，画出它的树状图、网格图。（12）某QPSK系统，传输速率为64KB/S，接收输入EB/NO 为8dB，假设设备不理想引起的EB/NO损失为2 dB，求该 系统的误比特率。若采用（3，2，3）卷积码，在保持信道 频带不变时，信息率为多少？误比特率提高到多少？
