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

《差错控制和信道编码课件.ppt》由会员分享，可在线阅读，更多相关《差错控制和信道编码课件.ppt（89页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2/6/2023通通 信信 原原 理理程琳程琳 兰州大学信息科学与技术学院电信系兰州大学信息科学与技术学院电信系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 Province，P.R.ChinaPrinciples o

2、f Communications兰州大学信息科学与工程学院电信、通信工程系 第十三章第十三章 差错控制和信道编码差错控制和信道编码主要内容提要：主要内容提要：差错控制方式及信道编码的基本概念差错控制方式及信道编码的基本概念 线性分组码线性分组码 循环码循环码 卷积码卷积码 其它信道编码简介其它信道编码简介2/6/20232兰州大学信息科学与工程学院电信、通信工程系本章的教学基本要求本章的教学基本要求 本章要求本章要求掌握掌握差错控制的基本方式、差错控制的基本方式、信道编码的一些基本概念、线性分组码信道编码的一些基本概念、线性分组码特性及其设计、循环码特性及其设计、特性及其设计、循环码特性及其设

3、计、卷积码特性及其设计；其余的内容可根卷积码特性及其设计；其余的内容可根据学时情况酌情加以了解即可。据学时情况酌情加以了解即可。2/6/20233兰州大学信息科学与工程学院电信、通信工程系在实际信道上传输数字信号时，由于信道传输特在实际信道上传输数字信号时，由于信道传输特性不理想以及加性噪声的影响，接收端所收到的性不理想以及加性噪声的影响，接收端所收到的数字信号不可避免地会发生错误。数字信号不可避免地会发生错误。产生差错的原因产生差错的原因信道的电气特性引起信号幅度、频率、相位的畸变；信道的电气特性引起信号幅度、频率、相位的畸变；信号反射；信号反射；串扰；串扰；闪电、大功率电机的启停产生脉冲干

4、扰等。闪电、大功率电机的启停产生脉冲干扰等。一般说来，一般说来，线路传输差错是不可避免的，但要线路传输差错是不可避免的，但要尽量减小其影响。尽量减小其影响。1.1.引言引言2/6/20234兰州大学信息科学与工程学院电信、通信工程系1.1.引引 言言信道差错的几种模式信道差错的几种模式随机差错随机差错：差错的出现是随机的，一般而言差错出现的位置是随机分布的。这种情况一般是由信道的加性随机噪声引起的。一般将这种信道称为随机信道随机信道。突发差错突发差错：差错的出现是一连串出现的。这种情况如移动通信中信号在某一段时间内发生衰落，造成一串差错；光盘上的一条划痕等等。这样的信道我们称之为突发突发信道信

5、道。混合差错混合差错：既有突发错误又有随机差错的情况。这种信道称之为混合信道混合信道。2/6/20235兰州大学信息科学与工程学院电信、通信工程系1.1.引引 言言降低误码的技术措施：降低误码的技术措施：为了在已知信噪比情况下达到一定的误比特为了在已知信噪比情况下达到一定的误比特率指标，首先应该合理设计基带信号，选择调率指标，首先应该合理设计基带信号，选择调制解调方式，采用时域制解调方式，采用时域/频域均衡，使误比特频域均衡，使误比特率尽可能降低。率尽可能降低。但若误比特率仍不能满足要求，则必须采用但若误比特率仍不能满足要求，则必须采用信道编码信道编码（即（即差错控制编码差错控制编码），将误比

6、特率进，将误比特率进一步降低，以满足系统指标要求。一步降低，以满足系统指标要求。随着差错控制编码理论的完善和数字电路技术随着差错控制编码理论的完善和数字电路技术的发展，信道编码已经成功地应用于各种通信的发展，信道编码已经成功地应用于各种通信系统中，并且在计算机、磁记录与存储中也得系统中，并且在计算机、磁记录与存储中也得到日益广泛的应用。到日益广泛的应用。2/6/20236兰州大学信息科学与工程学院电信、通信工程系1.1.引引 言言我们研究的是编码和译码，所以完全可以将调我们研究的是编码和译码，所以完全可以将调制、解调与信道合起来等效成一个等效信道制、解调与信道合起来等效成一个等效信道编码信道编

7、码信道。编码信道根据调制解调的不同输入和输出具有编码信道根据调制解调的不同输入和输出具有不同的类型不同的类型离散无记忆对称二进制输入二进制输出信道（BSC）离散无记忆二进制输入多进制输出信道离散无记忆多进制输入多进制输出离散无记忆二进制输入连续输出离散有记忆信道编码信道编码信道信源编编码码调制信道解调译译码码信宿2/6/20237兰州大学信息科学与工程学院电信、通信工程系1.1.引引 言言信道编码的目的信道编码的目的：改善数字通信系统的传输质量信道编码信道编码(差错控制编码差错控制编码)的基本思路的基本思路：在发送端将被传输的信息附上一些监督码元，这些冗余的码元与信息码元之间以某种确定的规则某

8、种确定的规则相互关联（约束）。接收端按照既定的规则校验信息码元与监督码元之间的关系，一旦传输发生差错，则信息码元与监督码元的关系就受到破坏，从而接收端可以发现错误乃至纠正错误。信道编码的任务信道编码的任务：构造出以最小多余度（冗余度）代价换取最大抗干扰性能的“好码”。研究各种编码和译码方法是信道编码所要解决的研究各种编码和译码方法是信道编码所要解决的主要问题。主要问题。2/6/20238兰州大学信息科学与工程学院电信、通信工程系信道编码与信源编码的区别信道编码与信源编码的区别信源编码尽量减少信源的尽量减少信源的冗冗余度余度。即尽可能用。即尽可能用最少的信息比特来最少的信息比特来表示信源。表示信

9、源。如话音压缩编码、如话音压缩编码、图象压缩编码图象压缩编码。信道编码在待传输信息中加在待传输信息中加入冗余信息，以此入冗余信息，以此达到差错控制的目达到差错控制的目的，从而提高通信的，从而提高通信系统的系统的可靠性可靠性。如纠错编码、检错如纠错编码、检错重发编码等重发编码等2/6/20239兰州大学信息科学与工程学院电信、通信工程系2.2.差错控制方式及信道编码的基本概念差错控制方式及信道编码的基本概念一、差错控制的三种方式：一、差错控制的三种方式：检错重发（检错重发（ARQ：Automatic Repeat Request）在接收端根据编码规则进行检查，如果发现规则被破坏，则通过反向信道反

10、向信道要求发送端重新发送，直到接收端检查无误为止。ARQ系统需要反馈信道，效率较低，但是能达到很好的性能。前向纠错（前向纠错（FEC：Forward Error Correction）发送端发送能纠正错误的编码，在接收端根据接收到的码和编码规则，能自动纠正传输中的错误。不需要反馈信道，实时性好，但是随着纠错能力的提高，编译码设备复杂。混合方式混合方式（HEC：Hybrid Error Correction）结合前向纠错FEC和ARQ的系统，在纠错能力范围内，自动纠正错误，超出纠错范围则要求发送端重新发送。它是一种折中的方案。2/6/202310兰州大学信息科学与工程学院电信、通信工程系差错控制

11、的三种方式差错控制的三种方式检错重发（检错重发（ARQ：Automatic Repeat Request）前向纠错（前向纠错（FEC：Forward Error Correction）混合方式混合方式（HEC：Hybrid Error Correction）发送发送接收接收可检错的码序列应答信号发送发送接收接收可检错和纠错的码序列可检错和纠错的码序列发送发送接收接收可检错和纠错的码序列可检错和纠错的码序列应答信号2/6/202311兰州大学信息科学与工程学院电信、通信工程系差错控制的三种方式差错控制的三种方式 之之 ARQ检错重发检错重发 ARQ系统具有各种不同的重发机制系统具有各种不同的重发

12、机制停等 ARQ发送方每发完一帧必须等接收方确认后才能发下一帧。Go-back-N ARQ(回退N)发送方可连续发送多帧。若前面某帧出错，从该帧以后的各帧都需重发。（一般与流控结合使用）选择性重传 SARQ发送方可连续发送多帧。若前面某帧出错，只需重发该出错的帧。发送方需要缓存前面所有未被确认的帧。其它不常用的差错控制方式：其它不常用的差错控制方式：信息反馈方式（信息反馈方式（IRQ）2/6/202312兰州大学信息科学与工程学院电信、通信工程系差错控制的三种方式差错控制的三种方式 之之 ARQ停等停等ARQ回退回退N选择性重传选择性重传码组1ACKNAK码组2ACK重发码组2码组3无错无错有

13、错发送接收1234563456712345634567发现错误发现错误NAK重发重发12345637891234563789发现错误发现错误NAK重发2/6/202313兰州大学信息科学与工程学院电信、通信工程系二、二、信道编码的分类信道编码的分类 1、按功能划分为：、按功能划分为：检错码、纠错码、纠删码（兼检错、纠错）2、按信息位和校验位的约束关系分为：、按信息位和校验位的约束关系分为：线性码、非线性码3、按信息码元和监督码元的约束关系分为：、按信息码元和监督码元的约束关系分为：分组码：监督码仅与本码组信息码有关卷积码：监督码不仅与本码组信息码有关，而且与前面码组的信息码有关。4、按编码后信

14、息码结构是否发生变化分为：、按编码后信息码结构是否发生变化分为：系统码：编码前后信息码结构不变非系统码：编码前后信息码结构发生改变5、按码元的进制进行划分：、按码元的进制进行划分：二进制码、多进制码：2/6/202314兰州大学信息科学与工程学院电信、通信工程系三、信道编码的基本概念三、信道编码的基本概念分组码分组码：将将k比特信息编成比特信息编成n比特一组的码字比特一组的码字（码组），记为（码组），记为（n，k）分组码。分组码。K位码元，作为信息码元r=n-k位码元，称作冗余码、监督码许用码组：许用码组：禁用码组：禁用码组：码重码重W：码字中码字中1的个数。的个数。如W(11000)=2;W

15、(010)=1 码距码距d（汉明距离汉明距离Hamming）：两码组中两码组中对应位不同的比特（对应位不同的比特（bit）数。数。如C1:11000，C2:11101,则d(C1，C2)=22/6/202315兰州大学信息科学与工程学院电信、通信工程系信道编码的基本概念信道编码的基本概念最小码距最小码距：分组码(n,k)中任何两个码字Ci、Cj之间的码距的最小值，用dmin表示。最小码距是衡量码的一种内在属性 最小码距决定了码的纠错、检错性能若要发现e个独立随机错误，要求dmine+1若要纠正t个独立随机错误，要求dmin2t+1若要发现e个同时又纠正t(et)个独立随机错误，要求dmine+

16、t+1e+1ee2t+1tte+t+1et2/6/202316兰州大学信息科学与工程学院电信、通信工程系四、常用简单检错码四、常用简单检错码1.奇偶监督码（奇偶校验码）奇偶监督码（奇偶校验码）最简单的检错码(1bit校验)，在计算机数据传输中得到广泛应用 传送信息分组(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个独立随机差错。个独立随机差错。2/6/20231

17、7兰州大学信息科学与工程学院电信、通信工程系简单的检错简单的检错码码2.二维奇偶监督码（行列监督码）二维奇偶监督码（行列监督码）可检测出任一行或任一列上所有奇数个错码信息码元信息码元水平监督码水平监督码010110110010101010010000110000110垂直监督码垂直监督码001111110112/6/202318兰州大学信息科学与工程学院电信、通信工程系简单的检错码简单的检错码3.恒比码恒比码 每个码组中的1的个数都是一样的。典型应用：一般用在电传、电报。例如，我国电传机传输汉字时每个汉字用4位阿拉伯数字表示，每个阿拉伯数字用5个比特的码字表示，即从32种组合选取10个为阿拉伯

18、数字编码阿拉伯数字编码阿拉伯数字编码101011610101211001711100310110801110411010910011500111001101恒比码的编译码可恒比码的编译码可以采用查表的方法，以采用查表的方法，检错时检查检错时检查1的个的个数是否为数是否为32/6/202319兰州大学信息科学与工程学院电信、通信工程系简单的检错码简单的检错码4.ISBN国际统一图书编号（例一）国际统一图书编号（例一）在国际图书的发行中，经常用编码的方式来防止书号在通信过程中发生错误，举例如下所述。如通信原理的书号是ISBN 7-5635-0525-3其中第一位数字“7”表示“中国”，“5635”

19、表示出版社，“0525”表示书名编号，最后一位“3”表示校验位。这里所采用的校验方式如下所示：7 5 6 3 5 0 5 2 5 37 12 18 21 26 26 31 33 38 417 19 37 58 84 110 141 174 212 253(模模11)0若通信过程中统一书号发生了若通信过程中统一书号发生了错误，则上述累计和就不能被错误，则上述累计和就不能被11整除，从而可以校验出来。整除，从而可以校验出来。2/6/202320兰州大学信息科学与工程学院电信、通信工程系简单的检错码简单的检错码4.ISBN国际统一图书编号（例二）国际统一图书编号（例二）如通信原理的书号是ISBN 7

20、-118-0429-X其中第一位数字“7”表示“中国”，“118”表示出版社，“01429”表示书名编号，最后一位“X”表示校验位（它是罗马数字10的表示）。这里所采用的校验方式如下所示：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，大家可自行分析。2/6/202321兰州大学信息科学与工程学院电信、通信工程系3.3.线性分组码线性分组码 近世代数学近世代数学有限域有限域的概念：的概念：有限个元素的集合，

21、按规定可以进行的代数四则运算，其运算结果仍属于该集合中有限的元素。最简单的有限域 0，1Galois域1+1=0、1+0=1、0+1=1、0+0=0 1x1=1、1x 0=0、0 x0=0、0 x1=0定义线性分组码的加法为模定义线性分组码的加法为模2加，乘法为加，乘法为二进制乘法。且码字与码字的运算是各二进制乘法。且码字与码字的运算是各个相应比特位上的上述二进制运算规则。个相应比特位上的上述二进制运算规则。2/6/202322兰州大学信息科学与工程学院电信、通信工程系3.3.线性分组码线性分组码基本概念基本概念码组中监督码与信息码之间满足线性方程；任意两个可用码组之和(逐位模2加)仍为一个可

22、用码组奇偶监督奇偶监督码码最简单的线性分组码最简单的线性分组码偶校验时 奇校验时不满足线性分组码的第二个性质。定义校正子（校验子伴随式）接收时进行校验计算：S=0无错；S=1有错（奇数个）2/6/202323兰州大学信息科学与工程学院电信、通信工程系3.3.线性分组码线性分组码一般情况下：一般情况下：如果码组中有2个监督码，校正子为S=s1,s2可以检测到三种误码状态2/6/202324兰州大学信息科学与工程学院电信、通信工程系3.3.线性分组码线性分组码如果码组中有如果码组中有r个监督码，假设码组中有个监督码，假设码组中有K个信息码，则线性分组码的长度应该为个信息码，则线性分组码的长度应该为

23、n=K+r。码的结构码的结构线性分组线性分组码码（n，k）的性质的性质封闭性：任意两个码组的和还是许用的码组码的最小距离等于非零码的最小码重K位信息位r位监督位n位码组位码组2/6/202325兰州大学信息科学与工程学院电信、通信工程系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为信息码

24、，c2c1c0为监督码2/6/202326兰州大学信息科学与工程学院电信、通信工程系3.3.线性分组线性分组码码一般分析，对于线性分组码（一般分析，对于线性分组码（n,k）,若若可记为：可记为：（Cn-1 Cn-2 Cn-3 Cn-K Cr-1 Cr-2 Cr-3C1 C0）现令信息码元与监督码元的约束关系为：现令信息码元与监督码元的约束关系为：2/6/202327兰州大学信息科学与工程学院电信、通信工程系3.3.线性分组线性分组码码据此可得如下结果据此可得如下结果：由上式可得由上式可得一致监督关系一致监督关系为为：2/6/202328兰州大学信息科学与工程学院电信、通信工程系3.3.线性分组

25、线性分组码码其中的其中的H为：为：2/6/202329兰州大学信息科学与工程学院电信、通信工程系3.3.线性分组线性分组码码同样可知：同样可知：2/6/202330兰州大学信息科学与工程学院电信、通信工程系3.3.线性分组线性分组码码若令下述关系成立：若令下述关系成立：对比对比H和和G，可见：可见：2/6/202331兰州大学信息科学与工程学院电信、通信工程系3.3.线性分组线性分组码码所以可得如下结果：所以可得如下结果：这里称这里称H为一致监督矩阵；为一致监督矩阵；G则是生成矩阵。则是生成矩阵。下面研究一个实际例子。下面研究一个实际例子。2/6/202332兰州大学信息科学与工程学院电信、通

26、信工程系3.3.线性分组码线性分组码现以一个现以一个(7,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）2/6/202333兰州大学信息科学与工程学院电信、通信工程系3.3.线性分组码线性分组码n位的码组，由k个信息位的输入消息u通过一个线性变换矩阵kn阶G来产生，称G生成生成矩阵矩阵G=，I为k阶单位方阵

27、典型生成矩阵生成矩阵G2/6/202334兰州大学信息科学与工程学院电信、通信工程系3.3.线性分组码线性分组码将监督位线性方程组写为将监督位线性方程组写为即即 可见上述监督关系的线性方程组完全由矩阵可见上述监督关系的线性方程组完全由矩阵H所所决定。故将决定。故将此此r n的的H矩阵称为矩阵称为监督矩阵监督矩阵H=,I为为(n-kr)维（阶）单位方阵 典型监督矩阵典型监督矩阵2/6/202335兰州大学信息科学与工程学院电信、通信工程系3.3.线性分组码线性分组码根据前面所得可推导：G与与H生成的空间互为零空间，且生成的空间互为零空间，且G与与H可以可以互相转换。互相转换。（即P、Q互为转置矩

28、阵）2/6/202336兰州大学信息科学与工程学院电信、通信工程系3.3.线性分组线性分组码码校正子（码组伴随式）校正子（码组伴随式）发送码组C经过传输系统到达接收端时，假设收到的码组为B，B=bn-1bn-2b0差错关系为 B-C=E，BE=CE=en-1en-2e0，E又称为错误图样。其中接收时计算校正子为 2/6/202337兰州大学信息科学与工程学院电信、通信工程系3.3.线性分组码线性分组码编码器编码器若以c0c1c2为信息码,由监督码的生成关系可得c3=1c0+0c1+1c2 c4=1c0+1c1+1 c2 c5=1c0+1c1+0c2 c6=0c0+1c1+1c2 C0C1C2+

29、u0u1u2C4C5C6C32/6/202338兰州大学信息科学与工程学院电信、通信工程系3.3.线性分组码线性分组码译码器译码器由校正子关系可得2/6/202339兰州大学信息科学与工程学院电信、通信工程系3.3.线性分组码线性分组码译码器译码器b0b1b2b3b4b5b6+b0s1s2s3s4s1s2s3s4与+r0c0b1与+r1c1b2与+r2c2b3与+r3c3b4与+r4c4b5与+r5c5b6与+r6c6伴随式计算电路错误图样检测电路2/6/202340兰州大学信息科学与工程学院电信、通信工程系3.3.线性分组线性分组码码汉明（海明）码（汉明（海明）码（Hamming）能纠正单个

30、随机错误的线性分组码码长 n=2m-1信息位 k=2m-1-m监督位 n-k=m，且 m3最小距离 dmin=d0=3汉明码是一类高效率的纠错码编码效率 R=k/n=(n-m)/n=1-m/nn很大时，R12/6/202341兰州大学信息科学与工程学院电信、通信工程系4.4.循环码循环码基本概念基本概念线性分组码的一个子类，比较成熟任何一个可用码组经过循环移位后所得到的码组仍为一个可用码组原码组 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

31、cn-2 c1 c0 可表示为多项式 C(x)=cn-1 xn-1+cn-2 xn-2+c1 x+c0式中x的幂次表示：码元的位置；码的移位次数2/6/202342兰州大学信息科学与工程学院电信、通信工程系4.4.循环码循环码基本概念基本概念如多项式C(x)=x6+x4+x+1C=1010011c6x6可以看作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-i2/6/202343兰州大学信息科学与

32、工程学院电信、通信工程系4.4.循环码循环码循环码多项式的运算特性循环码多项式的运算特性码长为n的循环码，其码多项式C(x)，则xiC(x)=Q(x)(xn+1)+C(i)(x)即例如：某循环码组例如：某循环码组为为C=(1100101)，码码长长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）2/6/202344兰州大学信息科学与工程学院电信、通信工程系4.4.循环码循环码左移左移2位时位时x2C(x)=x8+x7+x4+x2 x+

33、1 x7+1)x8+x7+x4+x2 x8 +x x7+x4+x2+x x7 +1 x4+x2+x+1C(2)(x)=x4+x2+x+1(0010111)2/6/202345兰州大学信息科学与工程学院电信、通信工程系4.4.循环循环码码生成多项式生成多项式g(x)对于(n,k)循环码来说，生成多项式g(x)是一个能除尽xn+1的（n-k）阶多项式。阶数低于n并能被g(x)除尽的一组多项式就构成一个(n,k)循环码阶数小于等于(n-1)并能被g(x)除尽的每个多项式都是循环码的可用码组多项式。所以，循环码完全由其码组长所以，循环码完全由其码组长度度n和和生成多项式生成多项式g(x)所决定。所决定

34、。2/6/202346兰州大学信息科学与工程学院电信、通信工程系4.4.循环码循环码生成多项式生成多项式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）。可用码组如下：2/6/202347兰州大学信息科学与工程学院电信、通信工程系4.4.循环码循环码生成多项式生成多项式g(x)以上是一个（7，3）循环码，最小码距dmin=4，其信息码多项式如下：2/6/202348兰州大学信息科学与工程

35、学院电信、通信工程系4.4.循环码循环码生成多项式生成多项式g(x)为了得到g(x)，需对xn+1进行因式分解对于大部分n值，xn+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)2/6/202349兰州大学信息科学与工程学院电信、通信工程系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

36、+1)(7,4)3x3+x2+1(x+1)(x3+x+1)x3+x+1(x+1)(x3+x2+1)(7,3)4(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)循环码互为对偶码循环码互为对偶码.2/6/202350兰州大学信息科学与工程学院电信、通信工程系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的不同取值可求得(

37、n,k)循环码的所有2k个码字，但这样所得到的码并非系统码。2/6/202351兰州大学信息科学与工程学院电信、通信工程系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)为模求余，所得余式即为监督码多项式“除法除法求余求余”过程2/6/202352兰州大学信息科学与工程学院电信、通信工程系4.4.循环码循环码例如：例如：已知已知(7,4)系统码的生成多项式为系统码的生成多

38、项式为g(x)=x3+x2+1，求其生成矩阵求其生成矩阵。解：由 先求出2/6/202353兰州大学信息科学与工程学院电信、通信工程系4.4.循环码循环码监督矩阵监督矩阵H由于 xn+1=g(x)h(x)生成多项式g(x)=gn-kxn-k+g1x+g0监督多项式h(x)=hkxk+h1x+h02/6/202354兰州大学信息科学与工程学院电信、通信工程系4.4.循环码循环码例如，已知例如，已知(7,3)系统循环码的生成多项系统循环码的生成多项式式g(x)=x4+x3+x2+1，求生成矩阵求生成矩阵G及监督矩阵及监督矩阵H。解：由g(x)h(x)=x7+1的关系可得：h(x)=x3+x2+1=

39、h3x3+h2x2+h1x+h0根据前例方法先计算 rn-i(x)xn-imod g(x)可得2/6/202355兰州大学信息科学与工程学院电信、通信工程系4.4.循环码循环码编码器编码器循环码的特点一：可以采用反馈线性移位寄存器实现编码和伴随式计算以g(x)=x3+x+1的（7，4）循环编码器为例D0D1D2+门输入输入u(x)xn-k12码字输出码字输出2/6/202356兰州大学信息科学与工程学院电信、通信工程系4.4.循环循环码码编码器编码器以g(x)=x3+x+1的（7，4）循环编码器为例节拍信息组输入依存状态输出码字D0(x0)D1(x1)D2(x2)000011110120011

40、0301110410111500116000170000初态为初态为000门开门开四次移位后信四次移位后信息息1001全部输全部输出，出，关门关门，输，输出开关倒向出开关倒向2又循环回到又循环回到初始状态初始状态信信息息位位监监督督位位2/6/202357兰州大学信息科学与工程学院电信、通信工程系4.4.循环码循环码译码器译码器仍以g(x)=x3+x+1生成的（7，4）循环码译码为例复用器复用器+门门1门门2+门门2Y(x)s0s1s2错误图样检测电路只有1套，其译码电路比一般的(7,4)线性分组码大大简化2/6/202358兰州大学信息科学与工程学院电信、通信工程系4.4.循环码循环码(7，

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

42、4.循环码循环码循环码检错：循环码检错：CRC (Cyclic Redundancy Check,循环冗余校验循环冗余校验)常用的CRC码国际标准CRC-12：g(x)=x12+x11+x3+x2+x+1CRC-16:g(x)=x16+x15+x2+1CRC-CCITT:g(x)=x16+x12+x5+1CRC-32:g(x)=x32+x26+x23+x22+x16+x12+x11 +x10+x8+x7+x5+x4+x2+x+1CRC-12用于字符长度为6bit情况，后三种用于8bit字符。2/6/202361兰州大学信息科学与工程学院电信、通信工程系CRC 校验示例校验示例待校验数据：待校验

43、数据：1101,0110,11 g(x)=x4+x+1,即即10011 1 1 0 1 0 1 1 0 1 1 0 0 0 01 0 0 1 1 1 1 0 0 0 0 1 0 1 0 1 0 0 1 1 1 0 0 1 1 1 0 0 1 1 0 0 0 0 1 0 1 1 0 1 0 0 1 1 1 0 1 0 0 1 0 0 1 1 1 1 1 0余数余数传送序列传送序列 T(x)=1101,0110,11 11,10待发送的原数据待发送的原数据校验码2/6/202362兰州大学信息科学与工程学院电信、通信工程系CRC接收端的处理过程接收端的处理过程假设收到序列假设收到序列R(X)=11

44、01,1110,1111,10T(x)(出错)仍然用g(x)=x4+x+1,即10011 做做除数除数1 1 0 1 1 1 1 0 1 1 1 1 1 01 0 0 1 1 1 1 0 0 1 0 1 1 0 0 1 0 0 1 1 1 0 0 0 1 1 0 0 1 1 1 0 1 0 1 1 0 0 1 1 1 1 0 1 11 0 0 1 11 0 0 0 1 1 0 0 1 11 0 1 0非非0 0余数余数表示有错表示有错2/6/202363兰州大学信息科学与工程学院电信、通信工程系接收端的处理过程（续）接收端的处理过程（续）假设收到序列无误，则有假设收到序列无误，则有 R(X)=

45、T(X)=1101,0110,1111,10 仍然用 g(x)=x4+x+1,即10011 做做除除数数1 1 0 1 0 1 1 0 1 1 1 1 1 01 0 0 1 1 1 1 0 0 0 0 1 0 1 0 1 0 0 1 1 1 0 0 1 1 1 0 0 1 1 0 0 1 0 1 1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 1 1 0 0 0 0 0 0余数为余数为0 0表示正表示正确接收确接收2/6/202364兰州大学信息科学与工程学院电信、通信工程系5.5.卷积码卷积码卷积码卷积码是非分组码的典型代表，亦称是非分组码的典型代表，亦称连环码连环码。它是它是1

46、955年由埃里亚斯（年由埃里亚斯（Elias）最早提出。最早提出。与分组码的主要差异：与分组码的主要差异：卷积码编码器有记忆有记忆，在任意给定的时段，编码器的n个输出不仅与此时段的k个输入有关，而且与前m个输入有关卷积码记为（卷积码记为（n，k，m）n为输出码元数k为输入码元数m为编码器的存储器数2/6/202365兰州大学信息科学与工程学院电信、通信工程系5.5.卷积码卷积码卷积码编码卷积码编码串串并并转转换换.有限状态的有记忆系统有限状态的有记忆系统（最大延迟为（最大延迟为m）.并并串串转转换换输出码字输出码字序列序列C输入信息输入信息序列序列uucuc描述时序网络的方法描述时序网络的方法

47、解析表示法离散卷积法、生成矩阵法、码多项式法图形表示法状态图法、树图法、格图法2/6/202366兰州大学信息科学与工程学院电信、通信工程系5.5.卷积码卷积码卷积码编码卷积码编码现以一个二元（2，1，3）卷积码为例输入信息序列输入信息序列u=(u0u1u2)+输出码字序列输出码字序列c=(c0 c0 c1 c1 c2 c2)g有限状态的有记忆系统有限状态的有记忆系统k=1，即一个输入位n=2，即两个输出位m=3，即三级移位寄存器输出c=u*g=(c0c1c2)输出c=u*g=(c0 c1 c2)g 2/6/202367兰州大学信息科学与工程学院电信、通信工程系5.5.卷积码卷积码卷积码编码卷

48、积码编码离散卷积法离散卷积法以一个二元（2，1，3）卷积码为例由图可知 g1(x)=1+x2+x3 g=(1011)g2(x)=1+x+x2+x3 g=(1111)设u=(10111)，则有 c=(10111)*(1011)=(10000001)c=(10111)*(1111)=(11011101)最后输出的码字为 c=(1101000101010011)生成序列2/6/202368兰州大学信息科学与工程学院电信、通信工程系5.5.卷积码卷积码生成矩阵生成矩阵G生成矩阵法生成矩阵法理论分析理论分析 g g0 0g g0 0 g g1 1g g1 1 g g2 2g g2 2 g g3 3g g

49、3 3 0 0 0 0 0 g 0 g0 0g g0 0 g g1 1g g1 1 g g2 2g g2 2 g g3 3g g3 3 0 0G=G=0 0 g 0 0 g0 0g g0 0 g g1 1g g1 1 g g2 2g g2 2 g g3 3g g3 3 生成矩阵G是一个半无限的矩阵编码方程的矩阵形式：c=uG2/6/202369兰州大学信息科学与工程学院电信、通信工程系5.5.卷积码卷积码生成矩阵生成矩阵G已知 u=(10111),求得 g=(1011),g=(1111)代入公式，可求得 11 01 11 11 01 11 1111 0 0 0 0 0 0 0 0 0 11 0

50、1 11 0 11 01 11 1111 0 0 0 0 0 0 0 0 11 01 11 0 0 11 01 11 1111 0 0 0 0 0 0 0 11 01 11 0 0 0 11 01 11 1111 0 0 0 0 0 0 11 01 11 0 0 0 0 11 01 11 1111 C=uG=(10111)=(11 01 00 01 01 01 00 11)2/6/202370兰州大学信息科学与工程学院电信、通信工程系5.5.卷积码卷积码码多项式表达式码多项式表达式 工程应用工程应用u=(10111)=1+x2+x3+x4g=(1011)=1+x2+x3g=(1111)=1+x