通信原理-第九章-差错控制编码课件.ppt

1、第九章第九章 差错控制编码差错控制编码主要内容主要内容纠错编码的原理纠错编码的原理线性分组码线性分组码循环码循环码重点重点检错、纠错的概念检错、纠错的概念分组码的结构分组码的结构汉明码汉明码循环码循环码9.1 9.1 引言引言9.2 9.2 纠错编码的原理纠错编码的原理9.3 9.3 常用的简单编码常用的简单编码9.4 9.4 线性分组码线性分组码9.5 9.5 循环码循环码作业作业习题习题 9-19-1、5 5、7 7、8 8、1212作业作业9.1 引引 言言 检错重发法检错重发法9.1.2 差错控制的方法差错控制的方法9.1.1 编码的目的：提高信号抗加性干扰的能力编码的目的：提高信号抗

2、加性干扰的能力 干扰种类：干扰种类：加性加性 克服方法：差错控制编码克服方法：差错控制编码 加性干扰的特征：加性干扰的特征：突发信道：出现错码成串集中。突发信道：出现错码成串集中。混合信道：前两者中和。混合信道：前两者中和。乘性乘性 克服方法：均衡器克服方法：均衡器随机信道：出现错码是随机的，相互间统计独立。随机信道：出现错码是随机的，相互间统计独立。反馈校验法反馈校验法前向纠错方法前向纠错方法定义定义误码率标准误码率标准速率速率(b/s)线路类别线路类别误码率标准误码率标准300电话交换线电话交换线专用线专用线10-45510-5600电话交换线电话交换线专用线专用线10-35510-512

3、00电话交换线电话交换线专用线专用线10-55510-52400专用线专用线10-5CCITT 建议的误码率标准建议的误码率标准检错重发法：在接收端检测出错码时，通知发端重发信号，检错重发法：在接收端检测出错码时，通知发端重发信号，直到接收正确为止。此方法只能判断是否有错直到接收正确为止。此方法只能判断是否有错码，不能判断具体的错码位置。所以，只能检码，不能判断具体的错码位置。所以，只能检错不能纠错，且需要错不能纠错，且需要双向双向通道。通道。前向纠错方法：前向纠错方法：在收端检测出错码时，可以确定错码在收端检测出错码时，可以确定错码的位置，并予纠正。此方法只需要的位置，并予纠正。此方法只需要

4、单向单向通道。通道。实时性好，但设备复杂。实时性好，但设备复杂。反馈校验法：接反馈校验法：接收端将收到的信号原封不动的发回发收端将收到的信号原封不动的发回发端，由发端将其与原发信号相比较，如果端，由发端将其与原发信号相比较，如果有错则重发。这种方法需有错则重发。这种方法需双向双向通道，效率通道，效率低，但设备简单。低，但设备简单。在信息码序列中加在信息码序列中加监督码元监督码元（也称纠错码）（也称纠错码）自动请求重发系统自动请求重发系统（ARQ）9.1.3 差错控制编码的原理差错控制编码的原理不同的编码方法，有不同的检错或纠错能力，监督码不同的编码方法，有不同的检错或纠错能力，监督码元越多，检

5、、纠错能力越强。元越多，检、纠错能力越强。由于信息码元是随机序列，收端无法预知信号状态，由于信息码元是随机序列，收端无法预知信号状态，因而无法判别接收码是否有错。增加了监督码元之后，因而无法判别接收码是否有错。增加了监督码元之后，监督码和信息码之间存在一种逻辑关系，因此，收端监督码和信息码之间存在一种逻辑关系，因此，收端可以利用这种逻辑关系发现或纠正存在的错码。可以利用这种逻辑关系发现或纠正存在的错码。自动请求重发系统自动请求重发系统（ARQ）工作工作过程：过程：3 3）重发控制器收到重发命令时，控制输入缓冲储存器重）重发控制器收到重发命令时，控制输入缓冲储存器重发一次当前码组，否则发送后一码

6、组。发一次当前码组，否则发送后一码组。2 2）收端解码器检测出错码时由指令发生器产生重发命令）收端解码器检测出错码时由指令发生器产生重发命令传给发端，同时发出删除命令，删除输出缓冲器内容。传给发端，同时发出删除命令，删除输出缓冲器内容。1 1）收发正常时，重发控制与指令发生器不工作。）收发正常时，重发控制与指令发生器不工作。重发控制重发控制信信源源双双向向通通道道指令发生器指令发生器解码器解码器输出缓存器输出缓存器收收信信者者错误时删除错误时删除编码编码输入缓存器输入缓存器优点：优点：1 1）监督码少，占总码的）监督码少，占总码的(20%)2 2）对各种信道有一定的适应能力。）对各种信道有一定

7、的适应能力。3 3）成本及复杂性低。）成本及复杂性低。缺点：缺点：1 1）需要双向通道）需要双向通道 2 2）干扰大时系统可能处于）干扰大时系统可能处于重发循环中，效率降低重发循环中，效率降低 3 3）实时性差）实时性差9.2 纠错编码的基本原理纠错编码的基本原理9.2.1 分组码的概念分组码的概念9.2.2 分组码参数分组码参数例：例：天气预报天气预报9.2.1 分组码的概念分组码的概念特征：特征：分组码中的监督码元仅监督本码组中的信息码元。分组码中的监督码元仅监督本码组中的信息码元。分组码分组码定义：定义：将信息码分组，为每组信息码后附加若将信息码分组，为每组信息码后附加若干监督码元形成的

8、码集合。干监督码元形成的码集合。分组码检错、纠错能力的体现分组码检错、纠错能力的体现信源信源发送信息码发送信息码晴晴0 0云云0 1阴阴1 0雨雨1 1接收信息码接收信息码判别判别0 1云云10 阴阴0 0晴晴1 0阴阴结论：结论：虽然接收码组有错，但接收端无法识别。虽然接收码组有错，但接收端无法识别。讨论讨论信源信源 发送信息码发送信息码监督码监督码晴晴0 00云云0 11阴阴1 01雨雨1 10接收码组接收码组判别判别001、010、100010、001、111100、111、001111、100、010建立分组码建立分组码 A错错 1 位位接收码组接收码组判别判别011、110、101云

9、、雨、阴云、雨、阴000、101、110晴、阴、雨晴、阴、雨110、000、011雨、晴、云雨、晴、云101、000、011阴、晴、云阴、晴、云错错 2 位位结论：结论：只能检测出只能检测出 1 位错位错码，码，但不能纠正。但不能纠正。禁用码组：非禁用码组：非信息信息码组码组许用码组：有效许用码组：有效信息信息码组码组结论：结论：能纠正能纠正 1 位错码位错码，或，或检测出检测出 2 位错码位错码。信源信源 发送信息码发送信息码 监督码监督码晴晴0 0000云云0 1011阴阴1 0101雨雨1 1110接收码组接收码组判别判别00001、00010、00100、01000、100000101

10、0、01001、01111、00011、1101110100、10111、10001、11101、0010111111、11100、11010、10110、01110建立分组码建立分组码 B错错 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、010

11、10、01100、01111、10010、10100、10111、11000、11011、11111错错 2 位位 k：码组中信息码元的数目。码组中信息码元的数目。n：码组的总位数，又称为码组长度。码组的总位数，又称为码组长度。r=n-k：码组中监督码元的数目。：码组中监督码元的数目。结构结构符号符号(n,k)码长码长 n=k+r k 个信息位个信息位 r 个监督位个监督位码组重量码组重量 码组中码组中“1”的数目的数目9.2.2 分组码参数分组码参数an-1an-2arar-1a0码距码距 d：两个码组对应位数值不同的码元个数称为：两个码组对应位数值不同的码元个数称为码组间的汉明距离码组间的

12、汉明距离码距与码集合码距与码集合检、纠错能力的关系检、纠错能力的关系例：例：码组（码组（a2 a1 a0）=1 1 0 （b2 b1 b0）=0 1 0码距的几何概念码距的几何概念码距是码距是 1最小码距最小码距 d0 ：码集合中任意两两码组间距离的最小值：码集合中任意两两码组间距离的最小值（0 1 0）（1 1 0）（0 0 0）（1 0 0）（1 0 1）（0 0 1）（0 1 1）（1 1 1）a1a0a2选许用码组：选许用码组：0 0 0 0 1 1 1 1 0 1 0 1令令 n=3,共有共有 8 个码组个码组沿立方体各边行走，沿立方体各边行走，4 个码个码组的距离均为组的距离均为

13、2 个边长个边长 d0 =2 检测检测 e 个错码，要求最小码距个错码，要求最小码距1ed0 纠正纠正 t 个错码，要求最小码距个错码，要求最小码距1t2d0 纠正纠正 t 个错码、同时检测个错码、同时检测 e 个错码，要求最小码距个错码，要求最小码距1ted0 )te(码距与码集合检、纠错能力的关系码距与码集合检、纠错能力的关系AB例：例：A=(00000)、B=(11111)，d0=5 结论：结论：e=4 或或 t=2 或或 e=3、t=1 d=1d=2d=39.3 常用的简单编码常用的简单编码9.3.1 奇偶监督码奇偶监督码9.3.2 正反码正反码 奇数监督码奇数监督码:偶数监督码偶数监

14、督码:监督码元监督码元 1 位位,使码组中使码组中“1”的个数为奇的个数为奇监督码元监督码元 1 位位,使码组中使码组中“1”的个数为偶的个数为偶只能检测奇数个错码只能检测奇数个错码二维奇偶监督码（矩阵码）二维奇偶监督码（矩阵码）能检测部分偶数个错码能检测部分偶数个错码 生成规则：生成规则：许用码组写成一行（包括信息码和许用码组写成一行（包括信息码和1 位位监督码），设共有监督码），设共有m 行。第行。第 m+1 行为按列行为按列增加的监督码。（构成监督码行）增加的监督码。（构成监督码行）例例9.3.1 奇偶监督码奇偶监督码一维奇偶监督码一维奇偶监督码 例例监督方程监督方程监督方程监督方程1a

15、aa02n1n 0aaa02n1n 信源信源发送信息码发送信息码a2 a1 监督码监督码a0晴晴0 00云云0 11阴阴1 01雨雨1 10例例:一维偶数监督码一维偶数监督码接收码组接收码组判别判别001、010、100010、001、111100、111、001111、100、010错错 1 位位检验满足检验满足0aaa012 检验检验不满足不满足0aaa012 只能检错，不能纠错只能检错，不能纠错m0m1n1011naaaa 2）当）当 同时出错，则按行按列均不能检测出有错。同时出错，则按行按列均不能检测出有错。能检测部分偶数个错码适用于突发信道。能检测部分偶数个错码适用于突发信道。若仅一

16、行有奇数个错码时，可通过列确定错码若仅一行有奇数个错码时，可通过列确定错码位置并纠正。位置并纠正。1）设）设 和和 发生错码，按行无法检测出错，而按列可检测。发生错码，按行无法检测出错，而按列可检测。22na 21aa2 a1 a00 0 00 1 11 0 11 1 00 0 0例例：二维偶数监督码二维偶数监督码通式通式02n1nm0m2nm1n2022n21n1012n11ncccaaaaaaaaa 结论：结论：方阵码除对构成矩形四角的错码无法检测外，方阵码除对构成矩形四角的错码无法检测外，其余均能检测。其余均能检测。特征：特征：具有纠正具有纠正 1 位错码、检测位错码、检测 2 位和大部

17、分位和大部分 2 位以上位以上错码的能力错码的能力定义：定义：信息码位数与监督码位数信息码位数与监督码位数相同相同 编码编码规则：规则：1)当信息位中有当信息位中有奇奇数个数个“1”时，监督位是信息位的重复。时，监督位是信息位的重复。2)当信息位中有当信息位中有偶偶数个数个“1”时，监督位是信息位的反码。时，监督位是信息位的反码。1 0 0 0 1 例：例：若信息码为若信息码为 1 1 0 0 1 9.3.2 正反码正反码 则正反码为则正反码为 1 1 0 0 1 1 1 0 0 11 0 0 0 1 0 1 1 1 01）将接收码组中信息码和监督码对应按位模）将接收码组中信息码和监督码对应按

18、位模2 加，得加，得合成码组合成码组2）根据接收码组中信息码含）根据接收码组中信息码含“1”的奇偶情况，由合成的奇偶情况，由合成码组生成码组生成校验码组校验码组 3）根据校验码组的值依表判断错码情况，并予检、纠错）根据校验码组的值依表判断错码情况，并予检、纠错译码译码规则：规则：“1”为奇为奇 校验校验=合成合成“1”为偶为偶 校验校验=合合成成例例例：发例：发 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

19、 0译码判决：译码判决：校验码组校验码组错码情况错码情况 1全全“0”无错码无错码 24 个个“1”1 个个“0”信息码中有一位错码，对应信息码中有一位错码，对应校验码组中的校验码组中的“0”的位置的位置 34 个个“0”1 个个“1”监督码中有一位错码，对应监督码中有一位错码，对应校验码组中的校验码组中的“1”的位置的位置 4其他组成其他组成 错码多于错码多于 1 个个 校验码组校验码组=合成码组合成码组=00000判断接收无错码判断接收无错码合成码组合成码组=1 0 0 0 1 1 1 0 0 10 1 0 0 0 信息码中含偶数个信息码中含偶数个“1”查表知信息码第二位错查表知信息码第二

20、位错10111 合合成成码码组组校校验验码码组组特征：特征：编码效率低编码效率低9.4 线性分组码线性分组码9.4.1 汉明码的编码原理汉明码的编码原理9.4.2 一般线性分组码的编码原理一般线性分组码的编码原理9.4.3 线性码分组码的数学描述线性码分组码的数学描述0aaa02n1n 9.4.1 汉明码的编码原理汉明码的编码原理定义：定义：能纠正一位错码，且能纠正一位错码，且编码效率较高编码效率较高的线性分组码的线性分组码问题：问题：在正反码中，为纠正一位错码，其监督码位数与信息码在正反码中，为纠正一位错码，其监督码位数与信息码位数一样多，能否减少监督码位数但纠错能力不变？位数一样多，能否减

21、少监督码位数但纠错能力不变？如何实现纠错？如何实现纠错？思路：思路：分组码分组码(n,k)只可能出现只可能出现 n 个一位错码事件，若某种逻个一位错码事件，若某种逻辑组合具有辑组合具有n 个状态，就能利用这种逻辑组合描述一位个状态，就能利用这种逻辑组合描述一位错码事件并予纠正。错码事件并予纠正。例：例：分析偶数监督码，寻找逻辑组合分析偶数监督码，寻找逻辑组合汉明码汉明码 监督方程监督方程 则接收时解码是在计算则接收时解码是在计算02n1naaaS 0 无错无错1 有错有错定义：定义：校正子校正子 S=只能表示出错只能表示出错不能描述错码位置不能描述错码位置一位监督码对应一位监督码对应一个监督方

22、程一个监督方程结论：若增加监督码元，建立多个监督方程，多个校正子就能形结论：若增加监督码元，建立多个监督方程，多个校正子就能形成逻辑组合描述错码位置成逻辑组合描述错码位置汉明码汉明码确定监督码元位数确定监督码元位数 r确定监督关系表确定监督关系表建立监督方程建立监督方程建立编码方程建立编码方程 分组码分组码(n,k)共需共需 n+1 个状态描述无错及个状态描述无错及 n 个有错事件个有错事件n12r 1n823 为提高编码效率，为提高编码效率，r 取最小值取最小值例：例：已知已知(7,4)码，码，r=3 共有共有3个监督方程，构成个监督方程，构成 3个校正子个校正子 S1 S2 S3S1 S2

23、 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例：已知例：已知(7,4)汉明码汉明码，求码组集合，求码组集合解：解：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 错错 监督方程监督方程0aaaa0aaaa0aaaa045613452356 编码方程编

24、码方程456034513562aaaaaaaaaaaa k=4，信息码组有信息码组有 16 个个a6 a5 a4 a3a2 a1 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 r=3例：例：汉明码的监督方程为汉明码的监督方程为 矩阵表达式矩阵表达式 000aaaaaa0011110010011110011011234569.4.2 一般线性分组码的编码原理（矩阵方程）一般线性分组码的编码原理（矩阵方程）0aaaa0aaaa0aaaa04561

25、3452356 记为：记为：0AHT H：监督矩阵：监督矩阵A：码组向量：码组向量111000101110101101100H0123456aaaaaaaA 当当 称称 H 为典型矩阵为典型矩阵（含单位阵）（含单位阵）rIPH 阶阶为为krP阶阶为为rrIr思路：思路：确定编码矩阵方程，确定编码矩阵方程，构造构造生成矩阵生成矩阵QIGk又又 根据监督方程确定了根据监督方程确定了编码方程编码方程34563456012aaaaPaaaa111001111101aaa456034513562aaaaaaaaaaaa 两边同取转置两边同取转置QaaaaPaaaaaaa3456T3456012阶阶其其中

26、中rkPQT构造构造生成矩阵生成矩阵GaaaaaaaaaaaA34560123456称称 G 为典型生成矩阵为典型生成矩阵（含单位阵）（含单位阵）编码矩阵方程编码矩阵方程特点：信息位不变，监督位附加于其后。特点：信息位不变，监督位附加于其后。定义定义系统码：由典型生成矩阵得出的码组系统码：由典型生成矩阵得出的码组 AQIGk生成矩阵生成矩阵0111000110010011100101010001G 中中每行均为一个码组，且线性无关每行均为一个码组，且线性无关nk TkPI译码运算，当译码运算，当TTH)EA(HBTTTHESSHEHAS 为校正子。说明为校正子。说明 S 与与E 间有确定的线性

27、关系间有确定的线性关系若若 E 的数目有限的数目有限，能与能与 S 一一对应，一一对应，则则 说明说明 S 能描述错码的位置，具有纠错能力。能描述错码的位置，具有纠错能力。9.4.3 线性码分组码的数学描述线性码分组码的数学描述令令 发码组为发码组为 A、收码组为、收码组为 B 错码图样错码图样 E=B-A收发码组的关系收发码组的关系THB0 无错无错1 有错有错 令令 B=E+A例例发码组发码组 A=1 1 0 0 0 1 0收码组收码组 B=1 0 0 0 0 1 0 译码运算译码运算例：例：(7,4)汉明码汉明码,111000101110101101100H001010100110011

28、111101)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(HET定义：定义：线性码中任意两个码组之和仍为这种码中的一个码组线性码中任意两个码组之和仍为这种码中的一个码组证：证：设设 A1 、A2 为线性码中两个许用码组为线性码中两个许用码组0HAT10HAT2两式相加两式相加0H)AA(HAHAT21T2T121AA 是许用码

29、组是许用码组推广：推广：1）两个码组间的距离必是另一码组的重量）两个码组间的距离必是另一码组的重量2）除）除 0 码组之外，码组的最小重量是码集合的最小距离码组之外，码组的最小重量是码集合的最小距离线性分组码具有线性分组码具有封闭性封闭性9.5 循环码循环码 9.5.1 码多项式码多项式9.5.2 循环码的特性循环码的特性9.5.3 循环码的编码方法循环码的编码方法码多项式的按模运算码多项式的按模运算9.5.1 码多项式码多项式码多项式码多项式定义：定义：以码组中各码元为系数的多项式以码组中各码元为系数的多项式T(x)=an-1 x n-1 +an-2 x n-2+.+a1 x+a0设设 多项

30、式多项式 F(x)、除数为、除数为 N(x)x(N)x(R)x(Q)x(N)x(F)x(R)x(F模模 N(x)运算运算注：注：多项式按模多项式按模 N(x)运算过程中，其系数按运算过程中，其系数按模模2 加加运算。运算。（系（系 数为二进制，只能取数为二进制，只能取 0 或或 1）。）。x 仅为码元位置仅为码元位置的标记的标记例例R(x)：余式余式例：例：(110 0101)T(x)=x 6 +x 5+x 2+1例：例：1x1xx324xxx1xx1x42431xx21xx1xx224解：解：记为：记为：余式余式定理：若定理：若 T(x)对应一个码长为对应一个码长为 n 的许用码组，的许用码

31、组，证：证：令令)x(T)x(Txi1xn模模02n2n1n1naxaxa)x(Ti01ni1ni1n1nixaxaxa)x(Tx1n1i1ni02ni2n1ni1n1xModiiaxaxaxaxaxTxn)()(T(x)的系数是的系数是 T(x)中系数向左循环移位中系数向左循环移位 i 次的结果次的结果9.5.2 循环码的特性循环码的特性码集合中任意一个码组，左移或右移一位得到的新码组码集合中任意一个码组，左移或右移一位得到的新码组必是该码集合中另一码组必是该码集合中另一码组循环码的定义循环码的定义循环码的码多项式循环码的码多项式则则 x i T(x)按模按模 x n+1 运算后运算后余式余

32、式T(x)仍为许用码组。仍为许用码组。例例例：例：(7,3)循环码循环码,码组为码组为(110 0101)，求码多项式，求码多项式T(x)；验证验证 x 3 T(x)按模按模 x 7+1 运算后余式仍是一个许用码组。运算后余式仍是一个许用码组。解：解：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)码组左移三位码组左

33、移三位循环码的生成矩阵循环码的生成矩阵 G9.5.3 循环码的编码方法循环码的编码方法思路：思路：确定编码矩阵方程，确定编码矩阵方程，构造构造生成矩阵生成矩阵码生成多项式码生成多项式 g(x)x(g)x(gx)x(gx)x(gx)x(G2k1k循环码的监督矩阵循环码的监督矩阵 H码生成多项式码生成多项式 g(x)的求解的求解QIGkTkPIrIPH 例例G 是是 G(x)的系数矩阵的系数矩阵循环码的检、纠错能力循环码的检、纠错能力与与 n、k 的值相关的值相关循环码的编码方法循环码的编码方法循环码循环码生成矩阵生成矩阵 G 的数学描述的数学描述0111000110010011100101010

34、001G已知已知(7,4)汉明码汉明码 G 中每行均为一个码组，且线性无关中每行均为一个码组，且线性无关是线性分组码的共性。是线性分组码的共性。nk 循环码是线性分组码成员之一，其循环码是线性分组码成员之一，其 G 除满足上述除满足上述特性外，每行之间必须满足特性外，每行之间必须满足循环性。循环性。循环码每个码组对应一个码多项式循环码每个码组对应一个码多项式 以最简方式寻找以最简方式寻找 k 个线性无关的码多项式就能建立个线性无关的码多项式就能建立 G(x)码生成多项式码生成多项式 g(x)定义：定义：g(x)是幂次为是幂次为(n-k)的码多项式。（唯一性）的码多项式。（唯一性）分析循环码：循

35、环码分析循环码：循环码(n,k)的形成方法是在信息码后加监督码的形成方法是在信息码后加监督码且保持移位循环的特征。且保持移位循环的特征。除全零码组外，权值最除全零码组外，权值最小的小的信息码组信息码组为为 0 0.0 0 1，且监督位，且监督位 a0 不可能不可能为零为零，否则循环数次后码组前，否则循环数次后码组前 k 位均为零，而监位均为零，而监督位不为零的情况，这不符合监督码的定义督位不为零的情况，这不符合监督码的定义结论：信息码组结论：信息码组 0 0.0 0 1 对应的码多项式必为对应的码多项式必为(n-k)次幂，且次幂，且常数项不等于零常数项不等于零 信息码组信息码组 0 0.0 0

36、 1 唯一唯一 码多项式唯一，且码多项式唯一，且幂次最低，记为幂次最低，记为 g(x)与与 g(x)线性无关的线性无关的 k-1 个个码多项式为码多项式为 x g(x)、.x k-1g(x)，可组成生成矩阵可组成生成矩阵 G(x)码生成多项式码生成多项式 g(x)的求解的求解定理：定理：g(x)是是 x n+1 的一个的一个(n-k)次因子。次因子。证：证：g(x)是幂次最低的码多项式是幂次最低的码多项式 任意一个码多项式任意一个码多项式 T(x)都是都是 g(x)倍数倍数令令 T(x)=h(x)g(x)1xxRxQ1xxgxnnk )()()(1xxT1n )(余式余式为码组为码组 x k

37、g(x)=x n+1+T(x)x n+1=x k g(x)+T(x)模模 2 加加=x k g(x)+h(x)g(x)=x k+h(x)g(x)得证得证例：已知例：已知(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)(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

38、(gx)x(G2k1k1xxxxxxxxxxx242352346 111010001110100011101G A=(a6 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 4）0 1 1 1 0 0 11 0 0 3）1 0 1 1 1 0 01 0 1 7）1 0 0 1 0 1 11 1 0 5）1 1 1 0 0 1 01 1 1 6）1 1 0 0 1 0 1 111010001110

39、100011101G 111010001110101101001 0001101001011101000111000110H 111010001110100011101)aaa(456监督方程：监督方程：0aaa356 0aaa245 0aaaa1456 0aaa046 d0=4 t=1 非系统码非系统码循环码的编码方法循环码的编码方法思路：思路：已知信息码组多项式已知信息码组多项式 m(x)，建立，建立T(x)编码步骤为：编码步骤为：1）生成）生成 x n-k m(x)2）生成）生成 x n-k m(x)/g(x)，求余式，求余式 r(x)3）生成循环码多项式）生成循环码多项式 T(x)T(

40、x)=x n-k m(x)+r(x)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 4）0 1 1 1 0 0 11 0 0 3）1 0 1 1 1 0 01 0 1 7）1 0 0 1 0 1 11 1 0 5）1 1 1 0 0 1 01 1 1 6）1 1 0 0 1 0 1例：例：m(x)=101 建立建立(7,3)循环码循环码解：解：x n-k m(x)=1010000g(x)=x 4+x 2+x+1 r(x)=x 3+x 2 T(x)=x 6+x 4+x 3+x 2码组为码组为 1011100 系统码系统码非系统码非系统码9.5.4 循环码的译码方法循环码的译码方法