CH13差错控制和信道编码课件.ppt

1、2023年1月30日13时01分兰州大学信息科学与工程学院电信、通信工程系通通 信信 原原 理理 兰州大学信息科学与技术学院电信系兰州大学信息科学与技术学院电信系M.P:M.P:+86-0931-6161799+86-0931-6161799Email:Email: oror AddressAddress：Department of Electronics&Information Science,School of Information Science&Engineering,Lanzhou University,Tianshui Southern Road 222#，Gansu Provi

2、nce，P.R.ChinaPrinciples of Communications2023年1月30日13时01分兰州大学信息科学与工程学院电信、通信工程系2 第十三章第十三章 差错控制和信道编码差错控制和信道编码主要内容提要：主要内容提要：差错控制方式及信道编码的基本概念差错控制方式及信道编码的基本概念 线性分组码线性分组码 循环码循环码 卷积码卷积码 其它信道编码简介其它信道编码简介2023年1月30日13时01分兰州大学信息科学与工程学院电信、通信工程系3 本章的教学基本要求本章的教学基本要求 本章要求本章要求掌握掌握差错控制的基本方式、差错控制的基本方式、信道编码的一些基本概念、线性分

3、组码信道编码的一些基本概念、线性分组码特性及其设计、循环码特性及其设计、特性及其设计、循环码特性及其设计、卷积码特性及其设计；其余的内容可根卷积码特性及其设计；其余的内容可根据学时情况酌情加以了解即可。据学时情况酌情加以了解即可。2023年1月30日13时01分兰州大学信息科学与工程学院电信、通信工程系4 在实际信道上传输数字信号时，由于信道传输特在实际信道上传输数字信号时，由于信道传输特性不理想以及加性噪声的影响，接收端所收到的性不理想以及加性噪声的影响，接收端所收到的数字信号不可避免地会发生错误。数字信号不可避免地会发生错误。产生差错的原因产生差错的原因信道的电气特性引起信号幅度、频率、相

4、位的畸变；信道的电气特性引起信号幅度、频率、相位的畸变；信号反射；信号反射；串扰；串扰；闪电、大功率电机的启停产生脉冲干扰等。闪电、大功率电机的启停产生脉冲干扰等。一般说来，一般说来，线路传输差错是不可避免的，但要线路传输差错是不可避免的，但要尽量减小其影响。尽量减小其影响。1.1.引言引言2023年1月30日13时01分兰州大学信息科学与工程学院电信、通信工程系5 1.1.引引 言言信道差错的几种模式信道差错的几种模式随机差错随机差错：差错的出现是随机的，一般而言差错出现的位置是随机分布的。这种情况一般是由信道的加性随机噪声引起的。一般将这种信道称为随机信道随机信道。突发差错突发差错：差错的

5、出现是一连串出现的。这种情况如移动通信中信号在某一段时间内发生衰落，造成一串差错；光盘上的一条划痕等等。这样的信道我们称之为突发突发信道信道。混合差错混合差错：既有突发错误又有随机差错的情况。这种信道称之为混合信道混合信道。2023年1月30日13时01分兰州大学信息科学与工程学院电信、通信工程系6 1.1.引引 言言降低误码的技术措施：降低误码的技术措施：为了在已知信噪比情况下达到一定的误比特为了在已知信噪比情况下达到一定的误比特率指标，首先应该合理设计基带信号，选择调率指标，首先应该合理设计基带信号，选择调制解调方式，采用时域制解调方式，采用时域/频域均衡，使误比特频域均衡，使误比特率尽可

6、能降低。率尽可能降低。但若误比特率仍不能满足要求，则必须采用但若误比特率仍不能满足要求，则必须采用信道编码信道编码（即（即差错控制编码差错控制编码），将误比特率进，将误比特率进一步降低，以满足系统指标要求。一步降低，以满足系统指标要求。随着差错控制编码理论的完善和数字电路技术随着差错控制编码理论的完善和数字电路技术的发展，信道编码已经成功地应用于各种通信的发展，信道编码已经成功地应用于各种通信系统中，并且在计算机、磁记录与存储中也得系统中，并且在计算机、磁记录与存储中也得到日益广泛的应用。到日益广泛的应用。2023年1月30日13时01分兰州大学信息科学与工程学院电信、通信工程系7 1.1.引

7、引 言言我们研究的是编码和译码，所以完全可以将调我们研究的是编码和译码，所以完全可以将调制、解调与信道合起来等效成一个等效信道制、解调与信道合起来等效成一个等效信道编码信道编码信道。编码信道根据调制解调的不同输入和输出具有编码信道根据调制解调的不同输入和输出具有不同的类型不同的类型离散无记忆对称二进制输入二进制输出信道（BSC）离散无记忆二进制输入多进制输出信道离散无记忆多进制输入多进制输出离散无记忆二进制输入连续输出离散有记忆信道编码信道编码信道信源编编码码调制信道解调译译码码信宿2023年1月30日13时01分兰州大学信息科学与工程学院电信、通信工程系8 1.1.引引 言言信道编码的目的信

8、道编码的目的：改善数字通信系统的传输质量信道编码信道编码(差错控制编码差错控制编码)的基本思路的基本思路：在发送端将被传输的信息附上一些监督码元，这些冗余的码元与信息码元之间以某种确定的规则某种确定的规则相互关联（约束）。接收端按照既定的规则校验信息码元与监督码元之间的关系，一旦传输发生差错，则信息码元与监督码元的关系就受到破坏，从而接收端可以发现错误乃至纠正错误。信道编码的任务信道编码的任务：构造出以最小多余度（冗余度）代价换取最大抗干扰性能的“好码”。研究各种编码和译码方法是信道编码所要解决的研究各种编码和译码方法是信道编码所要解决的主要问题。主要问题。2023年1月30日13时01分兰州

9、大学信息科学与工程学院电信、通信工程系9 信道编码与信源编码的区别信道编码与信源编码的区别尽量减少信源的尽量减少信源的冗冗余度余度。即尽可能用。即尽可能用最少的信息比特来最少的信息比特来表示信源。表示信源。如话音压缩编码、如话音压缩编码、图象压缩编码图象压缩编码。在待传输信息中加在待传输信息中加入冗余信息，以此入冗余信息，以此达到差错控制的目达到差错控制的目的，从而提高通信的，从而提高通信系统的系统的可靠性可靠性。如纠错编码、检错如纠错编码、检错重发编码等重发编码等2023年1月30日13时01分兰州大学信息科学与工程学院电信、通信工程系10 2.2.差错控制方式及信道编码的基本概念差错控制方

10、式及信道编码的基本概念一、差错控制的三种方式：一、差错控制的三种方式：检错重发（检错重发（ARQ：Automatic Repeat Request）在接收端根据编码规则进行检查，如果发现规则被破坏，则通过反向信道反向信道要求发送端重新发送，直到接收端检查无误为止。ARQ系统需要反馈信道，效率较低，但是能达到很好的性能。前向纠错（前向纠错（FEC：Forward Error Correction）发送端发送能纠正错误的编码，在接收端根据接收到的码和编码规则，能自动纠正传输中的错误。不需要反馈信道，实时性好，但是随着纠错能力的提高，编译码设备复杂。混合方式混合方式（HEC：Hybrid Error

11、 Correction）结合前向纠错FEC和ARQ的系统，在纠错能力范围内，自动纠正错误，超出纠错范围则要求发送端重新发送。它是一种折中的方案。2023年1月30日13时01分兰州大学信息科学与工程学院电信、通信工程系11 差错控制的三种方式差错控制的三种方式检错重发（检错重发（ARQ：Automatic Repeat Request）前向纠错（前向纠错（FEC：Forward Error Correction）混合方式混合方式（HEC：Hybrid Error Correction）发送发送接收接收可检错的码序列应答信号发送发送接收接收可检错和纠错的码序列可检错和纠错的码序列发送发送接收接收

12、可检错和纠错的码序列可检错和纠错的码序列应答信号2023年1月30日13时01分兰州大学信息科学与工程学院电信、通信工程系12 差错控制的三种方式差错控制的三种方式 之之 ARQ检错重发检错重发 ARQ系统具有各种不同的重发机制系统具有各种不同的重发机制停等 ARQ发送方每发完一帧必须等接收方确认后才能发下一帧。Go-back-N ARQ(回退N)发送方可连续发送多帧。若前面某帧出错，从该帧以后的各帧都需重发。（一般与流控结合使用）选择性重传 SARQ发送方可连续发送多帧。若前面某帧出错，只需重发该出错的帧。发送方需要缓存前面所有未被确认的帧。其它不常用的差错控制方式：其它不常用的差错控制方式

13、：信息反馈方式（信息反馈方式（IRQ）2023年1月30日13时01分兰州大学信息科学与工程学院电信、通信工程系13 差错控制的三种方式差错控制的三种方式 之之 ARQ停等停等ARQ回退回退N选择性重传选择性重传码组1ACKNAK码组2ACK重发码组2码组3无错无错有错发送接收1234563456712345634567发现错误发现错误NAK重发重发12345637891234563789发现错误发现错误NAK重发2023年1月30日13时01分兰州大学信息科学与工程学院电信、通信工程系14 二、二、信道编码的分类信道编码的分类 1、按功能划分为：、按功能划分为：检错码、纠错码、纠删码（兼检错

14、、纠错）2、按信息位和校验位的约束关系分为：、按信息位和校验位的约束关系分为：线性码、非线性码3、按信息码元和监督码元的约束关系分为：、按信息码元和监督码元的约束关系分为：分组码：监督码仅与本码组信息码有关卷积码：监督码不仅与本码组信息码有关，而且与前面码组的信息码有关。4、按编码后信息码结构是否发生变化分为：、按编码后信息码结构是否发生变化分为：系统码：编码前后信息码结构不变非系统码：编码前后信息码结构发生改变5、按码元的进制进行划分：、按码元的进制进行划分：二进制码、多进制码：2023年1月30日13时01分兰州大学信息科学与工程学院电信、通信工程系15 三、信道编码的基本概念三、信道编码

15、的基本概念分组码分组码：将将k比特信息编成比特信息编成n比特一组的码字比特一组的码字（码组），记为（码组），记为（n，k）分组码。分组码。K位码元，作为信息码元r=n-k位码元，称作冗余码、监督码许用码组：许用码组：禁用码组：禁用码组：码重码重W：码字中：码字中1的个数。的个数。如W(11000)=2;W(010)=1 码距码距d（汉明距离（汉明距离Hamming）：两码组中对：两码组中对应位不同的比特（应位不同的比特（bit）数。）数。如C1:11000，C2:11101,则d(C1，C2)=22023年1月30日13时01分兰州大学信息科学与工程学院电信、通信工程系16 信道编码的基本概念

16、信道编码的基本概念最小码距最小码距：分组码(n,k)中任何两个码字Ci、Cj之间的码距的最小值，用dmin表示。最小码距是衡量码的一种内在属性 最小码距决定了码的纠错、检错性能若要发现e个独立随机错误，要求dmine+1若要纠正t个独立随机错误，要求dmin2t+1若要发现e个同时又纠正t(et)个独立随机错误，要求dmine+t+1e+1ee2t+1tte+t+1et2023年1月30日13时01分兰州大学信息科学与工程学院电信、通信工程系17 四、常用简单检错码四、常用简单检错码1.奇偶监督码（奇偶校验码）奇偶监督码（奇偶校验码）最简单的检错码(1bit校验)，在计算机数据传输中得到广泛应

17、用 传送信息分组(an-1,a1,)+监督位(a0)=一个传输码组(an-1,a1,a0)偶校验：an-1+an-2+a1+a0=0(mod 2)（即偶数个1）奇校验：an-1+an-2+a1+a0=1(mod 2)（即奇数个1）可见这种码的最小码距为可见这种码的最小码距为2，只能检，只能检出出1个独立随机差错。个独立随机差错。2023年1月30日13时01分兰州大学信息科学与工程学院电信、通信工程系18 简单的检错简单的检错码码2.二维奇偶监督码（行列监督码）二维奇偶监督码（行列监督码）可检测出任一行或任一列上所有奇数个错码信息码元信息码元水平监督码水平监督码0101101100101010

18、10010000110000110垂直监督码垂直监督码001111110112023年1月30日13时01分兰州大学信息科学与工程学院电信、通信工程系19 简单的检错码简单的检错码3.恒比码恒比码 每个码组中的1的个数都是一样的。典型应用：一般用在电传、电报。例如，我国电传机传输汉字时每个汉字用4位阿拉伯数字表示，每个阿拉伯数字用5个比特的码字表示，即从32种组合选取10个为阿拉伯数字编码阿拉伯数字编码阿拉伯数字编码101011610101211001711100310110801110411010910011500111001101恒比码的编译码可恒比码的编译码可以采用查表的方法，以采用查表

19、的方法，检错时检查检错时检查1的个的个数是否为数是否为32023年1月30日13时01分兰州大学信息科学与工程学院电信、通信工程系20 简单的检错码简单的检错码4.ISBN国际统一图书编号（例一）国际统一图书编号（例一）在国际图书的发行中，经常用编码的方式来防止书号在通信过程中发生错误，举例如下所述。如通信原理的书号是ISBN 7-5635-0525-3其中第一位数字“7”表示“中国”，“5635”表示出版社，“0525”表示书名编号，最后一位“3”表示校验位。这里所采用的校验方式如下所示：7 5 6 3 5 0 5 2 5 37 12 18 21 26 26 31 33 38 417 19

20、37 58 84 110 141 174 212 253(模模11)0若通信过程中统一书号发生了若通信过程中统一书号发生了错误，则上述累计和就不能被错误，则上述累计和就不能被11整除，从而可以校验出来。整除，从而可以校验出来。2023年1月30日13时01分兰州大学信息科学与工程学院电信、通信工程系21 简单的检错码简单的检错码4.ISBN国际统一图书编号（例二）国际统一图书编号（例二）如通信原理的书号是ISBN 7-118-0429-X其中第一位数字“7”表示“中国”，“118”表示出版社，“01429”表示书名编号，最后一位“X”表示校验位（它是罗马数字10的表示）。这里所采用的校验方式如

21、下所示：7 1 1 8 0 4 2 9 X=107 8 9 17 17 21 23 32 427 15 24 41 58 79 102 134 176 176(模11)=0。又譬如：ISBN 7ISBN 703030144560144562 2，大家可自行分析。2023年1月30日13时01分兰州大学信息科学与工程学院电信、通信工程系22 3.3.线性分组码线性分组码 近世代数学近世代数学有限域有限域的概念：的概念：有限个元素的集合，按规定可以进行的代数四则运算，其运算结果仍属于该集合中有限的元素。最简单的有限域 0，1Galois域 1+1=0、1+0=1、0+1=1、0+0=0 1x1=1

22、、1x 0=0、0 x0=0、0 x1=0定义线性分组码的加法为模定义线性分组码的加法为模2加，乘法为加，乘法为二进制乘法。且码字与码字的运算是各二进制乘法。且码字与码字的运算是各个相应比特位上的上述二进制运算规则。个相应比特位上的上述二进制运算规则。2023年1月30日13时01分兰州大学信息科学与工程学院电信、通信工程系23 3.3.线性分组码线性分组码基本概念基本概念码组中监督码与信息码之间满足线性方程；任意两个可用码组之和(逐位模2加)仍为一个可用码组奇偶监督奇偶监督码码最简单的线性分组码最简单的线性分组码偶校验时 奇校验时不满足线性分组码的第二个性质。定义校正子（校验子伴随式）接收时

23、进行校验计算：S=0无错；S=1有错（奇数个）01n-1aaa001n-1S=aaa2023年1月30日13时01分兰州大学信息科学与工程学院电信、通信工程系24 3.3.线性分组码线性分组码一般情况下：一般情况下：如果码组中有2个监督码，校正子为S=s1,s2可以检测到三种误码状态S=00No error!01S=10Error!112023年1月30日13时01分兰州大学信息科学与工程学院电信、通信工程系25 3.3.线性分组码线性分组码如果码组中有如果码组中有r个监督码，假设码组中有个监督码，假设码组中有K个信息码，则线性分组码的长度应该为个信息码，则线性分组码的长度应该为n=K+r。码

24、的结构码的结构线性分组线性分组码码（n，k）的性质的性质封闭性：任意两个码组的和还是许用的码组码的最小距离等于非零码的最小码重K位信息位r位监督位n位码组位码组2023年1月30日13时01分兰州大学信息科学与工程学院电信、通信工程系26 3.3.线性分组线性分组码码检错能力：检错能力：有r个校正子方程可以指示（2r-1）个错误纠错能力：纠错能力：对1位错码，可以指示（2r-1）个错误位置若2r-1n，可以纠正1bit或以上的错码，即2r-1r+k，2r-1-rk设k=4，能纠正1位误码的最小r=3，则n=7 （7，4）线性分组码，码组C=c6c5c4c3c2c1c0，其中c6c5c4c3为信

25、息码，c2c1c0为监督码2023年1月30日13时01分兰州大学信息科学与工程学院电信、通信工程系27 3.3.线性分组线性分组码码一般分析，对于线性分组码（一般分析，对于线性分组码（n,k）,若若可记为：可记为：（Cn-1 Cn-2 Cn-3 Cn-K Cr-1 Cr-2 Cr-3C1 C0）现令信息码元与监督码元的约束关系为：现令信息码元与监督码元的约束关系为：1,112,211,110,01.kniririkniririkniiikniiiCCCCCCCC2023年1月30日13时01分兰州大学信息科学与工程学院电信、通信工程系28 3.3.线性分组线性分组码码据此可得如下结果据此可得

26、如下结果：,111,221,111,001.0.0.0.0kirnirikirnirikiniikiniiCCCCCCCC由上式可得由上式可得一致监督关系一致监督关系为为：.0TTH C2023年1月30日13时01分兰州大学信息科学与工程学院电信、通信工程系29 3.3.线性分组线性分组码码其中的其中的H为：为：1,12,13,1,11,22,23,2,21,12,13,1,11,02,03,0,01.1 0.0 0.0 1.0 0.0 0.1 0.0 0.0 1rrrk rrrrk rkkrkrrnHPICC21210.00 0 0.0 0 nnkrrkrrCCCCCC2023年1月30日

27、13时01分兰州大学信息科学与工程学院电信、通信工程系30 3.3.线性分组线性分组码码同样可知：同样可知：1,112,211,110,011,2,3,4.njnjkrirniikrirniikiniikiniiCCjkCCCCCCCC2023年1月30日13时01分兰州大学信息科学与工程学院电信、通信工程系31 3.3.线性分组线性分组码码若令下述关系成立：若令下述关系成立：12312312101,11,21,11,02,12,22,12,01.1 0.00.0 1.00.0 0.1 0其 中TTTMMMnnnnknnnnkrrrrrrkCGCorGCCCCCCCCCCCCCCC CG,11

28、,21,11,0,1,2,1,0.0 0.01.rkrkkk rk rkkkkkrIQ对比对比H和和G，可见：，可见：2023年1月30日13时01分兰州大学信息科学与工程学院电信、通信工程系32 3.3.线性分组线性分组码码所以可得如下结果：所以可得如下结果：P,PTTkrrkrkkrQQ 这里称这里称H为一致监督矩阵；为一致监督矩阵；G则是生成矩阵。则是生成矩阵。下面研究一个实际例子。下面研究一个实际例子。rkrrTkrrrkkkrTkkrkHPIQIGIQIP2023年1月30日13时01分兰州大学信息科学与工程学院电信、通信工程系33 3.3.线性分组码线性分组码现以一个现以一个(7,

29、3)线性分组码为例线性分组码为例n=7,k=3,r=n-k=4编码效率为：R=k/n=3/7 c0=u0 c3=u0+u2 信息位 c1=u1 监督位 c4=u0+u1+u2 c2=u2 c5=u0+u1 c6=u1+u2 则C=（c0c1c2c3c4c5c6）=（u0,u1,u2,u0+u2,u0+u1+u2,u0+u1,u1+u2）2023年1月30日13时01分兰州大学信息科学与工程学院电信、通信工程系34 3.3.线性分组码线性分组码n位的码组，由k个信息位的输入消息u通过一个线性变换矩阵kn阶G来产生，称G生生成矩阵成矩阵G=，I为k阶单位方阵典型生成矩阵01210011100100

30、111()0011101cu u uu GuI Q生成矩阵G()I Q2023年1月30日13时01分兰州大学信息科学与工程学院电信、通信工程系35 3.3.线性分组码线性分组码将监督位线性方程组写为将监督位线性方程组写为即即 可见上述监督关系的线性方程组完全由矩阵可见上述监督关系的线性方程组完全由矩阵H所所决定。故将决定。故将此此r n的的H矩阵称为矩阵称为监督矩阵监督矩阵H=,I为为(n-kr)维（阶）单位方阵 典型监督矩阵典型监督矩阵01610 1100001110 100011000 1000 11000 10ccc 02301230151260000ccccccccccccc0()0

31、TTTTH CP IC()PI2023年1月30日13时01分兰州大学信息科学与工程学院电信、通信工程系36 3.3.线性分组码线性分组码根据前面所得可推导：G与与H生成的空间互为零空间，且生成的空间互为零空间，且G与与H可可以互相转换。以互相转换。00000()0TC u GTTTTuTTTTTH CC Hu G HG HPG HI QPQIorPQPQ （即P、Q互为转置矩阵）2023年1月30日13时01分兰州大学信息科学与工程学院电信、通信工程系37 3.3.线性分组线性分组码码校正子（码组伴随式）校正子（码组伴随式）发送码组C经过传输系统到达接收端时，假设收到的码组为B，B=bn-1

32、bn-2b0差错关系为 B-C=E，BE=CE=en-1en-2e0，E又称为错误图样。其中接收时计算校正子为 iiiii0 bce1 bc TTTTTSB H(CE)H=C HE HS0No error!S0ErroE HSEC+ErB!=2023年1月30日13时01分兰州大学信息科学与工程学院电信、通信工程系38 3.3.线性分组码线性分组码编码器编码器若以c0c1c2为信息码,由监督码的生成关系可得c3=1c0+0c1+1c2 c4=1c0+1c1+1 c2 c5=1c0+1c1+0c2 c6=0c0+1c1+1c2 C0C1C2+u0u1u2C4C5C6C32023年1月30日13时

33、01分兰州大学信息科学与工程学院电信、通信工程系39 3.3.线性分组码线性分组码译码器译码器由校正子关系可得T0123456123410232012430154126111001111101S=B H=b b b b b b b s s s s 1000010000100001sbbb sbbbb sbbb sbbb 2023年1月30日13时01分兰州大学信息科学与工程学院电信、通信工程系40 3.3.线性分组码线性分组码译码器译码器10232012430154126ssssbbbbbbbbbbbbb b0b1b2b3b4b5b6+b0s1s2s3s4s1s2s3s4与+r0c0b1与+r

34、1c1b2与+r2c2b3与+r3c3b4与+r4c4b5与+r5c5b6与+r6c6伴随式计算电路错误图样检测电路2023年1月30日13时01分兰州大学信息科学与工程学院电信、通信工程系41 3.3.线性分组线性分组码码汉明（海明）码（汉明（海明）码（Hamming）能纠正单个随机错误的线性分组码 码长 n=2m-1 信息位 k=2m-1-m 监督位 n-k=m，且 m3 最小距离 dmin=d0=3汉明码是一类高效率的纠错码 编码效率 R=k/n=(n-m)/n=1-m/n n很大时，R12023年1月30日13时01分兰州大学信息科学与工程学院电信、通信工程系42 4.4.循环码循环码

35、基本概念基本概念线性分组码的一个子类，比较成熟任何一个可用码组经过循环移位后所得到的码组仍为一个可用码组 原码组 C=cn-1 cn-2 c1 c0 左移一位 C1=cn-2 cn-3 c0 cn-1 右移一位 C2=c1 cn-1 c3 c2 移i位 Ci=cn-i-1 cn-i-2 cn-i循环码组 C=cn-1 cn-2 c1 c0 可表示为多项式 C(x)=cn-1 xn-1+cn-2 xn-2+c1 x+c0 式中x的幂次表示：码元的位置；码的移位次数2023年1月30日13时01分兰州大学信息科学与工程学院电信、通信工程系43 4.4.循环码循环码基本概念基本概念如多项式C(x)=

36、x6+x4+x+1C=1010011 c6x6可以看作c6从最低位c0左移6次的结果C(x)左移一位记作 C(1)(x)C(1)(x)=cn-2 xn-1+cn-3 xn-2+c0 x+cn-1C(x)左移i位后为 C(i)(x)=cn-i-1 xn-1+cn-i-2 xn-2+cn-i+1 x+cn-i2023年1月30日13时01分兰州大学信息科学与工程学院电信、通信工程系44 4.4.循环码循环码循环码多项式的运算特性循环码多项式的运算特性码长为n的循环码，其码多项式C(x)，则xiC(x)=Q(x)(xn+1)+C(i)(x)即例如：某循环码组例如：某循环码组为为C=(1100101)

37、，码，码长长n=7，对应的码多项式，对应的码多项式为为C(x)=x6+x5+x2+1左移一位左移一位后后xC(x)=x7+x6+x3+x因为C(1)(x)xC(x)(mod（x7+1）)=x6+x3+x+1（1001011）(in)i(ini)xC(x)xC(x)QC(x)(mod(x1C(x(x1)x)2023年1月30日13时01分兰州大学信息科学与工程学院电信、通信工程系45 4.4.循环码循环码左移左移2位时位时x2C(x)=x8+x7+x4+x2 x+1 x7+1)x8+x7+x4+x2 x8 +x x7+x4+x2+x x7 +1 x4+x2+x+1C(2)(x)=x4+x2+x+

38、1(0010111)2023年1月30日13时01分兰州大学信息科学与工程学院电信、通信工程系46 4.4.循环循环码码生成多项式生成多项式g(x)对于(n,k)循环码来说，生成多项式g(x)是一个能除尽xn+1的（n-k）阶多项式。阶数低于n并能被g(x)除尽的一组多项式就构成一个(n,k)循环码阶数小于等于(n-1)并能被g(x)除尽的每个多项式都是循环码的可用码组多项式。所以，循环码完全由其码组长度所以，循环码完全由其码组长度n和和生成多项式生成多项式g(x)所决定。所决定。2023年1月30日13时01分兰州大学信息科学与工程学院电信、通信工程系47 4.4.循环码循环码生成多项式生成

39、多项式g(x)设构成循环码的信息码多项式为u(x)，其阶数不大于(k-1)，则有循环码组为C(x)=u(x)g(x)例如，n=7，g(x)=x4+x3+x2+1是x7+1的一个因式；g(x)最高幂次为4=n-k；则k=3，r=4（即信息码3bit，监督码4bit）。可用码组如下：4325432654226530 g(x)=0 (0000000)1 g(x)=xxx1 (0011101)x g(x)=xxxx (0111010)x g(x)=xxxx (1110100)(x1)g(x)=xxx1 264522632 (1101001)(xx1)g(x)=xxx1(1010011)(x1)g(x)

40、=xxx1 (0100111)(xx)g(x)=xxxx (1001110)2023年1月30日13时01分兰州大学信息科学与工程学院电信、通信工程系48 4.4.循环码循环码生成多项式生成多项式g(x)以上是一个（7，3）循环码，最小码距dmin=4，其信息码多项式如下：22220(000)1(001)x(010)x(100)M(x)(x1)(101)(xx1)(111)(x1)(011)(xx)(110)2023年1月30日13时01分兰州大学信息科学与工程学院电信、通信工程系49 4.4.循环码循环码生成多项式生成多项式g(x)为了得到g(x)，需对xn+1进行因式分解对于大部分n值，x

41、n+1仅有很少的几个因式；只有很少的几个n值，xn+1才有较多因式设g(x)h(x)=xn+1 或g(x)h(x)0 mod(xn+1)以（7，3）循环码为例，n=7 x7+1=(x+1)(x3+x2+1)(x3+x+1)2023年1月30日13时01分兰州大学信息科学与工程学院电信、通信工程系50 4.4.循环码循环码生成多项式生成多项式g(x)n=7，x7+1=(x+1)(x3+x2+1)(x3+x+1)循环码 dming(x)h(x)(7,6)2x+1(x3+x2+1)(x3+x+1)(7,4)3x3+x2+1(x+1)(x3+x+1)x3+x+1(x+1)(x3+x2+1)(7,3)4

42、(x+1)(x3+x+1)x3+x2+1(x+1)(x3+x2+1)x3+x+1(7,1)7(x3+x2+1)(x3+x+1)x+1显然，显然，(7，3)、(7，4)循环码互为对偶码循环码互为对偶码.2023年1月30日13时01分兰州大学信息科学与工程学院电信、通信工程系51 4.4.循环循环码码生成矩阵生成矩阵GC(x)=u(x)g(x)=(uk-1xk-1+uk-2xk-1+u1x+u0)g(x)=uk-1xk-1 g(x)+uk-2xk-2 g(x)+u0 g(x)=uG根据u的不同取值可求得(n,k)循环码的所有2k个码字，但这样所得到的码并非系统码。k 1k 2k-1k-20 xg

43、(x)(uuu)xg(x)1 g(x)2023年1月30日13时01分兰州大学信息科学与工程学院电信、通信工程系52 4.4.循环码循环码生成矩阵生成矩阵G为了进一步得到系统码，可作如下运算：xn-ku(x)=Q(x)g(x)+r(x)C(x)=xn-ku(x)+r(x)=Q(x)g(x)+r(x)+r(x)=Q(x)g(x)构造系统循环码：只需将信息码多项式升(n-k)阶，然后以g(x)为模求余，所得余式即为监督码多项式“除法求除法求余余”过程n 1n 1n 2n-in 2n-in kn kxr(x)xr(x)G,r(x)x mod g(x)xr(x)2023年1月30日13时01分兰州大学

44、信息科学与工程学院电信、通信工程系53 4.4.循环码循环码例如：例如：已知已知(7,4)系统码的生成多项式为系统码的生成多项式为g(x)=x3+x2+1，求其生成矩阵求其生成矩阵。解：由 先求出n-in-ir(x)x mod g(x)626mod g(x)55mod g(x)424mod g(x)323mod g(x)662655542443233r(x)x xxr(x)x x1r(x)x xx+1r(x)x x1xr(x)xxx1000110 xr(x)xx10100011G(x)Gxxx+1xr(x)xx1xr(x)001011100011012023年1月30日13时01分兰州大学信息

45、科学与工程学院电信、通信工程系54 4.4.循环码循环码监督矩阵监督矩阵H由于 xn+1=g(x)h(x)生成多项式g(x)=gn-kxn-k+g1x+g0 监督多项式h(x)=hkxk+h1x+h0n-kk0001100021120n-10n21nk101k10gh1 gh1 ghg h0 ghg hgh0 ghgh+gh00000H=00kkkhhhhhhhhh 2023年1月30日13时01分兰州大学信息科学与工程学院电信、通信工程系55 4.4.循环码循环码例如，已知例如，已知(7,3)系统循环码的生成多项系统循环码的生成多项式式g(x)=x4+x3+x2+1，求生成矩阵，求生成矩阵G

46、及监督矩阵及监督矩阵H。解：由g(x)h(x)=x7+1的关系可得：h(x)=x3+x2+1=h3x3+h2x2+h1x+h0根据前例方法先计算 rn-i(x)xn-imod g(x)可得6325243201230123012301231001110()10100111001110110 0 0101100000 001011000 00001011000010110 0 0 xxxxG xxxxGxxxh h h hh h h hHh h h hh h h h 2023年1月30日13时01分兰州大学信息科学与工程学院电信、通信工程系56 4.4.循环码循环码编码器编码器循环码的特点一：可以

47、采用反馈线性移位寄存器实现编码和伴随式计算以g(x)=x3+x+1的（7，4）循环编码器为例D0D1D2+门输入输入u(x)xn-k12码字输出码字输出2023年1月30日13时01分兰州大学信息科学与工程学院电信、通信工程系57 4.4.循环循环码码编码器编码器以g(x)=x3+x+1的（7，4）循环编码器为例节拍信息组输入依存状态输出码字D0(x0)D1(x1)D2(x2)0000111101200110301110410111500116000170000初态为初态为000门开门开四次移位后信四次移位后信息息1001全部输全部输出，出，关门关门，输，输出开关倒向出开关倒向2又循环回到又循

48、环回到初始状态初始状态信信息息位位监监督督位位2023年1月30日13时01分兰州大学信息科学与工程学院电信、通信工程系58 4.4.循环码循环码译码器译码器仍以g(x)=x3+x+1生成的（7，4）循环码译码为例复用器复用器+门门1门门2+门门2Y(x)s0s1s2错误图样检测电路只有1套，其译码电路比一般的(7,4)线性分组码大大简化2023年1月30日13时01分兰州大学信息科学与工程学院电信、通信工程系59 4.4.循环码循环码(7，4)循环码循环码d=3g(x)=(x3+x+1)100101101011100010111H (8,4)非循环码d=4100101101011100010

49、11111111100011H(7，3)循环码d=4g(x)=(x3+x+1)(x+1)1000110010001100101110001101H 删删减减增增扩扩收收缩缩加长加长缩短缩短扩扩展展2023年1月30日13时01分兰州大学信息科学与工程学院电信、通信工程系60 4.4.循环码循环码循环码检循环码检错错CRC (Cyclic Redundancy Check,循环冗余校验循环冗余校验)一般能检测的错误：突发长度n-k+1的错误，其中不可检出错误仅占2-(n-k)所有与许用码组码距dmin-1的错误 所有奇数个错误CRC码在数据通信及移动通信中得到广泛应用2023年1月30日13时0

50、1分兰州大学信息科学与工程学院电信、通信工程系61 4.4.循环码循环码循环码检错：循环码检错：CRC (Cyclic Redundancy Check,循环冗余校验循环冗余校验)常用的CRC码国际标准 CRC-12：g(x)=x12+x11+x3+x2+x+1 CRC-16:g(x)=x16+x15+x2+1 CRC-CCITT:g(x)=x16+x12+x5+1 CRC-32:g(x)=x32+x26+x23+x22+x16+x12+x11 +x10+x8+x7+x5+x4+x2+x+1CRC-12用于字符长度为6bit情况，后三种用于8bit字符。2023年1月30日13时01分兰州大学