差错控制编码

1、第九章差错控制编码9.1引言一、信源编码与信道编码数字通信中，根据不同的目的，编码分为信源编码与信道编码二大类。信源编码提高数字信号的有效性，如，PCM编码，AM编码，图象 数据压缩编码等。信道编码提高传输的可靠性，又称抗干扰编码，纠错编码。由于数字通信传输过程中，受到干扰，乘性干扰引起的码间干扰，可用 均衡办法解决。加性干扰解决的办法有：选择调制解码，提高发射功率。如果上述措施难以满足要求，则要考虑本章讨论的信道编码技术，对误 码（可能或已经由现）进行差错控制。从差错控制角度看：信道分三类：（信道编码技术） 随机信道：由加性白噪声引起的误码，错码是随机的，错码间统计独 立。 突发信道：错码成

2、串，由脉冲噪声干扰引起。 混合信道：既存在随机错误，又存在突发错码，那一种都不能忽略不 计的信道。信道编码（差错控制编码）是使不带规律性的原始数字信号，带上规律 性（或加强规律性，或规律性不强）的数字信号，信道译码器则利用这些规 律性来鉴别是否发生错误，或进而纠错。需要说明的是信道编码是用增加数码，增加冗余来提高抗干扰能力。检错重发二：差错控制的工作方式w>判决信号纠错码、A信息信号<发前向纠错发反馈校验法收信息信号（1）检错重发（2）前向纠错，不要反向信道（3）反馈校验法，双向信道这三种差错控制的工作方式 见下图所示：9.2 纠错编码的基本原理举例说明纠错编码的基本原理。用三位二

3、进制编码表示8种不同天气晴OOo OI I010阴一组码共彳011雨需、4计8种 I 0 0雪I 01霜|110雾II 11雹0 0 0 晴0 1 1云许用码组，其它为禁用码组1 0 1 阴：1 1 0 雨J160许用码组中，只要错一位（不管哪位错），就是禁用码组，故这种编码能 发现任何一位由错，但不能发现的二位由错，二位由错后又产生许用码。上述这种编码只能检测错误，不能纠正错误。因为晴雨阴错一位，都变成1 0 0。要想纠错，可以把8种组合（3位编码）中，只取2种为许用码，其它6 种为禁用码。例如：0 0 0 晴1 1 1 雨这时，接收端能检测两个以下的错误，或者能纠正一个错码。例：收到禁用码

4、组1 0 0时，如认为只有一位错，则可判断此错码发 生在第1位，从而纠正为0 0 0 （晴），因为1 1 1 （雨）发生任何一个错误都 不会变成1 0 0。若上述接收码组种的错码数认为不超过二个，则存在两种可能性:(000) (111)li¥错2位变成（1 1 1）或（1 0 0）因为只能检生错误，但不能纠正。:分组码，码重，码距 （见樊书P282表9-1）将码组分段：分成信息位段和监督位段，称为分组码，记为（n, k）n 编码组的总位数，简称码长（码组的长度）k 每组二进制信息码元数目，（信息位段）n - k = r 监督码元数目，（监督位段）（见樊书P282,图9-2）在分组码中

5、，有“ 1”的数目称为码组的重量，简称码重。例如，码组(1 1 0 1 0),码长n=5,码重为3。把两个码组对应位不同的数目称为这两个码组的距离，简称码距，又称11000、<10011,Hamming (汉明)的距离例如，码组(1 1 0 0 0)与(1 0 0 1 1)的距离为3而码组集合中，全体码组之间的距离的最小值称为最小码距( d。) 码距的几何意义见樊书P283,图9-3。从图看由，码距d越小，检错，纠错能力越强 二：纠错编码的效用樊书P284监督位数r越多，对提高抗干扰，降低误码率越有好处9.3 常用的简单编码纠错码的分类：(沈振元书P388)(1)奇偶校验码(“1”的数目

6、应为偶数或奇数)。(见樊书P285)偶校验码满足条件：an_1二an_2二二a0 = 0举例：偶校验的例子：码组：110011一一二入码长 n = 6,11001 L信息位段长k = 5，信息位偶校验位监督位数r = 1偶校验位="1” 满足条件：1 1份05 0 15 1 = 0(2)二维奇偶校验码仍然举偶校验的例子：（3）恒比码例如，我国电传机传输阿拉伯数字时，用 5位代码表示，每个码组的长 度为5,其中恒有3个“1”，称为“5中取3”恒比码。阿拉伯数字保护电码阿拉伯数字保护电码101011610101211001711100310110801110411010910011500

7、111001101（4）正反码正反码的信息位段长k与监督位段长r相同，如正反码组：信息位段有奇数个1： 1100111001（监督位与信息位重复）一、一、,人 信息位监督位 "、，、一、信息位段有偶数个1: 1000101110（监督位是信息位反码）A A信息位监督位9.4 线性分组码一：基本概念可用线性方程组（代数关系）表述码的规律性的分组码称为线性分组码。如奇偶校验码的编程原理利用了代数关系，an_1旨an_2$ a0 = 0 （偶校验关系），称奇偶校验码为线性分组码。在代数码中，常见的是线性码，即编码中的信息位和监督位是由一些线 性代数方程联系着，或者说可用线性代数方程表述编码

8、的规律性。上述正反码中，为了纠正一位错误，使用的监督位和信息位一样多，即编码效率只有50% （编码效率。=k/n）o那么为了纠正一位错误码，在分组码中最少要几位监督码位？编码效率 能否提高。从这种思想由发，便导致了汉明码的诞生。汉明码是能够纠正一位错码且编码效率较高的一种线性分组码。二：线性分组码的一种一一汉明码下面介绍汉明码（Hamming）的构造原理。先回顾偶校验码，在接收端实际上计算监督关系式:s = an/二 an_2 二二 ao若s = 0 无错5 = 1 有错6 称校正子由于s校正子只有两种形式“ 0”或“1”，只能代表有错或无错，因而不 能找由错码的位置。不难想象，如果监督位增加

9、一位，即变成二位监督位，即能增加一个类 似于偶校验码监督式的新的监督式。两个监督式就有两个校正子，其可能值有 4种组合：0 0, 0 1,1 0,1 1,这4种组合代表不同信息。若用1种组合表示无错，其余3种组合就可以用来表示一位错码的3种 不同位置。同理，r个监督式能指示一位错码的2r-1个可能位置。一般来说，若码长n ,信息位数k ,则监督位r = n - k ,汉明码n与r满 足：现以（n, k） = （7, 4）, r =3为例的汉明码来说明如何具体构造这些监 督关系式。a6a5a4a0a2 a1a0 监督位a6 a5 a4 信息位51, s2, s3校正子（3个监督关系式中的校正子）

10、这3个校正子、,s, s3,可建立三个互为独立的监督关系式4 , s2 , s3的值与错码位置的对应关系可以规定如下表：（见樊书P288,图9-4）s , s2 , s3错码位置s , s2 , s3错码位置001a0101a4010a1110a5100a2111a6011a3000无错s , s2 , s3全为零,表示无错。只要s1 （或s2,或S3）为“1”，就表示有错，、是不是1,由22,a4,a5,a6 的由错决定，可写成偶监督关系式：s1 = a6 二 a5 二 a4 二 a2（只有&为零时才无错，发送编码时，将监督码元22与信息码元的关系满足此式）王里 S2 = a6 二

11、a5 二 a3 二 a1同理 s3 = a6 二 a4 - a3 二 a0在发端编码时，信息位a3, a4, a5 ,a6的值是随机的，监督位a2, a1 ,a0应根 据信息位按监督关系来确定，即监督位应使上面的 s1, s2, s3监督式为零。即要求：a6 二 a5 二 a4 二 a2 = 0a6 二 a5 二 a3 二 a1 = 0a6六a4宁''a?六a。= 0或写成监督码元在左边的形式：a2 = a6 二 a5 二 a4a 二 a6 二 a5 二 a3a。 二 a6 二 a4二 a3信息位a6, a5 ,a4, a3一旦确定后，可直接按上式计算由监督位（见樊书P289图

12、9-5）接收端收到每个码字（码组）后，先计算由偶监督关系式，Si ,S2 , S3再按 表9-4 （樊书P288）判断错码情况。如果Si, S2 ,S3不全零,可判由在哪一位由错a2 = a6 5a5 9 a4ai = a6 a5 份 a3 一查樊书表9-4, 判错哪一位并 纠正之a6 5a55a4 3 a2 = 0a © a © a a = 0a6a5a3 a10a63a4 * a33a0 = 0发送端，将信息位按接收端，先计算校正& , S2 , S3为零否,a。= a6 出 a4 6 a?此式加上监督位后汉明码最小距d0=3 （见樊书表9-5）,能够纠正单个错

13、误。三：线性分组码的一般原理（1）监督阵和生成矩阵将上述汉明码（7, 4）的监督关系式改写成：（见樊书P289, 9.4-8）1a61a51a40a31a20a10ao= 01a61a50a41a30a21a10ao= 01a60a51a41a30a20a11ao= 0上式中简写为十 , 写成矩阵形式：表示模2相加。11_1a6I Ia5a4a3a2a1 I I.a。0=0,0(模2)简记H AT二0T监督矩阵H为r父n 关。(H (r行,监督矩阵）n列）阶矩阵，H阵的每行之间彼此线性无也可将H矩阵分为两部分:1H = 1_1a6a3a2a1a0其中P为rxk阶矩阵,1r为rx r阶单位矩阵。

14、若把监督关系式改写补充:a6a4a3 a2a1a0a6a6a6a5a5a4a4a4a3a3a3ai一1100。111 11 a§0100I 5 I1甩1a4100101可改写为矩阵形式：a31000a |a51 1= 1111a4 0 | 41 11/3 -旧1|1101 |I1>0 J!1011Ja6I I即 AT = GT，,变换为 A = 16a5a4a3 】G ,a4 I a -其中G =100001000 00 01 00 1111110101011一QG称为生成矩阵，如果找到 和G可产生全部码字。G,则纠错编码方法就确定了，可由信息组hQ1 也称典型生成矩阵，其中Q

15、1 1 1L ,一1 1 011 0 11'I-0 1 1一Ik为kxk方阵100 _00 0 01 0 00 1 01'0 0 1由典型生成矩阵得由的码组 A中，信息位不变，监督位附加其后，这种码称为系统码。（2）校正子S （伴随式）设发送码组A= a», an/，ai汨0（在传输过程中可能发生误码）设接收码组B = bn,bn_2, bi, bo1则发送码组与接收码组之差定义为 E （也称错误图样）：E = B - A （模 2）l r1 甘 ,°，当 4 = aiE = bn,en/e ,e°其中0 ="11，当 b，ai因此，若0 = 0 ,表示该位接收码元无错；若e = 1,则表示有错。E = B - A ,也可改写为B = A E例如：发送A = 1 0 0 0 1 1 1错误 E = 0 0 0 0 1 0 0接收 B = 1 0 0 0 0 1 1令5 = B NT称S为校正子，也称伴随式。S= B HT = （A+ E）HT =JAHT + EH二零矩阵=EH T由此可见，校正子S与错误图样E之间有确定的线性变换关系，若S和 E之间一一对应，则S将能代表错码的位置。接收端译码器的任务就是从校正子 S确定错误图样，然后，从接收到的 码字中减去错误图样Eo上述（7, 4）汉明码的校正子S与错误图