第9章 信道的纠错编码(ok)

1、9.1 概述概述 9.2 纠错编码的基本原理纠错编码的基本原理 9.3 纠错编码的性能纠错编码的性能 3 9.4 简单的实用编码简单的实用编码 4 5 9.5 线性分组码线性分组码 第第9 9章章 信道的纠错编码信道的纠错编码 9.6 循环码循环码 9.1 9.1 概述概述 1 1、概述、概述 n 信道分类：从差错控制角度看信道分类：从差错控制角度看 o 随机信道：错码的出现是随机的。随机信道：错码的出现是随机的。 o 突发信道：错码是成串集中出现的。突发信道：错码是成串集中出现的。 o 混合信道：既存在随机错码又存在突发错码。混合信道：既存在随机错码又存在突发错码。 n 差错控制技术的种类差

2、错控制技术的种类 o 检错重发检错重发 o 前向纠错前向纠错 o 混合纠错混合纠错 差错控制编码差错控制编码：常称为纠错编码，不同的编码方法，有：常称为纠错编码，不同的编码方法，有 不同的检错或纠错能力。不同的检错或纠错能力。 9.1 9.1 概述概述 o 监督码元监督码元：信息码元序列中增加的一些差错控制码元，：信息码元序列中增加的一些差错控制码元， 它们称为监督码元。它们称为监督码元。 o 多余度多余度：就是指增加的监督码元多少。例如，若编码序：就是指增加的监督码元多少。例如，若编码序 列中平均每两个信息码元就添加一个监督码元，则这种列中平均每两个信息码元就添加一个监督码元，则这种 编码的

3、多余度为编码的多余度为1/31/3。 o 编码效率编码效率( (简称码率简称码率) ) ：设编码序列中信息码元数量为：设编码序列中信息码元数量为k k， 总码元数量为总码元数量为n n，则比值，则比值k/n k/n 就是码率。就是码率。 o 冗余度冗余度：监督码元数：监督码元数( (n n- -k k) ) 和信息码元数和信息码元数 k k 之比。之比。 o 理论上，差错控制以降低信息传输速率为代价换取提高理论上，差错控制以降低信息传输速率为代价换取提高 传输可靠性。传输可靠性。 9.1 9.1 概述概述 2 2 差错控制技术差错控制技术 图图 三种差错控制方式示意图三种差错控制方式示意图 发

4、端 纠错码 收端 前向纠错 FEC 发端 检错码 收端 检错重发 ARQ 判决信号 发端 检错和纠错码 收端 混合纠错 HEC 判决信号 1. 1. 检错重发方式检错重发方式 检 错 重 发 又 称 自 动 请 求 重 传 方 式 ， 记 作检 错 重 发 又 称 自 动 请 求 重 传 方 式 ， 记 作 ARQ(Automatic Repeat Request)ARQ(Automatic Repeat Request)。 由发端送出能够发现错由发端送出能够发现错 误的码，由收端判决传输中无错误产生，如果发现错误，则误的码，由收端判决传输中无错误产生，如果发现错误，则 通过反向信道把这一判决

5、结果反馈给发端，然后，发端把收通过反向信道把这一判决结果反馈给发端，然后，发端把收 端认为错误的信息再次重发，从而达到正确传输的目的。其端认为错误的信息再次重发，从而达到正确传输的目的。其 特点特点是需要反馈信道，译码设备简单，对突发错误和信道干是需要反馈信道，译码设备简单，对突发错误和信道干 扰较严重时有效，扰较严重时有效， 但实时性差，主要在计算机数据通信中但实时性差，主要在计算机数据通信中 得到应用。得到应用。 11.1 11.1 概述概述 2. 2. 前向纠错方式前向纠错方式 前向纠错方式记作前向纠错方式记作FEC(Forword ErrorFEC(Forword Error Corr

6、ection)Correction)。发端发送能够纠正错误的码，收端。发端发送能够纠正错误的码，收端 收到信码后自动地纠正传输中的错误。收到信码后自动地纠正传输中的错误。 特点特点: :是单向传输，实时性好，但译码设备较复杂。是单向传输，实时性好，但译码设备较复杂。 11.1 11.1 概述概述 3. 3. 混合纠错方式混合纠错方式 混合纠错方式记作混合纠错方式记作HEC(Hybrid ErrorHEC(Hybrid ErrorCorrection)Correction) 是是FECFEC和和ARQARQ方式的结合。发端发送具有自动纠错同时又具有方式的结合。发端发送具有自动纠错同时又具有 检错

7、能力的码。收端收到码后，检查差错情况，如果错误在检错能力的码。收端收到码后，检查差错情况，如果错误在 码的纠错能力范围以内，则自动纠错，如果超过了码的纠错码的纠错能力范围以内，则自动纠错，如果超过了码的纠错 能力，能力， 但能检测出来，则经过反馈信道请求发端重发。这种但能检测出来，则经过反馈信道请求发端重发。这种 方式具有自动纠错和检错重发的优点，可达到较低的误码率，方式具有自动纠错和检错重发的优点，可达到较低的误码率， 因此，因此， 近年来得到广泛应用。近年来得到广泛应用。 11.1 11.1 概述概述 9.2 9.2 纠错编码的基本原理纠错编码的基本原理 1 1、分组码基本原理：（举例说明

8、）、分组码基本原理：（举例说明） n 设有一种由设有一种由3 3位二进制数字构成的码组，它共有位二进制数字构成的码组，它共有8 8种不种不 同的可能组合。若将其全部用来表示天气，则可以表同的可能组合。若将其全部用来表示天气，则可以表 示示8 8种不同天气，种不同天气， n 例如：例如：“000000”（晴），（晴），“001001”（云），（云）， “010010”（阴），（阴）， “011011”（雨），（雨）， “100100”（雪），（雪），“101101”（霜），（霜）， “110110”（雾），（雾），“111111”（雹）。（雹）。 n 其中任一码组在传输中若发生一个或多个错码，则

9、将其中任一码组在传输中若发生一个或多个错码，则将 变成另一个信息码组。这时，接收端将无法发现错误。变成另一个信息码组。这时，接收端将无法发现错误。 9.2 9.2 纠错编码的基本原理纠错编码的基本原理 o 若在上述若在上述8 8种码组中只准许使用种码组中只准许使用4 4种来传送天气，例如：种来传送天气，例如： “000000”晴，晴， “011011”云云 ， “101101”阴阴 ， “110110”雨雨 n 这时，虽然只能传送这时，虽然只能传送4 4种不同的天气，但是接收端却种不同的天气，但是接收端却 有可能发现码组中的一个错码。有可能发现码组中的一个错码。 n 例如，若例如，若“0000

10、00”（晴）中错了一位，则接收码组将（晴）中错了一位，则接收码组将 变成变成“100100”或或“010010”或或“001001”。这。这3 3种码组都是不准种码组都是不准 使用的，称为使用的，称为禁用码组禁用码组。 9.2 9.2 纠错编码的基本原理纠错编码的基本原理 接收端在收到禁用码组时，就认为发现了错码。当发生接收端在收到禁用码组时，就认为发现了错码。当发生 3 3个错码时，个错码时，“000000”变成了变成了“111111”，它也是禁用码组，它也是禁用码组， 故这种编码也能检测故这种编码也能检测3 3个错码。个错码。 n 但是这种码不能发现一个码组中的两个错码，因为但是这种码不能

11、发现一个码组中的两个错码，因为 发生两个错码后产生的是发生两个错码后产生的是许用码组许用码组。 o 上面这种编码只能检测错码，不能纠正错码上面这种编码只能检测错码，不能纠正错码。例如，当。例如，当 接收码组为禁用码组接收码组为禁用码组“100100”时，接收端将无法判断是哪时，接收端将无法判断是哪 一位码发生了错误，因为晴、阴、雨三者错了一位都可一位码发生了错误，因为晴、阴、雨三者错了一位都可 以变成以变成“100100”。 9.2 9.2 纠错编码的基本原理纠错编码的基本原理 o 检错和纠错检错和纠错 n 要能够纠正错误，还要增加多余度要能够纠正错误，还要增加多余度。例如，若规定许用。例如，

12、若规定许用 码组只有两个：码组只有两个：“000000”（晴），（晴），“111111”（雨），其他都（雨），其他都 是禁用码组，则能够检测两个以下错码，或能够纠正一是禁用码组，则能够检测两个以下错码，或能够纠正一 个错码。个错码。 n 例如，当收到禁用码组例如，当收到禁用码组“100100”时，若当作仅有一个错码，时，若当作仅有一个错码， 则可以判断此错码发生在则可以判断此错码发生在“1 1”位，从而纠正为位，从而纠正为“000000” （晴）。因为（晴）。因为“111111”（雨）发生任何一位错码时都不会（雨）发生任何一位错码时都不会 变成变成“100100”这种形式。这种形式。 n 但是

13、，这时若假定错码数不超过两个，则存在两种可能但是，这时若假定错码数不超过两个，则存在两种可能 性：性：“000000”错一位和错一位和“111111”错两位都可能变成错两位都可能变成“100100”， 因而只能检测出存在错码而无法纠正错码。因而只能检测出存在错码而无法纠正错码。 9.2 9.2 纠错编码的基本原理纠错编码的基本原理 2 2、分组码的结构、分组码的结构 n 将信息码分组，为每组信息码附加若干监督码的编码称将信息码分组，为每组信息码附加若干监督码的编码称 为为分组码分组码 。 n 在分组码中，监督码元仅监督本码组中的信息码元。信在分组码中，监督码元仅监督本码组中的信息码元。信 息位

14、和监督位的关系：举例如下（偶校验）息位和监督位的关系：举例如下（偶校验） 信息位信息位监督位监督位 晴晴000 云云011 阴阴101 雨雨110 9.2 9.2 纠错编码的基本原理纠错编码的基本原理 n 分组码的一般结构分组码的一般结构 o 分组码的符号：分组码的符号：( (n n, , k k) ) nN N 码组的总位数，又称为码组的长度（码长），码组的总位数，又称为码组的长度（码长）， nk k 码组中信息码元的数目，码组中信息码元的数目， nn n k k r r 码组中的监督码元数目，或称监督位码组中的监督码元数目，或称监督位 数目。数目。 9.2 9.2 纠错编码的基本原理纠错编

15、码的基本原理 3 3、分组码的码重和码距、分组码的码重和码距 n 码重：码重：把码组中把码组中“1 1”的个数目称为码组的重量，简称码的个数目称为码组的重量，简称码 重。重。 n 码距：码距：把两个码组中对应位上数字不同的位数称为码组把两个码组中对应位上数字不同的位数称为码组 的距离，简称码距。码距又称汉明距离。的距离，简称码距。码距又称汉明距离。 n 例如，例如，“000000”晴，晴，“011011”云，云，“101101”阴，阴，“110110” 雨，雨，4 4个码组之间，任意两个的距离均为个码组之间，任意两个的距离均为2 2。 n 最小码距：最小码距：把某种编码中各个码组之间距离的最小

16、值称把某种编码中各个码组之间距离的最小值称 为最小码距为最小码距( (d d0 0) )。例如，上面的编码的最小码距。例如，上面的编码的最小码距d d0 0 = 2 = 2。 码距和检纠错能力的关系码距和检纠错能力的关系 (1)(1)在一个码组内要想检出在一个码组内要想检出e e位误码，要求最小码位误码，要求最小码 距为距为 d dmin min e e+1 +1 (2) (2)在一个码组内要想纠正在一个码组内要想纠正t t位误码，要求最小码位误码，要求最小码 距为距为 d dmin min2 2t t+1 +1 (3) (3)在一个码组内要想纠正在一个码组内要想纠正t t位误码，同时检测出位

17、误码，同时检测出e e 位误码（位误码（e ett）, ,要求最小码距为要求最小码距为 d dmin min t t+ +e e+1+1 9.2 9.2 纠错编码的基本原理纠错编码的基本原理 9.3 9.3 纠错编码的性能纠错编码的性能 o 系统带宽和信噪比的矛盾：系统带宽和信噪比的矛盾： n 由上节所述的纠错编码原理可知，为了减少接收错由上节所述的纠错编码原理可知，为了减少接收错 误码元数量，需要在发送信息码元序列中加入监督误码元数量，需要在发送信息码元序列中加入监督 码元。这样作的结果使发送序列增长，冗余度增大。码元。这样作的结果使发送序列增长，冗余度增大。 若仍须保持发送信息码元速率不变

18、，则传输速率必若仍须保持发送信息码元速率不变，则传输速率必 须增大，因而须增大，因而增大了系统带宽。系统带宽的增大将增大了系统带宽。系统带宽的增大将 引起系统中噪声功率增大，使信噪比下降。引起系统中噪声功率增大，使信噪比下降。信噪比信噪比 的下降反而又使系统接收码元序列中的错码增多。的下降反而又使系统接收码元序列中的错码增多。 一般说来，采用纠错编码后，一般说来，采用纠错编码后，误码率总是能够得到误码率总是能够得到 很大改善的。很大改善的。改善的程度和所用的编码有关。改善的程度和所用的编码有关。 9.3 9.3 纠错编码的性能纠错编码的性能 o 编码性能举例编码性能举例 o 未采用纠错编码时，

19、未采用纠错编码时， 若接收信噪比等于若接收信噪比等于 7dB7dB，编码前误码率，编码前误码率 约为约为8 8 1010-4 -4，图中 ，图中A A 点，在采用纠错编码点，在采用纠错编码 后，误码率降至约后，误码率降至约4 4 1010-5 -5，图中 ，图中B B点。这样，点。这样， 不增大发送功率就能不增大发送功率就能 降低误码率约一个半降低误码率约一个半 数量级。数量级。 10-6 10-5 10-4 10-3 10-2 10-1 编码后 Pe C D E A B 信噪比 (dB) 9.3 9.3 纠错编码的性能纠错编码的性能 n 由图还可以看出，若保持由图还可以看出，若保持 n 误码

20、率在误码率在1010-5 -5，图中 ，图中C C点，点， n 未采用编码时，约需要信噪未采用编码时，约需要信噪 n 比比E Eb b/n/n0 0 =10.5dB =10.5dB。在。在 采用这种编码时，约需要采用这种编码时，约需要 信噪比信噪比7.5 dB7.5 dB，图中，图中D D点。点。 可以节省功率可以节省功率2 dB2 dB。通常。通常 称这称这2dB2dB为为编码增益编码增益。 n 上面两种情况付出的代上面两种情况付出的代 价是带宽增大。价是带宽增大。 10-6 10-5 10-4 10-3 10-2 10-1 编码后 Pe C D E A B 信噪比 (dB) 9.3 9.3

21、 纠错编码的性能纠错编码的性能 n 传输速率和传输速率和E Eb b/n/n0 0的关系的关系 对于给定的传输系统对于给定的传输系统 式中，式中，R RB B为码元速率。为码元速率。 若希望提高传输速率，若希望提高传输速率， 由上式看出势必使信由上式看出势必使信 噪比下降，误码率增噪比下降，误码率增 大。假设系统原来工作大。假设系统原来工作 在图中在图中C C点，提高速率后点，提高速率后 由由C C点升到点升到E E点。但加用点。但加用 纠错编码后，仍可将误码纠错编码后，仍可将误码 率降到率降到D D点。这时付出的点。这时付出的 代价仍是带宽增大。代价仍是带宽增大。 B sssb Rn P T

22、n P n TP n E 0000 )/ 1 ( 10-6 10-5 10-4 10-3 10-2 10-1 编码后 Pe C D E A B 信噪比 (dB) 9.4 9.4 简单的实用编码简单的实用编码 o 1 1、 奇偶监督码奇偶监督码 奇偶监督码分为奇数监督码和偶数监督码两种，两者的奇偶监督码分为奇数监督码和偶数监督码两种，两者的 原理相同。在偶数监督码中，无论信息位多少，监督位原理相同。在偶数监督码中，无论信息位多少，监督位 只有只有1 1位，它使码组中位，它使码组中“1 1”的数目为偶数，即满足下式条的数目为偶数，即满足下式条 件：件： 式中式中a a0 0为监督位，其他位为信息位

23、。为监督位，其他位为信息位。 这种编码能够检测奇数个错码。在接收端，按照上式求这种编码能够检测奇数个错码。在接收端，按照上式求 “模模2 2和和”，若计算结果为，若计算结果为“1 1”就说明存在错码，结果为就说明存在错码，结果为 “0 0”就认为无错码。就认为无错码。 奇数监督码与偶数监督码相似，只不过其码组中奇数监督码与偶数监督码相似，只不过其码组中“1 1”的的 数目为奇数：数目为奇数： 0 021 aaa nn 1 021 aaa nn 9.4 9.4 简单的实用编码简单的实用编码 o 2 2、二维奇偶监督码（方阵码）、二维奇偶监督码（方阵码） n 二维奇偶监督码的构成二维奇偶监督码的构

24、成 它是先把上述奇偶监督码的若干码组排成矩阵，它是先把上述奇偶监督码的若干码组排成矩阵， 每一码组写成一行，然后再按列的方向增加第二每一码组写成一行，然后再按列的方向增加第二 维监督位，如下图所示维监督位，如下图所示 0121 0121 2 0 2 1 2 2 2 1 1 0 1 1 1 2 1 1 cccc aaaa aaaa aaaa nn mmm n m n nn nn 9.4 9.4 简单的实用编码简单的实用编码 n 图中图中a a0 01 1 a a0 02 2 a a0 0m m为为m m行奇偶监督码中的行奇偶监督码中的m m个监个监 督位。督位。 c cn n-1 -1 c cn

25、 n-2-2 c c1 1 c c0 0为按列进行第二次编码所增加为按列进行第二次编码所增加 的监督位，它们构成了一监督位行。的监督位，它们构成了一监督位行。 o 二维奇偶监督码的性能二维奇偶监督码的性能 n 这种编码有可能检测偶数个错码。因为每行的这种编码有可能检测偶数个错码。因为每行的 监督位虽然不能用于检测本行中的偶数个错码，监督位虽然不能用于检测本行中的偶数个错码， 但按列的方向有可能由但按列的方向有可能由c cn n-1 -1 c cn n-2-2 c c1 1 c c0 0等监督等监督 位检测出来。有一些偶数错码不可能检测出来。位检测出来。有一些偶数错码不可能检测出来。 9.4 9

26、.4 简单的实用编码简单的实用编码 o 例如，构成矩形的例如，构成矩形的4 4个错码，如图中个错码，如图中 错了，就检测不出。错了，就检测不出。 n 这种二维奇偶监督码适于检测突发错码。因为突发这种二维奇偶监督码适于检测突发错码。因为突发 错码常常成串出现，随后有较长一段无错区间。错码常常成串出现，随后有较长一段无错区间。 n 由于方阵码只对构成矩形四角的错码无法检测，故由于方阵码只对构成矩形四角的错码无法检测，故 其检错能力较强。其检错能力较强。 n 二维奇偶监督码不仅可用来检错，还可以用来纠正二维奇偶监督码不仅可用来检错，还可以用来纠正 一些错码。一些错码。 例如，仅在一行中有奇数个错码时

27、。例如，仅在一行中有奇数个错码时。 mm nn aaaa 12 2 1 2 2 9.4 9.4 简单的实用编码简单的实用编码 3、恒比码恒比码 n 在恒比码中，每个码组均含有相同数目的在恒比码中，每个码组均含有相同数目的“1 1” （和（和“0 0”）。由于）。由于“1 1”的数目与的数目与“0 0”的数目之比的数目之比 保持恒定，故得此名。保持恒定，故得此名。 n 这种码在检测时，只要计算接收码组中这种码在检测时，只要计算接收码组中“1 1”的数的数 目是否对，就知道有无错码。目是否对，就知道有无错码。 n 恒比码的主要优点是简单和适于用来传输电传机恒比码的主要优点是简单和适于用来传输电传机

28、 或其他键盘设备产生的字母和符号。对于信源来或其他键盘设备产生的字母和符号。对于信源来 的二进制随机数字序列，这种码就不适合使用了。的二进制随机数字序列，这种码就不适合使用了。 11.4 11.4 简单的实用编码简单的实用编码 4 4、正反码、正反码 o 正反码的编码：正反码的编码： n 它是一种简单的能够纠正错码的编码。其中的监督位数它是一种简单的能够纠正错码的编码。其中的监督位数 目与信息位数目相同，监督码元与信息码元相同或者相目与信息位数目相同，监督码元与信息码元相同或者相 反则由信息码中反则由信息码中“1 1”的个数而定。的个数而定。 n 例如，若码长例如，若码长n n = 10 =

29、10，其中信息位，其中信息位 k k = 5 = 5，监督位，监督位 r r = = 5 5。其编码规则为：。其编码规则为： o 当信息位中有奇数个当信息位中有奇数个“1 1”时，监督位是信息位的简单时，监督位是信息位的简单 重复；重复； o 当信息位有偶数个当信息位有偶数个“1 1”时，监督位是信息位的反码。时，监督位是信息位的反码。 9.5 9.5 线性分组码线性分组码 o 一、基本概念一、基本概念 n 代数码代数码：建立在代数学基础上的编码。：建立在代数学基础上的编码。 n 线性码线性码：按照一组线性方程构成的代数码。在：按照一组线性方程构成的代数码。在 线性码中信息位和监督位是由一些线

30、性代数方线性码中信息位和监督位是由一些线性代数方 程联系着的。程联系着的。 n 线性分组码线性分组码：按照一组线性方程构成的分组码：按照一组线性方程构成的分组码 。 本节将以汉明码为例引入线性分组码的一般原理。本节将以汉明码为例引入线性分组码的一般原理。 9.5 9.5 线性分组码线性分组码 汉明码汉明码 能够纠正能够纠正1 1位错码且编码效率较高的一种线性分组码位错码且编码效率较高的一种线性分组码 1 1、汉明码的构造原理、汉明码的构造原理。 o 在偶数监督码中，由于使用了一位监督位在偶数监督码中，由于使用了一位监督位a a0 0，它和信，它和信 息位息位a an-1 n-1 a a1 1一

31、起构成一个代数式： 一起构成一个代数式： 在接收端解码时，实际上就是在计算在接收端解码时，实际上就是在计算 若若S S = 0 = 0，就认为无错码；若，就认为无错码；若S S = 1 = 1，就认为有错，就认为有错 0 021 aaa nn 021 aaaS nn 9.5 9.5 线性分组码线性分组码 码。现将上式称为码。现将上式称为监督关系式监督关系式，S S称为称为校正子校正子。由于校正。由于校正 子子S S只有两种取值，故它只能代表有错和无错这两种信息，只有两种取值，故它只能代表有错和无错这两种信息， 而不能指出错码的位置。而不能指出错码的位置。 一般来说，若码长为一般来说，若码长为n

32、 n，信息位数为，信息位数为k k，则监督位数，则监督位数r r n nk k。如果希望用如果希望用r r个监督位构造出个监督位构造出r r个监督关系式来指个监督关系式来指 示示1 1位错码的位错码的n n种可能位置，则要求种可能位置，则要求 下面通过一个例子来说明如何具体构造这些监督关系式。下面通过一个例子来说明如何具体构造这些监督关系式。 1212rkn rr 或 9.5 9.5 线性分组码线性分组码 o 例：设分组码例：设分组码( (n n, , k k) )中中k k = 4 = 4，为了纠正，为了纠正1 1位错码，由上式位错码，由上式 可知，要求监督位数可知，要求监督位数 r r 3

33、 3。若取。若取 r r = 3 = 3，则，则n n = = k k + + r r = = 7 7。我们用。我们用a a6 6 a a5 5 a a0 0表示这表示这7 7个码元，用个码元，用S S1 1、S S2 2和和S S3 3表示表示3 3个个 监督关系式中的校正子，则监督关系式中的校正子，则S S1 1、S S2 2和和S S3 3的值与错码位置的对的值与错码位置的对 应关系可以规定如下表所列（表应关系可以规定如下表所列（表1 1） S1 S2 S3错码位置错码位置S1 S2 S3错码位置错码位置 001a0101a4 010a1110a5 100a2111a6 011a3000

34、无错码无错码 9.5 9.5 线性分组码线性分组码 由表中规定可见，仅当一位错码的位置在由表中规定可见，仅当一位错码的位置在a a2 2 、a a4 4、 a a5 5或或a a6 6时，校正子时，校正子S S1 1为为1 1；否则；否则S S1 1为零。这就意味着为零。这就意味着 a a2 2 、a a4 4、a a5 5和和a a6 6四个码元构成偶数监督关系：四个码元构成偶数监督关系： 同理，同理， a a1 1、a a3 3、a a5 5和和a a6 6构成偶数监督关系：构成偶数监督关系： 以及以及a a0 0、a a3 3、a a4 4 和和a a6 6构成偶数监督关系构成偶数监督关

35、系 24561 aaaaS 13562 aaaaS 03463 aaaaS 9.5 9.5 线性分组码线性分组码 n 在发送端编码时，信息位在发送端编码时，信息位a a6 6、a a5 5、a a4 4和和a a3 3的值决定的值决定 于输入信号，因此它们是随机的。监督位于输入信号，因此它们是随机的。监督位a a2 2、a a1 1和和 a a0 0应根据信息位的取值按监督关系来确定，即监督应根据信息位的取值按监督关系来确定，即监督 位应使上位应使上3 3式中式中S S1 1、S S2 2和和S S3 3的值为的值为0 0（表示编成的码（表示编成的码 组中应无错码）：组中应无错码）： 上式经过

36、移项运算，解出监督位上式经过移项运算，解出监督位 0 0 0 0346 1356 2456 aaaa aaaa aaaa 3460 3561 4562 aaaa aaaa aaaa 9.5 9.5 线性分组码线性分组码 信息位信息位 a6 a5 a4 a3 监督位监督位 a2 a1 a0 信息位信息位 a6 a5 a4 a3 监督位监督位 a2 a1 a0 00000001000111 00010111001100 00101011010010 00111101011001 01001101100001 01011011101010 01100111110100 01110001111111

37、给定信息位后，给定信息位后， 可以直接按上可以直接按上 式算出监督位，式算出监督位， 结果见表结果见表2 2： 9.5 9.5 线性分组码线性分组码 n 接收端收到每个码组后，先计算出接收端收到每个码组后，先计算出S S1 1、S S2 2和和S S3 3，再查，再查 表判断错码情况。例如，若接收码组为表判断错码情况。例如，若接收码组为00000110000011， 按上述公式计算可得：按上述公式计算可得：S S1 1 = 0 = 0，S S2 2 = 1 = 1，S S3 3 = 1 = 1。 由于由于S S1 1 S S2 2 S S3 3 等于等于011011，故查表，故查表1 1可知在

38、可知在a a3 3位有位有1 1错码。错码。 o 按照上述方法构造的码称为汉明码按照上述方法构造的码称为汉明码。表中所列的。表中所列的(7, 4)(7, 4) 汉明码的最小码距汉明码的最小码距d d0 0 = 3 = 3。因此，这种码能够纠正。因此，这种码能够纠正1 1个个 错码或检测错码或检测2 2个错码。由于码率个错码。由于码率k k/ /n n = ( = (n n - - r r) /) /n n =1 =1 r r/ /n n，故当，故当n n很大和很大和r r很小时，码率接近很小时，码率接近1 1。可见，汉。可见，汉 明码是一种高效码。明码是一种高效码。 9.5 9.5 线性分组码

39、线性分组码 二、线性分组码的一般原理二、线性分组码的一般原理 1 1、线性分组码的构造、线性分组码的构造 nH H矩阵矩阵 上面上面(7, 4)(7, 4)汉明码的例子有汉明码的例子有 现在将上面它改写为现在将上面它改写为 上式中已经将上式中已经将“ ”简写成简写成“+ +”。 0 0 0 0346 1356 2456 aaaa aaaa aaaa 01001101 00101011 00010111 0123456 0123456 0123456 aaaaaaa aaaaaaa aaaaaaa 9.5 9.5 线性分组码线性分组码 上式可以表示成如下矩阵形式：上式可以表示成如下矩阵形式： 0

40、1001101 00101011 00010111 0123456 0123456 0123456 aaaaaaa aaaaaaa aaaaaaa ）（模2 0 0 0 1011001 1101010 1110100 0 1 2 3 4 5 6 a a a a a a a 该式可以简记为该式可以简记为 H H A AT T = 0 = 0T T 或或 A A H HT T = 0 = 0 9.5 9.5 线性分组码线性分组码 式中式中 A A = = a a6 6 a a5 5 a a4 4 a a3 3 a a2 2 a a1 1 a a0 0 ，0 = 0000 = 000 将将H H 称

41、为称为监督矩阵监督矩阵。 只要监督矩阵只要监督矩阵H H 给定，编码时监督位和信息位的关系给定，编码时监督位和信息位的关系 就完全确定了。就完全确定了。 1011001 1101010 1110100 H 9.5 9.5 线性分组码线性分组码 oH H矩阵的性质：矩阵的性质： 1) 1) H H 的行数就是监督关系式的数目，它等于监督位的行数就是监督关系式的数目，它等于监督位 的数目的数目r r。H H 的每行中的每行中“1 1”的位置表示相应码元之间存的位置表示相应码元之间存 在的监督关系。例如，在的监督关系。例如，H H的第一行的第一行11101001110100表示监督位表示监督位 a

42、a2 2是由是由a a6 6 a a5 5 a a4 4之和决定的。之和决定的。H H矩阵可以分成两部分，矩阵可以分成两部分， 例如例如 r PIH 0011011 0101101 1001110 式中，式中，P P为为r r k k 阶矩阵，阶矩阵， I Ir r为为r r r r阶单位方阵。阶单位方阵。 我们将具有我们将具有 P IP Ir r 形式形式 的的H H 矩阵称为矩阵称为典型阵典型阵。 9.5 9.5 线性分组码线性分组码 2) 2) 由代数理论可知，由代数理论可知，H H矩阵的各行应该是线性无关矩阵的各行应该是线性无关 的，否则将得不到的，否则将得不到 r r个线性无关的监督

43、关系式，从个线性无关的监督关系式，从 而也得不到而也得不到 r r个独立的监督位。若一矩阵能写成典个独立的监督位。若一矩阵能写成典 型阵形式型阵形式 PIPIr r ，则其各行一定是线性无关的。因为，则其各行一定是线性无关的。因为 容易验证容易验证 I Ir r 的各行是线性无关的，故的各行是线性无关的，故 PIPIr r 的各行的各行 也是线性无关的。也是线性无关的。 9.5 9.5 线性分组码线性分组码 G G矩阵：矩阵：上面汉明码例子中的监督位公式为上面汉明码例子中的监督位公式为 也可以改写成矩阵形式：也可以改写成矩阵形式： 或者写成或者写成 3460 3561 4562 aaaa aa

44、aa aaaa 3 4 5 6 0 1 2 1011 1101 1110 a a a a a a a Q 34563456012 011 101 110 111 aaaaaaaaaaa 9.5 9.5 线性分组码线性分组码 式中，式中，Q Q 为一个为一个k k r r 阶矩阵，它为阶矩阵，它为P P 的转置，即的转置，即 Q Q = = P PT T 上式表示，在信息位给定后，用信息位的行矩阵上式表示，在信息位给定后，用信息位的行矩阵 乘矩阵乘矩阵Q Q 就产生出监督位。就产生出监督位。 Q 34563456012 011 101 110 111 aaaaaaaaaaa 9.5 9.5 线性

45、分组码线性分组码 我们将我们将Q Q的左边加上的左边加上1 1个个k k k k阶单位方阵，就构成阶单位方阵，就构成1 1个矩阵个矩阵G G G G称为称为生成矩阵生成矩阵，因为由它可以产生整个码组，即有，因为由它可以产生整个码组，即有 或者或者 因此，如果找到了码的生成矩阵因此，如果找到了码的生成矩阵G G，则编码的方法就完全确定了。具，则编码的方法就完全确定了。具 有有 I Ik kQ Q 形式的生成矩阵称为形式的生成矩阵称为典型生成矩阵典型生成矩阵。由典型生成矩阵得出的码。由典型生成矩阵得出的码 组组A A中，信息位的位置不变，监督位附加于其后。这种形式的码称为中，信息位的位置不变，监督

46、位附加于其后。这种形式的码称为 系统码系统码。 0110001 1010010 1100100 1111000 QG k I I G 34560123456 aaaaaaaaaaa GA 3456 aaaa 9.5 9.5 线性分组码线性分组码 oG G矩阵的性质：矩阵的性质： 1) 1) G G矩阵的各行是线性无关的。因为由上式可以看出，矩阵的各行是线性无关的。因为由上式可以看出， 任一码组任一码组A A都是都是G G的各行的线性组合。的各行的线性组合。G G共有共有k k行，若它们行，若它们 线性无关，则可以组合出线性无关，则可以组合出2 2k k种不同的码组种不同的码组A A，它恰是有，

47、它恰是有k k 位信息位的全部码组。若位信息位的全部码组。若G G的各行有线性相关的，则不的各行有线性相关的，则不 可能由可能由G G生成生成2 2k k种不同的码组了。种不同的码组了。 2) 2) 实际上，实际上，G G的各行本身就是一个码组的各行本身就是一个码组。因此，。因此，如果已如果已 有有k k个线性无关的码组，则可以用其作为生成矩阵个线性无关的码组，则可以用其作为生成矩阵G G，并，并 由它生成其余码组。由它生成其余码组。 9.5 9.5 线性分组码线性分组码 o 错码矩阵和错误图样错码矩阵和错误图样 n 一般说来，一般说来，A A为一个为一个n n列的行矩阵。此矩阵的列的行矩阵。

48、此矩阵的n n个元素个元素 就是码组中的就是码组中的n n个码元，所以发送的码组就是个码元，所以发送的码组就是A A。此。此 码组在传输中可能由于干扰引入差错，故接收码组码组在传输中可能由于干扰引入差错，故接收码组 一般说来与一般说来与A A不一定相同。不一定相同。 n 若设接收码组为一若设接收码组为一n n列的行矩阵列的行矩阵B B，即，即 则发送码组和接收码组之差为则发送码组和接收码组之差为 B B A A = = E E ( (模模2)2) 0121 bbbb nn B 9.5 9.5 线性分组码线性分组码 o 错码矩阵和错误图样错码矩阵和错误图样 E E就是传输中产生的就是传输中产生的

49、错码行矩阵错码行矩阵 式中式中 因此，若因此，若e ei i=0=0，表示该接收码元无错；若，表示该接收码元无错；若e ei i=1=1，则表示该，则表示该 接收码元有错。接收码元有错。 B B A A = = E E 可以改写成可以改写成 B B = = A A + + E E 例如，若发送码组例如，若发送码组A A = 1000111 = 1000111，错码矩阵，错码矩阵E E = = 00001000000100，则接收码组，则接收码组B B = 1000011 = 1000011。 错码矩阵有时也称为错码矩阵有时也称为错误图样错误图样。 0121 eeee nn E ii ii i

50、ab ab e 当 当 , 1 , 0 9.5 9.5 线性分组码线性分组码 o 校正子校正子S S 当接收码组有错时，当接收码组有错时，E E 0 0，将，将B B当作当作A A代入公式代入公式( (A A H H T T = 0) = 0)后，该式不一定成立。在错码较多，已超过后，该式不一定成立。在错码较多，已超过 这种编码的检错能力时，这种编码的检错能力时，B B变为另一许用码组，则该变为另一许用码组，则该 式仍能成立。这样的错码是不可检测的。在未超过检式仍能成立。这样的错码是不可检测的。在未超过检 错能力时，上式不成立，即其右端不等于错能力时，上式不成立，即其右端不等于0 0。假设这。

51、假设这 时该式的右端为时该式的右端为S S，即，即 B B H H T T = = S S 将将B B = = A A + + E E代入上式，可得代入上式，可得 S S = ( = (A A + + E E) ) H H T T = = A A H H T T + + E E H H T T 9.5 9.5 线性分组码线性分组码 o校正子校正子S S 由于由于A A H HT T = 0 = 0，所以，所以 S S = = E E H H T T 式中式中S S称为校正子称为校正子。它能用来指示错码的位置。它能用来指示错码的位置。 S S和错码和错码E E之间有确定的线性变换关系。若之间有确

52、定的线性变换关系。若S S和和E E 之间一一对应，则之间一一对应，则S S将能代表错码的位置。将能代表错码的位置。 9.5 9.5 线性分组码线性分组码 二、线性分组码的性质二、线性分组码的性质 n 封闭性封闭性：是指一种线性码中的任意两个码组之和：是指一种线性码中的任意两个码组之和 仍为这种码中的一个码组。仍为这种码中的一个码组。 由于线性码具有封闭性，所以两个码组由于线性码具有封闭性，所以两个码组( (A A1 1和和A A2 2) )之之 间的距离（即对应位不同的数目）必定是另一个间的距离（即对应位不同的数目）必定是另一个 码组码组( (A A1 1 + + A A2 2) )的重量（

53、即的重量（即“1 1”的数目）。因此，的数目）。因此， 码的最小距离就是码的最小重量（除全码的最小距离就是码的最小重量（除全“0 0”码组码组 外）。外）。 【例题例题1 1】 已知一线性已知一线性(6(6，3)3)码的生成矩阵为码的生成矩阵为, ,写写 出该码组的所有许用码组出该码组的所有许用码组, ,并判断该码组的纠检并判断该码组的纠检 错能力，求监督矩阵。错能力，求监督矩阵。 100101 010011 001110 G 9.5 9.5 线性分组码线性分组码 【例题例题2 2】设一线性分组码的一致监督方程为下式关系设一线性分组码的一致监督方程为下式关系, , 其中，其中，C5C5、C4C

54、4、C3C3为信息码元为信息码元 （1 1）写出监督矩阵和生成矩阵。）写出监督矩阵和生成矩阵。 （2 2）写出所有的码字。）写出所有的码字。 （3 3）判断下列码是否为码字，）判断下列码是否为码字，B1=B1=（011101011101），），B2=B2= （101011101011），），B3=B3=（110101110101）。若为非码字，如何）。若为非码字，如何 纠错或检错。纠错或检错。 0 0 0 035 0145 0234 CCC CCCC CCCC 9.5 9.5 线性分组码线性分组码 9.6 9.6 循环码循环码 1 1、循环码原理、循环码原理 循环性循环性：循环性是指任一码组循

55、环一位（即将最右端的一：循环性是指任一码组循环一位（即将最右端的一 个码元移至左端，或反之）以后，仍为该码中的一个码个码元移至左端，或反之）以后，仍为该码中的一个码 组。在下表中给出一种组。在下表中给出一种(7, 3)(7, 3)循环码的全部码组。循环码的全部码组。 码组编码组编 号号 信息位信息位监督位监督位 码组码组 编号编号 信息位信息位监督位监督位 a6a5a4a3a2a1a0a6a5a4a3a2a1a0 1000000051001011 2001011161011100 3010111071100101 4011100181110010 9.6 9.6 循环码循环码 例如，表中的第例

56、如，表中的第2 2码组向右移一位即得到第码组向右移一位即得到第5 5码组；码组； 第第6 6码组向右移一位即得到第码组向右移一位即得到第7 7码组。码组。 一般说来，若一般说来，若( (a an n-1 -1 a an n-2-2 a a0 0) )是循环码的一个码组，则 是循环码的一个码组，则 循环移位后的码组循环移位后的码组 ( (a an n-2 -2 a an n-3-3 a a0 0 a an n-1-1) ) ( (a an n-3 -3 a an n-4-4 a an n-1 -1 a an n-2-2) ) ( (a a0 0 a an n-1 -1 a a2 2 a a1 1

57、) ) 也是该编码中的码组。也是该编码中的码组。 9.6 9.6 循环码循环码 o 码多项式码多项式 n 码组的多项式表示法码组的多项式表示法 把码组中各码元当作是一个多项式的系数，即把一把码组中各码元当作是一个多项式的系数，即把一 个长度为个长度为n n的码组表示成的码组表示成 这种多项式中，这种多项式中，x x 仅是码元位置的标记，例如上式仅是码元位置的标记，例如上式 表示第表示第7 7码组中码组中a a6 6、a a5 5、a a2 2和和a a0 0为为“1 1”，其他均为，其他均为0 0。因。因 此我们并不关心此我们并不关心x x的取值。的取值。 01 2 2 1 1 )(axaxa

58、xaxT n n n n 9.6 9.6 循环码循环码 o 码多项式的按模运算码多项式的按模运算 n 在整数运算中，有模在整数运算中，有模n n运算。例如，在模运算。例如，在模2 2运算中，运算中， 有有 1 + 1 = 2 1 + 1 = 2 0 ( 0 (模模2)2)， 1 + 2 = 3 1 + 2 = 3 1 ( 1 (模模2)2)， 2 2 3 = 6 3 = 6 0 ( 0 (模模2)2) 等等。一般说来，若一个整数等等。一般说来，若一个整数m m可以表示为可以表示为 式中，式中，Q Q 整数，整数， 则在模则在模 n n 运算下，有运算下，有m m p p ( (模模n n) )

59、 即，即，在模在模 n n 运算下，一个整数运算下，一个整数m m等于它被等于它被 n n 除得的余数除得的余数P P。 np n p Q n m , 9.6 9.6 循环码循环码 o 在码多项式运算中也有类似的按模运算在码多项式运算中也有类似的按模运算 若一任意多项式若一任意多项式F F( (x x) )被一被一 n n 次多项式次多项式N N ( (x x) )除，得到商式除，得到商式 Q Q( (x x) )和一个次数小于和一个次数小于n n的余式的余式R R( (x x) )，即，即 则写为则写为 这时，码多项式系数仍按模这时，码多项式系数仍按模2 2运算，即系数只取运算，即系数只取0

60、 0和和1 1。例如，。例如， x x3 3被被( (x x3 3 + 1) + 1)除，得到余项除，得到余项1 1。所以有。所以有 )()()()(xRxQxNxF ）（模)()()(xNxRxF ）（模)1(1 33 xx ）（模) 1(11 3224 xxxxx 9.6 9.6 循环码循环码 ）（模) 1(11 3224 xxxxx x4 +x2 + 1 x x3 + 1 x4+x x2 +x +1 应当注意，由于在模应当注意，由于在模2运运 算中，用加法代替了减法，算中，用加法代替了减法， 故余项不是故余项不是x2 x + 1， 而是而是x2 + x + 1。 例：例： 9.6 9.6