差错控制编码

1、1第九章第九章 差错控制编码差错控制编码主要内容：主要内容：纠错编码的原理纠错编码的原理线性分组码线性分组码循环码循环码卷积码卷积码（数字通信特有）（数字通信特有）29.1 9.1 引引 言言 信号在信道中受到干扰信号在信道中受到干扰干扰种类：乘性干扰种类：乘性码间干扰；克服方法：均衡器码间干扰；克服方法：均衡器 加性干扰的类型：加性干扰的类型：突发突发型型错码错码：错码成串集中出现；：错码成串集中出现； 原因：脉冲干扰，衰落原因：脉冲干扰，衰落混合型错码混合型错码：加性加性错码；克服方法：差错控制编码错码；克服方法：差错控制编码随机型错码随机型错码：错码是随机出现的，相互间统计独立：错码是随

2、机出现的，相互间统计独立 原因：白噪声。原因：白噪声。提高信号抗加性干扰的能力提高信号抗加性干扰的能力3速率速率( b/s )线路类别线路类别误码率标准误码率标准300电话交换线电话交换线专用线专用线10- - 45510- - 5600电话交换线电话交换线专用线专用线10- - 35510- - 51200电话交换线电话交换线专用线专用线10- - 55510- - 52400专用线专用线10- - 5CCITT 建议的误码率标准建议的误码率标准检错重发、检错重发、前向纠错、反馈校验、检错删除前向纠错、反馈校验、检错删除 差错控制的方法差错控制的方法4检错重发：如接收端检测出错码，通知发端重

3、发，直到检错重发：如接收端检测出错码，通知发端重发，直到 (ARQ) 接收正确为止。此方法只能判断是否有错码，接收正确为止。此方法只能判断是否有错码， 不能判断具体的错码位置。所以，只能检错不不能判断具体的错码位置。所以，只能检错不 能纠错，且需要能纠错，且需要双向双向通道。通道。前向纠错：前向纠错：收端能检测出错码，并可以确定错码的位收端能检测出错码，并可以确定错码的位 (FEC) 置，并予纠正。此方法只需要置，并予纠正。此方法只需要单向单向通道。实通道。实 时性好，但设备复杂。时性好，但设备复杂。反馈校验：接反馈校验：接收端将收到的信号原封不动的发回发端，收端将收到的信号原封不动的发回发端

4、，由发端将其与原发信号相比较，如果有错则重由发端将其与原发信号相比较，如果有错则重发。这种方法需发。这种方法需双向双向通道，效率低，设备简单通道，效率低，设备简单检错删除：如：重复发送的的遥测信号。检错删除：如：重复发送的的遥测信号。5自动请求重发系统自动请求重发系统（ARQ） 工作过程：工作过程：2 2）重发控制器收到重发命令时，控制输入缓冲储存器重发控制器收到重发命令时，控制输入缓冲储存器重发一次当前码组，否则发送后一码组。重发一次当前码组，否则发送后一码组。1 1）收端解码器检测出错码时由指令发生器产生重发收端解码器检测出错码时由指令发生器产生重发命令传给发端，同时发出删除命令，删除输出

5、缓冲命令传给发端，同时发出删除命令，删除输出缓冲器内容。器内容。重发控制重发控制信信源源双双向向通通道道指令发生器指令发生器解码器解码器输出缓存器输出缓存器收收信信者者错误时删除错误时删除编码编码输入缓存器输入缓存器6优点：优点：1 1）监督码少）监督码少; ; 2 2）对各种信道有一定的适应能力；）对各种信道有一定的适应能力； 3 3）成本及复杂性低。）成本及复杂性低。缺点：缺点：1 1）需要双向通道；）需要双向通道； 2 2）干扰大时系统可能处于重发循）干扰大时系统可能处于重发循环中，效率降低；环中，效率降低； 3 3）实时性差。）实时性差。7在信息码序列中加在信息码序列中加监督码元监督码

6、元，监督码和信息码之监督码和信息码之间存在一种逻辑关系。因此，收端可以利用这种逻辑间存在一种逻辑关系。因此，收端可以利用这种逻辑关系发现或纠正存在的错码。关系发现或纠正存在的错码。一般来说，一般来说，监督码元越多监督码元越多，检、纠错检、纠错能力越强能力越强。用降低传输速率换取传输可靠性的提高。用降低传输速率换取传输可靠性的提高。不同的编码方法，有不同的检错或纠错能力。不同的编码方法，有不同的检错或纠错能力。目标：监督码元要少，目标：监督码元要少，检、纠错能力要强。检、纠错能力要强。9.2 9.2 纠错编码的基本原理纠错编码的基本原理8例：例：表示天气表示天气信源信源发送信息码发送信息码晴晴0

7、 0云云0 1阴阴1 0雨雨1 1接收信息码接收信息码 判别判别(错误错误)0 1云云11 雨雨0 0晴晴1 0阴阴结论：结论：虽然接收码组有错，但接收端无法识别。虽然接收码组有错，但接收端无法识别。错错 1 位位9信源信源发送信息码发送信息码监督码监督码晴晴0 00云云0 11阴阴1 01雨雨1 10接收码组接收码组判别判别001、010、100 010、001、111 100、111、001 111、100、010 增加一位监督码增加一位监督码错错 1 位位接收码组接收码组判别判别(错误错误)011、110、101 云、雨、阴云、雨、阴000、101、110 晴、阴、雨晴、阴、雨110、0

8、00、011 雨、晴、云雨、晴、云101、000、011 阴、晴、云阴、晴、云错错 2 位位结论：可以检测出结论：可以检测出 1 位错码，但不能纠错。位错码，但不能纠错。禁用码组：非禁用码组：非信息信息码组码组许用码组：有效许用码组：有效信息信息码组码组码距码距10结论：结论：能纠正能纠正 1 位错码位错码，或，或检测出检测出 2 位错码位错码。信源信源 发送信息码发送信息码 监督码监督码晴晴0 0000云云0 1011阴阴1 0101雨雨1 1110接收码组接收码组判别判别00001,00010,00100,01000,10000晴晴01010,01001,01111,00011,11011

9、云云10100,10111,10001,11101,00101阴阴11111,11100,11010,10110,01110雨雨错错 1 位位接收码组接收码组判别判别11000,10100,10010,10001,01100,01010,01001,00110,00101,0001110011,11111,11001,11010,00111,00001,00010,01101,01110,0101001101,00001,00111,00110,11001,11110,11101,10011,10000,1010000110,01010,01100,01111,10010,10100,1011

10、1,11000,11011,11111错错 2 位位增加三位监督码增加三位监督码码距关系码距关系11特征：特征：分组码中的监督码元仅监督本码组分组码中的监督码元仅监督本码组中的信息码元。中的信息码元。分组码分组码定义：定义：将信息码分组，为每组信息码将信息码分组，为每组信息码后附加若干监督码元形成的码集合。后附加若干监督码元形成的码集合。 分组码分组码 k ： 码组中码组中信息码元信息码元的数目。的数目。 n ： 码组的总位数，又称为码组的总位数，又称为码组长度码组长度。 r = n - - k ：码组中：码组中监督码元监督码元的数目。的数目。编码效率：编码效率：k/n；冗余度：；冗余度：(n

11、-k)/k符号：符号：( n , k )12结构结构 码长码长 n = k + r k 个信息位个信息位 r 个监督位个监督位码组重量码组重量：码组中：码组中 “1 ” 的数目。的数目。an-1an-2arar-1a0码距码距 d ：两个码组对应位上不同的码元个数，：两个码组对应位上不同的码元个数，称为称为汉明距离汉明距离。最小码距最小码距 d0 ：码集合中任意两两码组间距离：码集合中任意两两码组间距离的最小值。的最小值。天气编码举例天气编码举例13 检测检测 e 个错码，要求最小码距个错码，要求最小码距1ed0 纠正纠正 t 个错码，要求最小码距个错码，要求最小码距1t2d0 纠正纠正 t

12、个错码、同时检测个错码、同时检测 e 个错码，要求最小码距个错码，要求最小码距1ted0 )te( 码距与码集合检、纠错能力的关系码距与码集合检、纠错能力的关系AB例：例： A = ( 00000 ) 、B = ( 11111 )， d0 = 5 结论：结论：e = 4 或或 t = 2 或或 t = 1 、 e = 3d = 1d = 2d = 3天气编码举例天气编码举例14 奇数监督码奇数监督码: :使码组中使码组中“1” 的个数为奇数的个数为奇数 偶数监督码偶数监督码: :使码组中使码组中“1” 的个数为偶数的个数为偶数码距为码距为2 2，能检，能检测奇数个错码测奇数个错码二维奇偶监督码

13、（矩阵码）二维奇偶监督码（矩阵码）生成规则：生成规则： 许用码组写成一行（包括信息码和许用码组写成一行（包括信息码和1 位监位监督码），设共有督码），设共有m 行。第行。第 m+1 行为按列增加的行为按列增加的监督码。（构成监督码行）监督码。（构成监督码行） 1 1、奇偶监督码奇偶监督码一维奇偶监督码：一维奇偶监督码： 1 位监督码；位监督码；9.3 9.3 常用的简单编码常用的简单编码常用常用an-1 an-2 a0=1an-1 an-2 a0=015消息消息发送信息码发送信息码a2 a1 监督码监督码a0晴晴0 00云云0 11阴阴1 01雨雨1 10例例 :一维偶数监督码一维偶数监督码接

14、收码组接收码组判别判别001、010、100010、001、111100、111、001111、100、010错错 1 位位满足：满足：0aaa012 检验检验:0aaa012 只能检错，不能纠错只能检错，不能纠错返回返回161）设）设 和和 发生错码，按行无法检测出有错，而发生错码，按行无法检测出有错，而按列可检测。按列可检测。11na 10aa2 a1 a00 0 00 1 11 0 11 1 00 0 0例例 二维偶数监督码二维偶数监督码通式通式突发性错码突发性错码111n1n20222n1n20mmmn1n20n1n20aaaaaaaaaccc 2 2）能检测突发性错码；适用于突发信道

15、。）能检测突发性错码；适用于突发信道。173）若仅一行有奇数个错码时，可通过列确定错码位置若仅一行有奇数个错码时，可通过列确定错码位置并纠正。并纠正。4）当当 同时出错，则按行按列均不能检测同时出错，则按行按列均不能检测 出有错。出有错。5）方阵码除了在行列上的错码都为偶数时，无法检测）方阵码除了在行列上的错码都为偶数时，无法检测外，其余均能检测。外，其余均能检测。上页上页m0m1n1011naaaa 182 2恒比码恒比码在恒比码中，每个码组均含有在恒比码中，每个码组均含有相同数目相同数目的的“1 1”( (和和“0 0”) )。这种码在检测时，只要判断接收码组中。这种码在检测时，只要判断接

16、收码组中“1 1”的的数目是否正确，就能判断有无错误。数目是否正确，就能判断有无错误。P286P286表表9-29-2中的保护电码，每个码组的长度为中的保护电码，每个码组的长度为5 5，其，其中恒有中恒有3 3个个“1 1”，称为，称为5/35/3恒比码恒比码。用于我国的汉字电传。用于我国的汉字电传编码。编码。从从5 5中取中取3 3的组合数的组合数C C3 35 5=5!/(3! 2!)=10=5!/(3! 2!)=10。这。这1010种许用种许用码组恰好可用来表示码组恰好可用来表示1010个阿拉伯数字。用个阿拉伯数字。用4 4位阿拉伯数位阿拉伯数字表示一个汉字。字表示一个汉字。在无线电报通

17、信中，广泛采用的是在无线电报通信中，广泛采用的是 7/37/3恒比码恒比码，这，这种码组中总是有种码组中总是有3 3个个“1 1”。共有。共有7!/(37!/(3！4!)=354!)=35种许用码种许用码组，它们可用来代表组，它们可用来代表2626个英文字母及其他控制符号个英文字母及其他控制符号。 19特征：特征：具有纠正具有纠正 1 位错码、检测位错码、检测 2 位和大部分位和大部分 2 位以上错码位以上错码的能力的能力定义：定义：信息码位数与监督码位数信息码位数与监督码位数相同相同 编码编码规则：规则： 1）当信息位中有）当信息位中有奇奇数个数个“1”时，监督位是信息位的重复时，监督位是信

18、息位的重复2）当信息位中有）当信息位中有偶偶数个数个“1”时，监督位是信息位的反码时，监督位是信息位的反码1 0 0 0 1 例：例：若信息码为若信息码为 1 1 0 0 1 3 3、 正反码正反码 则正反码为则正反码为 1 1 0 0 1 1 1 0 0 11 0 0 0 1 0 1 1 1 01）将接收码组中信息码和监督码对应按位模将接收码组中信息码和监督码对应按位模2 加，得加，得合成码组合成码组2）根据接收码组中信息码含）根据接收码组中信息码含 “1” 的奇偶情况，的奇偶情况，由合成码组生成由合成码组生成校验码组校验码组 3）根据校验码组的组成，依表判断错码情况，并予检错与纠错）根据校

19、验码组的组成，依表判断错码情况，并予检错与纠错译码译码规则：规则：“1”为奇为奇 校验校验 = 合成合成“1”为偶为偶 校验校验 =合合成成20例：发例：发 1 1 0 0 1 1 1 0 0 1 1）收无错）收无错 信息码中含奇数个信息码中含奇数个“1”2）收有错、为）收有错、为 1 0 0 0 1 1 1 0 0 1合成码组合成码组= 1 1 0 0 1 1 1 0 0 10 0 0 0 0译码判决：译码判决：校验码组校验码组错码情况错码情况 1全全 “0” 无错码无错码 24 个个“1”1 个个“0” 信息码中有一位错码，信息码中有一位错码，对应校验码组中的对应校验码组中的“0” 的位置

20、的位置 34 个个“0”1 个个“1” 监督码中有一位错码，监督码中有一位错码，对应校验码组中的对应校验码组中的“1” 的位置的位置 4 其他组成其他组成 错码多于错码多于 1 个个 校验码组校验码组 = 合成码组合成码组 = 00000判断接收无错码判断接收无错码合成码组合成码组= 1 0 0 0 1 1 1 0 0 10 1 0 0 0 信息码中含偶数个信息码中含偶数个“1”查表知信息码第二位错查表知信息码第二位错10111 合合成成码码组组校校验验码码组组特征：特征：编码效率低编码效率低219.4 9.4 线性分组码线性分组码汉明码的编码原理汉明码的编码原理一般线性分组码的编码原理一般线

21、性分组码的编码原理（可以纠错）（可以纠错）线性码：监督码和信息码之间的关系是线性关系线性码：监督码和信息码之间的关系是线性关系22分析偶数监督码，寻找逻辑组合分析偶数监督码，寻找逻辑组合 监督方程监督方程 所以解码就是要计算所以解码就是要计算0 无错无错1 有错有错s =只能表示出错只能表示出错不能描述错码位置不能描述错码位置一位监督码对一位监督码对应一个监督方应一个监督方程程，即，即对应一对应一个校正子个校正子结论：若增加监督码元，建立多个监督方程，多个结论：若增加监督码元，建立多个监督方程，多个校正子就能形成逻辑组合描述错码位置。校正子就能形成逻辑组合描述错码位置。r位监督码对应位监督码对

22、应r个校正子，就有个校正子，就有2r 种组合，用其中种组合，用其中一种组合表示无错，其余一种组合表示无错，其余2r-1种组合表示错码的位置。种组合表示错码的位置。9.4.1 9.4.1 汉明码汉明码s=an-1 an-2 a0an-1 an-2 a0=0校正子校正子 23确定监督关系表确定监督关系表建立监督方程建立监督方程建立编码方程建立编码方程如果只错一位，分组码如果只错一位，分组码(n,k)中的错码有中的错码有n个可能的位个可能的位置置 ，要用要用r 位监督码表示这位监督码表示这n 个错码的位置，个错码的位置， 为提高编码效率，为提高编码效率， r 取最小值取最小值n12r 例：例：已知已

23、知( 7 , 4 )码，码，r = 3 共有共有3个监督方程，个监督方程， 构成构成 3个校正子个校正子 S1 S2 S3S1 S2 S30 0 0无错无错0 0 1a0 错错0 1 0a1 错错1 0 0a2 错错1 1 0a3 错错0 1 1a4 错错1 1 1a5 错错1 0 1a6 错错0aaaa2356456034513562aaaaaaaaaaaa 0aaaa04560aaaa1345只纠正一位错码只纠正一位错码n7123 监督码出错只与监督码出错只与一个校正子有关一个校正子有关24求码组集合求码组集合 k = 4，信息码组有信息码组有 16 个个a6 a5 a4 a3a2 a1

24、a00 0 0 00 0 00 0 0 11 1 00 0 1 00 1 10 0 1 11 0 1.1 1 0 00 1 01 1 0 11 0 01 1 1 00 0 11 1 1 11 1 1能纠正一位错码，且能纠正一位错码，且2r-1=n的的线性分组码，称为线性分组码，称为汉明码汉明码。其编码效率为其编码效率为k/n=(2r-1-r)/(2r-1)=1-r/(2r-1)=1-r/n当当n很大时，则编码效率接近很大时，则编码效率接近1。可见，汉明码是。可见，汉明码是一种高效码。一种高效码。25 汉明码的监督方程为汉明码的监督方程为用用矩阵表示矩阵表示6543210110110000111

25、01001110 0010aaaaaaa 9.4.2 9.4.2 一般线性分组码的编码原理一般线性分组码的编码原理0aaaa0aaaa0aaaa045613452356 记为：记为：0AHT 监督矩阵监督矩阵码组向量码组向量111000101110101101100H0123456aaaaaaaA 当当 称称 H 为典型监督矩阵为典型监督矩阵（含单位阵）（含单位阵）rIPH阶阶为为krP阶阶为为rrIr错误图样错误图样26QIGk根据监督方程确定了根据监督方程确定了编码方程编码方程34563456012aaaaPaaaa111001111101aaa456034513562aaaaaaaaaa

26、aa 两边同取转置两边同取转置QaaaaPaaaaaaa3456T3456012阶阶其其中中rkPQT构造构造生成矩阵生成矩阵GaaaaaaaaaaaA34560123456G 为典型生成矩阵为典型生成矩阵 编码矩阵方程编码矩阵方程特点：信息位不变，监督位附加于其后。特点：信息位不变，监督位附加于其后。由典型生成矩阵得出的码组由典型生成矩阵得出的码组 A是是系统码系统码27QIGk生成矩阵生成矩阵0111000110010011100101010001G 中中每行均为一个码组，且线性无关每行均为一个码组，且线性无关若能找到若能找到k个线性无关的已知码组，就能构成矩阵个线性无关的已知码组，就能构

27、成矩阵G。 nk TkPI循环码生成矩阵循环码生成矩阵28译码运算，当译码运算，当TTH)EA(HBTTTHESSHEHAS 为校正子。说明为校正子。说明 S 与与E 有确定的线性关系有确定的线性关系若若 E 的数目有限的数目有限，能与能与 S 一一对应，一一对应，则则 说明说明 S 能描述错码的位置，具有纠错能力。能描述错码的位置，具有纠错能力。令令 发码组为发码组为 A、收码组为、收码组为 B 错码图样错码图样 E = B- - A错误图样错误图样收发码组的关系收发码组的关系THB0 无错无错1 有错有错 令令 B =E + + A29发码组发码组 A = 1 1 0 0 0 1 0收码组

28、收码组 B = 1 0 0 0 0 1 0 译码运算译码运算例：例： ( 7 , 4 )汉明码汉明码, 111000101110101101100H001010100110011111101)1000010(HBT)111(S1 S2 S30 0 0无错无错0 0 1a0 错错0 1 0a1 错错1 0 0a2 错错1 1 0a3 错错0 1 1a4 错错1 1 1a5 错错1 0 1a6 错错 a5 错错含义：含义：错码图样错码图样 E =（0 1 0 0 0 0 0） 只有一位错码只有一位错码)111(HET30线性码中任意线性码中任意两个码组之和两个码组之和仍为这种码中的一个码组仍为这种

29、码中的一个码组证：证： 设设 A1 、 A2 为线性码中两个许用码组为线性码中两个许用码组0HAT10HAT2两式相加两式相加0H)AA(HAHAT21T2T121AA 是许用码组是许用码组推广：推广： 1）两个码组间的）两个码组间的距离距离必是另一码组的必是另一码组的重量重量2）除）除 全全0 码组之外，编码的码组之外，编码的最小码重最小码重是码集是码集合的合的最小码距最小码距。线性分组码的性质：线性分组码的性质：封闭性封闭性3)线性分组码中必有全线性分组码中必有全0码；码；（信息码全（信息码全0，监督码全，监督码全0）319.5 9.5 循环码循环码 9.5.1 9.5.1 码多项式码多项

30、式9.5.2 9.5.2 循环码的特性循环码的特性9.5.3 9.5.3 循环码的编码方法循环码的编码方法 循环码是线性分组码中一种重要的编码。它是在严循环码是线性分组码中一种重要的编码。它是在严密的代数理论基础上建立起来的。其编码和解码不密的代数理论基础上建立起来的。其编码和解码不太复杂，但检太复杂，但检(纠纠)错的能力较强。循环码除了具有线错的能力较强。循环码除了具有线性码的一般性质外，还具有循环性，见表性码的一般性质外，还具有循环性，见表11-5。32码多项式的模运算：码多项式的模运算：9.5.1 9.5.1 码多项式码多项式码多项式码多项式以码组中各码元为系数的多项式以码组中各码元为系

31、数的多项式T( x ) = an-1 x n-1 + an-2 x n-2 + . + a1 x + a0设设 多项式多项式 F(x)、除式为、除式为 N(x)x(N)x(R)x(Q)x(N)x(F)()(xRxF注：注：多项式按模多项式按模 N(x) 运算过程中，其系数均为运算过程中，其系数均为模模2 运算。运算。x 仅为码元位置的标记仅为码元位置的标记模模 N( x )； R( x )：余式：余式例：例：( 110 0101 ) T( x ) = x 6 + x 5 + x 2 + 133例：例：1x1xx324xxx1xx1x42431xx21xx1xx224解：解：记为：记为：余式余式

32、系数为二进制，只能取系数为二进制，只能取0或或1，二进制的加减都是一样的，二进制的加减都是一样的34 用码多项式的运算来表示：若用码多项式的运算来表示：若T(x)对应一个码长为对应一个码长为 n 的许用码组，则的许用码组，则x i T(x)按模按模x n+1运算后余式运算后余式T (x)仍为仍为许用码组许用码组。证：证： 令令( )( )ixT xTx 1xn模模 T (x)的系数是的系数是T(x)中系数向左循环移位中系数向左循环移位 i 次的结果次的结果9.5.2 9.5.2 循环码的特性循环码的特性 编码中任意一个码组，左移或右移一位得到的新码编码中任意一个码组，左移或右移一位得到的新码组

33、必是该码集合中另一码组。组必是该码集合中另一码组。生成多项式生成多项式 T( x ) = an-1 x n-1 + an-2 x n-2 + . + a1 x + a0 x iT( x ) = an-1 x n-1+i + . + an-1-i x n-1+ . + a0 xix iT(x) an-1-i x n-1 +. + a0 x i + an-1 x i-1 + . +an-i1xn模模35例：例： ( 7 , 3 )循环码循环码, 码组为码组为( 110 0101 )，验证验证 x 3 T( x ) 按模按模 x 7 +1 运算后余式仍是一个许用码组运算后余式仍是一个许用码组 。 解

34、：解： T( x ) = an-1 x n-1 + an-2 x n-2 + . + a1 x + a0 T( x ) = x 6 + x 5 + x 2 + 1 x 3 T( x ) = x 9 + x 8 + x 5 + x 3xxxxxxxxxxxxxxxxxx1x2235823582935897xxxxxTx2353)( 余式余式T (x) 对应码组为对应码组为(0101110) 是是T(x)码组循环左移三位的结果码组循环左移三位的结果369.5.3 9.5.3 循环码的编码方法循环码的编码方法思路：思路：由码的循环性，由码的循环性，可知找到一个码多项式，可知找到一个码多项式，就能就能

35、得到其他的码多项式得到其他的码多项式一个一个(n,k)码有码有2k个不同码组。用个不同码组。用g(x)表示其中表示其中前前(k-1)位皆为位皆为“0”的码组。则的码组。则g(x)，xg(x)，x2g(x)，xk-1g(x)都是该循环码的码组，而且这都是该循环码的码组，而且这k个码组个码组是线性无关的，是线性无关的，用它们可以构成此循环码的用它们可以构成此循环码的生成矩阵生成矩阵G。循环码的生成矩阵循环码的生成矩阵 G)()()()()(xgxgxxgxxgxxG2k1kk是一个码是一个码组中信息组中信息码的长度码的长度37对对g(x)的说明：的说明： 是该循环码中是该循环码中阶数最低阶数最低的

36、码多项式。的码多项式。 在循环码中除全在循环码中除全“0”码组外，即码组外，即连连“0”的长度的长度最多最多只能有只能有(k-1)位位。否则在经过若干次循环移位后将得到。否则在经过若干次循环移位后将得到一个一个k个信息位全为个信息位全为“0”，但监督位不全为，但监督位不全为“0”的码组。的码组。这显然是不可能的。这显然是不可能的。 g(x)必须是必须是一个常数项不为一个常数项不为“0”的的(n-k)次多项式次多项式。 而且还是而且还是唯一唯一的。因为如果有两个，则由码的封闭的。因为如果有两个，则由码的封闭性，把这两个相加也应该是一个码组，且此码组多项性，把这两个相加也应该是一个码组，且此码组多

37、项式的次数将小于式的次数将小于(n-k)，即连续，即连续“0”的个数多于的个数多于(n-k)，这是不可能的。这是不可能的。 我们称这唯一的我们称这唯一的(n-k)次多项式次多项式g(x)为码的为码的生成多项生成多项式式。一旦确定一旦确定g(x)，则整个，则整个(n-k)循环码就被确定了。循环码就被确定了。38(7,3)循环码的码组循环码的码组:T(x)=a6a5a4G(x) =a6a5a4 =(a6 x2+a5 x+a4)g(x) 这表明，所有码多项式这表明，所有码多项式T(x)都是都是g(x)倍式倍式，而且任一，而且任一次数不大于次数不大于(k-1)的多项式乘的多项式乘g(x)都是码多项式。

38、都是码多项式。在表在表11-5中找出生成多项式中找出生成多项式)()()(xgxxgxgx2所有的信息码组合所有的信息码组合39码生成多项式码生成多项式 g( x ) 的求解的求解定理：定理：循环码循环码( n , k ) 的的 g( x ) 是是 xn +1 的一个的一个( n- - k ) 次次 因子。因子。证：证： 任意一个码多项式任意一个码多项式 T( x ) 都是都是 g( x ) 倍式倍式令令 T( x ) = h( x ) g( x ) ( )( )( )knnx g xT xQ xx1x1 1x)x(T1n而而 x k g( x ) = x n + 1 + T( x ) x n

39、 +1 = x k g( x ) + T( x ) = x k g( x ) + h( x ) g( x ) = x k + h( x ) g( x ) g(x)为一为一(n-k)次多项式，次多项式，故故xkg(x)为一为一n次多项式。次多项式。余式余式T(x) 也是一个许用也是一个许用码组。码组。按模运算按模运算40例：已知例：已知 (7,3) 循环码，求码组集合循环码，求码组集合 、监督矩阵、监督矩阵 H 。解：解： n = 7 x7 + 1 = ( x +1 )( x 6 + x 5+ x 4 + x 3 + x 2+ x + 1 ) = ( x +1 )( x 3 + x 2+ 1 )

40、( x 3 + x + 1 ) g1( x ) = ( x +1 )( x 3 + x 2+ 1 ) = x 4 + x 2+ x + 1 g2( x ) = ( x +1 )( x 3 + x + 1 ) = x 4 + x 3+ x 2 + 1 取取 g( x ) = g1( x ) = x 4 + x 2+ x + 1 )x( g)x( gx)x( gx)x( gx)x(G2k1k1xxxxxxxxxxx242352346 111010001110100011101G互逆互逆(生成多项式的逆多项式也是生成多项式生成多项式的逆多项式也是生成多项式)表表11-5（2）41 A = ( a6

41、a5 a4 a3 a2 a1 a0 ) G)aaa(456 a6 a5 a4 a6 a5 a4 a3 a2 a1 a0 0 0 0 0 0 0 0 0 0 00 0 1 1） 0 0 1 0 1 1 10 1 0 2） 0 1 0 1 1 1 00 1 1 3） 0 1 1 1 0 0 11 0 0 5） 1 0 1 1 1 0 01 0 1 4） 1 0 0 1 0 1 11 1 0 7） 1 1 1 0 0 1 01 1 1 6） 1 1 0 0 1 0 1111010001110100011101G111010001110101101001 00011010010111010001110

42、00110H 111010001110100011101)aaa(456监督方程：监督方程：0aaa356 0aaa245 0aaaa1456 0aaa046 d0 = 3 , t = 1 非典型非典型非系统非系统429.5.4 循环码的编、解电路循环码的编、解电路1、循环码的编码电路、循环码的编码电路设设m(x)为信息码多项式，其次数小于为信息码多项式，其次数小于k。 (1)用用xn-k乘乘m(x)。得到的得到的xn-km(x)的次数必小于的次数必小于n。也。也就是把信息码后附加上就是把信息码后附加上(n-k)个个“0”，这是监督位的位，这是监督位的位置。置。 (2)用用g(x)除除xn-k

43、m(x): xn-km(x)/ /g(x)=Q(x)r(x)得到得到余式余式r(x) 。 (3) T(x)=xn-km(x)+r(x)由于由于xn-km(x)+r(x)=Q(x)g(x)，能被，能被g(x)整除，因此整除，因此T(x)必为一码多项式必为一码多项式。 余式余式r(x) 就是就是监督码多项式监督码多项式。43上述三步运算，可由除法电路来实现。上述三步运算，可由除法电路来实现。 ( (移存器的反馈抽头取决于生成多项式移存器的反馈抽头取决于生成多项式) ) 44452循环码的解码电路循环码的解码电路 接收端解码的要求有两个：检错和纠错。接收端解码的要求有两个：检错和纠错。 用于检错的解

44、码电路比较简单。用于检错的解码电路比较简单。 把接收码组把接收码组R(x)除以除以生成多项式生成多项式g(x)。 当传输中当传输中未发生错误未发生错误时，接收码组与发送码组相时，接收码组与发送码组相同，即同，即R(x)=T(x)，故接收码组，故接收码组R(x)必定必定能被能被g(x)整除整除 若码组在传输中若码组在传输中发生错误发生错误，则，则R(x)T(x)，R(x)被被g(x)除时可能除时可能除不尽除不尽而有余项，即有而有余项，即有 R(x)/ /g(x)=Q(x)+r(x)/ /g(x) 当错码数超过了这种编码的检错能力时，有错码当错码数超过了这种编码的检错能力时，有错码的接收码组也可能

45、被的接收码组也可能被g(x)整除，这时的错码就不能检整除，这时的错码就不能检出了。这种错误称为出了。这种错误称为不可检错误不可检错误。4647 用于纠错的解码方法比较复杂。要求每个可纠正的用于纠错的解码方法比较复杂。要求每个可纠正的错误图样错误图样必须与一个特定必须与一个特定余式余式有有一一对应一一对应关系。可按关系。可按下述步骤进行：下述步骤进行： (1)用生成多项式用生成多项式g(x)除接收码组除接收码组R(x)=T(x)+E(x)，得，得出出余式余式r(x)； (2)按余式按余式r(x)用用查表查表的方法或通过某种的方法或通过某种运算运算得到得到错误错误图样图样E(x)。 (3)从从R(

46、x)中中减去减去E(x)，便得到已纠正错误的原发送码便得到已纠正错误的原发送码组组T(x)； 上述运算第上述运算第(2)步较复杂，并且在计算余式和决定步较复杂，并且在计算余式和决定E(x)的时候需要把整个接收码组的时候需要把整个接收码组R(x)暂时存储起来。暂时存储起来。 对于纠正突发错误或单个错误的编码还算简单，而对于纠正突发错误或单个错误的编码还算简单，而对于纠正多个随机错误的编码却是十分复杂的。对于纠正多个随机错误的编码却是十分复杂的。 48 这种解码方法称为这种解码方法称为捕错解码法捕错解码法。一种编码可以有几。一种编码可以有几种不同的纠错解码法。对于循环码来说，可用捕错解码、种不同的纠错解码法。对于循环码来说，可用捕错解码、大数逻辑解码等大数逻辑解码等 现在主要用现在主要用软件软件来做编解码来做编解码499.5.5 缩短循环码缩短循环码并不是在所有码长并不是在所有码长(n,k)码中，都能找到相应的满足码中，都能找到相应的满足某纠错能力的循环码。但在系统设计中，码长某纠错能力的循环码。但在系统设计中，码长n、信、信息位数息位数k和和纠错能力纠错能力常常是预先确定的。常常是预先确定的。这时可采用缩短循环码来