CH13-差错控制和信道编码

1、*兰州大学信息科学与工程学院电信、通信工程系通通 信信 原原 理理 兰州大学信息科学与工程学院兰州大学信息科学与工程学院M.P:M.P:+86-013993113069+86-013993113069Email: Email: oror AddressAddress：Department of Electronics & Information Science, School of Information Science&Engineering, Lanzhou University, Tianshui Southern Road 222#， Gansu Province，P.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

16、程学院电信、通信工程系17 四、常用简单检错码四、常用简单检错码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个独立随机差错。个独立随机差错。*兰州大学信息科学与工程学院电信、通信工程系18 简单的检错码简单

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

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

19、式如下所示：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整除，从而可以校验出来。整除，从而可以校验出来。*兰州大学信息科学与工程学院电信、通信工程系21 简单的检错码简单的检错码4.ISBN国际统一图书编号（例二）国际统一图书编号（例二）如通信原理的书号是ISBN 7-118-0429-X其中第一位数字“7”表示“中国”，“118”表示出版社，“01429”

20、表示书名编号，最后一位“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，大家可自行分析。*兰州大学信息科学与工程学院电信、通信工程系22 3. 3. 线性分组码线性分组码 近世代数学近世代数学有限域有限域的概念：的概念：有限个元素的集合，按规定可以进行的代数四则运算，其运算结果仍属于该集合中有限的元素。最简单的有限域 0，1Galoi

21、s域 1+1=0、 1+0=1、 0+1=1、 0+0=0 1x1=1、 1x 0=0、 0 x0 =0、 0 x1 =0定义线性分组码的加法为模定义线性分组码的加法为模2加，乘法为加，乘法为二进制乘法。且码字与码字的运算是各二进制乘法。且码字与码字的运算是各个相应比特位上的上述二进制运算规则。个相应比特位上的上述二进制运算规则。*兰州大学信息科学与工程学院电信、通信工程系23 3. 3. 线性分组码线性分组码基本概念基本概念码组中监督码与信息码之间满足线性方程；任意两个可用码组之和(逐位模2加)仍为一个可用码组奇偶监督码奇偶监督码最简单的线性分组码最简单的线性分组码偶校验时 奇校验时不满足线

22、性分组码的第二个性质。定义校正子（校验子伴随式）接收时进行校验计算： S=0无错； S=1有错（奇数个） 01n-1aaa001n-1S=aaa*兰州大学信息科学与工程学院电信、通信工程系24 3. 3. 线性分组码线性分组码一般情况下：一般情况下：如果码组中有2个监督码，校正子为S=s1,s2可以检测到三种误码状态S=00No error!01S= 10Error!11*兰州大学信息科学与工程学院电信、通信工程系25 3. 3. 线性分组码线性分组码如果码组中有如果码组中有r个监督码，假设码组中有个监督码，假设码组中有K个信息码，则线性分组码的长度应该为个信息码，则线性分组码的长度应该为n=

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

24、2c1c0为监督码*兰州大学信息科学与工程学院电信、通信工程系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. . . . . .kniririkniririkniiikniiiCCCCCCCC*兰州大学信息科学与工程学院电信、通信工程系28 3. 3. 线性分组码线性分组码据此可得如下结果据此可得如下结果：,111,221, 11

25、1, 001.0.0. . . . . .0.0kirnirikirnirikiniikiniiCCCCCCCC由上式可得由上式可得一致监督关系一致监督关系为为：.0TTHC*兰州大学信息科学与工程学院电信、通信工程系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 nnkrrkrrCCCCCC*兰州大学信息科学与工程

26、学院电信、通信工程系30 3. 3. 线性分组码线性分组码同样可知：同样可知：1,112,211,110, 011 , 2 , 3 , 4 . . . . . . . .njnjkrirniikrirniikiniikiniiCCjkCCCCCCCC*兰州大学信息科学与工程学院电信、通信工程系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,

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

28、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 ）*兰州大学信息科学与工程学院电信、通信工程系34 3. 3. 线性分组码线性分组码n位的码组，由k个信息位的输入消息u通过一个线性变换矩阵kn阶G来产生，称G生生成矩阵成矩阵G= ，I为k阶单位方阵典型生成矩阵01210011100100111()0011101c

29、u u uu GuI Q生成矩阵G()I QC=(c0c1c2c3c4c5c6)=(u0,u1,u2,u0 + u2,u0 + u1 + u2, u0 + u1, u1 + u2 )*兰州大学信息科学与工程学院电信、通信工程系35 3. 3. 线性分组码线性分组码将监督位线性方程组写为将监督位线性方程组写为即即 可见上述监督关系的线性方程组完全由矩阵可见上述监督关系的线性方程组完全由矩阵H所所决定。故将此决定。故将此r n的的H矩阵称为矩阵称为监督矩阵监督矩阵H= , I为为(n-kr)维（阶）单位方阵 典型监督矩阵典型监督矩阵01610 1100001110 100011000 1000 1

30、1000 10ccc 02301240151260000ccccccccccccc0()0TTTTH CP IC ()PI*兰州大学信息科学与工程学院电信、通信工程系36 3. 3. 线性分组码线性分组码根据前面所得可推导： G与与H生成的空间互为零空间，且生成的空间互为零空间，且G与与H可以可以互相转换。互相转换。 00TTTTH CC H TToPQQrP （即P、Q互为转置矩阵）0C u GTu G H 00uTG H ()0TTPG HI QPQI *兰州大学信息科学与工程学院电信、通信工程系37 3. 3. 线性分组码线性分组码校正子（码组伴随式）校正子（码组伴随式）发送码组C经过传

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

32、 C0C1C2+u0u1u2C4C5C6C3*兰州大学信息科学与工程学院电信、通信工程系39 3. 3. 线性分组码线性分组码译码器译码器由校正子关系可得T0123456123410232012430154126111001111101S=B H =b b b b b b b s s s s 1000010000100001sbbb sbbbb sbbb sbbb *兰州大学信息科学与工程学院电信、通信工程系40 3. 3. 线性分组码线性分组码译码器译码器10232012430154126ssssbbbbbbbbbbbbb b0b1b2b3b4b5b6+b0s1s2s3s4s1s2s3s4与

33、+r0c0b1与+r1c1b2与+r2c2b3与+r3c3b4与+r4c4b5与+r5c5b6与+r6c6伴随式计算电路错误图样检测电路*兰州大学信息科学与工程学院电信、通信工程系41 系统码系统码 VS. 非系统码非系统码非典型生成矩阵非典型生成矩阵-典型生成矩阵典型生成矩阵利用初等行变换初等行变换以及列交换列交换例如：10110000101100001011000010111000010000100001xxxxxxxxxxxx目标4 71010001010010100101100001011交换第 、两列31111000111010010100101100001011第 行乘以加到第行成

34、为新的第 行*兰州大学信息科学与工程学院电信、通信工程系42 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很大时，R1*兰州大学信息科学与工程学院电信、通信工程系43 4. 4. 循环码循环码基本概念基本概念线性分组码的一个子类，比较成熟任何一个可用码组经过循环移位后所得到的码组仍为一个可用码组 原码组 C=cn-1 cn-2 c1 c0 左移一

35、位 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的幂次表示：码元的位置；码的移位次数*兰州大学信息科学与工程学院电信、通信工程系44 4. 4. 循环码循环码基本概念基本概念如多项式C(x)= x6 + x4 +x+1C=1010011 c6x6可以看作c6从最低位c0左移6次的结果C(x)左移一位记作 C(1)(x) C(1)(x)=cn-2 xn-1 +

36、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-i*兰州大学信息科学与工程学院电信、通信工程系45 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

37、(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) *兰州大学信息科学与工程学院电信、通信工程系46 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 +1(0010111)*兰州大学信息科学与工程学院电信、通信工程系47 4. 4. 循环码循环码

38、生成多项式生成多项式g(x)对于(n,k)循环码来说，生成多项式g(x)是一个能除尽xn+1的（n-k）阶多项式。阶数低于n并能被g(x)除尽的一组多项式就构成一个(n,k)循环码阶数小于等于(n-1)并能被g(x)除尽的每个多项式都是循环码的可用码组多项式。 所以，循环码完全由其码组长度所以，循环码完全由其码组长度n和和生成多项式生成多项式g(x)所决定。所决定。*兰州大学信息科学与工程学院电信、通信工程系48 4. 4. 循环码循环码生成多项式生成多项式g(x)设构成循环码的信息码多项式为u(x)，其阶数不大于(k-1)，则有循环码组为C(x)=u(x) g(x)例如，n=7，g(x)=x

39、4+x3+x2+1是x7+1的一个因式；g(x)最高幂次为4=n-k；则k=3，r=4（即信息码3bits，监督码4bits）。可用码组如下：4325432654226530 g(x)=0 (0000000)1 g(x)=xxx1 (0011101)x g(x)=xxxx (0111010) xg(x)=xxxx (1110100) (x1) g(x)=xxx1 264522632 (1101001) (xx1) g(x)=xxx1(1010011)(x1) g(x)=xxx1 (0100111)(xx) g(x)=xxxx (1001110) *兰州大学信息科学与工程学院电信、通信工程系49

40、 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) *兰州大学信息科学与工程学院电信、通信工程系50 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）循环码为例

41、，n=7 x7+1=(x+1)(x3+x2+1)(x3+x+1)*兰州大学信息科学与工程学院电信、通信工程系51 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(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)循环码可以互为对

42、偶码循环码可以互为对偶码.*兰州大学信息科学与工程学院电信、通信工程系52 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(x)(uuu ) xg(x)1 g(x) *兰州大学信息科学与工程学院电信、通信工程系53 4. 4. 循环码循环码生成矩阵生成矩阵G为了进一步得到系统码，可作如下运算： xn-ku

43、(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) *兰州大学信息科学与工程学院电信、通信工程系54 4. 4. 循环码循环码例如：例如：已知已知(7,4)系统码的生成多项式为系统码的生成多项式为g(x)=x3+x2+1，求，求其生成矩阵其生成矩阵。 解：由 先求出n-in-i

44、r (x)x mod g(x) 662655542443233xr (x)xxx1000110 xr (x)xx10100011G(x)G0010111xxx+1xr (x)0001101xx1xr (x) 626mod g(x)55mod g(x)424mod g(x)323mod g(x)r (x)x xxr (x)x x1r (x)x xx+1r (x)x x1*兰州大学信息科学与工程学院电信、通信工程系55 4. 4. 循环码循环码监督矩阵监督矩阵H由于 xn+1=g(x) h(x) 生成多项式g(x)=gn-kxn-k+g1x+g0 监督多项式h(x)=hkxk+h1x+h0n -k

45、k000110021120n -10n21nkk1gh1 gh1 ghg h0 ghg hgh0 ghgh+ gh0 . . . . . . . 010100 000H=0 0kkkh hhh hhh hh*兰州大学信息科学与工程学院电信、通信工程系56 4. 4. 循环码循环码例如，已知例如，已知(7,3)系统循环码的生成多项系统循环码的生成多项式式g(x)=x4+x3+x2+1，求生成矩阵，求生成矩阵G及监督矩阵及监督矩阵H。解：由g(x) h(x)=x7+1的关系可得： h(x)=x3+x2+1=h3x3+h2x2+h1x+h0根据前例方法先计算 rn-i (x)xn-imod g(x)

46、可得6325243201230123012301231001110( )10100111001110110 0 0101100000 001011000 00001011000010110 0 0 xxxxG xxxxGxxxh h h hh h h hHh h h hh h h h *兰州大学信息科学与工程学院电信、通信工程系57 4. 4. 循环码循环码编码器编码器循环码的特点一：可以采用反馈线性移位寄存器实现编码和伴随式计算以g(x)=x3+x+1的（7，4）循环编码器为例D0D1D2+门输入输入u(x) xn-k12码字输出码字输出1XX2X3*兰州大学信息科学与工程学院电信、通信工程

47、系58 编码器编码器以g(x)=x3+x+1的（7，4）循环编码器为例节拍信息组输入依存状态输出码字D0(x0)D1(x1)D2(x2)0000111101200110301110410111500116000170000初态为初态为000门开门开四次移位后信四次移位后信息息1001全部输全部输出，出，关门关门，输，输出开关倒向出开关倒向2又循环回到又循环回到初始状态初始状态信信息息位位监监督督位位D0D1D2+门输入输入u(x) xn-k12码字输码字输出出*兰州大学信息科学与工程学院电信、通信工程系59 4. 4. 循环码循环码译码器译码器仍以g(x)=x3+x+1生成的（7，4）循环码译

48、码为例复用器复用器+门门1门门2+门门2Y(x)s0s1s2错误图样检测电路只有1套，其译码电路比一般的(7,4)线性分组码大大简化*兰州大学信息科学与工程学院电信、通信工程系60 4. 4. 循环码循环码(7，4)循环码循环码d=3g(x)=(x3+x+1)100101101011100010111H (8,4)非循环码d=410010110101110001011111111100011H (7，3)循环码d=4g(x)=(x3+x+1)(x+1)1000110010001100101110001101H 删删减减增增扩扩收收缩缩加长加长缩短缩短扩扩展展*兰州大学信息科学与工程学院电信、通

49、信工程系61 4. 4. 循环码循环码循环码检错循环码检错CRC (Cyclic Redundancy Check, 循环冗余校验循环冗余校验)一般能检测的错误： 突发长度n-k+1的错误，其中不可检出错误仅占2-(n-k) 所有与许用码组码距dmin-1的错误 所有奇数个错误CRC码在数据通信及移动通信中得到广泛应用*兰州大学信息科学与工程学院电信、通信工程系62 4. 4. 循环码循环码循环码检错：循环码检错：CRC (Cyclic Redundancy Check, 循环冗余校验循环冗余校验)常用的CRC码国际标准 CRC-12：g(x)=x12+x11+x3+x2+x+1 CRC-16

50、: 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用于字符长度为6bits情况，后三种用于8bits字符。*兰州大学信息科学与工程学院电信、通信工程系63 CRC 校验示例校验示例待校验数据：待校验数据：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

51、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待发送的原数据待发送的原数据校验码*兰州大学信息科学与工程学院电信、通信工程系64 CRC接收端的处理过程接收端的处理过程假设收到序列假设收到序列R(X)=1101,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

52、 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余数余数表示有错表示有错*兰州大学信息科学与工程学院电信、通信工程系65 接收端的处理过程（续）接收端的处理过程（续）假设收到序列无误，则有假设收到序列无误，则有 R(X)=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

53、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表示正表示正确接收确接收*兰州大学信息科学与工程学院电信、通信工程系66 5. 5. 卷积码卷积码卷积码卷积码是非分组码的典型代表，亦称是非分组码的典型代表，亦称连环码连环码。 它是它是1955年由埃里亚斯（年由埃里亚斯（Elias ）最早提出。）最早提出。与分组码的主要差异：与分组码的主要差异：卷积码编码器有记忆有记忆，在任意给定的时段，编码器的n个输出不仅与此时段的k个输入有关，而且与前m个输入有

54、关卷积码记为（卷积码记为（n，k，m）n为输出码元数k为输入码元数m为编码器的存储器数卷积码记为（卷积码记为（n，k，K）n为输出码元数k为输入码元数K为卷积码的约束长度K=m+1*兰州大学信息科学与工程学院电信、通信工程系67 5. 5. 卷积码卷积码卷积码编码卷积码编码串串并并转转换换.有限状态的有记忆系统有限状态的有记忆系统（最大延迟为（最大延迟为m）.并并串串转转换换输出码字输出码字序列序列C输入信息输入信息序列序列uucuc描述时序网络的方法描述时序网络的方法解析表示法 离散卷积法、生成矩阵法、码多项式法图形表示法状态图法、树图法、格图法*兰州大学信息科学与工程学院电信、通信工程系6

55、8 5. 5. 卷积码卷积码卷积码编码卷积码编码现以一个二元（2，1，4）卷积码为例有限状态的有记忆系统有限状态的有记忆系统 k=1，即一个输入位 n=2，即两个输出位 K=4即约束长度为4；即m=3，有三级移位寄存器输入信息序列输入信息序列u=(u0u1u2)+输出码字序列输出码字序列c= (c0 c0 c1 c1 c2 c2 ) g输出c = u*g = (c0c1c2)输出c = u*g = (c0 c1 c2 )g *兰州大学信息科学与工程学院电信、通信工程系69 卷积码编码卷积码编码离散卷积法离散卷积法以一个二元（以一个二元（2，1，4）卷积码为例）卷积码为例 由图可知由图可知 g1

56、(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)生成序列输入信息序列输入信息序列u=(u0u1u2)+输出码字序列输出码字序列c= (c0 c0 c1 c1 c2 c2 ) g输出c = u*g = (c0c1c2)输出c = u*g = (c0 c1 c2 )g *兰州大学信息科学与工程学院电信、通信工程系70 5. 5. 卷

57、积码卷积码生成矩阵生成矩阵G生成矩阵法生成矩阵法理论分析理论分析 g g0 0g g0 0 g g1 1g g1 1 g g2 2g g2 2 g g3 3g g3 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=uG*兰州大学信息科学与工程学院电信、通信工程系71 5. 5. 卷积码卷积码生成矩阵生成矩阵G已知 u=(1

58、0111) ，求得 g=(1011),g=(1111) 代入公式，可求得 1 11 1 0 01 1 1 11 1 1 11 1 0 0 0 0 0 0 0 0 0 0 11 01 11 11 0 0 0 0 0 0 0 0 0 0 11 01 11 11 0 0 0 0 0 0 0 0 0 0 11 01 11 11 0 0 0 0 0 0 0 0 0 0 11 01 11 11 C = uG= (10111)= (11 01 00 01 01 01 00 11)*兰州大学信息科学与工程学院电信、通信工程系72 5. 5. 卷积码卷积码码多项式表达式码多项式表达式 工程应用工程应用u=(10

59、111)=1+x2+x3+x4g=(1011)=1+x2+x3g=(1111)=1+x+x2+x3 则卷积码输出为：则卷积码输出为：c= (1+x2+x3+x4)(1+x2+x3) =1+x7=(10000001)c= (1+x2+x3+x4)(1+x+x2+x3) =1+x+x3+x4+x5+x7=(11011101)输出序列为输出序列为 C=(1101000101010011)*兰州大学信息科学与工程学院电信、通信工程系73 5. 5. 卷积码卷积码状态图法状态图法描述描述现以（2，1，3）卷积码为例： k=1，n=2，K=3，m=2 总的可能状态数为 2km=22=4种，即 00, 10

60、, 01, 11 每次可能的输入有两个即 2k=2 每次可能的输出状态也只有两个状态图的画法 圆圈中的数字状态 状态之间的连线和箭头转移方向（分支） 分支上的数字转移时输出的码字 括号中的数字转移时输入的信息数字*兰州大学信息科学与工程学院电信、通信工程系74 5. 5. 卷积码卷积码状态图法状态图法（2，1，3）卷积码为例：）卷积码为例：（2，1，3）卷积码状态转移图）卷积码状态转移图0011100111(1)01(1)01(0)11(0)10(0)00(1)00(0)10(1)*兰州大学信息科学与工程学院电信、通信工程系75 5. 5. 卷积码卷积码树图法树图法按时间展开l=0l=1l=2l=3l=4l