第11章差错控制编码

1、第第11章章 差错控制编码差错控制编码11.1 引引 言言11.2 纠错编码的基本原理纠错编码的基本原理11.3 纠错编码的性能纠错编码的性能11.4 简单的实用编码简单的实用编码11.5 线性分组码线性分组码11.6 循环码循环码11.7 卷积码卷积码11.8 Turbo码码11.9 低密度奇偶校验码低密度奇偶校验码11.7 网格编码调制网格编码调制11.1 引言 在数字通信中，根据不同的目的，编码可分为信源编码和信道编码。信源编码是为了提高数字信号的有效性以及为了使模拟信号数字化而采取的编码。n信道编码是为了降低误码率， 提高数字通信的可靠性而采取的编码n数字信号在传输过程中受到干扰的影响

2、，使信号波形变坏，发生误码，可以采用一些方法解决。同时设计系统时，还要合理地选择调制、解调、发送功率等因素，采用上述措施仍难以满足性能要求，就要采用差错控制措施了。一、一、从差错控制角度看，信道可以分为从差错控制角度看，信道可以分为三类：三类：即随机信道、突发信道和混合信道。随机信道随机信道在随机信道中、错码的出现是随机的，且错码之间是统计独立的。突发信道突发信道错码是成串集中出现的。混合信道混合信道存在随机和突发两种错码。、接收端根据什么来识别有无错码由发送端的信道编码器在信息码元序列中增加一些监督码元。这些监督码和信码之间有确定的关系，使接收端可以利用这种关系由信道译码器来发现或纠正可能存

3、在的错码。 在信息码元序列中加入监督码元就称为差错控制编码，有时也称为纠错编码。、差错控制编码原则上是以降低信息传输速率为代价来换取传输可靠性的提高。二、差错控制编码的基本思想二、差错控制编码的基本思想三、常用的差错控制方法有以下几种： 检错重发法接收端在收到的信码中检测出(发现)错码时，即设法通知发送端重发，直到正确收到为止。 ARQ(Automatic Repeat Request)前向纠错法接收端不仅能发现错码，还能够确定错码的位置，能够纠正它。反馈校验法接收端将收到的信码原封不动地转发回发送端与原信码比较。若发现错误则发端重发。三种差错控制方法可以结合使用。发发可以纠正错误的码(a)

4、前向纠错(FEC)收收发能够发现错误的码应答信号(b) 检错重发(ARQ)收可以发现和纠正错误的码应答信号(c) 混合纠错检错(HEC)ARQ系统组成信源编码器和缓冲存储重发控制双向信道译码器指令产生缓冲存储收信者ARQ优点：冗余码元少、对信道有自适应能力、成本和复杂性低；ARQ缺点：需要反向信道、重发控制较复杂、干扰大通信效率低、实时性差。一、分类一、分类（1）按照信道编码的不同功能，分为检错码和纠错码。）按照信道编码的不同功能，分为检错码和纠错码。 （2）按照信息码元和监督码元之间的检验关系，可以将按照信息码元和监督码元之间的检验关系，可以将它分为线性和非线性码。它分为线性和非线性码。 （

5、3）按照信息码元和监督码元之间的约束方式不同，可按照信息码元和监督码元之间的约束方式不同，可以将它分为分组码和卷积码。以将它分为分组码和卷积码。 （4）按照信息码元在编码后是否保持原来的形式，可以按照信息码元在编码后是否保持原来的形式，可以将它分为系统码和非系统码。将它分为系统码和非系统码。 （5）按照纠正错误的类型不同，可以将它分为纠正随机）按照纠正错误的类型不同，可以将它分为纠正随机错误码和纠正突发错误码。错误码和纠正突发错误码。 随着数字通信系统的发展，可以将信道编码器和调制器随着数字通信系统的发展，可以将信道编码器和调制器统一起来综合设计，这就是所谓的网格编码调制。统一起来综合设计，这

6、就是所谓的网格编码调制。 11. 2 纠错编码的基本原理11.2 纠错编码的基本原理 分组码举例 设：有一种由3个二进制码元构成的编码，它共有23 = 8种不同的可能码组：000 晴 001 云 010 阴 011 雨100 雪 101 霜 110 雾 111 雹 这时，若一个码组中发生错码，则将收到错误信息。 若在此8种码组中仅允许使用4种来传送天气，例如：令000 晴 011 云 101 阴 110 雨 为许用码组，其他4种不允许使用，称为禁用码组。 这时，接收端有可能发现（检测到）码组中的一个错码。 这种编码只能检测错码，不能纠正错码。 若规定只许用两个码组：例如000 晴 111 雨就

7、能检测两个以下错码，或纠正一个错码。 例：3位二进制数字构成的码组，共有8种不同的组合。若将其全部利用来表示天气，则可以表示8种不同的天气。000(晴)，001(多云)，010(阴)，011(雨)，100(雪)， 101(霜)， 110(雾)， 111(雹)。）种状态，个许用码组，个禁用码组任一码组在传输中若发生一个或多个措码则将变成另一信息码组。这时接收端将无法发现错误。二、一般原理、检错原理若：000=晴001 =不可用010 =不可用011=云100 =不可用101=阴110=雨111 =不可用）种状态，个许用码）种状态，个许用码组，个禁用码组组，个禁用码组 虽然只能传送4种不同的天气但

8、是接收消却有可能发现码组中的一个错码。 例如，若000(晴)中错了一位，则接收码组将变成100或010或001，这三种码组都是不准许使用的，称为禁用码组，故接收端在收到禁用码组时，就认为发现了错码。但是这种码不能发现两个措码，因为发生两个错码后产生的是许用码组。上述码只能检测错误，不能纠正错误。例如，当收到的码组为禁用码组100时，无法判断是哪一位码发生了错误因为晴、阴、雨三者错了一位都可以变成100。）种状态，个许用码组，个禁用码组）种状态，个许用码组，个禁用码组要想能纠正错误纠正错误，还要增加多余度。例如，苦规定许用码组只有两个：000(晴)、111(雨)、其余都是禁用码组。这时，接收场能

9、检测两个以下错码，或能纠正一个错码。n、分组码的一般概念。n为了传输4种不同的信息，用两位二进制码组就够了，它们是：00、01、10、11。代表所传信息的这些两位码，称为信息位。前面使用3位码，多出的一位称为监督位。，每组信码附加若干监督码的编码集合，称为分组码。n例如分组码的结构n符号 (n，k)表示分组码nk信息码元数nn码组长度(码长)nn-k监督码元数an-1an-2arar-1a0k位信息位r位监督位n=k+r时间码重、码距与码的纠检错能力n码重“1”的数量称为码组的重量n码距两个码组对应位上数字不同的位数称为码组的距离，简称码距。又称汉明(Hamming)距离。n最小码距某种编码中

10、各个码组间距离的最小值称为最小码距(d0)。（1） e +1 d0，即码的检错能力e比最小码距d0小1位；（2）2t+1 d0，即码的纠错能力t的2倍比最小码距d0小1位；（3） e +t+1 d0 ，即若码同时纠t个错并检出e个错误，则e +t比最小码距d0小1位。n、最小码距决定检错纠错n若记： d0 最小码距； e检错位数； t纠错位数；则有：（1） e +1 d0（2） 2t +1 d0（3） t +e+1 d0三、差错控制编码的效用n 假设:发送“0”的错误概率和发送“1”的错误概率相等，都等于P，且P1，则在码长为n的码组中恰好发生r个错码的概率为rrnrrnnprnrnpprPC

11、)!( !)1 ()(例如，当码长n7时，p=10-3则有P7(1) 7p= 710-3 ；P7(2) 21p2=2.110-5 ； P7(3) 35p3=3.510-8。可见，采用差错控制编码，即使仅能纠正(或检测)这种码组中12个错误，也可以使误码率下降几个数量级。这就表明，即使是较简单的差错控制编码也具有较大实际应用价值。例如，当码长n7时，p=10-3则有P7(1) 7p= 710-3 ；P7(2) 21p2=2.110-5 ； P7(3) 35p3=3.510-8。编码效率用差错控制编码提高通信系统的可靠性， 是以降低有效性为代价换来的。我们定义编码效率R来衡量有效性:R=k/n其中

12、, k是信息元的个数，n为码长。对纠错码的基本要求是: 检错和纠错能力尽量强； 编码效率尽量高；编码规律尽量简单。实际中要根据具体指标要求，保证有一定纠、检错能力和编码效率，并且易于实现。 .奇偶监督码n如果以上关系被破坏，则出现错误，因此能检查出奇数个错误，但不能检测偶数个错误。最小码距为 dmin=212100nnaaaa12101nnaaaa01221 aaaaann信息位监督位 11. 3 常用的简单编码偶监督奇监督如：信息码为如：信息码为10010101，则奇校验码为则奇校验码为10010101 1 偶校验码为偶校验码为10010101 02二维奇偶监督码又称方阵码。每一行是奇偶监督

13、码的一个码组，若干码组再按列排列成矩阵，每列增加一位监督位。图 7-2 (66,50)行列监督码 110010100000100001101001111000011100111000001010101010111000111100n二维奇偶监督码特点：可检测奇数个错误适于检测突发错码。不仅可检错，还可纠一些错。检错能力强。n3恒比码每个码组均含有相同数目的“1”(和“0”)。n应用：电传机传输汉字，每个汉字用4位阿拉伯数字表示。每个阿拉伯数字又用5位二进制符号构成的码组表示。每个码组的长度为5位，其中恒有3个1，称为5中取3恒比码。可能编成的不同码组数等于从5中取3组合数30。30种许用码组恰

14、好可用来表示10个阿拉伯数字。表表9-3 39-3 3：2 2的恒比码的恒比码数数字字码字码字数数字字码字码字00 1 l 0 l50 0 1 l l10 1 0 l l61 0 1 0 l2l l 0 0 171 1 1 0 031 0 l 1 080 1 l 1 041 1 0 1 091 0 0 1 111.3 线性分组码一、基本概念 代数码 利用代数关系式产生监督位的编码 线性分组码 代数码的一种，其监督位和信息位的关系由线性代数方程决定 汉明码 一种能够纠正一个错码的线性分组码 校正子：在偶数监督码中，计算实际上就是计算 并检验S是否等于0。S称为校正子。 监督关系式：0021aaa

15、nn021aaaSnn021aaaSnn 纠错基本原理 中，S只有两种取值，故只能表示有错和无错，而不能进一步指明错码的位置。 若此码组长度增加一位，则能增加一个监督关系式。这样，就能得到两个校正子。两个校正子的可能取值有4种组合，即00，01，10，11，故能表示4种不同的信息。若用其中一种组合表示无错码，则还有其他3种组合可以用于指明一个错码的3种不同位置。 从而可以有纠错能力。 一般而言，若有 r 个监督关系式，则 r 个校正子可以指明一个错码的 (2r 1) 个不同位置。 当校正子可以指明的错码位置数目等于或大于码组长度n时，才能够纠正码组中任何一个位置上的错码，即要求1212rknr

16、r或021aaaSnn 汉明码的设计原理汉明码的设计原理 .例：要求设计一个能够纠正1个错码的分组码(n, k)，给定的码组中有4个信息位，即k = 4。S1 S2 S3错码位错码位置置S1 S2 S3错码位错码位置置001a0101a4010a1110a5100a2111a6011a3000无错码无错码2121rrnkr由或16542310(0)(0)(0)aaaSaaaa13562aaaaS03463aaaaS用a6 a5 a4 a3 a2 a1 a0表示这7个码元，S1 S2 S3表示校正子，则这3个校正子恰好能够指明23 1 = 7个错码的位置。若规定校正子和错码位置的关系如下表：这时

17、要求监督位数r 3。若取r = 3，则n = k + r = 7。则仅当在a6 a5 a4 a2位置上有错码时，校正子S1的值才等于1； 否则S1的值为零。这就意味着a6 a5 a4 a2四个码元构成偶数监督关系116542Saaaa111346035614562aaaaaaaaaaaa信息位信息位a6 a5 a4 a3监督位监督位a2 a1 a0信息位信息位a6 a5 a4 a3监督位监督位a2 a1 a00000000100011100010111001100001010110100100011110101100101001101100001010110111010100110011111

18、010001110001111111在编码时，信息位a6 a5 a4 a3的值决定于输入信号,它们是随机的.监督位a2 a1 a0是按监督关系确定的，应该保证上列3式中的校正子等于0，即有给定信息位后，为了计算监督位，上式可以改写为24561aaaaS13562aaaaS03463aaaaS265465136430aaaaaaaaaaaa =0 =0 =024561aaaaS13562aaaaS03463aaaaSS1 S2 S3错码位置错码位置001a0010a1100a2011a3101a4110a5111a6000无错码无错码在接收端解码时，对于每个接收码组，先按式计算出S1，S2和S3

19、，然后按照表判断错码的位置例：若接收码组为0000011，则按上三式计算得到：S1 = 0，S2 = 1，S3 = 1。这样，由上表可知，错码位置在a3.10 ed120 td1212rrrnk由于汉明码是(7, 4)码，其最小码距d0 = 3由式汉明码的码率：可知，此码能够检测，或或000034613562456aaaaaaaaaaaa010011010010101100010111012345601234560123456aaaaaaaaaaaaaaaaaaaaa可以改写为已经将“”简写成“+”（模2加）0001011001110101011101000123456aaaaaaa1 1、监

20、督矩阵、监督矩阵上式可以写成矩阵形式：HAT = 0T或AHT = 0将上式简写为101100111010101110100HA = a6 a5 a4 a3 a2 a1 a0 0 = 000称为监督矩阵rPIH001101101011011001110式中，P 为r k阶矩阵，Ir为 r r 阶单位方阵。典型监督矩阵H 矩阵的各行应该是线性无关的，否则将得不到 r 个线性无关的监督关系式。若一个矩阵能写成典型阵形式 P Ir ，则其各行一定是线性无关的。监督矩阵H确定码组中的信息位和监督位的关系。H 的行数就是监督关系式的数目，即监督位数 r 。H 的每行中“1”的位置表示相应的码元参与监督关

21、系。 H 可以分成两部分，例如3456012101111011110aaaaaaa346035614562aaaaaaaaaaaaQ34563456012011101110111aaaaaaaaaaa2、生成矩阵可以写为上式两端分别转置后，可以变成式中，Q为k r 阶矩阵，是是P的转置，即的转置，即 将将Q的左边加上一个的左边加上一个k阶单位阶单位方阵，称为生成矩阵方阵，称为生成矩阵0110001101001011001001111000QGkI IG34560123456aaaaaaaaaaaAG称为生成矩阵，因为可以用它产生整个码组A，即有 具有IkQ形式的生成矩阵称为典型生成矩阵典型生成

22、矩阵。 由典型生成矩阵得出的码组A中，信息位的位置不变，监督位附加于其后。这种形式的码组称为系统码系统码。 矩阵G的各行也必须是线性无关的。 如果已有k个线性无关的码组，则可以将其用来作为生成矩阵G，并由它生成其余码组。0110001101001011001001111000QGkI I 错误图样设：发送码组A是一个n列的行矩阵：接收码组是一个n列的行矩阵B： 令接收码组和发送码组之差为E就是错码的行矩阵 称为 式中， (i = 0, 1, , n-1)若ei = 0，表示该码元未错；若ei = 1，表示该码元为错码。 0121aaaaAnn0121bbbbBnnB A = E (模2)012

23、1eeeeEnniiiiiababe当当, 1, 0n3、校正子矩阵 B A = E 可以改写成 B = A + E上式表示发送码组A与错码矩阵E之和等于接收码组B。 例如， 若发送码组A = 1 0 0 0 1 1 1， 错码矩阵E = 0 0 0 0 1 0 0， 则 接收码组B = 1 0 0 0 0 1 1。 在接收端解码时，将接收码组B代入式AHT = 0中A的位置进行计算。若接收码组中无错码，则B = A。代入后，该式仍成立，即有BH T = 0只有当错码未超出检测能力时，上式才不成立。 假设，这时该式的右端等于S，即有BH T = S将B = A + E 代入上式，得到:S =

24、(A + E) H T = AH T + EH TS = (A + E) H T = AH T + EH T上式右端第一项等于0，所以 S = EH T 校正子矩阵当H 确定后，上式中S只与E 有关，而与A 无关。 这意味着，S 和错码E 之间有确定的线性变换关系。 若S 和E 有一一对应关系，则S 将能代表错码位置。 线性码的封闭性：若A1和A2是一种线性码中的两个码组，则(A1+A2)仍是其中一个码组。 证若A1和A2是两个码组，则有：A1HT = 0, A2HT = 0 将上两式相加，得出A1HT + A2HT = (A1 + A2 ) HT = 0 所以(A1 + A2)也是一个码组。

25、 由于线性码具有封闭性，所以两个码组(A1和A2)之间的距离（即对应位不同的数目）必定是另一个码组(A1 + A2)的重量（即“1”的数目）。因此，码的最小距离就是码的最小重量（除全“0”码组外）。11.5 循环码11.5.1 循环码的概念：循环性指任一码组循环一位后仍然是该编码中的一个码组 例：一种(7, 3)循环码的全部码组如下 表中第2码组向右移一位即得到第5码组；第5码组向右移一位即得到第7码组。 码组编码组编号号信息位信息位 监督位监督位 码组编码组编号号信息位信息位 监督位监督位A6a5a4a3a2a1a0a6a5a4A3a2a1a0100000005100101120010111

26、6101110030101110711001014011100181110010n一般情况n若(an-1 an-2 a0)是循环码的一个码组，则循环移位后的码组：012211)(axaxaxaxTnnnn11010011)(25623456xxxxxxxxxxT多项式表示法一个长度为n的码组(an-1 an-2 a0)可以表示成上式中x 的值没有任何意义，仅用它的幂代表码元的位置。例：码组1 1 0 0 1 0 1可以表示为n(an-2 an-3 a0 an-1)n(an-3 an-4 an-1 an-2)n n (a0 an-1 a2 a1)11.5.2 循环码的运算n 整数的按模运算在整数

27、运算中，有模n运算。例如，在模2运算中，1 + 1 = 2 0 (模2)，1 + 2 = 3 1 (模2)， 2 3 = 6 0 (模2) 等等。 一般说来，若一个整数m可以表示为式中，Q为整数，则在模n运算下，有m p (模n)所以,在模n运算下,一个整数m等于它被n除得的余数npnpQnm,)()()()(xRxQxNxF）（模)()()(xNxRxF）（模) 1(133xx）（模) 1(113224xxxxx码多项式的按模运算若任意一个多项式F(x)被一个n次多项式N(x)除，得到商式Q(x)和一个次数小于n的余式R(x)，即则在按模N(x)运算下，有这时，码多项式系数仍按模2运算。例1

28、：x3被(x3 + 1)除，得到余项1，即例2：x4 +x2 + 1X4 + xx2 +x +1x3 + 1x在模2运算中加法和减法一样。n 循环码的数学表示法 在循环码中，设T(x)是一个长度为n的码组，若则T (x)也是该编码中的一个码组。 证 设一循环码为 则有上式中的T (x) 正是码组T (x)向左循环移位 i 次的结果例： 一循环码为1100101，即若给定 i = 3，则 上式对应的码组为0101110，它正是T(x)向左移3位的结果。结论：一个长为n的循环码必定为按模(xn + 1)运算的一个余式。 ）（模) 1()()(nixxTxTx012211)(axaxaxaxTnnn

29、n)()(1102211011112211xTaxaxaxaxaxaxaxaxaxaxTxininininniniinininninni1)(256xxxxT）（模) 1()(723535893xxxxxxxxxxTx 循环码的生成 有了生成矩阵G，就可以由k个信息位得出整个码组：例：式中，生成矩阵G的每一行都是一个码组。 因此，若能找到 k 个已知的码组，就能构成矩阵G。如前所述，这k个已知码组必须是线性不相关的。 在循环码中，一个(n, k)码有2k个不同的码组。若用g(x)表示其中前(k-1)位皆为“0”的码组，则g(x)，x g(x)，x2 g(x)，xk-1 g(x)都是码组，而且这

30、k个码组是线性无关的。因此它们可以用来构成此循环码的生成矩阵G。G34560123456aaaaaaaaaaaA0110001101001011001001111000QGkI I 在循环码中除全“0”码组外，再没有连续k位均为“0”的码组。否则，在经过若干次循环移位后将得到k位信息位全为“0”，但监督位不全为“0”的一个码组。这在线性码中显然是不可能的。 因此，g(x)必须是一个常数项不为“0”的(n - k)次多项式，而且这个g(x)还是这种(n, k)码中次数为(n k)的唯一一个多项式。因为如果有两个，则由码的封闭性，把这两个相加也应该是一个码组，且此码组多项式的次数将小于(n k)，

31、即连续“0”的个数多于(k 1)。显然，这是与前面的结论矛盾的。 我们称这唯一的(n k)次多项式g(x)为码的生成多项式。一旦确定了g(x)，则整个(n, k)循环码就被确定了。)()()()()(21xgxxgxgxxgxxkkG码组编码组编号号信息位信息位监督位监督位码组编码组编号号信息位信息位监督位监督位A6a5a4a3a2a1a0a6a5a4A3a2a1a01000000051001011200101116101110030101110711001014011100181110010因此，循环码的生成矩阵G可以写成例：上表中的编码为(7, 3)循环码，n = 7, k = 3, n

32、k = 4，其中唯一的一个(n k) = 4次码多项式代表的码组是第二码组0010111，与它对应的码多项式，即生成多项式，为g(x) = x4 + x2 + x + 1。g(x) = x4 + x2 + x + 1 即 “1 0 1 1 1”将此g(x)代入上矩阵，得到 或上式不符合G = IkQ形式，所以它不是典型生成矩阵。但它经过线性变换后，不难化成典型阵。此循环码组的多项式表示式T(x)： 上式表明，所有码多项式T(x)都能够被g(x)整除，而且任意一个次数不大于(k 1)的多项式乘g(x)都是码多项式。 )()()()(2xgxxgxgxxG001011101011101011100

33、)(xG)()()()()()()()()()(452645262456456xgaxaxaxgaxxgaxgxaxgxxgxgxaaaxaaaxTG 寻求码生成多项式 因为任意一个循环码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。因此，上式可以写成）（模) 1()()(nixxTxTx1)

34、()(1)(nnkxxTxQxxTx)() 1()(xTxxTxnk将 T(x) = h(x)g(x) 和 T (x) = g(x) 代入化简后，得到上式表明，生成多项式g(x)应该是(xn + 1)的一个因子。例：(x7 + 1)可以分解为为了求出(7, 3)循环码的生成多项式 g(x)，需要从上式中找到一个(n k) = 4次的因子。这样的因子有两个，即以上两式都可以作为生成多项式。 选用的生成多项式不同，产生出的循环码码组也不同。 )() 1()(xTxxTxnk)()(1xhxxgxkn) 1)(1)(1(13237xxxxxx1) 1)(1(2423xxxxxx1) 1)(1(234

35、3xxxxxx11.6.3 循环码的编码方法用xn-k乘m(x)。这一运算实际上是在信息码后附加上(n k)个“0”。例如，信息码为110，它写成多项式为m(x) = x2 + x。当n k = 7 3 =4时，xn-k m(x) = x4 (x2 +x) = x6 +x5，它表示码组1100000。用g(x)除xn-k m(x)，得到商Q(x)和余式r(x)，即有例：若选定g(x) = x4 + x2 + x + 1，则有 上式是用码多项式表示的运算。它和下式等效：编出的码组T(x)为：T(x) = xn-k m(x) +r(x)在上例中，T(x) = 1100000 + 101 = 110

36、0101 )()()()()(xgxrxQxgxmxkn11) 1(1)()(24222456xxxxxxxxxxxxgxmxkn10111101111101111100000 11.6.4 循环码的解码方法 在检错时：当接收码组没有错码时，接收码组R(x)必定能被g(x)整除，即下式中余项r(x)应为零；否则，有误码。当接收码组中的错码数量过多，超出了编码的检错能力时，有错码的接收码组也可能被g(x)整除。这时，错码就不能检出了。 在纠错时：用生成多项式g(x)除接收码组R(x)，得出余式r(x)。按照余式r(x)，用查表的方法或计算方法得出错误图样E(x)。从R(x)中减去E(x)，便得到

37、已经纠正错码的原发送码组T(x)。)(/)()()(/)(xgxrxQxgxR硬件实现固定除式的多项式除法abcd信息码元输入移存器反馈输出mabcddf0000001111011110011101010100010100000101100001000000011校验码元11.5.3 缩短循环码通过缩短循环码，可以满足系统设计中，码长、信息位和纠错能力的不同要求。对于(n,k)循环码，使前i(0ik)个信息位为零可得到有2k-i个码组的集合，然后从这些码组中删去这i个零信息位，得到一种新的(r-i，k-i)的线性码，称为缩短循环码。缩短循环码与产生该码的原循环码至少具有相同的纠错能力。缩短循环

38、码的编码和译码可用原循环码使用的电路完成。n例：若要求构造一个能够纠正一位错误的(13，9)码，则可以由(15，11)汉明码选出前面两个信息位均为零的码组。然后在发送时，这两个零信息不发送，即发送的是(13，9)缩短循环码。n因校验位数相同，(13，9)码与(15，11)循环码具有相同的纠错能力。11.5.4 BCH码BCH码是一类纠正多个随机错误的特殊的循环码。特点是可以根据给定的纠错能力，找出生成多项式。 BCH码分两类：本原BCH码和非本原BCH码。本原BCH码的码长为n=2m-1(M 3)，生成多项式g(x)中含有最高次数为m次的本原多项式；非本原BCH码的码长n是2m-1的一个因子，

39、它的生成多项式中不含有最高次数为m的本原多项式。n对于正整数m(M3)和t(t 2)必存在有下列参数的二进制BCH码：码长n=2m-1，监督位数rmt，能纠正所有的小于或等于t个随机错误的BCH码。nBCH码生成多项式 g(x)=LCMm1(x)，m2(x)， m2t-1(x)式中t可纠正的错误个数；mi(x)最小多项式;LCM( )指取括号内所有多项式的最小公倍式.n查表法得到生成多项式，用八进制数表示。n例如当n=7,k=4,t=1 g=(13)8意指 g=(001011)2 g(x)=x3+x+1 n=3 kt g(x)117 n=7kt g(x)41131377表98（部分）nR-S码

40、是一类具有很强纠措能力的多进制BCH码。n伽罗华域(即有限域) ：对于有限个符号，若符号的数目是一素数的幂，可以定义有加法和乘法，则构成符号域为有限域；若它是2m个符号的域则称之为伽罗华域GF(2m) .n例如，两个符号0、1，定义有模2加法和模2乘法，即 0+0=0，0+1=1，1+1=0； 00=0，01=1，111，则称之为二元域，也是伽罗华域。11.5.5 里德-索罗门码（R-S码）n从两个符号0和1及一个m次多项式p(x)开始，并引入一个新符号 ，设p()=0。若适当地选择p(x)就可得到的各次幂，一直到2m-2次幂，都不相同，并且m-1 =1。这样一来， 构成GF(2m)的所有元素

41、。域中每个非零元素还可以用上面元素的和来表示。例如，m=4和p(x)=x4+x+1，则2242, 1 , 0mn得到GF(24)的所有元素，详见表9-10。01 2 3 4= +1 5= (+1)=2+ 6=(2+)= 3+2 7=(3+ 2)= 3+2 = 3+1 8=(3+1)= 4+2 +1=2 +1 9=(2 +1)= 3+ 10=(3+)= 2 +1 11=(2 +1)= 3+ 2 + 12= (3+ 2 +)= 3+ 2 +1 13= (3+ 2 +1)= 3+ 2+1R-S码是q进制BCH码的子类。具有如下的参数：码长：n=q-1符号监督位数： r=2t符号纠错位数： t 符号生

42、成多项式：每个码元都是q进制的，通常令q=2m，则每个q进制码元都可以表示为m位二进制码元，于是码长mn位，监督位数mr位，信息位数： mn- mr位。)()()(22txxxxgR-S码应用：n由于采用多进制，所以对于多进制调制是自然和方便的编码手段;n因为RS码能够纠正t个q位二进制码，即对以纠t个连续的突发性二进制错误,所以适合衰落信道应用;nRS码可应用在计算机存储系统中以克服系统的差错。n卷积编码则把k比特信息段编成n比特的码组，但所编的n长码组不仅同当前的k比特信息段有关联，而且还同前面的(N-1)个信息段有关联，人们常称这N为该卷积码的约束长度。n一般来说，对于卷积码，k和n是较

43、小的整数, 常把卷积码记作(n,k,N)卷积码，它的编码效率为R=k/n。 9. 6 卷积码1161 卷积码的图形描述n(3,1,3)卷积码编码器n编码器的输入和输出树状图状态图状态图网格图网格图特点： 有2N-1种状态；对于k个输入信息比特，相应出现有2k条支路；码树中的上支路用实线表示，下支路用虚线表示：支路上标注的码元为输出比特；从第N个节点开始，图形开始重复，且完全相同。n 例9-1 (3,1,3)编码器，起始状态为a，输入序列为1101011，求输出序列和相应状态变化路径。n解：由卷积码的网格图，可找出编码时网格图中的编码路径如图913所示，由此即可得到输出序列。为11.6.2 卷积

44、码的解析描述1生成矩阵卷积码是一种线性码。一个线性码完全由一个监督矩阵H或生成矩阵G所确定。生成矩阵G 输入第一个信息比特m1时，y1,1=m1； y21=m1 ；y31=m1。 输入第二个信息比特m2时，y1,2=m2； y22=m2 ；y32= m1 + m2。输入第j个信息比特mj时， y1j=mj； y2j=mj +mj-2 ； y3j= mj +mj-1+mj-2上式可写成矩阵形式 mj +mj-1+mj-2 A = y1j y2j y3jn其中生成矩阵为n在过渡时刻 m1 0 0 T1 = y11 y21 y31 m1 m2 0 T2 = y12 y22 y32其中11110011

45、0A0000001111Tn输出矩阵与输入矩阵的关系有 Y=MG0001111002TAAAATTG00000021 1 1 1 0 0 1 0 1 1 1 1 1 0 0 1 0 1 1 1 1 1 0 0 1 0 1 1 1 1 1 0 0 1 0 1 1 1 1 1 0 0 1 0 1 1 1 1 1 0 0 1 上面矩阵空白处均为0元素。该生成矩阵是半无限矩阵。2 . 多项式描述例如：输入序列1101110 可表示为 m(x)=1+x+x3+x4+x5+连接关系表示为 g1(x)=1 g2(x)= 1+x2 g3(x)= 1+x+x2编码输出为 y1(x)=m(x)g1(x)= 1+x

46、+x3+x4+x5+ y2(x)=m(x)g2(x)=(1+x+x3+x4+x5+)(1+x2)=1+x+x3+x4+x5+ +x2+x3+x5+x7+ = 1+x +x2 +x4 +x7 y3(x)= (1+x+x3+x4+x5+)(1+x+x2)= 1+x+x3+x4+x5+ x+x2+x4+x5+x6+ x2+x3+x5+x6+ x7+ =1+ x5 + x7+ 对应的序列为 y1=1 1 0 1 1 1 0 0； y2=1 1 1 0 1 0 0 1 y3=1 0 0 0 0 1 0 1 n总的输出序列为 Y=y11,y21,y31,y12,y22,y32, = 1 1 1, 1 1

47、0, 0 1 0, 1 0 0, 1 1 0, 1 0 1, 0 0 0, 0 1 1, 结果与网格图是一样的。 卷积码编码器的一般结构11.6.3 卷积码译码卷积码的译码方法有两类：一类是大数逻辑译码，又称门限译码：另一类是概率译码。概率译码又分为维特比译码和序列译码两种。门限译码方法是以分组码理论为基础的其译码设备简单，速度快，但其误码性能要比概率译码法差。下面只介绍维特比译码。11.6.3维特比译码维特比译码算法，简称VB算法。维特比(viterbi)译码和序列译码都属于概率译码。当卷积码的约束长度不太大时，与序列译码相比，维持比译码器比较简单，计算速度更快。VB算法在前向纠错系统中用得

48、较多，在卫星通信中已被采用作为标准技术。n概率译码的基本想法是：把已接收序列与所有可能的发送序列做比较，选择其中码距最小的一个序列作为发送序列。n如果发送L组信息比特，对于(n,k)卷积码来说，可能发送的序列有2kL个，计算机或译码器需存储这些序列并进行比较，以找到码距最小的那个序列。当传信率和信息组数人较大时，使得泽码器难以实现。VB算法则对上述概率译码(又称最大似然译码)做了简化，使其成为一种实用的译码算法。它并不是在网格图上一次比较所有可能的2kL条路径(序列)，而是接收一段，计算和比较一段，选择一段有最大似然可能的码段。从而达到整个码序列是一个有最大似然值的序列。以下以（2,1,3)卷

49、积码为例说明：设输入信息数目L=5，所以画有L+N=8个时间单位。编码器从a状态开始工作。该网格图的每一条路径都对应着不同的输入信息序列。由于所有的可能输入信息序列共有2kL=32个.n设输入编码器的信息序列为(11011000)，则由编码器输出的序列 y(1101000010,11100)，编码器的状态转移路线为abdcbdca。n若收到的序列为R=0101011001011100，对照网格图来说明维特比译码的方法。n前3步输入R=010101；根据不同输入信息，编码器的输出序列以及它们与接收序列的距离见下表R=010101信息编码路径距离000000000 aaaa3001000011 a

50、aab3010001110 aabc4011001101 aabd2100111011 abca4101111000 abcb4110110101 abdc1111110110 abdd3前3步对应网格图幸存路径，如下页对应4条幸存路径的序列分别为： a-a-a-a000000 a-a-a-b000011 a-b-d-c110101 a-a-b-d001101.到第5步的幸存路径和对应的序列分别为： a-a-b-d-d-c001101 1001. a-b-d-c-a-a110101 1100 a-b-d-c-a-b110101 1111 a-b-d-c-b-d110101 1101到第8步的幸存路径和对应的序列分别为： a-b-d-c-b-d-c-a-a 11 01 01, 00 01 01 11 00对应信息1 1 0 1 1 0 0 0与发送信息相同。对比接收0*1 01 01 1*0 01 01 11 00纠正了两个错误。总结与复习第一章第一章 绪