差错控制编码精.ppt

《差错控制编码精.ppt》由会员分享，可在线阅读，更多相关《差错控制编码精.ppt（56页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、差错控制编码第1页，本讲稿共56页本章要点本章要点第第11 11章章 差错控制编码差错控制编码 差错控制编码，又称为信道编码，是提高数字传输可靠性的一种技差错控制编码，又称为信道编码，是提高数字传输可靠性的一种技术，在数字信号传输中，由于噪声的存在及信道特性不理想，都可使信术，在数字信号传输中，由于噪声的存在及信道特性不理想，都可使信号波形变坏，从而在接收端就不可避免的产生错误判决。差错控制编码号波形变坏，从而在接收端就不可避免的产生错误判决。差错控制编码技术充分利用信道多余度，来减小信息传输差错概率。本章主要介绍差技术充分利用信道多余度，来减小信息传输差错概率。本章主要介绍差错控制编码的基本

2、概念；常用的几种检错编码；线性分组码；循环码；错控制编码的基本概念；常用的几种检错编码；线性分组码；循环码；卷积码等。卷积码等。教学重点：纠错编码的基本概念、定理和方法，常用的几种检错教学重点：纠错编码的基本概念、定理和方法，常用的几种检错编码。编码。教学难点：线性分组码；循环码；卷积码。教学难点：线性分组码；循环码；卷积码。第2页，本讲稿共56页差错控制编码目的：降低误码率差错控制编码目的：降低误码率信道分类：信道分类：随机随机信道，信道，突发突发信道，信道，混合混合信道信道差错控制技术的种类：差错控制技术的种类：检错重发，前向纠错，反馈校验，检错删除检错重发，前向纠错，反馈校验，检错删除

3、差错控制编码的基本方法：发送端：信息序列附加监督码元；接差错控制编码的基本方法：发送端：信息序列附加监督码元；接收端：检验信息码元与监督码元之间的关系收端：检验信息码元与监督码元之间的关系.发发收收检错码检错码应答信号应答信号发发收收纠错码纠错码发发收收纠检错纠检错应答信号应答信号检错重发检错重发前向纠错前向纠错混合纠错混合纠错常常用用差差错错控控制制方方法法11.1 11.1 概述概述第3页，本讲稿共56页接收数据接收数据有错码组有错码组有错码组有错码组9214365759810 11131412发送数据发送数据9958521436710 1113 1412重发码组重发码组重发码组重发码组N

4、AK9ACK1NAK5ACK5ACK9ARQ系统系统:停发等候重发停发等候重发 返回重发返回重发 选择重发选择重发接收码组接收码组ACKACKNAKACKACKNAKACKt1233455发送码组发送码组12334556t有错码组有错码组有错码组有错码组接收数据接收数据有错码组有错码组有错码组有错码组910 1110 1112214365798576ACK1NAK5NAK9ACK5发送数据发送数据576952143679810 1110 11 12重发码组重发码组重发码组重发码组第4页，本讲稿共56页例：例：3位位 二进制数构成的码组表示天气二进制数构成的码组表示天气0000010100111

5、00101110111全用全用晴晴云云阴阴雨雨雪雪霜霜雾雾雹雹用用4种种000 晴晴011 云云101 阴阴110 雨雨用用2种种晴晴000雨雨111不能检错、不能检错、不能纠错不能纠错能检能检1位错、位错、不能纠错不能纠错能检测能检测2个错，可个错，可纠纠1位错。位错。11.2 11.2 纠错编码的基本原理纠错编码的基本原理分组码分组码每组每组信息码信息码附加若干附加若干监督码监督码的的编码称为编码称为分组码分组码。如不用检错，传输如不用检错，传输4种信息，用两位码就够了，这两位码称为种信息，用两位码就够了，这两位码称为信信息位息位，多增加的称为，多增加的称为监督位监督位。在分组码中，监督码

6、元仅监督本码组中的信息码元。在分组码中，监督码元仅监督本码组中的信息码元。第5页，本讲稿共56页分组码的一般结构分组码的一般结构分组码的符号：分组码的符号：(n,k)n 码组的总位数，又称为码组的长码组的总位数，又称为码组的长度（码长），度（码长），k 码组中信息码元的数目，码组中信息码元的数目，n k r 码组中的监督码元数目，码组中的监督码元数目，或称监督位数或称监督位数信息位信息位 监监督位督位晴晴000云云011阴阴101雨雨110第6页，本讲稿共56页分组码的分组码的码重码重：码组中：码组中“1”的个数；的个数；码距码距：两个码组中对应位上数字不同的位数；或称汉明距离：两个码组中对应

7、位上数字不同的位数；或称汉明距离最小码距最小码距：某种编码中各个码组间距离的最小值。：某种编码中各个码组间距离的最小值。“000”晴，晴，“011”云，云，“101”阴，阴，“110”雨雨(0,0,0)(0,0,1)(1,0,1)(1,0,0)(1,1,0)(0,1,0)(0,1,1)(1,1,1)a2a0a1第7页，本讲稿共56页 码距和检纠错能力的关系码距和检纠错能力的关系编码的最小码距编码的最小码距 d0 的大小直接关系着这种编码的的大小直接关系着这种编码的检错检错和和纠错能纠错能力，力，为检测为检测e个错码，要求最小码距个错码，要求最小码距 d0 e+10123BA汉明距离汉明距离ed

8、01.若码组若码组A 中发生中发生两位错码两位错码，则，则其位置不会超出以其位置不会超出以O点为圆心，点为圆心，以以 e 为半径的圆。为半径的圆。因此，只要最小码距不小于因此，只要最小码距不小于e+12.为纠正为纠正 t 个错码，要求最小码距个错码，要求最小码距d0 2t+1设设A和和B的距离为的距离为5。码组。码组A或或B若发生不多于两位错码，则其位置若发生不多于两位错码，则其位置均不会超出半径为均不会超出半径为2以原位置为圆心的圆。这两个圆是以原位置为圆心的圆。这两个圆是不重叠不重叠的。的。第8页，本讲稿共56页BtA汉明距离汉明距离012345td03.为纠正为纠正 t 个错码，同时检测

9、个错码，同时检测e个错码，要求最小码距个错码，要求最小码距检错检错 e=d0 1=5 1=4，纠纠 2个错码，不能同时满足个错码，不能同时满足ABe1tt汉明距离汉明距离这种纠错和检错结合的工作方式简称这种纠错和检错结合的工作方式简称纠检结合纠检结合。第9页，本讲稿共56页系统带宽和信噪比的矛盾：系统带宽和信噪比的矛盾：举例：举例：未编码，误码率未编码，误码率A点，点，编码后，误码率编码后，误码率B点。点。保持误码率保持误码率10-5，C点，未编码时，点，未编码时，D点，点，编码后。编码后。10-610-510-410-310-210-1编码后编码后Pe CDE A B信噪比信噪比(dB)传输

10、速率和传输速率和 Eb/n0 关系关系若提高传输速率，若提高传输速率，误码率增大。误码率增大。信噪比下降信噪比下降C点点E点点D点点付出的代价仍是带宽增大。付出的代价仍是带宽增大。第10页，本讲稿共56页11.4.1 11.4.1 奇偶监督码奇偶监督码奇偶监督码：奇偶监督码：奇数监督码和偶数监督码。偶监督码中，奇数监督码和偶数监督码。偶监督码中，1位监督位，位监督位，使码组中使码组中“1”为偶数。为偶数。11.4 11.4 简单的实用编码简单的实用编码 这种编码能够检测这种编码能够检测奇数个奇数个错码。错码。在接收端，按照上式求在接收端，按照上式求“模模2和和”。结果为结果为“1”就说明就说明

11、有错码有错码，结果为，结果为“0”认为认为无错码无错码。第11页，本讲稿共56页a01 a02 a0m 为为 m 行奇偶监督码中的行奇偶监督码中的 m 个个监督位监督位。cn-1 cn-2 c1 c0为按列进行第二次编码所增加的监督位，它们构成了一为按列进行第二次编码所增加的监督位，它们构成了一监监督位行督位行。可能检测可能检测偶数个偶数个错码错码 构成矩形构成矩形四角四角的错码的错码无法检测无法检测 还可以用来纠正一些错码还可以用来纠正一些错码11.4.2 11.4.2 二维奇偶监督码（方阵码）二维奇偶监督码（方阵码）第12页，本讲稿共56页11.4.3 11.4.3 恒比码恒比码“1”的数

12、目与的数目与“0”的数目之比保持恒定。的数目之比保持恒定。这种码在检测时，只要计算接收码组中这种码在检测时，只要计算接收码组中“1”的数目是否对，就知的数目是否对，就知道有无错码。道有无错码。11.4.4 11.4.4 正反码正反码能够纠正错码的编码。其中的监督位数目与信息位数目相同能够纠正错码的编码。其中的监督位数目与信息位数目相同 编码规则：编码规则：信息位有奇数个信息位有奇数个“1”，监督位监督位是信息位的是信息位的重复重复；信息位有偶数个信息位有偶数个“1”，监督位监督位是信息位的是信息位的反码反码。正反码的解码正反码的解码在接收码组中在接收码组中 信息位信息位 监督位监督位=合成码组

13、合成码组00001 00001=00000校验码组校验码组第13页，本讲稿共56页 接收码组信息位有奇数个接收码组信息位有奇数个“1”，合成码组就是校验码组；，合成码组就是校验码组；接收码组信息位有偶数个接收码组信息位有偶数个“1”，取合成码组的反码作为校验码，取合成码组的反码作为校验码组。组。校验码组和错码的关系校验码组和错码的关系校校验码组验码组的的组组成成错码错码情况情况1全全为为“0”无无错码错码2有有4个个“1”和和1个个“0”信息信息码码中有中有1位位错码错码，其位置，其位置对应对应校校验码组验码组中中“0”的位置的位置3有有4个个“0”和和1个个“1”监监督督码码中有中有1位位错

14、码错码，其位置，其位置对应对应校校验码组验码组中中“1”的位置的位置4其他其他组组成成错码错码多于多于1个个若发送码组若发送码组 11001 11001，接，接收码组收码组 10001 11001则合成码组应为则合成码组应为 10001 11001=01000。校验码组就是校验码组就是10111。若发送码组若发送码组 11001 11001，接收，接收码组码组 11001 01001则合成码组应为则合成码组应为 11001 01001=10000。校验码组就是校验码组就是10000。第14页，本讲稿共56页11.5 11.5 线性分组码线性分组码 基本概念基本概念代数码代数码：建立在代数学基础

15、上的编码。：建立在代数学基础上的编码。线性码线性码：按照一组线性方程构成的代数码。在线性码中信息位：按照一组线性方程构成的代数码。在线性码中信息位和监督位是由一些线性代数方程联系着的。和监督位是由一些线性代数方程联系着的。线性分组码线性分组码：按照一组线性方程构成的分组码：按照一组线性方程构成的分组码。本节将以本节将以 汉明码汉明码 为例引入线性分组码一般原理。为例引入线性分组码一般原理。构造原理构造原理在在偶数监督码偶数监督码中，一位监督位中，一位监督位a0，和信息位构成代数式：，和信息位构成代数式：第15页，本讲稿共56页在在接收端接收端解码时，实际上就是在计算解码时，实际上就是在计算监督

16、关系式监督关系式校正子校正子S=0，认为无错码；，认为无错码；S=1，就认为有错码。，就认为有错码。若监督位增加一位，两个校正子的可能值有若监督位增加一位，两个校正子的可能值有4中组合：中组合：00，01，10，11，故能表示，故能表示4种不同信息。种不同信息。1种种表示无错表示无错 其余其余3种种能指示能指示1位错码位错码(2r 1)个可能位置。个可能位置。码长为码长为 n，信息位数为，信息位数为 k，则监督位，则监督位 rnk。指示指示1位错码的位错码的 n 种可能位置，要求种可能位置，要求第16页，本讲稿共56页 设分组码设分组码(n,k)中中k=4，为了，为了纠正纠正1位错码，位错码，

17、要求监督位数要求监督位数 r 3。若取。若取 r=3，则，则n=k+r=7S1 S2 S3错码错码位置位置S1 S2 S3错码错码位置位置001a0101a4010a1110a5100a2111a6011a3000无无错码错码 仅当仅当一位错码一位错码在在a2、a4、a5或或a6时，校正子时，校正子S1为为1,偶数监督关系偶数监督关系a1、a3、a5和和a6构成偶数监督关系：构成偶数监督关系：a0、a3、a4和和a6构成偶数监督关系：构成偶数监督关系：第17页，本讲稿共56页监督位监督位a2、a1和和a0应根据信息位的取值按监督关系来确定，即监督位应根据信息位的取值按监督关系来确定，即监督位应

18、使应使S1、S2和和S3的值为的值为0:上式经过移项运算，解出监督位上式经过移项运算，解出监督位第18页，本讲稿共56页信息位信息位a6 a5 a4 a3监监督位督位a2 a1 a0信息位信息位a6 a5 a4 a3监监督位督位a2 a1 a00000000100011100010111001100001010110100100011110101100101001101100001010110111010100110011111010001110001111111给定信息位后，可以直接按上式算出监督位给定信息位后，可以直接按上式算出监督位第19页，本讲稿共56页接收端接收端收到每个码组后，先计

19、算出收到每个码组后，先计算出S1、S2和和S3，再查表判断错码情，再查表判断错码情况。况。例如：若接收码组为例如：若接收码组为1101100按监督式计算可得：按监督式计算可得：S1=1，S2=1，S3=0。查表可知在查表可知在a5位有位有1错码。错码。码效率：码效率：k/n=(n-r)/n=1 r/n，当当n很大和很大和r很小时，码率接近很小时，码率接近1。汉明码是一种高效码。汉明码是一种高效码。按照上述方法构造的码称为按照上述方法构造的码称为汉明码汉明码。表中所列的表中所列的(7,4)汉明码的最小码距汉明码的最小码距d0=3。这种码能够纠正这种码能够纠正1个错码或检测个错码或检测2个错码。个

20、错码。S1 S2 S3错码错码位置位置S1 S2 S3错码错码位置位置001a0101a4010a1110a5100a2111a6011a3000无无错码错码信息位信息位a6 a5 a4 a3监监督位督位a2 a1 a0信息位信息位a6 a5 a4 a3监监督位督位a2 a1 a00000000100011100010111001100001010110100100011110101100101001101100001010110111010100110011111010001110001111111第20页，本讲稿共56页 线性分组码的一般原理线性分组码的一般原理线性分组码的构造线性分组码的

21、构造H矩阵矩阵上面上面(7,4)汉明码的例子有汉明码的例子有改写为改写为上式中已经将上式中已经将“”简写成简写成“+”。第21页，本讲稿共56页矩阵形式矩阵形式简记为简记为H AT=0T 或或 A HT=0H称为称为监督矩阵监督矩阵。只要监督矩阵只要监督矩阵 H 给给定，编码时监督位和定，编码时监督位和信息位的关系就完全信息位的关系就完全确定了。确定了。H矩阵的性质：矩阵的性质：1)H 的行数就是监督关系式数，等于监督位数的行数就是监督关系式数，等于监督位数 r。每行中每行中“1”的位置表示监督关系。的位置表示监督关系。H 矩阵可以分成两部分矩阵可以分成两部分P 为为 r k 阶矩阵，阶矩阵，

22、Ir为为r r阶单位方阵。阶单位方阵。我们将具有我们将具有P Ir形式的形式的H矩阵称为矩阵称为典型阵典型阵。第22页，本讲稿共56页2)H 矩阵各行线性无关，才有矩阵各行线性无关，才有 r个独立监督位。个独立监督位。若矩阵能写成形式若矩阵能写成形式P Ir，各行一定线性无关，各行一定线性无关G矩阵：汉明码例子中的监督位公式为矩阵：汉明码例子中的监督位公式为可以改写成可以改写成或或Q=PT信息位的行矩阵乘矩阵信息位的行矩阵乘矩阵Q 就产生出监督位就产生出监督位第23页，本讲稿共56页生成矩阵生成矩阵G由它可以产生整个码组由它可以产生整个码组具有具有IkQ形式的生成矩阵形式的生成矩阵称为称为典型

23、生成矩阵典型生成矩阵。由典型生成矩阵得出的由典型生成矩阵得出的码组码组 A中中，信息位的位置信息位的位置不变，监督位附加于其后。不变，监督位附加于其后。这种形式的码称这种形式的码称 系统码系统码。G矩阵的性质：矩阵的性质：1)G 矩阵的各行是线性无关的。矩阵的各行是线性无关的。任一码组任一码组 A 都是都是 G 的各行的线性组合。的各行的线性组合。2)实际上，实际上，G的各行本身就是一个码组。的各行本身就是一个码组。如果已有如果已有k个线性无关的码组，则可以用其作为生成矩阵个线性无关的码组，则可以用其作为生成矩阵G，并由它生成其余码组。，并由它生成其余码组。G 的的 k 行线性无关行线性无关2

24、k 种不同的码组种不同的码组 A恰是有恰是有 k 位信息位的全部码组。位信息位的全部码组。第24页，本讲稿共56页 错码矩阵和错误图样错码矩阵和错误图样A为一个为一个 n 列的行矩阵，发送的码组就是列的行矩阵，发送的码组就是A。设接收码组为设接收码组为 n列的行矩阵列的行矩阵 B，即，即发送码组和接收码组之差为发送码组和接收码组之差为B A=E(模模2)E 传输中产生的传输中产生的 错码错码 行矩阵行矩阵错码矩阵有时也称为错码矩阵有时也称为错误图样错误图样 校正子校正子S当接收码组有错时，当接收码组有错时，E 0，将，将 B 代入代入(A HT=0)，不一定成立。即，不一定成立。即 B HT=

25、S，将，将B=A+E 代入代入 S=(A+E)HT=A HT+E HT=E HT S 称为校正子。它能用来指示错码的位置。称为校正子。它能用来指示错码的位置。S 和和E 之间有确定的线性变换关系。之间有确定的线性变换关系。第25页，本讲稿共56页 线性分组码的性质线性分组码的性质封闭性封闭性：是指一种线性码中的任意两个码组之和仍为这种码中的一个码是指一种线性码中的任意两个码组之和仍为这种码中的一个码组。组。若若A1和和A2是一种线性码中的两个许用码组，则是一种线性码中的两个许用码组，则 (A1+A2)仍为其中的仍为其中的一个码组。一个码组。A1 和和A2之间的距离之间的距离=(A1+A2)的重

26、量。的重量。码的最小距离就是码的最小重量（除全码的最小距离就是码的最小重量（除全“0”码组外）码组外）第26页，本讲稿共56页(7,3)循环码的全部码组循环码的全部码组码组编码组编号号信息位信息位监监督位督位码组编码组编号号信息位信息位监监督位督位a6a5a4a3a2a1a0a6a5a4a3a2a1a01000000051001011200101116101110030101110711001014011100181110010循环码原理循环码原理循环性循环性：任一码组循环一位以后，仍为该码中的码组。：任一码组循环一位以后，仍为该码中的码组。11.6 11.6 循环码循环码第27页，本讲稿共5

27、6页 码多项式码多项式码组的多项式表示法码组的多项式表示法一个长度为一个长度为 n 的码组表示成的码组表示成（7，3）循环码）循环码 第第7个码组个码组1100101可以表示为可以表示为x仅是码元位置的标记仅是码元位置的标记 码多项式的按模运算码多项式的按模运算若一个整数若一个整数m可以表示为可以表示为则在模则在模 n 运算下，有运算下，有m p (模模n)在模在模 n 运算下，一个整数运算下，一个整数 m 等于它被等于它被 n 除得的余数。除得的余数。Q 整数整数第28页，本讲稿共56页 码多项式运算码多项式运算 多项式多项式 F(x)被被 n 次多项式次多项式N(x)除除=商式商式 Q(x

28、)+余式余式 R(x)按模按模2 运算，即系数只取运算，即系数只取 0 和和1。xx3+1 x4+x2+1 x4+x x2+x+1应当注意，由于在模应当注意，由于在模2运算中，用加运算中，用加法代替了减法，故余项不是法代替了减法，故余项不是x2 x+1，而是，而是x2+x+1。循环码的生成矩阵循环码的生成矩阵G码组生成公式码组生成公式G 是是 k 行行 n 列的矩阵，若能找到列的矩阵，若能找到 k 个个已知码组已知码组，就能，就能构成矩阵且这构成矩阵且这 k个已知码组必须是线性的。个已知码组必须是线性的。第29页，本讲稿共56页在循环码中，一个在循环码中，一个(n,k)码有码有 2k 个不同的

29、码组。个不同的码组。若用若用g(x)表示其中前表示其中前(k 1)位皆为位皆为“0”的码组，则的码组，则 g(x)，x g(x)，x2 g(x)，xk-1 g(x)都是码组，而且这都是码组，而且这k个码组是线性无关的。因个码组是线性无关的。因此它们可以用来构成此循环码的生成矩阵此它们可以用来构成此循环码的生成矩阵G。在循环码中除全在循环码中除全“0”码组外，再没有连续码组外，再没有连续k位均为位均为“0”的码组，即连的码组，即连“0”的长度最多只能有的长度最多只能有(k-1)位。位。g(x)必须是一个常数项不为必须是一个常数项不为“0”的的(n-k)次次多项式，且此多项式，且此g(x)还是这种

30、还是这种(n,k)码中次数码中次数为为(n k)的唯一多项式。的唯一多项式。我们称这唯一的我们称这唯一的(n k)次多项式次多项式g(x)为码的为码的生生成多项式成多项式。确定了确定了g(x)，则整个，则整个(n,k)循环码就被确定循环码就被确定了。了。循环码的生成矩阵循环码的生成矩阵 G 可以写成可以写成第30页，本讲稿共56页(7,3)循环码中，循环码中，n=7,k=3,n k=4。不符合不符合G=IkQ的形式，所以它不是典型阵。的形式，所以它不是典型阵。不过，将它作线性变换，不难化成典型阵。不过，将它作线性变换，不难化成典型阵。写出此循环码组，即写出此循环码组，即唯一唯一 (n k)=4

31、次次 码多项式代表的码多项式代表的码组是第二码组码组是第二码组0010111，对应码，对应码多项式多项式 g(x)=x4+x2+x+1。将。将g(x)代入上式，得代入上式，得第31页，本讲稿共56页 所有码多项式所有码多项式T(x)都可被都可被g(x)整除，而且任意一个次数不大于整除，而且任意一个次数不大于(k 1)的的多项式乘多项式乘g(x)都是码多项式。两个矩阵相乘的结果应该仍是一个矩阵。都是码多项式。两个矩阵相乘的结果应该仍是一个矩阵。上式中两个矩阵相乘的乘积是只有一个元素的一阶矩阵，这个上式中两个矩阵相乘的乘积是只有一个元素的一阶矩阵，这个元素就是元素就是T(x)。寻找寻找 (n,k)

32、循环码循环码 的生成多项式的生成多项式任一循环码多项式任一循环码多项式 T(x)都是都是 g(x)的的 倍式，可以写成倍式，可以写成T(x)=h(x)g(x)，而生成多项式而生成多项式g(x)本身也是一个码组，即有本身也是一个码组，即有T (x)=g(x)，码组，码组T (x)是是一个一个(n k)次多项式，次多项式，xk T (x)是一个是一个n次多项式。次多项式。xk T (x)在模在模(xn+1)运算下也是一个码组运算下也是一个码组上式左端分子和分母都上式左端分子和分母都是是 n 次多项式，故商式次多项式，故商式Q(x)=1。第32页，本讲稿共56页可以化成可以化成将将T(x)和和T(x

33、)代入得代入得g(x)是是(xn+1)的一个因子，且为的一个因子，且为(n k)次因式。次因式。【例例】(x7+1)可以分解成可以分解成(7,3)循环码的生成多项式循环码的生成多项式g(x)需要从上式中找到一个需要从上式中找到一个(n k)=4次的因子次的因子都可作为生成多项式都可作为生成多项式第33页，本讲稿共56页 循循环码环码的的编码编码方法方法选选定生成多定生成多项项式式g(x)-从从(xn+1)的因子中的因子中选选一个一个(n-k)次多次多项项式作式作为为g(x)。用用 xn-k乘乘m(x)，得到，得到 xn-k m(x)，其次数小于，其次数小于n。xn-k m(x)/g(x)，得余

34、式，得余式r(x)，其次数必小于，其次数必小于g(x)，即小于，即小于(n k)。r(x)加于信息位之后作加于信息位之后作为监为监督位督位将将r(x)和和xn-k m(x)相加得到相加得到码码多多项项式。式。编码步骤：编码步骤：用用xn-k乘乘m(x)。在信息码后附加上。在信息码后附加上(n k)个个“0”。信息码为信息码为110，它相当于，它相当于m(x)=x2+x用用g(x)除除xn-k m(x)，得到商，得到商Q(x)和余式和余式r(x)，即，即第34页，本讲稿共56页例如，若选定例如，若选定g(x)=x4+x2+x+1，则，则上式相当于上式相当于编出的码组编出的码组T(x)为为T(x)

35、=xn-k m(x)+r(x)T(x)=1100000+101=1100101，是表中的第，是表中的第7码组。码组。循环码的解码方法循环码的解码方法解码要求：解码要求：检错和纠错。检错和纠错。检错解码原理：检错解码原理：在接收端将接收在接收端将接收R(x)用用g(x)去除。去除。若码组在传输中发生错误，则若码组在传输中发生错误，则 R(x)T(x)，R(x)被被g(x)除时可能除不尽而有余项，即有除时可能除不尽而有余项，即有第35页，本讲稿共56页 纠错解码原理：纠错解码原理：要求每个可纠正的错误图样必须与一个特定余式有一一对应关系。要求每个可纠正的错误图样必须与一个特定余式有一一对应关系。纠

36、错可按下述步骤进行：纠错可按下述步骤进行：用生成多项式用生成多项式g(x)除接收码组除接收码组R(x)，得出余式，得出余式r(x)。按余式按余式r(x)，用，用 查表查表 或或 计算计算 得到错误图样得到错误图样E(x)；例如，通过计算校正子例如，通过计算校正子S和查表，可以确定错码的位置。和查表，可以确定错码的位置。R(x)-E(x)，便得到已经纠正错码的原发送码组，便得到已经纠正错码的原发送码组T(x)。u一种编码可以有几种纠错解码方法，上述解码方法为一种编码可以有几种纠错解码方法，上述解码方法为捕错解码捕错解码u目前多采用软件运算实现上述编解码运算。目前多采用软件运算实现上述编解码运算。

37、第36页，本讲稿共56页 截短循环码截短循环码截短目的：截短目的：在设计纠错编码时，纠错能力预先给定的。在设计纠错编码时，纠错能力预先给定的。不一定有恰好满足这些条件的循环码存在。不一定有恰好满足这些条件的循环码存在。截短方法：截短方法：一个一个(n,k)循环码，使前循环码，使前i(0 i k)个信息位全为个信息位全为“0”，于是它变成仅有于是它变成仅有 2k-i 种码组。种码组。删去这删去这i位全位全“0”的信息位，得到的信息位，得到(n i,k i)的线性码。将这种码称为的线性码。将这种码称为截短循环码截短循环码。截短循环码性能：截短循环码性能：循环码截短前后至少具有相同的纠错能力，并且循

38、环码截短前后至少具有相同的纠错能力，并且编解码方法仍和截短前的方法一样。编解码方法仍和截短前的方法一样。【例例】要求构造一个能够纠正要求构造一个能够纠正1位错码的位错码的(13,9)码。由码。由(15,11)循环循环码的码的11种码组中选出前两信息位均为种码组中选出前两信息位均为“0”的码组，构成一个新的码组的码组，构成一个新的码组集合。然后在发送时不发送这两位集合。然后在发送时不发送这两位“0”。于是发送码组成为。于是发送码组成为(13,9)截截短循环码。短循环码。第37页，本讲稿共56页11.7 11.7 卷积码卷积码卷积码是一种卷积码是一种非分组码非分组码。更适用于前向纠错，性能优于分组

39、码，运算简单。更适用于前向纠错，性能优于分组码，运算简单。一个码组中的监督码元监督着一个码组中的监督码元监督着N个信息段个信息段本码组本码组 k bit信息段，信息段，前前 m=(N 1)个码组的信息段。个码组的信息段。N称为编码称为编码约束度约束度，nN称为编码称为编码约束长度约束长度。卷积码记作卷积码记作(n,k,N)码率则仍定义为码率则仍定义为k/n第38页，本讲稿共56页 卷积码的基本原理卷积码的基本原理编码器原理方框图编码器原理方框图编码输出编码输出每次每次输入输入k比特比特1k1k1k1k 1 k2k3kNk 12nNk级级移存器移存器n个模个模2加法器加法器每输入每输入k比特比特

40、旋转旋转1周周第39页，本讲稿共56页【例例】(n,k,N)=(3,1,3)卷积码编码器卷积码编码器bi-2bi输入输入bibi-1编码输出编码输出dicieiM2M3M1设输入信息比特序列是设输入信息比特序列是bi-2 bi-1 bi bi+1，则当输入，则当输入bi时，此编码器时，此编码器输出输出3比特比特ci di ei，输入和输出，输入和输出第40页，本讲稿共56页c1d1e1c2d2e2c3d3e3b1b2b3tt输入输入输出输出虚线示出了信息位虚线示出了信息位 bi 的的监督位监督位和各和各信息位信息位之间的约束关系。之间的约束关系。约束度约束度N=3约束长度约束长度 nN=9第4

41、1页，本讲稿共56页第第4级支路开始，码树上半部和下半部相同。从第级支路开始，码树上半部和下半部相同。从第4个输入信息位开始，个输入信息位开始，输出码元与第输出码元与第1位输入信息位无关，此编码器约束度位输入信息位无关，此编码器约束度N=3 卷积码的几何表述卷积码的几何表述:(3,1,3)码树图码树图起点起点信息位信息位状态状态 M3M2 a 0 0 b 0 1 c 1 0 d 1 1信息位信息位 11 0 1000111000111001110011100010101000111001110011100010101111000001110c2d2e2000100111011001101110

42、010abcdabcdabcdabcd上上半半部部下下半半部部ba10aabcdabcdcdab011001c4d4e4c3d3e3c1d1e1第42页，本讲稿共56页移存器前一移存器前一状状态态M3 M2当前当前输输入入信息位信息位 bi输输出出码码元元cidiei移存器下一移存器下一状状态态M3 M2a(00)01000111a(00)b(01)b(01)01001110c(10)d(11)c(10)01011100a(00)b(01)d(11)01010101c(10)d(11)状态图状态图由编码器结构可知，输出码元由编码器结构可知，输出码元ci di ei决定于当前输入信息位决定于当前

43、输入信息位bi和前和前两位信息位两位信息位bi-1和和bi-2（即移存器（即移存器M2和和M3的状态）。的状态）。第43页，本讲稿共56页abcd111000110101100001011010虚线表示输入信息位为虚线表示输入信息位为“0”时状态转变的路线；时状态转变的路线；实线表示输入信息位为实线表示输入信息位为“1”时状态转变的路线。时状态转变的路线。-线条旁的线条旁的3位数字是编码输出比特。位数字是编码输出比特。第44页，本讲稿共56页110110110110011011011010010010101101101001001001001abcdabcd000000000000000111

44、111111111111100100100网格图网格图 将状态图在时间上展开，网格图：将状态图在时间上展开，网格图：图中画出了图中画出了5个时隙。在第个时隙。在第4时隙以后的网格图形完全是重复时隙以后的网格图形完全是重复第第3时隙的图形。这也反映了此时隙的图形。这也反映了此(3,1,3)卷积码的约束长度为卷积码的约束长度为3。第45页，本讲稿共56页abcdabcd110010001111100输入信息位为输入信息位为11010时，在网格图中的编码路径。时，在网格图中的编码路径。有了上面的状态图和网格图，就可以讨论维特比解码算法了。有了上面的状态图和网格图，就可以讨论维特比解码算法了。卷积码的

45、解码卷积码的解码代数解码代数解码：利用代数结构进行解码，不考虑信道的统计特性。：利用代数结构进行解码，不考虑信道的统计特性。大数逻辑解码大数逻辑解码，又称，又称门限解码门限解码，对于约束长度较短的卷积码最为有，对于约束长度较短的卷积码最为有效，而且设备较简单。效，而且设备较简单。概率解码概率解码：又称：又称 最大似然解码最大似然解码。它基于信道的统计特性和卷积码的特点进。它基于信道的统计特性和卷积码的特点进行计算。另一种概率解码方法是行计算。另一种概率解码方法是 维特比算法维特比算法。第46页，本讲稿共56页维特比解码算法维特比解码算法基本原理：基本原理：将接收到的序列和所有可能的发送序列比较

46、，选择其将接收到的序列和所有可能的发送序列比较，选择其中汉明距离最小的序列认为是当前发送信号序列。中汉明距离最小的序列认为是当前发送信号序列。若发送一个若发送一个k位序列，则有位序列，则有2k种可能的发送序列。种可能的发送序列。当当k较大时，存储量太大，使实用受到限制。较大时，存储量太大，使实用受到限制。维特比算法对此作了简化，使之能够实用。维特比算法对此作了简化，使之能够实用。第47页，本讲稿共56页(3,1,3)卷积码卷积码 设现在的发送信息位为设现在的发送信息位为1101，为使移存器的信息位全部移出，在信息位，为使移存器的信息位全部移出，在信息位后面加入后面加入3个个“0”，故编码后的发

47、送序列为，故编码后的发送序列为111 110 010 100 001 011 000。并且假设接收序列为。并且假设接收序列为111 010 010 110 001 011 000 由于这是一个由于这是一个(n,k,N)=(3,1,3)卷积码，发送序列的约束度卷积码，发送序列的约束度N=3，所，所以首先需考察以首先需考察nN 9比特。比特。第第1步考察接收序列前步考察接收序列前9位位“111 010 010”。由此码的网格图可见，。由此码的网格图可见，沿路径每一级有沿路径每一级有4种状态种状态a,b,c和和d。每种状态只有两条路径可以到达。每种状态只有两条路径可以到达。故故4种状态共有种状态共有

48、8条到达路径。条到达路径。第48页，本讲稿共56页110110110110011011011010010010101101101001001001001abcdabcd000000000000000111111111111111100100100由出发点状态由出发点状态a经过经过3级路径后到达状态级路径后到达状态a的两条路径中上面一条为的两条路径中上面一条为“000 000 000”。和接收序列。和接收序列“111 010 010”的汉明距离等于的汉明距离等于5；下面一条为下面一条为“111 001 011”,它和接收序列的汉明距离等于它和接收序列的汉明距离等于3。同样，。同样，由出发点由出发

49、点a经过经过3级到达状态级到达状态b、c和和d的路径分别都有两条，故总共有的路径分别都有两条，故总共有8条路径。条路径。第49页，本讲稿共56页序号序号路径路径对应对应序列序列汉汉明距离明距离幸存否幸存否1aaaa000 000 0005否否2abca111 001 0113是是3aaab000 000 1116否否4abcb111 001 1004是是5aabc000 111 0017否否6abdc111 110 0101是是7aabd000 111 1106否否8abdd111 110 1014是是将到达每个状态的两条路径比较，将距离小的路径保将到达每个状态的两条路径比较，将距离小的路径保

50、留，称为幸存路径。这样就剩下留，称为幸存路径。这样就剩下4条路径了，即表中条路径了，即表中第第2,4,6和和8条路径。条路径。第50页，本讲稿共56页110110110110011011011010010010101101101001001001001abcdabcd000000000000000111111111111111100100100111 010 010 110 001 53第一次比较后的幸存路径。第一次比较后的幸存路径。序号序号路径路径对应对应序列序列汉汉明距离明距离幸存否幸存否1abca111 001 0113是是2abcb111 001 1004是是3abdc111 110