通信原理-CH11-差错控制编码和线性分组码

1、第十一章第十一章 差错控制编码和线性分组码差错控制编码和线性分组码2主要内容和重点主要内容和重点n差错控制编码的基本概念差错控制编码的基本概念n线性分组码线性分组码 n性质、基本原理n校正子n监督矩阵n生成矩阵n汉明码n循环码循环码n概念及性质n生成多项式n生成矩阵与监督矩阵n编码器32.1 引言引言 n为什么要引入差错控制编码？n什么是差错控制编码（信道编码）？n差错控制编码的3种方式 n信道发生差错的模式n差错控制编码的基本原理n差错控制编码的分类n编码信道及香农编码定理42.1 引言引言 n为什么要引入差错控制编码？n在实际信道上传输数字信号时，由于信道传输特性不理想及加性噪声的影响，接

2、收端所收到的数字信号不可避免地会发生错误 n为了在已知信噪比情况下达到一定的误比特率指标，应该合理设计基带信号，选择调制解调方式，采用时域、频域均衡，使误比特率尽可能降低n但若误比特率仍不能满足要求，则必须采用信道编码若误比特率仍不能满足要求，则必须采用信道编码（即差错控制编码），将误比特率进一步降低（即差错控制编码），将误比特率进一步降低52.1 引言引言 n什么是差错控制编码n差错控制编码的基本思路差错控制编码的基本思路：n在发送端将被传输的信息附上一些监督码元，这些多余的码元与信息码元之间以某种确定的规则相互关联（约束）n接收端按照既定的规则校验信息码元与监督码元之间的关系，一旦传输发生

3、差错，则信息码元与监督码元的关系就受到破坏，从而接收端可以发现错误乃至纠正错误n差错控制编码所要解决的问题：各种编码和译码差错控制编码所要解决的问题：各种编码和译码方法方法62.1 引言引言 n差错控制的三种方式n检错重发（ARQ）n在接收端根据编码规则进行检查，如果发现规则被破坏，则通过反向信道要求发送端重新发送，直到接收端检查无误为止nARQ系统的重发机制：停发等候重发、返回重发和选择重发n需要反馈信道，效率较低，但是性能很好发收能够发现错误的码应答信息72.1 引言引言 n差错控制的三种方式（续）n前向纠错（FEC） n发送端发送能纠正错误的编码，在接收端根据接收到的码和编码规则，能自动

4、纠正传输中的错误n不需要反馈信道，实时性好，但是随着纠错能力的提高，编译码设备复杂 发收可以纠正错误的码82.1 引言引言 n差错控制的三种方式（续）n混合方式n结合FEC和ARQ：在纠错能力范围内，自动纠正错误，超出纠错范围则要求发送端重新发送发收可以发现和纠正错误的码应答信号92.1 引言引言 n信道发生差错的模式n随机差错：n差错的出现是随机的，差错出现的位置是随机分布的n一般由信道的加性随机噪声引起n这种信道称为随机信道随机信道 n突发差错：n差错的出现是一连串出现的。这种情况如移动通信中信号在某一段时间内发生衰落，造成一串差错；光盘上的一条划痕等等n这样的信道称之为突发信道突发信道

5、n混合差错：n既有突发错误又有随机差错的情况n这种信道称之为混合信道混合信道 102.1 引言引言 n差错控制编码的基本原理 n以差错重发编码来阐述差错编码在相同的信噪比情况下为什么会获得更好的系统性能？ n例1：假设发送的信息0、1等概，采用2PSK方式，则最佳接收的系统误比特率为 ，现假设n如果将信息0编码成00，信息1编码成11，则在接收端：n如果发送00，收到01、10，知道发生了差错，要求发送端重新传输，直到传送正确为止n只有当收到11时，我们才错误地认为当前发送的是1 n因此在这种情况下发生译码错误的概率是 n同理，如果发送的是11，只有收到00时才可能发生错误译码，因此在这种情况

6、下发生译码错误的概率是n故采用00、11编码的系统误比特率为 021NEerfcPse310eP221eP221eP2eP112.1 引言引言 n差错控制编码的基本原理（续） n依此类推，可知：n采用000、111编码的ARQ系统误比特率是多少？n采用0000、1111编码的ARQ系统误比特率是多少？n例2，如例1，如果0、1采用00000、11111编码，在接收端用如下的译码方法，每收到5个比特译码一次，采用大数判决，即5个比特中0的个数大于1的个数则译码成0，反之译码成1；不采用ARQ方式。那么，这种编码方式就变成了纠错编码n由于传输错误当接收端收到11000，10100，10010，10

7、001，01100，01010，01001，00110，00101，00011中的任何一种时，都可以自动纠正成00000n课外题：请计算在这种情况下的系统性能n上述例1、例2的编码方式叫重复码122.1 引言引言 n差错控制编码的基本原理（续） n例3，2PSK系统中误比特率与Es/N0有关n我们看到，重复码中假设传输时每个符号的Es/N0相等，因此才得到以上的性能分析对比n但是如果我们以Eb/N0的指标进行比较，则我们看到n例1的 n例2的 n如果要求各系统在Eb/N0相同的情况下进行比较（n重复码中用了n倍能量来传输一个比特，从每个比特能量的角度来看），则可看到这2种系统性能相近（即获得相

8、近的编码增益）002NENEsb005NENEsb132.1 引言引言 n差错控制编码的基本原理（续）n当x1有n2PSK系统： n2重重复码： n编码增益编码增益= 221)(xexxerfc00011/22/bENebbPerfcENeEN020011222/bENbebEPerfceNEN00/NENEbb所需要的编码时达到一定性能时时所需的未编码时达到一定性能142.1 引言引言 n差错控制编码的分类n根据差错控制编码的功能不同n检错码、纠错码、纠删码（兼检错、纠错）n根据信息位和校验位的检验关系n线性码（存在线性关系）和非线性码n按信息码元在编码后是否保持原来的形式n系统码：保持不变

9、n非系统码：信息码元改变了原有的信号形式n按纠正错误的类型：n纠正随机错误的码：用于随机错误的信道n纠正突发错误的码：用于突发信道152.1 引言引言 n差错控制编码的分类（续）n根据信息码元和监督码元的约束方式：n分组码：监督码元仅与本码组的信息码元有关n卷积码：监督码元还与前面码组的信息码元有约束关系n分组码：将k个信息比特编成n个比特的码字，共有2k个码字。所有个码字组成一个分组码。传输时前后码字之间毫无关系 n卷积码：也是将k个信息比特编成n个比特的码字，但是前后的N个码字之间相互关联 n编码速率=平均每个码字所携带的信息比特率 kknn个信息比特编成 个比特的码字162.1 引言引言

10、 n编码信道n所谓的编码信道就是将调制解调包括在信道内的一种模型上的等效。 即如果研究编码和译码，完全可以将调制、解调与信道合起来等效成一个等效的信道，这种信道就称之为编码信道编码信道源编码调制信道解调译码宿172.1 引言引言 n编码信道（续）n根据调制解调的不同输入和输出具有不同的类型 n离散无记忆对称二进制输入二进制输出信道（BSC）n这种情况相应于2进制调制解调+判决n离散无记忆二进制输入多进制输出信道n对应于2进制输入，量化后输出的情况，即所谓的软译码n离散无记忆多进制输入多进制输出n对应于多进制输入、量化后输出n离散无记忆二进制输入连续输出n对应于二进制输入，模拟输出（未判决、未量

11、化）182.1 引言引言 n香农有扰离散信道的编码定理n对于一个给定的有扰信道，若信道的容量为C，只要发送端以低于C的速率R发送信息（R为编码器的输入二进制码元速率），则一定存在一种编码方法，使编码错误概率P随着码长n的增加，按指数下降到任意小的值，表示为n其中E(R)称为误差指数 n结论：nn和R一定情况下，为减小P，可增大C n在C及R一定的情况下，增加n，可以 使P指数下降。从实际的角度看，这时 设备复杂性和译码延时也随之增加 )(RnEePE（R） C0 C1 C2 R19 2.2 纠错编码的基本原理纠错编码的基本原理n主要内容n码重、码距n最小码距n码的纠错、检错性能20 2.2 纠

12、错编码的基本原理纠错编码的基本原理n分组码将k个比特编成n个比特一组的码字（码组），记为（n，k）码n由于输入有 2k种组合，因此（n，k）码应该有2k个码字n码重、码距n码重：码字中1的个数。如码字11000的码重为2n码距：码字C1与码字C2之间不同的比特数（又称汉明距）21 2.2 纠错编码的基本原理纠错编码的基本原理n最小码距n所用码字中任何两个码字之间的码距的最小值，用 dmin表示n码的纠错、检错性能：由最小码距决定 n为了检测e个错误，要求最小码距n为了纠正t个错误，要求最小码距n为了纠正t个错误，同时检测e个错误，要求最小码距 min1de12min tdmin1()dteet

13、 22eBAd0tAtB1tAeB1(a)(b)(c)d0d0纠错码的抗干扰能力完全取决于许用码字之间的距离，码的最小纠错码的抗干扰能力完全取决于许用码字之间的距离，码的最小距离越大，说明码字间的最小差别越大，抗干扰能力就越强距离越大，说明码字间的最小差别越大，抗干扰能力就越强 2.2 纠错编码的基本原理纠错编码的基本原理23 2.3 常用的简单编码常用的简单编码 n奇偶监督码（奇偶校验）n设奇偶监督码的码字表示为： n则偶校验码： （即偶数个1） 奇校验码： （即奇数个1）n可见这种码的最小码距为2，只能检1个错 ),.,(021aaann0.021aaann1.021aaann24 奇偶监

14、督码的编码可以用软件实现，也可用硬奇偶监督码的编码可以用软件实现，也可用硬件电路实现件电路实现 如果码组如果码组B无错，无错，BA，则，则M0；如果码组；如果码组B有单个（或奇数个）错误，则有单个（或奇数个）错误，则M1 a4a3a2a1a0a4a3a2a1信息组编码输出b0b4b3b2b1接收码组检错信号SBAM 2.3 常用的简单编码常用的简单编码 25 2.3 常用的简单编码常用的简单编码 n二维奇偶监督码n提高奇偶校验码对突发错误的检测能力 n将若干奇偶校验码排成若干行，然后对每列进行奇偶校验，放在最后一行。传输时按照列顺序进行传输，在接收端又按照行的顺序检验是否差错 n由于突发错误是

15、成串发生的，经过传输后错误被分散（交织编码+奇偶校验） n移动通信中的信道衰落造成突发错误，因此传输前，先将输入的信息比特交织，将突发错误尽可能分散成随机错误，然后用其它编码方式来纠正随机的错误mmnmnnnnncccaaaaaa021202221101211.26 2.3 常用的简单编码常用的简单编码 n恒比码n每个码组中的1的个数都一样n电传机传输汉字时每个汉字用4位阿拉伯数字表示，每个阿拉伯数字用5个比特的码字表示。由于阿拉伯数字只有10个，因此从32中可能的码字中挑出 =10个1的个数为3的码字作为阿拉伯数字的编码方式n译码可以采用查表方法，检错时检查1的个数是否为3n一般用在电传、电

16、报53C阿拉伯数字编码阿拉伯数字编码10101161010121100171110031011080111041101091001150011100110127 2.3 常用的简单编码常用的简单编码 nISBN国际统一图书编号n国际图书的发行中，用编码的方式来防止书号在通信过程中发生错误 n如通信原理的书号是ISBN 7-118-01429-Xn其中第一位数字“7”表示“中国”，“118”表示出版社，“01429”表示书名编号，最后一位“X”表示校验位（它是罗马数字10的表示）n所采用的校验方式如下所示：n7 1 1 8 0 1 4 2 9 X=10n7 8 9 17 17 18 22 24

17、33 43n7 15 24 41 58 76 98 122 155 198 198 (模11)=0 282.4 线性分组码线性分组码n差错编码的重点：各种编码和译码的方法n主要内容n性质n基本原理n校验矩阵（监督矩阵）n生成矩阵n校正子（伴随式）n汉明码292.4 线性分组码线性分组码n定义：n将信息码分组，为每组信息位附加若干监督位，且信息位和监督位间的关系可由线性方程组表示的编码n即可用线性方程组表述码的规律性的分组码 n线性分组码（n，k）的性质n许用码字（组）为2k个n定义线性分组码的加法为模2加，乘法为二进制乘法。即有n1+1=0、1+0=1、0+1=1、0+0=0 n1x1 = 1

18、, 1x 0 =0, 0 x0 =0, 0 x1 =0n且码字与码字的运算是各相应比特位上符合上述二进制加法运算规则 302.4 线性分组码线性分组码n线性分组码（n，k）的性质（续）n群：集合G上定义了一种加法运算，如果该运算符合以下4条公理，则称G是该运算的一个群n封闭性：任何a、b属于G，有a*b属于Gn单位元：G中存在一个元素e满足e*a=an有逆元：任何a属于G，存在b属于G满足a*b=en结合率成立：a*(b*c)=(a*b)*cn线性分组码的性质：n封闭性。任意两个许用码组的和仍是一个许用码组n最小码距等于非零码的最小码重 312.4 线性分组码线性分组码n基本原理n(n, k)

19、码：码长n，信息位数为k，则监督位数r=n-kn校正子（伴随式）S：为了检测传输过程中是否有错，将接收到的码组代入监督方程式所得到的结果n以（7，4）线性分组码为例，说明（n，k）码的基本原理n7码元a6a5a4a3a2a1a0，信息码元a6a5a4a3，监督码元a2a1a0n校正子S1S2S3与信息码元及监督码元之间的关系为654216531264303aaaaSaaaaSaaaaS322.4 线性分组码线性分组码n基本原理（续）n3个校正子可以指示23-1=7种错误图样，如表所示n可知，（7，4）码可纠正一位错误n在编码时a2a1a0应根据监督方程确定：S1S2S3001010100011

20、101110111000误码位置a0a1a2a3a4a5a6无误654265316430000aaaaaaaaaaaa265416530643aaaaaaaaaaaa即332.4 线性分组码线性分组码n基本原理（续）n由此可得16个许用码组信息位监督位信息位监督位a6a5a4a3a2a1a0a6a5a4a3a2a1a00000000100011100010111001100001010110100100011110101100101001101100001010110111010100110011111010001110001111111342.4 线性分组码线性分组码n基本原理（续）n接收端

21、收到每个码组后，计算出S1、S2和S3，如不全为0，则查表确定误码的位置，予以纠正n如，接收码组为0000011，可算得S1S2S3011，查表知a3错n（7，4）码：dmin=3，能纠正1个误码或检测2个误码n(n, k)线性分组码：nr=n-k个监督码元，有r个校正子，可以指示2r-1个误码图样n当2r-1n（即2rk+r+1）时，就可纠正1位或1位以上的错误n编码效率（编码速率）：k/n=(2r-r-1)/(2r-1)=1-r/n352.4 线性分组码线性分组码n校验矩阵（监督矩阵）n监督码元与信息码元之间的关系可表示为监督方程形式，上例（7，4）码的监督方程为n简记为 HAT0T 或或

22、 AHT0 TTTaaaaaaa0000000100110101010110010111012345600010011010101011001011101234560aaaaaaaAH其中362.4 线性分组码线性分组码n校验矩阵（监督矩阵）（续）n称H为监督矩阵n设收到的码组为B，则校正子SHBTn故可根据H及误码图样表构成差错控制译码器n典型形式监督矩阵nHP Ir n其中，其中，P为为rk阶矩阵，阶矩阵，Ir为为rr阶单位方阵阶单位方阵n各行线性无关n非典型形式监督矩阵可以经过行运算化为典型形式n由典型形式监督矩阵及信息码元可算出各监督码元372.4 线性分组码线性分组码n生成矩阵n监督

23、码元与信息码元之间的关系还可表示为生成方程形式n上述（7，4）码的生成方程为n称G为生成矩阵，由生成矩阵G可构造差错控制编码器 110100010101000110010111000111010001010100011001011100013456345634560123456GGAaaaaGaaaaaaaaaaaaaaa或382.4 线性分组码线性分组码n生成矩阵（续）n典型生成矩阵GnGIk Q n其中，其中，QPT为为kr阶矩阵，阶矩阵，Ik为为kk阶单位方阵阶单位方阵nPQTn由典型生成矩阵G可以得到系统码n各行线性无关n非典型形式生成矩阵可以经过行运算化为典型形式392.4 线性分组

24、码线性分组码n校正子（伴随式）n发送码组A在传输过程中可能发生误码n设接收到的码组为Bbn-1 bn-2 b0n则错误图样 E=B-A，或 B=A+En其中，E= en-1 en-2 e0n校正子为nS=BHT=(A+E)HT=AHT+EHT=EHTnS与E间有确定的关系iiiiab, 1ab, 0当当ie402.4 线性分组码线性分组码n汉明码n上述方法构造的纠正单个错误的线性分组码n特点n码长：n2m1n信息码位：k=2m-m-1n监督码位：r=n-k=mn最小码距：d=3n纠错能力：t=1412.5 循环码循环码n概念、性质和多项式表示n生成多项式n生成矩阵与监督矩阵n编码器422.5

25、循环码循环码n概念及性质n线性分组码中最重要的一种子类，比较成熟n特点n代数结构清晰：有严格的代数理论基础n性能较好：可纠随机错误和突发错误n编译码简单：特殊的代数性质有助于按照要求的纠错能力构造，并且简化译码算法n易于实现：很容易用带反馈的移位寄存器实现n目前的计算机纠错系统中广泛使用的线性分组码432.5 循环码循环码n概念及性质（续）n例：设（7，4）汉明码C的校验矩阵和生成矩阵为 n得到16个码组是：n（1000101）（0001011）（0010110）（0101100）n（1011000）（0110001）（1100010）n（0100111）（1001110）（0011101）（

26、0111010）n（1110100）（1101001）（1010011）n（1111111）（0000000）n可以看到：如果Ci是C的码组，则它的左右移位都是C的码组，具有这种特性的线性分组码称为循环码循环码 1101000011010011100101010001G100101101011100010111H442.5 循环码循环码n概念及性质（续）n循环码的性质：n封闭性n任何许用码组的线性和还是许用码组。由此性质可以得到：线性码都包含全零码线性码都包含全零码n最小码重就是最小码距最小码重就是最小码距n循环性n 任何许用的码组循环移位后的码组还是许用码组 452.5 循环码循环码n概念及

27、性质（续）n多项式表示：n目的：用代数理论的方法研究循环码的特性n定义：码 的码多项式如下 n其中，D为实变量、其幂次代表移位次数， nGF（2）表示2元域，只有两种元素0、1，且0、1满足如下的运算规则：n0+0=0，0+1=1，1+0=1，1+1=0 （加法）n0 x0=0，0 x1=0，1x0=0，1x1=1。 （乘法） n例如：（1011000）的码多项式为 ),.,(021cccCnni012211.)(cDcDcDcDCnnnni)2(GFci346DDD46n左移一位n左移 位)()(102312)1(nnnnnaDaDaDaDA)(121ininininaaaaA)()(122

28、11)(ininninniniaDaDaDaDAin若 是长度为n的循环码组，则 在按模 进行运算后，也是一个循环码组，也就是 用 多项式除后所得之余式，即为所求的码组)(DA)(DADi)(DADi)(1012nnaaaaA2.5 循环码循环码1nD1nD472.5 循环码循环码n生成多项式n循环码完全由其码长n和生成多项式g（D）构成n其中g（D）是一个能除尽Dn+1的r=n-k阶多项式n阶数低于n并能被g（D）除尽的一组码多项式就构成一个（n，k）循环码n即阶数小于或等于阶数小于或等于n-1且能被且能被g（D）除尽的每个多项式）除尽的每个多项式都是循环码的许用码组都是循环码的许用码组 信

29、息多项式为M(D),k 位，(k-1)次多项式 A(D)=M(D)g(D)482.5 循环码循环码n生成多项式（续）n例如，（7，4）循环码的生成多项式n则阶数低于n-1能被g（D）除尽的多项式为n其中 ，i=0，1，2，3n假设n则对应的循环码多项式为n故对应的循环码组为（1111111） 1)(23DDDg)()(012233DgmDmDmDm1011)(0123mmmm1)() 1(23343563DDDDDDDDDgDD123456DDDDDD)2(GFmi492.5 循环码循环码n生成多项式的构造n循环码多项式表示及循环性质 n循环码中任何码组的循环移位还是许用码组，可以表示成码多项

30、式的形式 n定理一：码组 ，经过移位i位，得到码组 则可以证明： 即n证明： 利用多项式的长除法：可以得证 ),.,(021cccCnn).,.,(),.,(21011021innnininnniccccccxxxC)() 1)()(DCDDQDCDini) 1mod()()(niiDDCDDC).()(02211cDcDcDDCDnnnniiiinninnDcDcDc02211.502.5 循环码循环码n生成多项式的构造（续）n循环码多项式表示及循环性质 n例：（7，4）循环码（1000101）的码多项式为 移位1位后变成 将它被 除，得到 因此，循环左移一位的余式为 其相对应的码组为（00

31、01011），正好是（1000101）循环左移一位的结果 126 DDDDDDDD3726) 1(17D) 1() 1(3737DDDDDD13 DD512.5 循环码循环码n生成多项式的构造（续）n循环码多项式的构造n定理二：（n，k）循环码的生成多项式g(D)一定是Dn+1的因式，即 反之，如果g(D)是一个n-k次多项式，且除尽Dn+1 ， 则此g(D)一定生成一个（n，k）循环码 n证明：循环码的码组T（D）是g（D）的倍式，因此 而生成多项式g(D)本身也是一个码组，该码组的多项式次数为n-k次 由定理一，可以知道 也是循环码组 而 所以， 即g（D）是Dn+1的因式n因式分解可以通

32、过计算机分解的方式分解，也可以通过查表（已经作好的因式分解表）得到)()(1DhDgDn)()()(DMDgDT)(DgDk)()(1)(1)(DgDMDDTDDgDnnk)()()()(1DgDhDgDMDDkn522.5 循环码循环码n生成多项式的构造（续）n循环码多项式的构造n例， 因此，（7，4）循环码的生成多项式可以选择 或 而（7，3）循环码的生成多项式可以选择 或 n练习：请验证以下结论练习：请验证以下结论n（7，6）循环码的生成多项式为D+1，实际上就是简单的偶校验码n（7，1）循环码的生成多项式为 ，实际上是7重重复码 ) 1)(1)(1(13237DDDDDD123 DD1

33、3 DD) 1)(1(23DDD) 1)(1(3DDD) 1)(1(323DDDD532.5 循环码循环码n生成矩阵n根据n循环码的码组多项式是生成多项式g（D）的倍式n根据线性码的生成矩阵的特性，（n，k）码的生成矩阵实际上可以由（n，k）码中k个不相关的码组构成n可以挑选出k个循环码组的码多项式形成n非系统码的生成矩阵n系统码的生成矩阵542.5 循环码循环码n生成矩阵n非系统码的生成矩阵n输入信息码元为 时， 相应的循环码组多项式为： 由上式得到的码组不是系统码)()()()(21DgDgDDgDDGkk).(021mmmkk)().,()(021DGmmmDTkk)().(02211D

34、gmDmDmkkkk)()(DgDM552.5 循环码循环码n生成矩阵n系统码的生成矩阵n系统码定义：（系统码定义：（n，k）系统码的码组中前k个比特是信息比特，后n-k个比特是监督位n问题：已知生成多项式g（D），如何构造系统码的生成矩阵？n 在系统码中，码组应该具备如下的形式： n同时有n由上式可得 其中，r（D）的次数小于等于n-k-1n实际上上式表示了如何生成系统码，即n将信息码多项式升n-k次，然后以g（D）为模，求出余式r（D） )(.)(02211DrDmDmDmDTknnknk)()()().(02211DrDDMDrDmDmDmknknkkkk)(mod)()(DgDDMDr

35、kn)()()(DgDMDT562.5 循环码循环码n生成矩阵n系统码的生成矩阵n例： 已知（7，4）系统循环码的生成多项式为 求生成矩阵n解：系统码的生成矩阵形式肯定是 因此选择信息多项式为 、1 将D3提升n-k=3次，得到D6 ，求D6除以g（D）的余式得到 因此，系统生成矩阵为表示成矩阵形式，得到 1)(23DDDgQIkDDD、23)(mod26DgDDD)(mod15DgDD)(mod124DgDDD)(mod123DgDD111)(2324526DDDDDDDDDDDG1011000111010011000100110001G572.5 循环码循环码n监督矩阵n由于g（D）能除尽Dn+1 ，即 （1式）n这里， 称为生成多项式 n h(D)称为监督多项式 n由（1式）知道， )()(1DhDgDn01.)(gDgDgDgknkn01.)(hDhDhDhkk0.0.0.001111102110110021120011000kknkknknknknknknknknkhghghghghghghghghghghghghgghgh582.5