1、南京理工大学南京理工大学通信工程系通信工程系Nanjing University of Science and TechnologyDepartment of Communication Engineering通信原理通信原理第八章第八章 差错控制编码差错控制编码Communication Principles Communication Principles Chapter 8 Channel Coding RUI YibinRUI Yibin 2012.04 2012.042/45差错控制编码差错控制编码n 数字通信系统数字通信系统数字信源数字调制噪声源解调终端信道编码器译码器同步信源编码
2、信道编码p数字通信系统的主要指标是数字通信系统的主要指标是有效性和可靠性有效性和可靠性p提高可靠性的措施提高可靠性的措施 针对加性干扰针对加性干扰n 调制解调方式、增大发射功率、加强天线方向性、提高接收机灵敏度等调制解调方式、增大发射功率、加强天线方向性、提高接收机灵敏度等n 信道编码（差错控制编码）信道编码（差错控制编码）p信道编码信道编码n 用适合信道传输的码进行传输，或对源码进行重编码，使不带规律性用适合信道传输的码进行传输，或对源码进行重编码，使不带规律性(或或规律性不强规律性不强)的数字信号变成的数字信号变成带上规律性带上规律性(或加强规律性或加强规律性)的数字信号的数字信号n 信道
3、译码器则利用这些规律性来鉴别是否发生错误，或进而纠错信道译码器则利用这些规律性来鉴别是否发生错误，或进而纠错n 信道编码与信道的统计特性有关信道编码与信道的统计特性有关在信息序列中在信息序列中加入加入监督码元监督码元Communication Principles Communication Principles Chapter 8 Channel Coding RUI YibinRUI Yibin 2012.04 2012.043/45差错控制编码差错控制编码n 信道根据加性干扰引起错码的分布规律进行分类信道根据加性干扰引起错码的分布规律进行分类 p随机信道随机信道n 信道中错码是随机的信道
4、中错码是随机的,且统计独立；且统计独立；（如高斯白噪声引起错码）（如高斯白噪声引起错码）p突发信道突发信道n 信道中错码成串集中出现；信道中错码成串集中出现；（如脉冲干扰引起错码）（如脉冲干扰引起错码）p混合信道混合信道n 信道中同时存在随机错误和突发错码，且都不能忽略不计信道中同时存在随机错误和突发错码，且都不能忽略不计 n 常用的差错控制技术常用的差错控制技术p检错重发检错重发p前向纠错前向纠错p反馈校验法反馈校验法不同类型的不同类型的信道应该采信道应该采用不同的差用不同的差错控制技术错控制技术检错码判决信号发收纠错码发收信息信号信息信号收发（典型为（典型为ARQ）p检错删除检错删除检错码
5、发收Communication Principles Communication Principles Chapter 8 Channel Coding RUI YibinRUI Yibin 2012.04 2012.044/45本章的主要内容本章的主要内容n 8.1 纠错编码的基本原理纠错编码的基本原理n 8.2 常用的简单编码常用的简单编码n 8.3 线性分组码线性分组码n 8.4 循环码循环码n 8.5 卷积码卷积码Communication Principles Communication Principles Chapter 8 Channel Coding RUI YibinRUI
6、 Yibin 2012.04 2012.045/45本章的主要内容本章的主要内容n 8.1 纠错编码的基本原理纠错编码的基本原理n 8.2 常用的简单编码常用的简单编码n 8.3 线性分组码线性分组码n 8.4 循环码循环码n 8.5 卷积码卷积码Communication Principles Communication Principles Chapter 8 Channel Coding RUI YibinRUI Yibin 2012.04 2012.046/458.1 纠错编码的基本原理纠错编码的基本原理雹雾霜雪雨阴云晴111011101001110010100000种许使用种中只准4
7、8码组许用码组，其它为禁用雨阴云晴 011101110000许用码组中，只要错一位许用码组中，只要错一位(不管哪位错不管哪位错)，就是禁用码组，故这种编码能发现，就是禁用码组，故这种编码能发现任何一位出错，但不能发现的二位出任何一位出错，但不能发现的二位出错，二位出错后又产生许用码。错，二位出错后又产生许用码。其中的任一码组在传输中其中的任一码组在传输中若发生一个或多个错码，若发生一个或多个错码，就会变成另一信息码，接就会变成另一信息码，接收端无法发现错误。收端无法发现错误。这样的码组也不能这样的码组也不能纠正错纠正错误，因为误，因为“晴晴”“”“雨雨”“”“阴阴”错一位，都可能变成错一位，都
8、可能变成“100”1 1 1 0 0 0雨晴若把若把8种组合（种组合（3位编位编码）中，只取码）中，只取2种为种为许用码，其它许用码，其它6种为种为禁用码，则可纠错禁用码，则可纠错例：收到禁用码组例：收到禁用码组“100”时，如认时，如认为只有一位错，则可判断此错码为只有一位错，则可判断此错码发生在第发生在第1位，从而纠正为位，从而纠正为“000”(晴晴)，因为，因为“111”(雨雨)发生任何一个发生任何一个错误都不会变成错误都不会变成“100”。信息位信息位监督位监督位p 这种将信息码分组，为每组信码附加若干监督码的编码集合，称为这种将信息码分组，为每组信码附加若干监督码的编码集合，称为分分
9、组码组码。信息位信息位监督位监督位Communication Principles Communication Principles Chapter 8 Channel Coding RUI YibinRUI Yibin 2012.04 2012.047/458.1 纠错编码的基本原理纠错编码的基本原理n 几个重要的参数几个重要的参数p分组码一般用符号分组码一般用符号(n,k)表示，表示，n k是每个码组二进制信息码元的数目，是每个码组二进制信息码元的数目，n n是编码组的总位数，又称为码组长度（是编码组的总位数，又称为码组长度（码长码长）。）。n n-k=r为每码组中的监督码元数目，称监督位
10、数目。为每码组中的监督码元数目，称监督位数目。p码重码重：在分组码中，在分组码中，“1”的数目称为码组的重量，简称码重。的数目称为码组的重量，简称码重。n 例如，码组（例如，码组（1 1 0 1 0），码长），码长 n=5，码重为，码重为3。p码距码距：把两个码组对应位不同的数目称为这两个码组的距离，简称：把两个码组对应位不同的数目称为这两个码组的距离，简称码距，又称码距，又称汉明（汉明（Hamming）距离）距离。n 例如，码组（例如，码组（1 1 0 0 0）与（）与（1 0 0 1 1）的距离为）的距离为 3。1001111000p最小码距最小码距：码组集合中，：码组集合中，全体全体码组
11、之间的距离的最码组之间的距离的最小值称为最小码距小值称为最小码距(d0)。011101110000雨阴云晴 1 1 1 0 0 0雨晴30d20dCommunication Principles Communication Principles Chapter 8 Channel Coding RUI YibinRUI Yibin 2012.04 2012.048/45n 圆上离圆上离 B 距离最近的码组是距离最近的码组是A。AB0d8.1 纠错编码的基本原理纠错编码的基本原理n 分组码的检错、纠错能力与最小码距的关系分组码的检错、纠错能力与最小码距的关系p分组码能检测分组码能检测 e 个错码
12、，所要求的最小码距个错码，所要求的最小码距 d0？en 设有两个许用码设有两个许用码A、B，它们的码距为，它们的码距为d0。n 若若 A 发生发生 e 个错误，则得到的码组与个错误，则得到的码组与A的的距离为距离为e，即该码组落在以，即该码组落在以A为圆心，半径为圆心，半径为为 e 的圆上。的圆上。n 若要译码器不将若要译码器不将A 错判成错判成B，必须有：，必须有：1,BAd1,0eBAdd即：为检测为检测 e 个错码，要求最小码距个错码，要求最小码距 d0 应不小于应不小于 e+1ACommunication Principles Communication Principles Chap
13、ter 8 Channel Coding RUI YibinRUI Yibin 2012.04 2012.049/458.1 纠错编码的基本原理纠错编码的基本原理p分组码能纠正分组码能纠正 t 个错码，所要求最小码距个错码，所要求最小码距 d0？tn 设有两个许用码设有两个许用码A、B，它们的码距为，它们的码距为d0。n 若若 A 发生发生 t 个错误，则得到的码组与个错误，则得到的码组与A的的距离为距离为t，即该码组落在以，即该码组落在以A为圆心，半径为圆心，半径为为 t 的圆上。的圆上。n 这时，离这时，离 B 距离最近的码组是距离最近的码组是A。n 根据根据最大似然的译码准则最大似然的译
14、码准则，要想使译码器，要想使译码器将将A正确译成正确译成A，必须，必须A 离离A比离比离B近。近。BAdAAd,BAdAAdd,0即：为纠正为纠正 t 个错码，要求最小码距个错码，要求最小码距 d0 应不小于应不小于 2t+1t0dABAt1 t1tt12 tn 分组码的检错、纠错能力与最小码距的关系分组码的检错、纠错能力与最小码距的关系Communication Principles Communication Principles Chapter 8 Channel Coding RUI YibinRUI Yibin 2012.04 2012.0410/458.1 纠错编码的基本原理纠错编
15、码的基本原理p分组码能纠正分组码能纠正 t 个错码，同时检个错码，同时检 e 个错码，所要求的最小码距个错码，所要求的最小码距 d0？en 设有两个许用码设有两个许用码A、B，它们的码距为，它们的码距为d0。n 若若 A 发生发生 e 个错误，则得到码组落在以个错误，则得到码组落在以A为为圆心，半径为圆心，半径为 e 的圆上。这时，离的圆上。这时，离 B 距离距离最近的码组是最近的码组是A。n A离离B的距离必须至少为的距离必须至少为t+1，否则，否则，A将将进入进入B的纠错能力范围内，而被错纠为的纠错能力范围内，而被错纠为B。BAdAAdd,0即：为纠正为纠正 t 个错码，同时检测个错码，同
16、时检测 e 个错码，最小码距个错码，最小码距 d0 应不小于应不小于 e+t+1t0dABA1ten 分组码的检错、纠错能力与最小码距的关系分组码的检错、纠错能力与最小码距的关系在某些情况下，要求对于出现较频繁但错码数很少的码组，按前向纠错方式工作，以在某些情况下，要求对于出现较频繁但错码数很少的码组，按前向纠错方式工作，以节省反馈重发的时间。同时又希望对一些错码数较多的码组，在超过该码的纠错能力节省反馈重发的时间。同时又希望对一些错码数较多的码组，在超过该码的纠错能力后，能检测出来，再按检错重发方式工作。这种工作方式称为后，能检测出来，再按检错重发方式工作。这种工作方式称为纠检结合纠检结合。
17、Communication Principles Communication Principles Chapter 8 Channel Coding RUI YibinRUI Yibin 2012.04 2012.0411/458.1 纠错编码的基本原理纠错编码的基本原理n 结论结论：分组码纠错、检错能力决定于最小码距：分组码纠错、检错能力决定于最小码距d0p检错能力：检错能力：p纠错能力：纠错能力：10 de21int0dt 011101110000雨阴云晴 1 1 1 0 0 0雨晴30d20d110 de能检一位错码能检一位错码210 de121int0dt能检能检 2 位错码位错码能纠
18、能纠 1 位错码位错码Communication Principles Communication Principles Chapter 8 Channel Coding RUI YibinRUI Yibin 2012.04 2012.0412/458.1 纠错编码的基本原理纠错编码的基本原理n 纠错编码的效用纠错编码的效用p设随机信道中发送设随机信道中发送“0”、“1”时的错误概率均为时的错误概率均为 p(p1)，则在码长，则在码长为为 n 的码组中有的码组中有r 位发生错码的概率为：位发生错码的概率为：rnrrnnppCrP1时，当3107pnrprnrn!3710771pP 527101
19、.2212pP 837105.3353pPp可见，采用纠错编码，即使仅能纠正（或检测）码组中可见，采用纠错编码，即使仅能纠正（或检测）码组中 12 个错误，个错误，也可以使误码率下降几个数量级。也可以使误码率下降几个数量级。Communication Principles Communication Principles Chapter 8 Channel Coding RUI YibinRUI Yibin 2012.04 2012.0413/45本章的主要内容本章的主要内容n 8.1 纠错编码的基本原理纠错编码的基本原理n 8.2 常用的简单编码常用的简单编码n 8.3 线性分组码线性分组码
20、n 8.4 循环码循环码n 8.5 卷积码卷积码Communication Principles Communication Principles Chapter 8 Channel Coding RUI YibinRUI Yibin 2012.04 2012.0414/458.2 常用的简单编码常用的简单编码n 奇偶校验码奇偶校验码p奇偶校验码分为奇偶校验码分为奇校验码奇校验码、偶校验码偶校验码两种两种p编码规则编码规则 无论信息位有多少，只有无论信息位有多少，只有一位监督位一位监督位，且对，且对an-1 an-2 a1 a0的码组，有的码组，有如下监督关系：如下监督关系：0021aaann
21、偶校验：1021aaann奇校验：n 如：对信息码组如：对信息码组 11001 进行偶校验编码进行偶校验编码校验位校验位信息位信息位1 1 0 0 10p检错能力检错能力n 能检测奇数位错误能检测奇数位错误。1Communication Principles Communication Principles Chapter 8 Channel Coding RUI YibinRUI Yibin 2012.04 2012.0415/458.2 常用的简单编码常用的简单编码n 二维奇偶校验码二维奇偶校验码行监督位行监督位列监督位列监督位01100110100010p检纠错能力检纠错能力n 能检测奇
22、数位错误及部分偶数位错误（如：能检测奇数位错误及部分偶数位错误（如：4位错码构成矩形位错码构成矩形不能不能检测）检测）n 当码组中仅在当码组中仅在一行一行有奇数个错误时，能够确定错码的位置，从而实现纠有奇数个错误时，能够确定错码的位置，从而实现纠错错n 适于检测适于检测突发错误突发错误0011p又称方阵码，将奇偶校验码按行组成矩阵，然后在列方向增加第二维又称方阵码，将奇偶校验码按行组成矩阵，然后在列方向增加第二维奇偶校验位。奇偶校验位。001111100001110011111001010111110011Communication Principles Communication Princ
23、iples Chapter 8 Channel Coding RUI YibinRUI Yibin 2012.04 2012.0416/458.2 常用的简单编码常用的简单编码n 恒比码恒比码p每个码组均含有相同数目的每个码组均含有相同数目的“1”和和“0”。由于。由于“1”的数目与的数目与“0”的数的数目之比保持恒定，所以称为恒比码。目之比保持恒定，所以称为恒比码。n 例如，我国电传机传输阿拉伯数字时，用例如，我国电传机传输阿拉伯数字时，用5位代码表示，每个码组的长位代码表示，每个码组的长度为度为5，其中恒有，其中恒有3个个“1”，称为，称为“5中取中取3”恒比码。恒比码。阿拉伯数字阿拉伯数
24、字保护电码保护电码阿拉伯数字阿拉伯数字保护电码保护电码123450101111001101101101000111678901010111100011101001101101p主要优点主要优点 简单，适于用来传输电传机或其它键盘设备产生的字母和符号。简单，适于用来传输电传机或其它键盘设备产生的字母和符号。p检错能力检错能力 能检测所有奇数个错误和部分偶数个错误（除去能检测所有奇数个错误和部分偶数个错误（除去“0”、“1”对换外对换外的偶数个错误都可检测）。的偶数个错误都可检测）。Communication Principles Communication Principles Chapter
25、8 Channel Coding RUI YibinRUI Yibin 2012.04 2012.0417/458.2 常用的简单编码常用的简单编码n 正反码正反码p正反码的监督位与信息位数目相同。监督码元与信息码元相同或相正反码的监督位与信息位数目相同。监督码元与信息码元相同或相反，由信息码中反，由信息码中“1”的个数决定。的个数决定。p正反码是一种简单的能纠错的编码，长度为正反码是一种简单的能纠错的编码，长度为10的正反码具有纠正的正反码具有纠正1位错位错码的能力，并能检测全部两位以下的错码和大部分两位以上的错码。码的能力，并能检测全部两位以下的错码和大部分两位以上的错码。p电报通信中的正
26、反码电报通信中的正反码n 信息位段有信息位段有奇数奇数个个1 1 1 0 0 1 1 1 0 0 1 （监督位与信息位（监督位与信息位重复重复）n 信息位段有信息位段有偶数偶数个个1 1 0 0 0 1 0 1 1 1 0 （监督位是信息位（监督位是信息位反码反码）Communication Principles Communication Principles Chapter 8 Channel Coding RUI YibinRUI Yibin 2012.04 2012.0418/45本章的主要内容本章的主要内容n 8.1 纠错编码的基本原理纠错编码的基本原理n 8.2 常用的简单编码常用
27、的简单编码n 8.3 线性分组码线性分组码n 8.4 循环码循环码n 8.5 卷积码卷积码Communication Principles Communication Principles Chapter 8 Channel Coding RUI YibinRUI Yibin 2012.04 2012.0419/458.3 线性分组码线性分组码n 基本概念基本概念0021aaann偶校验：p代数码和线性分组码代数码和线性分组码n 建立在代数关系基础上的编码称代数码建立在代数关系基础上的编码称代数码 n 可用线性方程组（代数关系）表述码的规律性的分组码称为线性分组码可用线性方程组（代数关系）表述
28、码的规律性的分组码称为线性分组码p编码与监督编码与监督n 偶校验码在接收端实际上计算代数关系式偶校验码在接收端实际上计算代数关系式 S=an-1 an-2 a0n 如果监督位增加到二位，就能增加一个类似于偶校验码的如果监督位增加到二位，就能增加一个类似于偶校验码的新新的监督式的监督式n 两个监督式的两个校正子有两个监督式的两个校正子有4种可能的组合：种可能的组合：00,01,10,11。若用。若用1种组种组合表示无错，其余合表示无错，其余3种组合就可以用来表示一位错码的种组合就可以用来表示一位错码的3种不同位置。种不同位置。n 同理，同理，r个监督式能指示一位错码的个监督式能指示一位错码的2r
29、-1个可能位置。个可能位置。n 对于线性分组码对于线性分组码(n,k)，监督位数，监督位数r=n-k，如果希望用，如果希望用r个监督关系式指示个监督关系式指示一位错码一位错码的的n种可能的位置，则要求种可能的位置，则要求监督关系式监督关系式校正子校正子nr1212rkr有错，无错 1 ,0只能发现错误，不只能发现错误，不能指示错误位置能指示错误位置汉明码的诞生汉明码的诞生Communication Principles Communication Principles Chapter 8 Channel Coding RUI YibinRUI Yibin 2012.04 2012.0420/4
30、58.3.1 汉明码汉明码n 基本概念基本概念 p线性分组码线性分组码(n,k)，监督位，监督位r=n-k，若满足，若满足n=2r-1，则称其为，则称其为汉明码汉明码p汉明码是能够汉明码是能够纠正一位错码纠正一位错码且编码效率最高的一种线性分组码。且编码效率最高的一种线性分组码。n 监督关系式的构造监督关系式的构造p以以(n,k)=(7,4)的汉明码的汉明码(r=3)为例，现规定为例，现规定3个校正子的组合个校正子的组合S1,S2,S3错码位置错码位置S1,S2,S3错码位置错码位置0 0 1a01 0 1a40 1 0a11 1 0a51 0 0a21 1 1a60 1 1a30 0 0无无
31、 错错034631356224561aaaaSaaaaSaaaaS 监督位的取值应使：监督位的取值应使：S1S2S3=000，所以监督关系式为所以监督关系式为000034613562456aaaaaaaaaaaa346035614562aaaaaaaaaaaa用码率用码率R衡量，衡量，Rk/nCommunication Principles Communication Principles Chapter 8 Channel Coding RUI YibinRUI Yibin 2012.04 2012.0421/458.3.1 汉明码汉明码n 编码原理编码原理信息位信息位a6a5a4a3监督位
32、监督位a2a1a0信息位信息位a6a5a4a3监督位监督位a2a1a00000000100011100010111001100001010110100100011110101100101001101100001010110111010100110011111010001110001111111346035614562aaaaaaaaaaaap给定信息位后，根据监督给定信息位后，根据监督关系可以算出监督位。关系可以算出监督位。p接收端收到码组后，先计算接收端收到码组后，先计算出校正子出校正子S1S2S3，再按规定，再按规定判断有无错码或错码位置，判断有无错码或错码位置，最后纠正错码。最后纠正错码
33、。0000011接收码组：S1,S2,S3错码位置错码位置S1,S2,S3错码位置错码位置0 0 1a01 0 1a40 1 0a11 1 0a51 0 0a21 1 1a60 1 1a30 0 0无无 错错034631356224561aaaaSaaaaSaaaaS011321：SSS0001011纠正后码组：a3出错出错Communication Principles Communication Principles Chapter 8 Channel Coding RUI YibinRUI Yibin 2012.04 2012.0422/458.3.1 汉明码汉明码n(7,4)汉明码汉明
34、码信息位信息位a6a5a4a3监督位监督位a2a1a0信息位信息位a6a5a4a3监督位监督位a2a1a00000000100011100010111001100001010110100100011110101100101001101100001010110111010100110011111010001110001111111p最小码距最小码距 d0=3p检错能力检错能力 e=d01=2p纠错能力纠错能力 t=int(d01)/2=1p编码效率编码效率1212rrrnkR121rr。接近很大时，1RnCommunication Principles Communication Princip
35、les Chapter 8 Channel Coding RUI YibinRUI Yibin 2012.04 2012.0423/458.3.2 线性分组码的一般原理线性分组码的一般原理n 监督矩阵和生成矩阵监督矩阵和生成矩阵线性分组码的编码线性分组码的编码p将上述汉明码将上述汉明码(7,4)的监督关系式改写的监督关系式改写010011010010101100010111012345601234560123456aaaaaaaaaaaaaaaaaaaaa“+”均为均为模模2加加 ）（模20001001101010101100101110123456aaaaaaaTTAHO0 THA或1001
36、10101010110010111Hnr3456aaaa012aaar k 阶矩阵阶矩阵Pr r 阶单位方阵阶单位方阵IrrPI 具有具有PIr形式的形式的H 矩阵矩阵称为称为典型监督矩阵典型监督矩阵HATp监督矩阵监督矩阵Communication Principles Communication Principles Chapter 8 Channel Coding RUI YibinRUI Yibin 2012.04 2012.0424/458.3.2 线性分组码的一般原理线性分组码的一般原理n 监督矩阵和生成矩阵监督矩阵和生成矩阵p把监督关系式改写为：把监督关系式改写为：3460356
37、1456233445566aaaaaaaaaaaaaaaaaaaa345601234561101101101111000010000100001aaaaaaaaaaa3456aaaaGATTGaaaaA34561101000101010001100101110001Gk r 阶矩阵阶矩阵Q Q=PTk k 阶单阶单位方阵位方阵IkQIk 具有具有IkQ形式的形式的G 矩阵矩阵称为典型生成矩阵称为典型生成矩阵GTp生成矩阵生成矩阵 这种前这种前k位是信息码元，后位是信息码元，后r位是监督码元位是监督码元(附加于信息码附加于信息码元之后元之后)的码称为的码称为系统码系统码。TkrPIGIPH100
38、110101010110010111HCommunication Principles Communication Principles Chapter 8 Channel Coding RUI YibinRUI Yibin 2012.04 2012.0425/458.3.2 线性分组码的一般原理线性分组码的一般原理n 校正子校正子S（伴随式）（伴随式）线性分组码的译码线性分组码的译码p设发送码组为：设发送码组为：A=an-1,an-2,a1,a0 接收码组为：接收码组为：B=bn-1,bn-2,b1,b0p发送码组与接收码组之差发送码组与接收码组之差(称称错误图样错误图样)为：为：E=A B
39、=en-1,en-2,e1,e0模模2操作操作bi=ai 时时,ei=0,正确正确bi ai 时时,ei=1,错码错码EABp令令S=B H T，S为校正子，也称为校正子，也称伴随式伴随式 THBSTEHTHEA)(TTEHAH 0 由此可见由此可见，校正子，校正子S与错误图样与错误图样E 间有确定间有确定的线性变换关系，若的线性变换关系，若S和和E之间一一对应，则之间一一对应，则S将能代表错码的位置。将能代表错码的位置。p接收端译码器的任务接收端译码器的任务n 根据接收码组根据接收码组 B 计算校正子计算校正子 S=BHT；n 从校正子从校正子S 确定错误图样；确定错误图样；n 从接收到的码
40、字中减去错误图样从接收到的码字中减去错误图样E。n 线性分组码具有封闭性线性分组码具有封闭性 错误错误码位码位错误图样错误图样校正子校正子 en-1,en-2,e1,e0S2,S1,S0 0 0 0 0 0 0 00 0 0b0 0 0 0 0 0 0 10 0 1b1 0 0 0 0 0 1 00 1 0b2 0 0 0 0 1 0 01 0 0b3 0 0 0 1 0 0 00 1 1b4 0 0 1 0 0 0 01 0 1b5 0 1 0 0 0 0 01 1 0b6 1 0 0 0 0 0 01 1 1码集中任两个码字模码集中任两个码字模二加后仍在码集中二加后仍在码集中Communi
41、cation Principles Communication Principles Chapter 8 Channel Coding RUI YibinRUI Yibin 2012.04 2012.0426/45本章的主要内容本章的主要内容n 8.1 纠错编码的基本原理纠错编码的基本原理n 8.2 常用的简单编码常用的简单编码n 8.3 线性分组码线性分组码n 8.4 循环码循环码n 8.5 卷积码卷积码Communication Principles Communication Principles Chapter 8 Channel Coding RUI YibinRUI Yibin 2
42、012.04 2012.0427/458.4 循环码循环码n 循环码的特点循环码的特点p循环码是一种分组的线性系统码循环码是一种分组的线性系统码p循环码除了有线性分组码的封闭性外，还有循环性循环码除了有线性分组码的封闭性外，还有循环性码集中任一码循环移码集中任一码循环移位后仍在码集中位后仍在码集中),(,0121knaaaaAnn码集若12101,aaaaAn循环右移一位：),(kn码集10322,nnnaaaaA循环左移一位：),(kn码集p是一类重要的线性分组码，比较方便用移位寄存器实现编码和译码是一类重要的线性分组码，比较方便用移位寄存器实现编码和译码信息位信息位a6a5a4监督位监督位
43、a3a2a1a0信息位信息位a6a5a4监督位监督位a3a2a1a000000001001011001011110111000101110110010101110011110010n(7,3)循环码的码集循环码的码集n 通常为了研究方便，我们用通常为了研究方便，我们用代数多项式代数多项式来表示码字。来表示码字。右移右移1位位Communication Principles Communication Principles Chapter 8 Channel Coding RUI YibinRUI Yibin 2012.04 2012.0428/458.4.1 码多项式码多项式n 码多项式的基本
44、概念码多项式的基本概念p用以表示码字的一个用以表示码字的一个代数多项式代数多项式称为码多项式。称为码多项式。0121,),(aaaaAknnn循环码的一个码字为：012211axaxaxaxAnnnn对应的码多项式为：多项式的系多项式的系数数ai对应于对应于码元的值。码元的值。p码左移一位，对应于码多项式乘以码左移一位，对应于码多项式乘以 x 1,0,1,1,1,0,01A0,1,0,1,1,1,03A 1 2341xxxxA xxxxxA3453 xxAxA13n 码多项式的按模运算码多项式的按模运算p若一任意多项式若一任意多项式F(x)被一个被一个n 次多项式次多项式N(x)除，得到商式除
45、，得到商式Q(x)和一个和一个次数小于次数小于n的余式的余式R(x)，即，即 xRxQxNxF 则称则称R(x)为为F(x)关于关于N(x)按模运算的结果，按模运算的结果，xNxRxF模 p例例124 xx13xxxx 412 xx1 113224xxxxx模最高次幂最高次幂为为x n-1左移一位左移一位Communication Principles Communication Principles Chapter 8 Channel Coding RUI YibinRUI Yibin 2012.04 2012.0429/458.4.2 生成多项式与生成矩阵生成多项式与生成矩阵n 生成多项式
46、生成多项式p在在(n,k)循环码码集所对应的码多项式中，循环码码集所对应的码多项式中，唯一唯一的一个的一个常数项不为常数项不为0的的(n-k)次次多项式多项式g(x)称为该循环码的生成多项式称为该循环码的生成多项式信息位信息位a6a5a4监督位监督位a3a2a1a0信息位信息位a6a5a4监督位监督位a3a2a1a000000001001011001011110111000101110110010101110011110010 例：例：(7,3)循环码的生成多项式循环码的生成多项式 124xxxxg xgxxgxgxxgxxGkk21p循环码的码多项式循环码的码多项式都是都是生成多生成多项式的
47、项式的倍式倍式 xQxgxAin 生成矩阵生成矩阵Gp将生成多项式将生成多项式逐次移位逐次移位，得到，得到k个线性无关个线性无关的码多项式，将它们构成矩的码多项式，将它们构成矩阵，称为生成多项式矩阵阵，称为生成多项式矩阵G(x)，其系数就是生成矩阵，其系数就是生成矩阵G。例：例：(7,3)循环码的循环码的生成多项式矩阵和生成矩阵生成多项式矩阵和生成矩阵 xgxxgxgxxG21242352346xxxxxxxxxxx001011101011101011100GCommunication Principles Communication Principles Chapter 8 Channel
48、Coding RUI YibinRUI Yibin 2012.04 2012.0430/458.4.3 如何寻找如何寻找(n,k)循环码的生成多项式循环码的生成多项式n 对于对于(n,k)循环码，将循环码，将xn+1因式分解因式分解(系数模二运算系数模二运算)，其中最高，其中最高幂次数为幂次数为r=n-k，且常数项为，且常数项为1的因子多项式，就是的因子多项式，就是(n,k)循环码循环码的生成多项式。的生成多项式。p例：例：x7+1因式分解因式分解11113237xxxxxx 为了求为了求(7,3)循环码的生成多项式，就要在上式中找一个最高幂次数为循环码的生成多项式，就要在上式中找一个最高幂次
49、数为r=n-k=4，且常数项为，且常数项为1的因子。这样的因子有两个：的因子。这样的因子有两个：1112343xxxxxx1112423xxxxxx 这两个多项式这两个多项式都可以都可以作为生成多项式用，作为生成多项式用，但但不同生成多项式所产生的不同生成多项式所产生的循环码码组也不同循环码码组也不同。Communication Principles Communication Principles Chapter 8 Channel Coding RUI YibinRUI Yibin 2012.04 2012.0431/458.4.4 系统循环码的编码电路系统循环码的编码电路p若若k位信息码
50、为：位信息码为：M=mk-1,mk-2,m1,m0，则，则信息码多项式信息码多项式为：为：012211mxmxmxmxmkkkk xrxmxxAkn系统码：码多项式码多项式 xgxmxAp系统码（系统码（前前k 位是信息码元，后位是信息码元，后r 位是监督码元位是监督码元）的生成矩阵是典型生成）的生成矩阵是典型生成矩阵，具有矩阵，具有IkQ的形式。的形式。由生成多项式矩阵直接得到的生成矩阵不具由生成多项式矩阵直接得到的生成矩阵不具有这样的形式，不是系统码有这样的形式，不是系统码。xrxmxxAkn xgxrxgxmxxAkn mod mod r(x)的最高次是的最高次是r 1，g(x)的最高次
