现代通信原理1

1、现代通信原理第十一章 差错控制编码和线性分组码单元概述单元概述 实际信道传输数字信号时，不可避免地会产生误码。差错控制编码的目的是用信道编码的方法检测和纠正误码，降低误比特率。在检错重发控制编码方式中，信道编码只是为了检测误码，而在前向纠错方式中，信道编码用于纠正误码。 检错和纠错能力是用信息冗余度即由附加附加在信息中的监督码元来实现的。信息码元与监督码元之间建立某种检验关系，根据建立检验关系的方法不同，可以分为分组码和卷积码。线性分组码中信息码元和监督码元是用现行方程联系起来的，卷积码中它们是以卷积的方式联系起来。码距是确定纠错检错能力的重要度量。单元学习提纲单元学习提纲 （1前向纠错、检错

2、重发差错控制方法； （2检错和纠错的基本原理； （3分组码、卷积码、线性码、系统码的定义； （4码距的定义，它与检错、纠错能力的关系； （5线性分组码中监督方程、监督矩阵、生成方程、生成矩阵的含义；（6汉明码的特点及构造；（7循环码的特点及编码方法；（8纠正一位误码的循环码的一种译码方法；（9交织码纠正突发错误的原理；（10） 卷积码的编码方法，生成多项式与编码器的构造； （11卷积码的树状图、网格图的表示；（12卷积码维持比译码的基本原理和译码过程；（13纠错编码误比特率性能，编码增益的含义；（14纠错编码在卫星信道、移动通信等实际通信系统中的应用。第十一章 差错控制编码和线性分组码 1、概

3、述： 数字通信系统是以电子方式传输信息的，接收方收到的数据应当就是发送方发送的数据，但这些电子信息都易受到干扰，太阳黑子活动、电源抖动或施工者用锄头对电缆的碰撞都会对传输产生不可预料的影响。 为保证传输数据的完整性，通常采用一定的措施，如利用均衡器纠正信道参数，加大发送功率、扩展信道频带宽度等办法来减少加性干扰。 采用上述方法仍难以满足要求时，必须采用差错控制措施，即用差错控制编码来检错和纠错。 对于数据传输，人们主要关心的是信息码元的差错概率，即误码率Pe，在中等传输速率1200/2400波特下，采用一般的调制方法，对于干线有线载波信道， Pe约为10-410-6的数量级，对于无线短波通信，

4、 Pe只有10-210-3的数量级，对于传输速率更高的系统，误码性能还要差。 在数据通信中，如计算机与计算机之间的数据传送，Pe要求低于10-9，这就需要加入纠错编码。从差错控制角度看，信道可以分为三类 1、随机信道。误码的出现是随机的，误码之间是统计独立的。如由正态分布白噪声引起的误码称为随机误码就具有这种性质。 2、突发信道。误码是成串集中出现的，即在短促的时间区间存在大量误码，在较长的时间区间无误码出现。产生突发误码的主要原因是脉冲干扰，信道中的衰落现象也是产生突发误码的主要原因。 3、混合信道。既存在随机误码又存在突发误码的信道称为混合信道。11.1 差错控制编码的基本概念 1、检错重

5、发方式ARQ）。 2、前向纠错方式FEC）。 3、混合纠错检错方式HEC）。 4、反馈校验方式IRQ）。 11.1.1 差错控制方式 （1停发等待重发，发对或发错，发送端均要等待接收端的回应。特点是系统简单，时延长。 （2返回重发，无ACK信号，当发送端收到NAK信号后，重发错误码组以后的所有码组，特点是系统较为复杂，时延减小。 （3选择重发。无ACK信号，当发送端收到NAK信号后，重发错误码组，特点是系统复杂，时延最小。11.1.2 差错控制编码的分类 1、按照差错控制编码的不同功能，可以分为检错码仅能检测误码）、纠错码仅可以纠正误码和纠删码兼有纠错和检错功能）。 2、按照信息码元和附加的监

6、督码元之间的检验关系可以分为线性码信息码元和监督码元满足一组线性方程式和非线性码。 3、按照信息码元和监督码元之间的约束关系可以分为分组码和卷积码。分组码中，码元序列每n位分成一组，其中k个是信息码元，r=n-k个是监督码元，监督码元仅与本组的信息码元有关。卷积码中，编码后序列也编为分组，但监督码元不仅与本组信息码元有关，还与前面码组的信息码元有关。 4、按照纠正错误的类型不同，可以分为纠正随机错误的码和纠正突发错误的码。 5、按照构成差错控制编码的数学方法来分类，可以分为代数码、几何码和算术码。其中代数码建立在近代数学基础上，是目前发展最为完善的编码，其中线性码是是代数码的一个最重要的分支。

7、 6、按照每个码元的取值不同，可以分为二进制码和多进制码。11.1.4 检错和纠错的基本原理 香农著名的信道编码定理指出：对于一个给定的有扰信道，若信道容量为C，只要发送端以低于C的速率R发送信息，则一定存在一种编码方法，使编码错误概率P随着码长n的增加，按指数下降到任意小的值。即可以通过增加冗余编码来降低误码率。 纠错编码的的基本思想就是在被传送的信息码元中附加一些监督码元，在两者之间建立某种校验关系，当这种校验关系因传输错误而受到破坏时，可以被发现并予以纠正。 这种检错和纠错能力是用信息量的冗余度来换取的。以一组二进制码为例 三位二进制码元有8个码组，如果用来表示天气的8种情况000晴），

8、001雷），010雹），011阴），100风），101云），110雨），111雪），如果有一个误码，接收端以为是另一条信息，这种编码没有检错和纠错能力。 如果这8种码组只用来传送4条信息，即只准使用其中的4种码组000晴），011阴），101云），110雨），如果有一位误码，不会在接收端产生误判，会检出错误。 4个状态只用2位二进制码就可以表达，所增加的第3位，就称为监督码元。增加1位监督码元，只能检出1位误码，对于上例，如果有2位误码，将发生误判。如将000晴误传成101云）。 要抗多位误码，就要增加监督码元的个数，即增加冗余度。码距与检错和纠错能力 定义： 1、码重：码组中非零码元的个数。

9、如001，码重为1；011，码重为2。 2、码距：两个码组中对应码位上具有的不同二进制码元的个数定义为两个码组的距离汉明距，简称码距），如111和000，码距为3，111和100码距为2，111和110码距为1。 3、最小码距：对于许用的n个码组，各码组之间最小的码距称为最小码距。 对于如图所示的3位二进制码，如果8个码组可用，（000，001，010，011，100，101，110，111），各点之间最小相差1个边长，最小码距为1。 如果只有4个码组可用，选010，111，100，001或110，011，000，101），各点之间相差2个边长，最小码距为2。 如果只有2个码组可用，分别选11

10、1，000）（100，011）（110，001）（101，010），各点之间相差3个边长，最小码距为3。码距与检错和纠错能力 如上所述，一种编码的最小码距直接关系到这种码的检错和纠错能力，因此最小码距是信道编码的一个重要参数。在一般情况下，对于分组码有如下结论： （1在一个码组内检测个e误码，要求最小码距 dmin=e+1 （2在一个码组内纠正个t误码，要求最小码距 dmin=2t+1 （3在一个码组内纠正t个误码，同时检测e个(e=t)误码当误码数大于t时就不能纠错，只能检测e个误码），要求最小码距 dmin=t+e+111.1.5 几种实用的简单检错码 1、奇偶监督码 这是一种最简单的检错

11、码，又称奇偶校验码，在计算机数据通信中得到广泛应用。七单位国际5层字母表、美国信息交换码ASCII字母表中都用7比特码组表示128种字符，如字符A的编码为1000001。为了检查字符传输过程中是否有误，常在7比特码组后码组后加1位作为奇偶校验位。使得8位码组一个字节中的“1的个数为奇数或偶数，如果为奇数，称为奇校验码；偶数时，称为偶校验码。 编码规则是：首先将要传送的信息分成组，然后将各位二进制信息加监督位用模2和。选择正确的监督位，使模2和为“0”（偶校验），为“1”（奇校验）。 奇偶校验码只能发现奇数个误码，对检测突发错误不适用。 2、水平奇偶监督码 将经过奇偶监督编码的码元按行排成方阵，

12、但传送时则按列进行的顺序传送。接收端仍将码元排成发送时的方形阵式，然后再进行奇偶校验。如： 发送时按顺序传送11101110011000010101。以此来抗突发性错误。 3、水平垂直奇偶校验码 在水平奇偶监督码的基础上，对方阵中的每一列也进行奇偶校验。发送时按列序顺次传送，接收端恢复成方阵后进行奇偶校验，如： 传送顺序为111010110011100001101011，它能发现某一行或某一列上所有奇数个误码。 4、群计数码 监督码组中“1的个数构成所谓群计数码。例如一个码组的信息码元为1010111，其中有5个“1”，用二进制表示为101，将它作为监督码元附加在信息码元之后，传输码组为101

13、0111101。 为了提高检突发错误的能力，也可以仿照水平奇偶方法，将信息排成方阵，按列发送。 5、恒比码 在恒比码中，每个码组中“1”（或“0”）的个数相同，因而称为等重码。检测时，只要计算每个码组中“1的数目是否对，就能判断有无错误。 我国电传机传输汉字电码的通信中，广泛采用五单位数字保护电码。每个码组长度为5，共有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电报通信系统中，它采

14、用3个“1”、4个“0的恒比码，7中取3共有35个许用码组，分别代表26个字母及其它符号。11.2.5 汉明Hamming)码 汉明码是1950年由美国贝尔实验室汉明提出来的，是第一个设计用来纠正错误的线性分组码，汉明码被广泛用于数字通信和数据存储系统中。 对于奇偶校验的偶校验，我们用下式作为作为监督方程。 021.aaaSnn 在接收端译码时，若S=0，就认为无错。 若S=1，就认为有错。 这里称S为校正子校验子），又称伴随式。 汉明Hamming)码 在上例中，由于只有一位监督码元，一个监督方程，所以只能检错，无法纠错。 汉明码n,k)是一种可用于纠单个随机错误的循环编码。一般汉明码的参数

15、如下： 码长 n=2r-1 信息位 k=2r-1-r 监督位 r=n-k，r是不小于3的任意正整数。 （因为要纠t位错误，dmin大于2t+1) 最小汉明距离 d=3 下表是纠错一位的一般汉明码结构。码字长度n 信息位k 校验位r743151143126563576（7，4汉明码举例 对于7，4汉明码，码元为a6,a5,a4,a3,a2,a1,a0 假设有三个相应的监督方程，在接收端根据校正子的取值组合能纠正某一位的错误。034631356224561aaaaSaaaaSaaaaSS1 S2 S3 错码位置001a0010a1100a2011a3101a4110a5111a6000无错（7，4

16、汉明码举例 如果传送a6,a5,a4,a3共4位数据，要求能自动纠正单个误码，须增加3位监督码a2,a1,a0。监督码的计算方程见下式。346035614562aaaaaaaaaaaa 7位数据按a6,a5,a1,a0的顺序一起发送，在接收端按校正子伴随式的组合来判断在哪一位出现了错误，并实时纠正将相应位取非）。（7，4汉明码的编码器和译码器1）（7，4汉明码的编码器2）+Z-1Z-1Z-1+1xx2x3s1s2（1S1接通，S2掷向下端，输出数据位a6,a5,a4,a3的同时，反馈移位寄存器串行接收数据，延时等待推出监督位。（24位数据发完后，断开S1，将S2掷向上端，开始送监督位。（33位

17、监督位送完后，开关又掷回原位。（4设监督位为n，反馈移位寄存器由n位的本原多项式设计。（15，11汉明码举例 对于15，11汉明码，码为a14,a13,a12.,a3,a2,a1,a0 假设有四个相应的监督方程，在接收端根据校正子的取值组合能纠正某一位的错误0457101112144146810111314325691012131423789111213141aaaaaaaaSaaaaaaaaSaaaaaaaaSaaaaaaaaSS1 S2 S3 s4错码位置0001a00010a10100a21000a30011a40101a50110a61001a71010a81100a90111a101

18、011a111101a121110a131111a140000无错（15，11汉明码举例 同理，如果传送a14,a13.a5,a4共11位数据，要求能自动纠正单个误码，须增加4位监督码a3,a2,a1,a0。监督码的计算方程见下式。457101112140468101113141569101213142789111213143aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa 15位数据按a14,a13,a1,a0的顺序一起发送，在接收端按校正子伴随式的组合来判断在哪一位出现了错误，并实时纠正将相应位取非）。11.2 线性分组码 线性分组码定义：分组码中信息码元和监督码元是用线性

19、方程联系起来的一种差错控制码。 汉明码是线性分组码的一种，能纠一位误码。 线性分组码有三个重要的运算式：监督矩阵、生成矩阵和校正子。 (11.2.2) 1、监督矩阵 从上节汉明码的例子可以看出，线性分组码的监督方程可以用矩阵形式来表达无误码时，下式成立）： 式中的系数矩阵称为监督矩阵，用H表示。如果用虚线分为两部分，左边为P矩阵，是一个r*k阶矩阵；右边为Ir矩阵，是一个r*r阶单位方阵。0000123456100110101010110010111aaaaaaa1、监督矩阵 设发送序列为A，则监督方程也可以写为：0000123456OaaaaaaaAOHAT其中(11.2.3) 2、生成矩阵

20、 已知监督方程和信号码元时可以按下式算出监督码元，式中用的是P矩阵。 或者用下式来计算，式中的矩阵是P的转置矩阵，称为Q矩阵。3456110110110111012aaaaaaa1101010111113456012aaaaaaa2、生成矩阵 在Q的左边加一个k*k阶单位方阵，就生成一个新的矩阵G。1101000101010001100101110001G 这个新矩阵G称为生成矩阵，因为可由它产生整个码组A。GaaaaA3456(11.2.4) 校正子 设发送码组A为一n列的行矩阵，矩阵中n个元素就是码组中的n个码元。发送码组在传输过程中出现了误码，接收端收到了B矩阵，也是一n列的行矩阵。 设

21、收发码组之差E=B-A模2），称为错误图样。校正子S可以根据接收序列和H矩阵来计算。TTTTTEHEHOEHAHHEABHS)( 可见校正子只与错误图样有关，与发送序列无关，是一个信道参数。校正子 如果不出现误码，校正子S=0。 如果有误码，通过计算校正子S来指示误码的位置和纠正误码。设发送的序列A=0001011 错误图样E=0001000 接收到的序列B=0000011，校正子可以由下式计算得到：1000100011101010111111100000THBS=(0 1 1)指示a3有错误。 11.3 循环码 循环码是线性分组码中的一类，是以现代代数理论作为基础建立起来的。 循环码的编码和

22、译码设备相对简单 循环码的检错和纠错能力较强。循环码的循环特性 循环码与其它线性分组码一样，设总长度为n，前k位是信息位，后r位是监督位。(r=n-k) 循环码中任意一许用码组经过循环移位后(将最右端的码元移至左端)，所得到的码组仍是许用码组。如表所示。a6a5a4a3a2a1a01000000020010111301011104011100151001011610111007110010181110010码组编号信息位监督位循环码的循环特性一般来说，假设an-1,an-2,a0)是循环码的码组，那么（an-2,an-3,a0,an-1)（an-3,an-4,an-1,an-2) （a0,an

23、-1,a2,a1)也是该循环码的码组。循环码的循环特性 码组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,a5,a1,a0是编码，x只是码元位置的标记。循环码的循环特性 对于一个循环码组，可以用下列码多项式来分别表示。 AX）=an-1xn-1+an-2xn-2+a1x+a0 A（X）=an-2xn-1+an-3xn-2+a1x2+a0 x+an-1 AiX）=an-i-1xn-1+an-i-2xn

24、-2+a0 xi+an-1xi-1+an-i 我们来看下式：循环码的循环特性 式中采用模2加减，所以加法与减法是等效的。 若被除式是xAX）（许用码组），除式是xn+1已知多项式），余式是A（X）（循环移一位的许用码组）。 若被除式是xiAX）（许用码组），除式是xn+1已知多项式），余式是AiX）（循环移i位的许用码组）。循环码的循环特性例如某循环码1100101， 则A(X)=X6+X5+X2+1, XA(X)=X7+X6+X3+X,11113673677XXXXXXXXX余数余数构成的码是1001011，正好是循环一位的结果。循环码的循环特性例如某循环码1100101， 则A(X)=X6

25、+X5+X2+X1, X2A(X)=X8+X7+X4+X2,1111247247824787XXXXXXXXXXXXXXXX余数构成的码是0010111，正好是循环两位的结果。由此得到一个重要结论 若A(x)是n阶循环码的一个许用码组(包括信息码元和监督码元)，通过除以xn+1再取余数的方法可以找到其它的许用码组。首先要找到第一个许用码组Ax） 在循环码中，有一个许用码组比较特殊，就是全0码，即信息位全0时，监督位也取全0，通过这一点可以找出另一个许用码组。 结论：除全0码组外，另一个n位循环码的许用码组n,k)，若前k-1位全为零，则第k位信息末位和第n位监督末位必定为1。 假若第k位不为1

26、，将造成信息位全为零，而监督位不为0的情况， 若第n位不为1，右移一位后，将使信息位全为0，而监督位不为0。循环码的生成多项式gx） 这一个前k-1位为0，第k位和第n位为1的许用码组可以用一个码多项式g(x)来标识，称为循环码的生成多项式。 （1g(x)是一个能除尽xn+1的n-k阶多项式。 （2要寻找生成多项式，必须对xn+1进行因式分解，这需要计算机来完成。 （3在一些参考书上有因式分解的表格可以选用。循环码的监督多项式hx） 设多项式h(x)满足下式： h(x)g(x)=xn+1 就称h(x)为监督多项式。X7+1因式分解构成的循环码生成多项式(n,k) dg(x)h(x)(7,6)

27、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的二次方。由生成多项式得到生成矩阵根据生成多项式可以求出生成矩阵Gx）)()(.)()()(21xgxgxxgxxgxXGkk根据生成矩阵可以由信息码组求出传输码组)()(.)()().()(2100112211xgxgxxgxxgxxmxmxmxmxAkkkkkkX7+1因式分解后构成的循环码特例 因式分解x7+1=(x+1)(x3+x+1)(x3+x2+1

28、)。 （1若取x+1为生成多项式，这是一种7，6码，有6个信息位，1个纠错位，这是一种偶校验码。 （2若取(x3+x2+1)为生成多项式，这是由本原多项式构成的7，4的汉明码。（能纠1位错码）。 （3若取(x3+x+1)(x3+x2+1)为生成多项式，只有1位信息位，构成的是全1码或全0码。例题一 对于一7，3循环码，其生成多项式 g(x)=(x3+x2+1)(x+1)=x4+x2+x+1 生成矩阵GX便可写成1000000000)()()()(2423523462xxxxxxxxxxxxgxxgxgxXG例题一111010001110100011101G 这不是典型的生成矩阵形式，若将第一列

29、加上第三列，那么如下生成矩阵形式。111010001110101101001G例题一假设信息码是111，生成序列为AX）0100111111010001110101101001111)(XA假设信息码是110，生成序列为AX）1010011111010001110101101001011)(XA和循环的结果一致。例题一 其它信息码的编码结果见下表a6a5a4a3a2a1a01000000020010111301011104011100151001011610111007110010181110010码组编号信息位监督位循环码编码器 循环码的编码电路，用硬件实现，可以采用除法电路。 对于生成多项式为g(x)=x4+x2+x+1的编码器，其硬件电路如图所示：循环码编码器反馈输出D1D2D3D4FA00000001111011110011101010100010100000101100001000000011移位寄存器输入M举输入信息码110为例,输出码为1100101。循环码的解码器 接收端解码的要求有两种：检错和纠错。 达到检错目的的移码原理十分简单。由于任一码组多项式都能被生成多项式整除，所以接收端可以将接收码组R(x)用原生成多项式g(x)去除。 （1若能除尽，传输中未发生错误。 （2若除不尽，传输中发生了错误。 下图是一个15，11循环码的检错译码器。循环码