11西南大学-通信原理-第十一章 差错控制编码

1、通信原理主讲教师：高 渤 含弘光大 继往开来学习内容概 述1234纠错编码的性能纠错编码的根本原理5第十一章 过失控制编码简单的实用编码5线性分组码卷积码77559低密度奇偶检验码6循环码8Turbo码10网格编码调制通信原理【第十一章 过失控制编码】2学习目标 学习要点1、过失控制方式和编码分类；2、最小码距与纠检错能力；3、几种常用的简单编码；4、线性分组码的生成G、监督H和纠错S；5、循环码的生成多项式、生成矩阵、编码和译码；6、卷积码的矩阵、多项式和图形描述方法。通信原理【第十一章 过失控制编码】3学习目标 重点1、概念： 过失控制的根本原理；码重、汉明距离、最小距离的概念和确定；纠检

2、能力与之间的关系；汉明码的概念及其有关参数；卷积码的描述方法和约束度N的含义。2、计算： 码率的计算；线性分组码的、编码、校正子和纠错；循环码编码和译码过程；给出卷积码编码器，能写出其输入和输出的关系；给定输入信码，得到输出卷积码序列。通信原理【第十一章 过失控制编码】4学习目标 难点1、编码效率。2、汉明码。3、校验接收码组B是否出错的方法。4、多项式运算规那么。通信原理【第十一章 过失控制编码】5学习内容概 述1234纠错编码的性能纠错编码的根本原理5第十一章 过失控制编码简单的实用编码5线性分组码卷积码77559低密度奇偶检验码6循环码8Turbo码10网格编码调制通信原理【第十一章 过

3、失控制编码】6一、信道分类 从过失控制角度看，按加性干扰引起的错码分布规律的不同，信道可以分为三类： 1、随机信道：错码的出现是随机的。 2、突发信道：错码是成串集中出现的。 3、混合信道：既存在随机错码又存在突发错码。第一节 概 述二、过失控制技术 1、过失控制技术 一般分为：检错重发、前向纠错、反响校验、检错删除。 通信原理【第十一章 过失控制编码】72、过失控制编码：常称为纠错编码。第一节 概 述2多余度： 指增加的监督码元多少。例如，假设编码序列中平均每两个信息码元就添加一个监督码元，那么这种编码的多余度为1/3。1监督码元： 除反响校验外，都是在接收端识别有无错码。所以在发送端需要在

4、信息码元序列中增加一些过失控制码元，称为监督码元。不同的编码方法，有不同的检错或纠错能力。通信原理【第十一章 过失控制编码】84冗余度： 监督码元数n-k 和信息码元数 k 之比n-k/ k 。第一节 概 述 理论上，过失控制以降低信息传输速率为代价换取提高传输可靠性。3编码效率简称码率 ： 设编码序列中信息码元数量为k，总码元数量为n，那么比值k/n 就是码率。通信原理【第十一章 过失控制编码】9三、过失控制原理举例自动要求重发ARQ系统接收码组ACKACKNAKACKACKNAKACKt1233455发送码组12334556t有错码组有错码组第一节 概 述 发送一组数据后发端等待收端确实认

5、ACK答复，再发送下一组数据；假设收到否认NAK答复，那么重发。系统工作在半双工状态，时间没有得到充分利用，传输效率较低。 1、停止等待ARQ系统 通信原理【第十一章 过失控制编码】102、拉后ARQ系统接收数据有错码组有错码组91011101112214365798576ACK1NAK5NAK9ACK5发送数据57695214367981011101112重发码组重发码组第一节 概 述 发送端连续发送数据组，接收端对于每个接收到的数据组都发回确认ACK或否认NAK答复。 在这种系统中需要对发送的数据组和答复进行编号，以便识别。显然，这种系统需要双工信道。 通信原理【第十一章 过失控制编码】1

6、13、选择重发ARQ系统接收数据有错码组有错码组921436575981011131412发送数据995852143671011131412重发码组重发码组NAK9ACK1NAK5ACK5ACK9第一节 概 述只选择重发出错的数据组，因此进一步提高了传输效率。通信原理【第十一章 过失控制编码】124、ARQ的主要优点和前向纠错方法相比：第一节 概 述5、ARQ的主要缺点：3检错用的编码方法和加性干扰的统计特性根本无关，能适应 不同特性的信道。2检错的计算复杂度较低；1监督码元较少即能使误码率降到很低，即码率较高；2因为重发而使ARQ系统的传输效率降低。1需要双向信道来重发，也不能用于一点到多点

7、的通信系统。3在信道干扰严重时，可能反复重发造成事实上的通信中断。4在要求实时通信的场合，往往不允许使用ARQ法。通信原理【第十一章 过失控制编码】136、ARQ系统的原理方框图第一节 概 述通信原理【第十一章 过失控制编码】14学习内容概 述1234纠错编码的性能纠错编码的根本原理5第十一章 过失控制编码简单的实用编码5线性分组码卷积码77559低密度奇偶检验码6循环码8Turbo码10网格编码调制通信原理【第十一章 过失控制编码】15一、纠错编码的根本原理 1、相关知识回忆 1纠错编码的概念 在信息码元序列中参加监督码元，称为过失控制编码。2实现纠错编码的根本思想原理 1利用冗余度 冗余比

8、特与信息比特之间存在着特定的相关性。 2使噪声均化(随机化) 噪声均化是将过失均匀分摊给各码字，到达提高总体差 错控制能力的目的。第二节 纠错编码的根本原理通信原理【第十一章 过失控制编码】162、纠错编码的分类1按对信息序列的处理方法：分组码和卷积码。2按照校验位与信息位的关系：线性码与非线性码。3按照适用的过失类型：纠随机过失码和纠突发过失码。4按照构码理论：代数码、几何码、算术码、组合码等。 有多少观察问题的角度，就有多少分类方法。不同的分类方法只是从不同的角度抓住码的某一特性加以归类，并不能说明某个码的全部特性。 分类可以进一步细化，把大类分割成小类。第二节 纠错编码的根本原理通信原理

9、【第十一章 过失控制编码】173、纠错编码举例分组码例子3, 2 既不能检错也不能纠错能检错，但不能纠错许用码组禁用码组合法码组许用码组000、111其余码组禁用既可检错，也能纠错第二节 纠错编码的根本原理通信原理【第十一章 过失控制编码】18 4、分组码的概念 1定义 将信息码分组，对每个信息码组附加假设干监督码元的编码。2表示法 用符号N，K表示，其中K是每组二进制信息码元的个数，N是编码组的总位数，又称码长，NK = r 为每码组中监督码元的数目。第二节 纠错编码的根本原理通信原理【第十一章 过失控制编码】191码重：码组中“1的个数，称为码组的重量简称码重。第二节 纠错编码的根本原理3

10、最小码距：把某种编码中各个码组之间距离的最小值称为最 小码距d0。如上面的编码的最小码距d0 = 2。 “000晴，“011云，“101阴，“110雨，4个码组之间，任意两个的距离均为2。2码距：把两个码组中对应位上数字不同的位数，称为码组的 距离，简称码距，又称汉明距离。例如：3分组码的码重和码距通信原理【第十一章 过失控制编码】20码距的几何意义 4码距汉明距的几何意义 两个码组对应位上数字不同的位数，称为码组的距离。最大码距最小码距d0 编码的最小码距决定了该编码的检错和纠错能力： d0 = 1 时，没有检、纠错能力； d0 = 2 时，具有检查一个过失的能力； d0 = 3 时，用于检

11、错时具有检查两个过失的能力； 用于纠错时具有纠正一个过失的能力。第二节 纠错编码的根本原理通信原理【第十一章 过失控制编码】21 最小码距 的大小与编码的检错和纠错能力的关系： 1为检测 个错码，那么要求： 2为纠正 个错码，那么要求： 3为纠正 个错码，同时检测 个错码，那么要求：第二节 纠错编码的根本原理通信原理【第十一章 过失控制编码】22纠正 t 个错码，同时检测 e 个错码5、码距与检、纠错能力的关系检测 e 个错码纠正 t 个错码第二节 纠错编码的根本原理通信原理【第十一章 过失控制编码】23第二节 纠错编码的根本原理 如何理解证明：为纠正 t 个错码，同时检测 e 个错码，要求最

12、小码距 d0 t + e +1 e t 。BtA汉明距离012345td0设码组A和B之间距离为5，那么最多能检测4个错码，最多能纠正2个错码。但是，不能同时满足。当错码位数超过纠错能力时，该码组会立即进入另一码组的圆内而被错误地“纠正了。因此，检错和纠错公式不能同时成立或同时运用。 通信原理【第十一章 过失控制编码】24 为了可以在纠正 t 个错码的同时，能够检测 e 个错码，需要如以下图所示。使某一码组譬如码组A发生e个错误之后所处位置，与其他码组譬如码组B的纠错圆圈至少距离等于 1 ，以防止落在该纠错圆上从而发生错误地“纠正。因此，由此图可以直观看出，要求最小码距ABe1tt汉明距离第二

13、节 纠错编码的根本原理 这种纠检结合的工作方式是自动转换的。它适用于大多数时间里错码数量很少，少数时间里错码数量多的情况。通信原理【第十一章 过失控制编码】25学习内容概 述1234纠错编码的性能纠错编码的根本原理5第十一章 错控制编码简单的实用编码5线性分组码卷积码77559低密度奇偶检验码6循环码8Turbo码10网格编码调制通信原理【第十一章 过失控制编码】26一、系统带宽和信噪比的矛盾第三节 纠错编码的性能 在发送码元序列中参加监督码元，使得发送序列增长，冗余度增大，假设仍保持发送信息码元速率不变，那么传输速率必须增大，因而增大了系统带宽。 系统带宽的增大将引起系统中噪声功率增大，使信

14、噪比下降。信噪比的下降反而又使系统接收码元序列中的错码增多。 一般说来，采用纠错编码后，误码率总是能够得到很大改善的。改善的程度和所用的编码有关。通信原理【第十一章 过失控制编码】27二、编码性能举例第三节 纠错编码的性能 未采用纠错编码时，假设接收信噪比等于7dB，编码前误码率约为810-3，图中A点； 在采用纠错编码后，误码率降至约410-4.5，图中B点。 这样，不增大发送功率就能降低误码率约一个半数量级。10-610-510-410-310-210-1编码后PeCDEBA信噪比 （dB）编码前通信原理【第十一章 过失控制编码】28 由图还可以看出，假设保持误码率在10-5，图中C点，未

15、采用编码时，约需要信噪比Eb / n0 = 10.5 dB。 采用编码时，约需要信噪比7.5 dB，图中D点。可以节省功率2dB，通常把这2dB称为编码增益。第三节 纠错编码的性能 上面两种情况付出的代价是带宽增大。10-610-510-410-310-210-1编码后PeCDEBA信噪比 （dB）编码前通信原理【第十一章 过失控制编码】29 传输速率和Eb/n0的关系第三节 纠错编码的性能 式中，RB为码元速率。假设希望提高传输速率，由上式看出势必使信噪比下降，误码率增大。对于给定的传输系统通信原理【第十一章 过失控制编码】30第三节 纠错编码的性能10-610-510-410-310-21

16、0-1编码后PeCDEBA信噪比 （dB）编码前 假设系统原来工作在图中C点，提高速率后由C点升到E点。 但加用纠错编码后，仍可将误码率降到D点。这时付出的代价仍是带宽增大。通信原理【第十一章 过失控制编码】31学习内容概 述1234纠错编码的性能纠错编码的根本原理5第十一章 过失控制编码简单的实用编码5线性分组码卷积码77559低密度奇偶检验码6循环码8Turbo码10网格编码调制通信原理【第十一章 过失控制编码】32 1、偶数监督码 无论信息位多少，监督位只有1位，它使码组中“1的数目为偶数，即满足下式条件： 。一、奇偶监督码适用于检测随机错码第四节 简单的实用编码 能检测奇数个错码。在接

17、收端，按照上式求“模2和，假设计算结果为“1就说明存在错码，结果为“0就认为无错码。 奇偶监督码分为奇数监督码和偶数监督码两种。 2、奇数监督码 码组中“1的数目为奇数，即满足下式条件： 通信原理【第十一章 过失控制编码】33二、二维奇偶监督码方阵码，适用于检测突发错码第四节 简单的实用编码 1、二维奇偶监督码的构成 先把上述奇偶监督码的假设干码组排成矩阵，每一码组写成一行，然后再按列的方向增加第二维监督位。2、二维奇偶监督码的性能 可能检测偶数个错码，也有一些偶数错码不能被检测出来。 由于方阵码只对构成矩形四角的错码无法检测，故其检错能力较强。此外，二维奇偶监督码不仅可用来检错，还可以用来纠

18、正一些错码，例如：仅在一行中有奇数个错码时。通信原理【第十一章 过失控制编码】34三、恒比码第四节 简单的实用编码 恒比码的主要优点是：简单和适于用来传输电传机或其他键盘设备产生的字母和符号。 检测时只要计算接收码组中“1的数目是否对，就知道有无错码。 每个码组均含有相同数目的“1和“0。由于“1的数目与“0的数目之比保持恒定，因此称为恒比码。通信原理【第十一章 过失控制编码】35 例如：假设码长 n = 10，其中信息位 k = 5，监督位 r = 5。编码规那么：信息位中有奇数个“1时，监督位是信息位的简单重复；信息位有偶数个“1时，监督位是信息位的反码。四、正反码第四节 简单的实用编码

19、1、正反码的编码 是一种简单的纠错码编码。监督码元与信息位数目相同或者相反，是由信息码中“1的个数而定。 例如：假设信息位为11001，那么码组为 11001 11001 ；假设信息位为10001，那么码组为 10001 01110 。2、正反码的解码略通信原理【第十一章 过失控制编码】36学习内容概 述1234纠错编码的性能纠错编码的根本原理5第十一章 过失控制编码简单的实用编码5线性分组码卷积码77559低密度奇偶检验码6循环码8Turbo码10网格编码调制通信原理【第十一章 过失控制编码】37一、线性分组码的根本概念第五节 线性分组码3、线性分组码：按照一组线性方程构成的分组码 。 2、

20、线性码： 按照一组线性方程构成的代数码。在线性码中信息位和监 督位是由一些线性代数方程联系着的。1、代数码：建立在代数学根底上的编码。4、汉明码： 是能够纠正1位错码且编码效率较高的一种线性分组码。通信原理【第十一章 过失控制编码】38 假设S = 0，就认为无错码；假设S = 1，就认为有错码。上式就称为监督关系式，S 称为校正子。由于校正子S只有两种取值，故它只能代表有错和无错这两种信息，而不能指出错码的位置。 在偶数监督码中，由于使用了一位监督位a0，它和信息位an-1 a1一起构成一个代数式：二、汉明码的构造原理第五节 线性分组码在接收端解码时，实际上就是在计算1、监督关系式的概念通信

21、原理【第十一章 过失控制编码】39第五节 线性分组码 假设监督位增加一位，即变成两位，那么能增加一个类似的监督关系式。由于两个校正子的可能值为： 00、01、10、11，故能表示4种不同的信息。 假设用其中1种组合表示无错，那么其余3种组合就有可能用来指示一个错码的3种不同位置。同理，r 个监督关系式能指示1位错码的2r 1个可能位置。 假设码长为 n ，信息位数为 k ，那么监督位数 rnk 。如果用 r 个监督位构造出 r 个监督关系式来指示1位错码的 n 种可能位置，那么要求通信原理【第十一章 过失控制编码】40第五节 线性分组码2、如何构造监督关系式 例：设分组码n, k中k = 4，

22、为纠正1位错码，那么要求监督位数 r 3。假设取 r = 3，那么n = k + r = 7。用a6 a5 a0表示7个码元，用S1、S2和S3表示3个监督关系式中的校正子，那么S1、S2和S3的值与错码位置的对应关系，可以规定如下表所列：S1 S2 S3错码位置S1 S2 S3错码位置0 0 1a01 0 1a40 1 0a11 1 0a51 0 0a21 1 1a60 1 1a30 0 0无错码通信原理【第十一章 过失控制编码】41 由表中可见，仅当一位错码的位置在a2 、a4、a5或a6时，校正子S1为1；否那么S1为零。即：a2 、a4、a5和a6四个码元构成偶数监督关系：第五节 线性

23、分组码以及a0、a3、a4 和a6构成偶数监督关系：同理， a1、a3、a5和a6构成偶数监督关系：S1 S2 S3错码位置S1 S2 S3错码位置0 0 1a01 0 1a40 1 0a11 1 0a51 0 0a21 1 1a60 1 1a30 0 0无错码通信原理【第十一章 过失控制编码】42 发端编码时，信息位a6、a5、a4和a3的值决定于输入信号，取值是随机的。监督位a2、a1和a0应根据信息位的取值按监督关系来确定，即监督位应使上3式中S1、S2和S3的值为0表示编成的码组中应无错码：第五节 线性分组码上式经过移项运算，解出监督位通信原理【第十一章 过失控制编码】43给定信息位后

24、，可直接按上式算出监督位， 结果见下表：第五节 线性分组码信息位a6 a5 a4 a3监督位a2 a1 a0信息位a6 a5 a4 a3监督位a2 a1 a00 0 0 00 0 01 0 0 01 1 10 0 0 10 1 11 0 0 11 0 00 0 1 01 0 11 0 1 00 1 00 0 1 11 1 01 0 1 10 0 10 1 0 01 1 01 1 0 00 0 10 1 0 11 0 11 1 0 10 1 00 1 1 00 1 11 1 1 01 0 00 1 1 10 0 01 1 1 11 1 1通信原理【第十一章 过失控制编码】44 收端收到每个码组后

25、，先计算出S1、S2和S3，再查表判断错码情况。例如，假设接收码组为0000011，按上述公式计算可得：S1 = 0，S2 = 1，S3 = 1。由于S1 S2 S3 等于011，故查表可知在a3位有1错码。第五节 线性分组码 按照上述方法构造的码称为汉明码。表中所列的7, 4汉明码的最小码距d0 = 3。因此，这种码能够纠正1个错码或检测2个错码。由于码率k/n = n - r /n =1 r/n，故当n很大和r很小时，码率接近1。可见，汉明码是一种高效码。通信原理【第十一章 过失控制编码】45三、线性分组码的一般原理第五节 线性分组码现在将上面它改写为式中已经将“简写成“+：上面7, 4汉

26、明码的例子有1H矩阵监督矩阵1、线性分组码的构造式中已经将“简写成“+。 通信原理【第十一章 过失控制编码】46第五节 线性分组码上式可表示成如下矩阵形式：H AT = 0T 或 A HT = 0还可以简记为： 式中A = a6 a5 a4 a3 a2 a1 a00 = 000“T表示将矩阵转置。 H称为监督矩阵。只要监督矩阵H给定，编码时监督位和信息位的关系就完全确定了。 通信原理【第十一章 过失控制编码】47第五节 线性分组码发2H矩阵的性质： 1H的行数就是监督关系式的数目r H的每行中“1的位置表示相应码元之间存在的监督关系。例如：1110100 。H矩阵可以分成两局部，如 式中，P为

27、r k阶矩阵，Ir为r r阶单位方阵。具有P Ir形式的H矩阵称为典型阵。通信原理【第十一章 过失控制编码】48 2H矩阵的各行线性无关 否那么得不到 r 个线性无关的监督关系式，也得不到 r 个独立的监督位。假设矩阵能写成典型阵形式P Ir，那么其各行一定是线性无关。第五节 线性分组码发3G矩阵生成矩阵：上例中也可改写成矩阵形式：通信原理【第十一章 过失控制编码】49或者写成第五节 线性分组码发 上式表示，在信息位给定后，用信息位的行矩阵乘矩阵Q就产生出监督位。式中，Q为一个k r阶矩阵，它为P的转置，即 Q = PT。通信原理【第十一章 过失控制编码】50将Q的左边加上1个k k阶单位方阵

28、，就构成1个矩阵G 第五节 线性分组码发或者G称为生成矩阵，因为由它可以产生整个码组，即有通信原理【第十一章 过失控制编码】51 因此，如果找到了码的生成矩阵G，那么编码的方法就完全确定了。具有Ik Q形式的生成矩阵，称为典型生成矩阵。 由典型生成矩阵得出的码组A中，信息位的位置不变，监督位附加于其后，这种形式的码称为系统码。 第五节 线性分组码发通信原理【第十一章 过失控制编码】524G矩阵的性质： 1G矩阵的各行是线性无关的 任一码组A都是G的各行的线性组合。G共有k行，假设它们线性无关，那么可以组合出2k种不同的码组A。第五节 线性分组码发 2G的各行本身就是一个码组 如果有 k 个线性无关的码组，