《差错控制(1).ppt》由会员分享，可在线阅读，更多相关《差错控制(1).ppt（93页珍藏版）》请在三一办公上搜索。
1、第7章 差错控制,本章节教学说明本章重点学习差错控制基本原理、简单差错控制编码、汉明码、循环码本章主要介绍检错和纠错的方法和原理本章主要详细介绍了常用的差错控制方法的基本原理,本章节内容概述差错控制基本思路随机差错与突发差错检错和纠错的基本原理码距与检错和纠错的关系简单的差错控制编码汉明码循环码,本章节学习重点、难点检错和纠错的基本原理简单的差错控制编码汉明码循环码,本章节学习目标熟悉检错和纠错的基本思路和原理熟悉掌握简单差错编码、汉明码、循环码的检错和纠错机制理解汉明码、循环码的编码原理,本章节学习能力要素及基础要求课前预习相关内容能够运用差错控制的编码技术对数据进行检错和纠错,本章节学习方
2、法建议预习复习结合课堂学习与课外学习结合自学与探讨结合课后作业与章节个人总结结合寻求教师答疑与学习反馈结合,差错控制是提高数字通信可靠性的重要方法，是数字通信中必须具有的功能。,7.1 差错控制的基本概念及原理,7.1.1 差错控制的基本概念 造成误码的原因很多，但主要原因可以归结为两点：一是信道不理想造成的符号间干扰；二是噪声对信号的干扰。差错即是误码。差错控制的核心是抗干扰编码，或差错纠正编码，简称纠错编码。,差错控制的基本思路是：发送端在被传输的信息序列上附加一些码元（称为监督码元），这些附加码元与信息（指数据）码元之间存在某种确定的约束关系；接收端根据既定的约束规则检验信息码元与监督码
3、元之间的这种关系是否被破坏，如传输过程中发生差错，则信息码元与监督码元之间的这一关系受到破坏，从而使接收端可以发现传输中的错误，乃至纠正错误。,7.1.2 随机差错与突发差错,数字信号在信道中传输，会受到各种不同的噪声干扰。噪声大体分为两类：随机噪声和脉冲噪声（突发噪声）。随机差错又称独立差错，是指那些独立地、稀疏地和互不相关地发生的差错。突发差错是指一串串，甚至是成片出现的差错，差错之间有相关性，差错出现是密集的。,实际信道是复杂的，所出现的错误也不是单一的，而是随机错误和突发错误并存，只不过有的信道以某种错误为主而已，这两类错误形式并存的信道称为组合信道或复合信道。,7.1.3 差错控制方
4、式,在数字通信系统中，差错控制方式一般可以分为4种类型：检错重发（ARQ）、前向纠错（FEC）、混合纠错检错（HEC）和信息反馈（IRQ），它们的系统构成如图7-1所示。,图7-1 差错控制方式的基本类型,1检错重发,图7-2 检错重发差错控制系统工作原理,2前向纠错,在前向纠错系统中，发送端经编码发出能够纠正错误的码，接收端收到这些码组后，通过译码能自动发现并纠正传输中的错误。,3混合纠错,混合纠错方式是前向纠错方式和检错重发方式的结合。,4信息反馈,信息反馈又称回程校验。它是收端把收到的数据序列全部由反向信道送回发端，发端比较发送的数据序列与送回的数据序列，从而发现是否有错误，对有错误的数
5、据序列的原数据再次传送，直到发端没有发现错误为止。上述几种差错控制方式应根据实际情况合理选用。,7.2 检错和纠错的基本概念,7.2.1 检错和纠错的基本原理 差错控制之所以具有检错和纠错能力，是因为在信息码之外附加了监督码，用来监督信息码在传输过程中是否存在差错，其对用户来说是多余的。监督码的引入，降低了信道的传输效率。,7.2.2 码距与检错和纠错的关系,（1）在信道编码中，定义码组中非零码元的数目为码组的重量，简称码重。（2）把两个码组中对应码位上具有不同二进制码元的位数定义为两码组的距离，简称码距。,（3）在一种编码中，任意两个许用码组间距离的最小值，即码组集合中任意两个元素之间的最小
6、距离，称为这一编码的汉明（Hamming）距离，用 表示。,图7-3 码距的几何表示法,（1）为检测e个错码，则,e+1,图7-4 码距与检错和纠错能力的关系,（2）为纠正t个错码，要求,2t+1,（3）为纠正t个错码，同时检测e个错码，则,e+t+1(et),7.2.3 编码效率,编码效率是指一个码组中信息位所占的比重，用R表示。设码组长为n，信息位长度为k，监督位长度为r，编码效率定义为。,7.2.4 纠错编码的分类,按码组的功能分，有检错码和纠错码。按监督码与信息码之间的关系分，有线性码和非线性码。按对信息码元处理方法的不同分，有分组码和卷积码。,图7-5 分组码的结构,按照信息码元在编
7、码后是否保持原来的形式不变分，可划分为系统码和非系统码。按纠正差错的类型分，可分为纠正随机错误的码和纠正突发错误的码。按照每个码元取值来分，可分为二进制码与多进制码。,7.3 简单的差错控制编码,7.3.1 奇偶监督码 奇偶监督码是一种最简单的检错码，又称奇偶校验码，在计算机数据传输中得到了广泛的应用。,一般情况下奇偶监督码的编码规则是：首先将要传输的信息分成组，然后将各位二元信息及附加监督位用模2和相加，选择正确的监督位，保证模2和的结果为0（偶校验）或1（奇校验）。,这种监督关系可以用公式表示。设码组长度为n，表示为（an1 an2 an3 a0），其中前n1位（an2 an3 a0）为信
8、息，第n位（an1）为校验位，则偶校验时有,奇校验时有,监督码元a0即为,监督码元a0为,奇校验方式就是使分组数据和监督位加起来整个码组中的“1”的个数为奇数个；偶校验方式就是使分组数据和监督位加起来整个码组中的“1”的个数为偶数个。,7.3.2 水平奇偶监督码,表7-1奇偶监督码,表7-2奇偶监督码,7.3.3 水平垂直奇偶监督码,表7-3水平垂直奇偶监督码,7.4 汉明码,7.4.1 汉明码的诞生 线性码中的信息位和监督位是由一些线性代数方程联系着的，或者说，线性码是按一组线性方程构成的，故又称线性分组码。,7.4.2 汉明码的原理,如果希望用r个监督位构造出r个监督关系式来指示一位错码的
9、n种可能位置，则要求 n或 k+r+1,由此可见：r=3，则有3个校正子S1、S2、S3，他们对应有8种组合。其中000无错。剩下7种错误，刚好可以对应指示n=4+3=7个位置的错误情况。,7.4.3 汉明码编码方法,S1=,S2=,表7-4校正子与错码位置,表7-5(7,4)汉明码的许用码组,7.4.4 汉明码编码效率,通常将码长n=的线性分组码称为汉明码，即(,)码。其编码效率为,7.5 线性分组码,7.5.1 监督矩阵 汉明码属于线性分组码，我们可以将汉明码中的,改写成下面的方程组,上式可以简记为 HAT=OT 或 AHT=0,其中，,=,H=,P为rk阶矩阵，Ir为rr阶单位方阵，将具
10、有PIr形式的H矩阵称为典型形式的监督矩阵。,监督矩阵H的特点如下。1H矩阵是通过 码 的个监督方程之后，抽取其系数构成的。2它的行数为监督码的位数，H矩阵的右半部分为一个单位矩阵，这种形式的H矩阵构成的 码的信息码组均在前k位，后r位为监督位，是 码的标准形式。,3H矩阵与 码的任何一个许用码字进行相乘的结果必等于0，若不属于许用码字，或有传输差错，且差错位数在 码纠错能力内，则运算结果将为非0值，此时，可以纠错或检错重发。4H矩阵中不含全0列。,7.5.2 生成矩阵,对其两侧做矩阵转置，有,式中Q为一个kr阶矩阵，为矩阵P的转置，即Q=P T。,或者,称G为生成矩阵，由它可以产生整个码组。
11、IkQ形式的生成矩阵称为典型生成矩阵。,生成矩阵G的特点如下。1Q矩阵的作用是根据信息码的值得到监督码位；G矩阵的作用是在编码设备（发送端）中直接生成信息码和监督码组合的 码组。,2由G矩阵求全部非0码字时，由于其构成为 形式，与H矩阵的 相对应，这种结构特征生成的 码中的前k位完全对应是信息码序列，而后面 位全是监督元，如 码的全部码字，从高位数共 位，均为源编码信息码组。,7.5.3 校正子和检错,R=rn1rn2.r0 RA=E（模2）E=en1 en2.e0,R=A+E RHT=0 RHT=S S=(A+E)HT=AHT+EHT S=EHT,校正子S的特点如下。1校正子S仅仅与错误样图
12、E有关，而与传输的码字C无关。校正子可以根据错误样图进行检错和纠错。,2(n,k)码的不同码字，都有同样多种全部错误样图，即2r1个。S不是一个简单的数值，而是位数等于H矩阵的列数。,7.5.4 线性分组码主要性质,（1）线性分组码具有封闭性，任意两个许用码组按位之和仍是一个许用码组。（2）线性分组最小距离 等于非零码组最小重量W。,7.6 循环码,7.6.1 循环码的循环特性 循环码是一种线性分组码，且为系统码，即前k位为信息位，后r位为监督位。,表7-8（7,3）循环码码组,7.6.2 循环码的多项式表示,1码多项式,2模N运算,若,则记为,所有余数为p的整数属于关于N的一个同余类。,式中
13、，Q(x)为整式，余式R(x)的幂N(x)的幂。则M(X)求模N(x)运算的结果就为R(x)。上式可写成,7.6.3 循环码的生成多项式g(x)及生成矩阵,线性分组可表示为,定理1 若A(x)是长度为n的循环码中的一个码多项式，则xiA(x)按模xn+1运算的余式必为循环码中的另一码多项式。定理2 在循环码中，nk次的码多项式g(x)有一个且只有一个。,定理3 在循环码中，所有的码多项式A(x)都能够被g(x)整除。定理4 循环码(n,k)的生成多项式g(x)是xn+1的一个因式。,7.6.4 循环码的编码方法,编码的任务是在已知信息位的条件下求得循环码的码组，而我们要求得到的是系统码，即码组
14、前k位为信息位，后r=nk位是监督位。因此，首先要根据给定的(n,k)值选定生成多项式g(x)，即从(xn+1)的因子中选一(nk)次多项式g(x)。,设信息位的码多项式为 m(x)=mk1xk1+mk2xk2+m1x+m0,其中，mi系数为1或0。我们知道(n,k)循环码的码多项式的最高幂次是n1次，而信息位是在它的最前面k位，因此信息位在循环码的码多项式中应表示为xnkm(x)。,7.6.5 循环码的解码方法,接收端解码的要求有两个：检错和纠错。,对于循环码纠错可以按如下步骤进行。（1）用生成多项式g(x)除接收码组R(x)=A(x)+E(x)，得出余式。（2）按余式 用查表的方法或通过某
15、种运算得到错误图样E(x)。,小 结,1在数字通信中，降低误码率的基本方法是采用差错控制编码，方法是对二进制数字序列进行某种变换使其具有某种规律性，接收端利用这种规律性检出或者纠正错误。但是，要做到这一点，必须加入若干监督码元，这必将降低信息传输有效性。,2差错控制方式一般可以分为4种类型：检错重发（ARQ）、前向纠错（FEC）、混合纠错检错（HEC）和信息反馈（IRQ）。这些方式各有特点，适用于不同的场合。,3码组中非零码元的数目为码组的重量，简称码重；两个码组中对应码位上具有不同二进制码元的位数定义为两码组的距离，简称码距；在一种编码中，任意两个许用码组间距离的最小值，即码组集合中任意两个
16、元素之间的最小距离，称为这一编码的汉明（Hamming）距离。,4为检测e个错误码，要求最小码距为dmine+1；为纠正t个错误码，要求最小码距dmin2t+1；为纠正t个错误码，同时检测e个错误码，要求最小码距为dmine+t+1(et)。,5常用的简单差错控制编码有奇偶监督码、水平奇偶监督码和二维奇偶监督码等。,6分组码是信息位和监督位用线性方程联系在一起的一类码。在线性分组码中，接收端是通过计算校正子S来检验或者纠正错误。当码长为n，信息位为k，则监督位为r=nk，若希望r个监督位构造出r个监督关系式，即用r个校正子S来表示一位错码的n种可能性位置，则要求。,7监督方程确定了信息位和监督位的关系，给定信息位之后就可以计算监督位，为了计算方便，监督方程可以用矩阵来表示，有了生成矩阵，便可以方便得到整个码组。,8线性分组码的重要性质是它的封闭性和线性分组码的最小距离等于非零码的最小码重。,9循环码是一种重要的线性分组码，它除了具有线性分组码的一般特性之外，还具有循环特性。求循环码编码的方法主要是找到生成多项式g(x)，从而通过g(x)得到所有许用码组。,
