聊城大学数字通信课件!第三章纠错编码12-3-31.ppt

《聊城大学数字通信课件!第三章纠错编码12-3-31.ppt》由会员分享，可在线阅读，更多相关《聊城大学数字通信课件!第三章纠错编码12-3-31.ppt（163页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数字通信原理数字通信原理LCU1第七章第七章 差错控制编码差错控制编码LCU2单元概述单元概述 实际信信道道传输数数字字信信号号时，不不可可避避免免地地会会产生生误码。差差错控控制制编码的的目目的的是是用用信信道道编码的方法的方法检测和和纠正正误码，降低降低误码率。率。LCU3单元学习提纲单元学习提纲 （1 1）前向纠错、检错重发差错控制方法；）前向纠错、检错重发差错控制方法；（2 2）检错和纠错的基本原理；）检错和纠错的基本原理；（3 3）码码距距的的定定义义，它它与与检检错错、纠纠错错能能力力的的关关系系；纠错编码误码率的计算纠错编码误码率的计算 （4 4）分组码、卷积码、线性码、系统码的

2、定义；）分组码、卷积码、线性码、系统码的定义；（5 5）线线性性分分组组码码中中监监督督方方程程、监监督督矩矩阵阵、生生成成方方程、生成矩阵的含义；程、生成矩阵的含义；LCU4 （6 6）汉明码的特点及构造；）汉明码的特点及构造；（7 7）循环码的特点及编码方法；）循环码的特点及编码方法；（8 8）循环码的一种解码方法；）循环码的一种解码方法；（9 9）卷卷积积码码的的编编码码方方法法，生生成成多多项项式式与与编编码码器器的的构造；构造；（1010）卷积码的树状图、网格图表示；）卷积码的树状图、网格图表示；（1111）卷积码维特比译码的基本原理和译码过程；）卷积码维特比译码的基本原理和译码过程

3、；LCU主要内容主要内容7.1 差差错错控制控制编码编码的基本概念的基本概念7.2 纠错编码纠错编码的基本原理的基本原理7.3 线线性分性分组码组码7.4 循循环码环码7.5 卷卷积码积码5LCU67.1 7.1 差错控制编码的基本概念差错控制编码的基本概念1、用差用差错控制控制编码来来检错和和纠错的原因的原因2、信道的分信道的分类3、差差错控制方式控制方式4、差差错控制控制编码的分的分类LCU77.1.1 7.1.1 用差错控制编码来检错和纠错的原因用差错控制编码来检错和纠错的原因LCU8u在中等传输速率（在中等传输速率（1200/2400波特）下，对于干线有波特）下，对于干线有线载波信道，

4、线载波信道，Pe约为约为10-410-6的数量级，对于无线的数量级，对于无线短波通信，短波通信，Pe只有只有10-210-3的数量级。的数量级。u对码速为对码速为64kbps的系统的系统,国际电报电话咨询委员会把国际电报电话咨询委员会把误码率误码率10-3的称为严重误码。的称为严重误码。u我国长途光缆通信系统的进网要求之一：误码性能我国长途光缆通信系统的进网要求之一：误码性能要优于要优于10-9。u千兆以太网的可接受的最高限度误码率为千兆以太网的可接受的最高限度误码率为10-10 LCU9为保证传输数据的完整性，通常采用一定的为保证传输数据的完整性，通常采用一定的措施，措施，如如利用均衡器利用

5、均衡器纠正信道中的正信道中的乘性干乘性干扰；加大加大发送功率、送功率、扩展信道展信道频带宽度度等等办法来减法来减少少加性干加性干扰。采用上述方法仍难以满足要求时，必须采用上述方法仍难以满足要求时，必须采用差错控制措施，即用采用差错控制措施，即用差错控制编码差错控制编码来来检检错错和和纠错纠错。LCU10 1 1、随机信道随机信道：误码的出现是随机的，误码的出现是随机的，误码之间误码之间是统计独立的。是统计独立的。如由正态分布白噪声引起的误码如由正态分布白噪声引起的误码（称为（称为随机误码随机误码随机误码随机误码）2 2、突发信道突发信道：误码是成串集中出现的，误码是成串集中出现的，即在短促即在

6、短促的时间区间存在大量误码，在较长的时间区间无误的时间区间存在大量误码，在较长的时间区间无误码出现。码出现。产生产生突发误码突发误码突发误码突发误码的主要原因是脉冲干扰的主要原因是脉冲干扰 3 3、混合信道混合信道：既存在随机误码又存在突发误码的既存在随机误码又存在突发误码的信道称为混合信道信道称为混合信道。7.1.2 7.1.2 信道的分类信道的分类LCU11 1、检错重重发方式（方式（ARQ）2、前向、前向纠错方式（方式（FEC）3、混合、混合纠错检错方式（方式（HEC）4、反、反馈校校验方式（方式（IRQ）7.1.3 7.1.3 差错控制方式差错控制方式LCU12LCU13 1 1、检错

7、重发方式、检错重发方式（ARQ）原理原理:采用采用检错重重发方式，方式，发端端经编码后后发出能出能检测错误的的码；接收端收到后；接收端收到后经检验如果如果发现传输中有中有错误，则通通过反向信道把反向信道把这一判断一判断结果反果反馈给发送端。然后送端。然后发送端把信息重送端把信息重发一次，直到一次，直到接收端确接收端确认为止。止。要求要求:采用采用这种差种差错控制方法控制方法需要具需要具需要具需要具备备双向通道双向通道双向通道双向通道，一般在一般在计算机数据通信中算机数据通信中应用。用。LCU14 ARQ停发等待重发方式停发等待重发方式：发对或发错，发送端均要发对或发错，发送端均要等待接收端的回

8、应。特点是系统简单，时延长。等待接收端的回应。特点是系统简单，时延长。图中图中ACK是确认信号，是确认信号，NAK是否认信号。是否认信号。LCU15 2、前向纠错方式（、前向纠错方式（FEC）原理：原理：发送端送端经编码发出能出能纠正正错误的的码，接收，接收端收到端收到这些些码组后，通后，通过译码能能发现并并纠正正误码。要求：要求：前向前向纠错方式不需要反方式不需要反馈通道，特通道，特别适合适合只能提供只能提供单向信道向信道的的场合，特点是合，特点是时延小，延小，实时性性好，但系好，但系统复复杂。但随着。但随着编码理理论和微和微电子技子技术的的发展，展，编译码设备成本下降，加之有成本下降，加之

9、有单向通信和控向通信和控制制电路路简单的的优点，在点，在实际应用中日益增多。用中日益增多。LCU16 3、混合纠错检错方式（、混合纠错检错方式（HEC）原理：原理：混合纠错检错方式是前向纠错方式和检错混合纠错检错方式是前向纠错方式和检错重发方式的结合，重发方式的结合，发送端发出的码不但有一定的纠错发送端发出的码不但有一定的纠错能力，对于超出纠错能力的错误要具有检错能力。能力，对于超出纠错能力的错误要具有检错能力。这种方式在实时性和复杂性方面是前向纠错和检错这种方式在实时性和复杂性方面是前向纠错和检错重发方式的折衷，因而在近年来，在数据通信系统中重发方式的折衷，因而在近年来，在数据通信系统中采用

10、较多。采用较多。LCU17 4、反馈校验方式（、反馈校验方式（IRQ）原理：原理：又称回程校又称回程校验。收端把收到的数据序列全部。收端把收到的数据序列全部由反向信道送回由反向信道送回发送端，送端，发送端比送端比较发送数据与回送数据与回送数据，从而送数据，从而发现是否有是否有错误，并把，并把认为错误的数的数据重新据重新发送，直到送，直到发送端没有送端没有发现错误为止。止。优点：优点：优点：优点：不需要不需要纠错、检错的的编译器，器，设备简单。缺点：缺点：缺点：缺点：需要反向信道；需要反向信道；实时性差；性差；发送端需要一定送端需要一定容量的存容量的存储器。器。IRQ方式方式仅适用于适用于传输速

11、率速率较低、低、数据差数据差错率率较低的控制低的控制简单的系的系统中。中。LCU187.1.4 7.1.4 差错控制编码的分类差错控制编码的分类 1、按照差、按照差错控制控制编码的不同功能，可以分的不同功能，可以分为检错码（仅能能检测误码）、）、纠错码（仅可以可以纠正正误码）和和纠删码（兼有（兼有纠错和和检错功能）。功能）。2、按照、按照信息信息信息信息码码元元元元和附加的和附加的监监督督督督码码元元元元之之间的的检验关关系可以分系可以分为线性性码（信息（信息码元和元和监督督码元元满足一足一组线性方程）和性方程）和非非线性性码。3、按照、按照信息信息信息信息码码元元元元和和监监督督督督码码元元

12、元元之之间的的约束关系可以束关系可以分分为分分组码和和卷卷积码。LCU19 4.根据信息码元在编码前后是否保持原来的形式不根据信息码元在编码前后是否保持原来的形式不变，可分为变，可分为系统码系统码和和非系统码非系统码。5、按照纠正错误的类型不同，可以分为、按照纠正错误的类型不同，可以分为纠正随机错纠正随机错误的码误的码和和纠正突发错误的码纠正突发错误的码。6、按照构成差错控制编码的数学方法来分类，可以、按照构成差错控制编码的数学方法来分类，可以分为分为代数码、几何码代数码、几何码和和算术码算术码。其中代数码建立在近。其中代数码建立在近代数学基础上，是目前发展最为完善的编码，其中线代数学基础上，

13、是目前发展最为完善的编码，其中线性码是是代数码的一个最重要的分支。性码是是代数码的一个最重要的分支。7、按照每个码元的取值不同，可以分为、按照每个码元的取值不同，可以分为二进制码二进制码和和多进制码多进制码。LCU20卷积码卷积码非线性码非线性码线性码线性码纠错码纠错码分组码分组码循环码循环码非循环码非循环码纠随机纠随机错误码错误码纠突发纠突发错误码错误码纠随机和突纠随机和突发错误码发错误码纠同步纠同步错误码错误码纠错码分类纠错码分类LCU217.2 7.2 纠错编码的基本原理纠错编码的基本原理1、纠错编码的基本思想的基本思想2、码重、重、码距、最小距、最小码距的定距的定义3、码距与距与检错和

14、和纠错能力能力4、差差错控制控制编码的效率的效率5、几种常用的几种常用的简单检错码LCU22回忆：回忆：香农的信道编码定理香农的信道编码定理 RC R=e+1Ae1dmin(a)LCU30（2）在一个码组内纠正）在一个码组内纠正t个误码，要求最小码个误码，要求最小码距距dmin=2t+11tABtdminLCU31（3）在一个码组内纠正）在一个码组内纠正t个误码，同时检测个误码，同时检测e个个(et)误码（当误码数大于误码（当误码数大于t时就不能纠错，只能检测时就不能纠错，只能检测e个个误码），要求最小码距误码），要求最小码距dmint+e+1ABtedmint(c)LCU32 假设在随机信道

15、中发送假设在随机信道中发送“0”时的错误概率和发送时的错误概率和发送“1”时的相等，都等于时的相等，都等于p,且且p1，则容易证明，则容易证明，在在码长为码长为n的码组中恰好发生的码组中恰好发生r个错码的概率为个错码的概率为7.2.4 7.2.4 差错控制编码的效率差错控制编码的效率LCU33例如：当例如：当码长n=7,p=1e-3时，有，有上式表明，即使是上式表明，即使是较简单的差的差错控制控制编码也具也具有有较大大实用价用价值。LCU347.2.5 7.2.5 几种常用的简单检错码几种常用的简单检错码1、奇偶、奇偶监督督码2、二、二维奇偶奇偶监督督码3、恒比、恒比码4、正反、正反码LCU3

16、5 奇奇偶偶监监督督码码的的编编码码规规则则是是在在信信息息位位后后加加上上一一位位监监督督位位形形成成具有检错能力的码。具有检错能力的码。如如果果是是偶偶校校验验，则则要要求求整整个个码码字字中中“1”的的个个数数为为偶偶数数，例例如如1 0 1 1 0 0 1 0 当传输过程中当传输过程中出现奇数个错误出现奇数个错误，接收端都能发现有无错误，但，接收端都能发现有无错误，但不能发现偶数个错误不能发现偶数个错误，比如，比如1 0 1 1 0 0 1 0 1 0 1 0 0 0 1 0 有错有错1 1 1 0 0 1 1 0 有错有错1 0 1 0 0 1 1 0 不能确定不能确定 如如果果是是

17、奇奇校校验验，则则要要求求整整个个码码字字中中“1”的的个个数数为为奇奇数数，例例如如1 0 1 1 0 0 1 1一、奇偶监督码一、奇偶监督码LCU36 行行列列奇奇偶偶监监督督码码亦亦称称水水平平垂垂直直奇奇偶偶监监督督码码，它它是是将将若若干干个个信信息息码码字字按按每每个个码码字字一一行行排排列列成成矩矩阵阵形形式式，然然后后在在每每一一行行和和每每一列的码元后面附加一位奇（偶）监督码元。一列的码元后面附加一位奇（偶）监督码元。行列奇偶监督码不但能检测出某一行或某一列的所有奇数行列奇偶监督码不但能检测出某一行或某一列的所有奇数个错误，有时还能检测出某些偶数个错误。个错误，有时还能检测出

18、某些偶数个错误。不能检测构成矩形四角的错码。不能检测构成矩形四角的错码。信息码元信息码元 监督码元监督码元 1 0 1 1 0 0 0 1 1 1 0 1 0 0 1 0 0 0 1 0 0 1 1 1 0 1 1 0 1 1 0 0 1 0 0 1 1 0 0 1监督码元监督码元 1 0 1 1 0 0 0 1二、二维奇偶监督码二、二维奇偶监督码信息码元信息码元 监督码元监督码元1 0 1 1 0 0 0 11 1 0 1 0 0 1 00 1 1 0 1 1 1 10 1 1 0 1 1 0 01 0 0 1 1 0 0 11 0 1 1 0 0 0 1LCU37 恒恒比比码码是是从从某某

19、种种特特定定长长度度的的码码字字中中选选出出那那些些“1 1”的的个个数数与与“0 0”的个数保持恒定比例的码字作为许用码字。的个数保持恒定比例的码字作为许用码字。五单位数字保护电码五单位数字保护电码 码字长度为码字长度为5，只选用码字中含有，只选用码字中含有三个三个“1”和两个和两个“0”的码字作为许的码字作为许用码字来表示用码字来表示10个阿拉伯数字个阿拉伯数字1，2，9，0，这种码亦称，这种码亦称“5中取中取3码码”。例：中文电报编码：例：中文电报编码：通通 信信 6639 020710101 10101 10110 10011 01101 11001 01101 11100 国际电报通

20、信中广泛采用的是国际电报通信中广泛采用的是“7中中取取3码码”，许用码字共有个，可分别表示，许用码字共有个，可分别表示26个字母和其它的一些符号。个字母和其它的一些符号。数数字字数字保护数字保护电码电码123456789001011110011011011010001111010111100011101001101101三、三、恒比码恒比码LCU38 正正反反码码是是一一种种简简单单的的能能够够纠纠正正错错码码的的编编码码。其其中中监监督督位位数数与与信信息息位位数数相相同同，监监督督码码元元与与信信息息码码元元相相同同（是是信信息息码码的的重重复复）或或者者相反（是信息码的反码），则由信息码

21、中相反（是信息码的反码），则由信息码中“1 1”的个数而定。的个数而定。四、四、正反码正反码 电报通信中使用的正反码的码长电报通信中使用的正反码的码长n=10,信息位信息位k=5,监监督位督位r=5，编码规则为：，编码规则为：a.信息位中有信息位中有奇数个奇数个“1”时，监督位是信息位的简单时，监督位是信息位的简单重复。重复。b.信息位中有信息位中有偶数个偶数个“1”时，监督位是信息位的反码。时，监督位是信息位的反码。信息位是信息位是11001码组是码组是1100111001信息位是信息位是10001码组是码组是1000101110LCU39电报通信中使用的正反通信中使用的正反码的的译码规则为

22、：先将接收码组中信息位和监督位按位模先将接收码组中信息位和监督位按位模2相加，得到相加，得到一个一个5位的合成码组，然后由此合成码组产生一个校位的合成码组，然后由此合成码组产生一个校验码组验码组a.若接收码组的信息位有若接收码组的信息位有奇数个奇数个“1”，则合成，则合成码组就是校验码组；码组就是校验码组；b.若接收码组的信息位有若接收码组的信息位有偶数个偶数个“1”，则合成，则合成码组的反码作为校验码组；码组的反码作为校验码组；LCU40发送码组是发送码组是1100111001接收码组是接收码组是1100111001合成码组合成码组1100111001=00000校验码组校验码组00000发

23、送码组是发送码组是1100111001接收码组是接收码组是1000111001？LCU417.3 7.3 线性分组码线性分组码1、线性分性分组码的基本概念的基本概念2、监督矩督矩阵、生成矩、生成矩阵、校正子、校正子3、汉明明码LCU427.3.1 7.3.1 线性分组码的基本概念线性分组码的基本概念1.代数学中把对某种运算满足以下条件的一类集合称为代数学中把对某种运算满足以下条件的一类集合称为群群：u封封闭性性：集合中任意两个元素：集合中任意两个元素经该运算后仍运算后仍为该集合的元素集合的元素u存在存在单位元素位元素：集合中任意元素与：集合中任意元素与该元素运算后仍元素运算后仍为原来的元素原来

24、的元素u存在逆元素存在逆元素：集合中任一元素与某元素运算后能得到：集合中任一元素与某元素运算后能得到单位元素位元素u结合律成立合律成立：（：（A+B）+C=A+(B+C)线性分组码：线性分组码：信息位和监督位是由一些信息位和监督位是由一些线性代数方程线性代数方程联系起来，联系起来，建立在代数学群论基础上，又称建立在代数学群论基础上，又称群码群码。LCU线性分组码的性质线性分组码的性质431.任意两个任意两个码组之和仍之和仍为一准用一准用码组。2.码的最小距离等于非零的最小距离等于非零码的最小重量的最小重量3.线性性码中中单位元素是全零位元素是全零码组4.线性性码中一个元素的逆元素就是中一个元素

25、的逆元素就是该元素本元素本身身LCU44 2.2.对于奇偶监督码的偶校验，我们用下式作为作为对于奇偶监督码的偶校验，我们用下式作为作为监督方程。监督方程。监督方程。监督方程。在接收端译码时，若在接收端译码时，若S=0，就认为无错。，就认为无错。若若S=1，就认为有错。，就认为有错。这里称这里称S为为校正子校正子（校验子），又称伴随式。（校验子），又称伴随式。在此例中，由于只有一位监督码元，一个监督方程，在此例中，由于只有一位监督码元，一个监督方程，所以所以只能检错，无法纠错。只能检错，无法纠错。LCU45如果监督位增加一位，变成两位，则能增加一个类如果监督位增加一位，变成两位，则能增加一个类似

26、上式的监督关系式。两个校正子的组合：似上式的监督关系式。两个校正子的组合：00、01、10、11，一种表示无错，其余三种指示一位错码的一种表示无错，其余三种指示一位错码的3种不同位置。种不同位置。r个监督关系式能指示一位错码有个监督关系式能指示一位错码有 个可能位置个可能位置LCU46 一般说来，若码长为一般说来，若码长为n，信息位数为，信息位数为k，则监督位，则监督位数为数为r=n-k。如果希望如果希望用用r个监督关系式来指示一位错码的个监督关系式来指示一位错码的n种种可能位置，可能位置，则要求：则要求：LCU47 3.3.对于（对于（7 7，4 4）线性分组码，码元为）线性分组码，码元为

27、如果传送如果传送a a6 6,a,a5 5,a,a4 4,a,a3 3共共4 4位数据，要求能自动纠正一个位数据，要求能自动纠正一个误码，须增加误码，须增加3 3位监督码位监督码a a2 2,a,a1 1,a,a0 0。假设有三个相应的监督方程，假设有三个相应的监督方程，S1，S2，S3表示三个监督关系式表示三个监督关系式中的校正子。中的校正子。在接收端根据校正子的在接收端根据校正子的取值组取值组合合能纠正某一位的错误。能纠正某一位的错误。a6,a5,a4,a3,a2,a1,a0LCU48 监督码监督码:由上表得到关系式：由上表得到关系式：LCU49 在发送端编码时，信息位在发送端编码时，信息

28、位a6,a5,a4,a3的值决定于输的值决定于输入信号，因此它们是随机的。入信号，因此它们是随机的。监督位监督位a2,a1,a0应根据应根据信息位的取值按监督关系来确定信息位的取值按监督关系来确定。a2a1a0000011101110110101011000a6a5a4a300000001001000110100010101100111LCU50接收端收到每个码组后，接收端收到每个码组后，先按式计算出先按式计算出S1,S2,S3，再，再按表判断错码情况按表判断错码情况。例如：接收码组为例如：接收码组为0000011 则则S1？S2？S3？LCU517.3.2 7.3.2 线性分组码的一般原理线

29、性分组码的一般原理从上从上节例子可以看出，例子可以看出，线性分性分组码的的监督方程可以督方程可以用矩用矩阵形式来表达（形式来表达（无无误码时，下式成立）：，下式成立）：1 1、监督矩阵、监督矩阵LCU52设发送序列为设发送序列为A A，则监督方程也可以写为：，则监督方程也可以写为：行数就是监督关系式的数行数就是监督关系式的数目目每行中每行中“1 1”的数目表示相的数目表示相应码元之间存在的监督应码元之间存在的监督关系关系LCU53 式中的系数矩阵称为式中的系数矩阵称为监督矩阵监督矩阵监督矩阵监督矩阵，用，用H表示。如果用表示。如果用虚线分为两部分，左边为虚线分为两部分，左边为P矩阵，是一个矩阵

30、，是一个r*k阶矩阶矩阵；右边为阵；右边为Ir矩阵，是一个矩阵，是一个r*r阶单位方阵。这种形阶单位方阵。这种形式的式的H矩阵也被称为矩阵也被称为典型阵。典型阵。IrPLCU54已知已知监督方程和信号督方程和信号码元元时可以可以按下式按下式算出算出监督督码元元，式中，式中用的是用的是P矩矩阵。或者用下式来计算，式中的矩阵是或者用下式来计算，式中的矩阵是P的转置矩阵，的转置矩阵，称为称为Q矩阵矩阵。2 2、生成矩阵、生成矩阵QPLCU55在在Q的左的左边加一个加一个k*k阶单位方位方阵，就生成一，就生成一个新的矩个新的矩阵G。这个新矩阵这个新矩阵G称为称为生成矩阵生成矩阵，因为可由它，因为可由它

31、产生整个码组产生整个码组A。IkLCU56监督矩阵监督矩阵生成矩阵生成矩阵LCU例例题：已知某：已知某线性性码的的监督矩督矩阵求其典型求其典型监督矩督矩阵、生成矩、生成矩阵、该码的最小距的最小距离和离和纠错能力能力57最小距离为最小距离为3 3，纠正纠正1 1位错码位错码LCU583 3 校正子校正子 设发送码组设发送码组A为一为一n列的行矩阵，发送码组在传列的行矩阵，发送码组在传输过程中出现了误码，接收端收到了输过程中出现了误码，接收端收到了B矩阵，也是矩阵，也是一一n列的行矩阵。列的行矩阵。设收发码组之差设收发码组之差E=B-A（模（模2），称为），称为错误图样错误图样。LCU59校正子校

32、正子S可以根据可以根据接收序列接收序列B和和H矩矩阵来来计算。算。可见校正子只与错误图样有关，与发送序列可见校正子只与错误图样有关，与发送序列无关，是一个信道参数。无关，是一个信道参数。u如果不出现误码，校正子如果不出现误码，校正子S=0。u如果有误码，通过计算校正子如果有误码，通过计算校正子S来指示误码的来指示误码的位置和纠正误码。位置和纠正误码。LCU60 举例：设发送的序列举例：设发送的序列A=0001011 错误图样错误图样 E=0001000 接收到的序列接收到的序列B=0000011，计算校正子：，计算校正子：=(0 1 1)指示指示a3有错误有错误 LCU61 1.汉明明码是是1

33、950年由年由美国美国贝尔实验室室汉明提出来的，明提出来的，是第一个是第一个设计用来用来纠正正错误的的线性分性分组码，汉明明码被广泛用于数字通信和数据存被广泛用于数字通信和数据存储系系统中。中。7.3.3 7.3.3 汉明（汉明（Hamming)码码LCU62 2.汉明码（汉明码（n,k)是一种可用于纠正是一种可用于纠正1个随机错误的循环个随机错误的循环编码。一般汉明码的参数如下编码。一般汉明码的参数如下：码长:n=2r-1 信息位信息位:k=2r-1-r 最小最小码距：距：d0=3，通常用于通常用于FEC系系统汉明码的编码效率汉明码的编码效率LCU63 纠错一位纠错一位的一般汉明码结构的一般

34、汉明码结构监督位监督位r信息位信息位k码字长度码字长度n347411155263165763LCU64监督矩督矩阵：它的：它的n列分列分别由全零之外的由全零之外的2r-1个个r位位码组构成，并且每个构成，并且每个码组只出只出现一次。如一次。如与前不同的另一个与前不同的另一个监督矩督矩阵：LCU65循环码是线性分组码中的一类，是以现代代数理论循环码是线性分组码中的一类，是以现代代数理论作为基础建立起来的。作为基础建立起来的。循环码的编码和译码设备相对简单循环码的编码和译码设备相对简单循环码的检错和纠错能力较强，常用于循环码的检错和纠错能力较强，常用于CRCCRC校验。校验。7.4 循环码概述循环

35、码概述LCU66 7.4 7.4 循环码内容循环码内容1.循循环码的基本概念的基本概念2.循循环码的性的性质3.循循环码的生成矩的生成矩阵4.寻找任一找任一(n,k)循循环码的生成多的生成多项式式5.循循环码的的监督矩督矩阵6.循循环码的的编码方法方法7.循循环码的解的解码方法方法LCU67循循环码除了具有除了具有线性性码的一般性的一般性质外，外，还具有循具有循环性，即任一性，即任一码组循循环移移动一位一位(将最右端的将最右端的码元移至元移至左端，或反之左端，或反之)以后，仍以后，仍为该码中的一个中的一个码组。即若。即若 是是许用用码组，则也是也是许用用码组。（不（不论左移、右移和移位位数）左

36、移、右移和移位位数）一、一、循环码的基本概念循环码的基本概念LCU68循循环码举例例(7,3)循循环码（左移）（左移）00101110101110101110001110011110010110010110010110000000循环码举例循环码举例2(6,3)循环码（循环码（P312）LCU69 例如例如A=1100101循环码的系数矩阵：循环码的系数矩阵：码多项式：码多项式：LCU70a.线性线性码码（封闭性、单位元素、逆元素、结合律）（封闭性、单位元素、逆元素、结合律）b.码多项式按模运算，码多项式按模运算，模为模为xn+1二、循环码的性质二、循环码的性质LCU71 对于整数对于整数对于

37、整数对于整数m,m,若可以表示为若可以表示为若可以表示为若可以表示为 则称则称则称则称mp(mp(模模模模n)n)，或称，或称，或称，或称mm与与与与p p是同余的。是同余的。是同余的。是同余的。码多项式码多项式码多项式码多项式F(x)F(x)被被被被n n次多项式次多项式次多项式次多项式N(x)N(x)除，得到商式除，得到商式除，得到商式除，得到商式Q(x)Q(x)和和和和一个次数小于一个次数小于一个次数小于一个次数小于n n的余式的余式的余式的余式R(x)R(x)，即，即，即，即则则则则 F(x)R(x)(F(x)R(x)(模模模模N(x)N(x)知识回顾知识回顾LCU72码多项式系数仍按

38、码多项式系数仍按模模2 2运算，即运算，即只取值只取值0 0和和1 1。例如例如有有模模2加加 0+0=0 0+1=1 1+0=1 1+1=0模模2乘乘00=001=010=011=1注意注意:模模2运算加法和减法是等价的，在式子中通运算加法和减法是等价的，在式子中通常用加法运算符，具体模常用加法运算符，具体模2运算的规则定义如下：运算的规则定义如下：一般情况下，取码多项式的模为一般情况下，取码多项式的模为xn+1LCU73若若T（X）是长度为）是长度为n的循环码一个许用码组，则的循环码一个许用码组，则左移左移i位后的位后的xiT（X）按模）按模xn+1运算也是一个许运算也是一个许用码组。即若

39、用码组。即若xiT（X）T(X)，则则T(X)也是也是一个许用码组。一个许用码组。c.循环移位循环移位LCU74例如某循例如某循环码1100101，则T(X)=X6+X5+X2+1,XT(X)=X7+X6+X3+X,余数构成的码是余数构成的码是1001011，正好是左移一位的结果，正好是左移一位的结果LCU75例如某循例如某循环码1100101，则T(X)=X6+X5+X2+1,左移两位左移两位余数构成的码是余数构成的码是0010111重要结论：重要结论：即即n位码组循环左移位码组循环左移i位等价于位等价于相应多项式乘以相应多项式乘以xi后取后取xn+1的模所得余数的模所得余数。LCU76循循

40、环码举例例(7,3)循循环码编号编号a6a5a4a3a2a1a0编号编号a6a5a4a3a2a1a00000000041001011100101115101110020101000611001013011100171110010LCU77 什么是生成矩阵？什么是生成矩阵？可以产生整个码组的矩阵。可以产生整个码组的矩阵。有了生成矩阵有了生成矩阵G，就可以由，就可以由k个信息位得出整个信息位得出整个码组，而且生成矩阵个码组，而且生成矩阵G的每一行都是一个码组。的每一行都是一个码组。若能找到若能找到k个线性无关的码组个线性无关的码组,就能构成矩阵就能构成矩阵G。否则，给定的信息位与编出的码组就不是一

41、一对否则，给定的信息位与编出的码组就不是一一对应的。应的。三、循环码的生成矩阵三、循环码的生成矩阵G GLCU781.在循环码中，一个在循环码中，一个(n，k)码有码有2k 个不同码组，个不同码组，若用若用g(x)表示其中表示其中前前(k-1)位皆为位皆为0的码组的码组，即，即则则 都是码组，而都是码组，而且这且这k个码组是线性无关的。因此可以个码组是线性无关的。因此可以用来构成用来构成循环码的生成矩阵循环码的生成矩阵G。g(x)=01xx k位位n-k位位LCU792.生成多项式生成多项式g(x)：l连连0长度最多有长度最多有k-1位，满足位，满足常数项常数项a0=1；如如0011101因为

42、循环码中除全因为循环码中除全“0”码外，再没有连续码外，再没有连续k位均为位均为“0”的码组。否则会出现的码组。否则会出现k个信息位全为个信息位全为“0”，但是，但是监督位不为监督位不为“0”的码组。的码组。l唯一的唯一的(n-k)次多项式次多项式(在非零码组中次在非零码组中次数最低数最低)；lg(x)必须是必须是xn+1的因式的因式（见后面分析）。（见后面分析）。LCU80 循环码生成多项式的定义：循环码生成多项式的定义：前前k-1位位为0，第，第k位和第位和第n位位为1的的许用用码组可以可以用一个用一个码多多项式式g(x)来来标识，称，称为循循环码的生成多的生成多项式式。（7,k）g(x)

43、(7,6)x+1(7,4)x3+x2+1或或x3+x+1(7,3)(x+1)(x3+x2+1)或或(x3+x+1)(x+1)(7,1)(x3+x+1)(x3+x2+1)LCU81例例1 1 已知（已知（7 7，4 4）循环码的全部码组为）循环码的全部码组为0000000100010100010111001110001011010100110011101101100001001111100010010110011010010110001111010001110101111111写出该循环码的循环圈及生成多项式写出该循环码的循环圈及生成多项式LCU82一旦确定了一旦确定了g(x)，则整个，则整个(

44、n,k)循环码就被循环码就被确定了。因此确定了。因此,循环码的生成矩阵循环码的生成矩阵G可以写可以写成成LCU83利用多项式表示利用多项式表示(7,3)循环码：循环码：1.所有码多项式所有码多项式T(x)都可以被都可以被g(x)整除整除2.任一次数不大于任一次数不大于(k-1)的多项式乘的多项式乘g(x)都是都是码多项式码多项式LCU84这个生成矩个生成矩阵不是系不是系统码的典型生成矩的典型生成矩阵，可以通，可以通过行行变换（第一行加上第三行），（第一行加上第三行），变换成系成系统码的生的生成矩成矩阵：将此将此g(x)代入上式，得到代入上式，得到例例2(7,3)循环码循环码,唯一的一个唯一的一

45、个(n-k)次码多项式代表次码多项式代表的码组是的码组是0010111，写出它的生成矩阵写出它的生成矩阵LCU85利用下式可以产生全部许用码组利用下式可以产生全部许用码组LCU86因因为任一任一码多多项式式T(x)都是都是g(x)的倍式的倍式，所以有，所以有四、如何寻找任一（四、如何寻找任一（n,k）循环码的生成多项式）循环码的生成多项式1.g(x)本身也是一个码组，其次数为本身也是一个码组，其次数为n-k次。左移次。左移k位位后后xkg(x)是是n次多项式（一许用码组次多项式（一许用码组），），在模在模xn+1运算下，假设运算下，假设即即LCU87因为因为xkg(x)是是n次的，所以次的，所

46、以Q(x)=1。所以。所以即即g(x)是是xn+1的一个的一个(n-k)次因式次因式。这样就这样就可以通过对可以通过对xn+1的因式分解得到的因式分解得到g(x).LCU882.举例：模为举例：模为X7+1，构成的循环码，构成的循环码x7+1=(x+1)(x3+x+1)(x3+x2+1)（7,k）g(x)(7,6)x+1(7,4)x3+x2+1或或x3+x+1(7,3)(x+1)(x3+x2+1)或或(x3+x+1)(x+1)(7,1)(x3+x+1)(x3+x2+1)LCU89例题例题3：对于一（：对于一（7，3）循环码，其生成多）循环码，其生成多项式项式g(x)=(x3+x+1)(x+1)

47、求生成矩阵求生成矩阵G和信息码和信息码111,110对应的码组对应的码组LCU90假设信息码是假设信息码是111，生成序列为，生成序列为假设信息码是假设信息码是110，生成序列为，生成序列为LCU91五五.监督矩阵监督矩阵得到得到k次多次多项式式h(x)称称为监督多督多项式。式。设可得可得LCU92由此可得到循由此可得到循环码的的监督矩督矩阵(r行行n列列)例：（例：（7，3）循环码）循环码的生成多项式为的生成多项式为g(x)x4+x2+x+1，写出它的监督矩阵，写出它的监督矩阵先得到先得到h(x)x3+x+1也可利用也可利用G与与H的关系求解！的关系求解！LCU93六、循环码的编码方法六、循

48、环码的编码方法根据根据给定的定的(n,k)值选定生成定生成多多项式式g(x)设编码前的信息多前的信息多项式式为m(x),m(x)的最高的最高幂次次为k-1。xn-km(x)次数小于次数小于n，再去除，再去除g(x),余式余式r(x)次数小于次数小于n-k。将将r(x)+xn-km(x)，可被，可被g(x)整除，就得到循环码。整除，就得到循环码。LCU943.编出的码组编出的码组为：为：1.用用乘信息码多项式乘信息码多项式（相（相当于添加当于添加 n-k个个0，例如，例如g(x)x4+x3+x2+1时时发送发送100）2.用用除除，得到商，得到商和和，即，即信息位信息位监督位监督位LCU954.

49、将此余式加于信息位之后作为监督位将此余式加于信息位之后作为监督位即将即将r(x)与与相加，相加，得到的多项式必为得到的多项式必为一码多项式，因为它必能被一码多项式，因为它必能被g(x)整除，且商的整除，且商的次数不大于次数不大于(k-1)。LCU96监督位信息位信息位例例3(7,3)循环码循环码m(x)=x2+x,g(x)=x4+x2+x+1解解r(x)LCU97例例4：对于一个：对于一个(15,11)循环码，发送的信息序循环码，发送的信息序列列I(x)=11101010001，其生成多项式，其生成多项式g(x)=x4+x+1，写出它的循环码组。写出它的循环码组。LCU98（7 7，3 3）循

50、环码编码的硬件实现）循环码编码的硬件实现x x4 4+x+x2 2+x+1+x+1a+b+cd+输入m输出feSu硬件实现循环码编码，可以由除法电路实现。除法电路的主硬件实现循环码编码，可以由除法电路实现。除法电路的主体由一些体由一些移存器和模移存器和模2加法器加法器组成。组成。ug(x)的次数等于移位寄存器的级数；另外有一双刀双掷开关的次数等于移位寄存器的级数；另外有一双刀双掷开关S。如当如当(7,4)循环码循环码g(x)=x3+x+1时时u信息位输入时，信息位输入时，S S倒向下，输入信码一方面进入除法器进行运倒向下，输入信码一方面进入除法器进行运算，另一方面直接输出。算，另一方面直接输出