第差错控制和流量控制.pptx

《第差错控制和流量控制.pptx》由会员分享，可在线阅读，更多相关《第差错控制和流量控制.pptx（176页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、会计学1第第 差错控制和流量差错控制和流量(liling)控制控制第一页，共176页。第第11章章 差错控制编码差错控制编码(bin m)n n11.1 11.1 差错控制的基本概念差错控制的基本概念n n11.2 11.2 检错码检错码n n11.3 11.3 纠错码纠错码n n11.411.4差错控制方法差错控制方法(fngf(fngf)n n本本 章章 小小 结结第1页/共175页第二页，共176页。11.1 差错控制的基本概念差错控制的基本概念n n 为了提高通信系统的水平，在数字通为了提高通信系统的水平，在数字通信系统中，在发送端对信源送出的二进制信系统中，在发送端对信源送出的二进制

2、数字序列附加多余的数字（编码）使得这数字序列附加多余的数字（编码）使得这些附加数字与数字信息建立某种相关性。些附加数字与数字信息建立某种相关性。在接收端对这组编码进行检测，若发现错在接收端对这组编码进行检测，若发现错误，则试图找出错误的位置并进行纠正。误，则试图找出错误的位置并进行纠正。由此可见，差错控制的基本原理在于增加由此可见，差错控制的基本原理在于增加(zngji)(zngji)冗余度使得原来的信息可以检测冗余度使得原来的信息可以检测传输差错。传输差错。第2页/共175页第三页，共176页。n n11.1.1 11.1.1 差错控制编码的分类差错控制编码的分类n n 差错控制的核心是抗干

3、扰编码，简称差错编码。它的基本差错控制的核心是抗干扰编码，简称差错编码。它的基本思想是通过对信息序列作某种变换，使原来彼此独立、互不相思想是通过对信息序列作某种变换，使原来彼此独立、互不相关关(xinggun)(xinggun)的信息码元列产生某种规律性（相关的信息码元列产生某种规律性（相关(xinggun)(xinggun)性）性），从而在接收端有可能根据这种规律性来检查、发现或纠正传，从而在接收端有可能根据这种规律性来检查、发现或纠正传输信号序列中的差错。变换的方法不同就构成了不同的差错编输信号序列中的差错。变换的方法不同就构成了不同的差错编码。码。第3页/共175页第四页，共176页。n

4、 n(1)(1)按照差错控制编码的不同功能，可以分为检错码（仅能检按照差错控制编码的不同功能，可以分为检错码（仅能检测误码）、纠错码（仅可以纠正误码）和纠删码（兼有纠错测误码）、纠错码（仅可以纠正误码）和纠删码（兼有纠错和检错功能）。和检错功能）。n n(2)(2)按照信息码元和附加的监督码元之间的检验关系可以分为按照信息码元和附加的监督码元之间的检验关系可以分为线性码（信息码元和监督码元满足线性码（信息码元和监督码元满足(m(m nz)nz)一组线性方程式）一组线性方程式）和非线性码。和非线性码。第4页/共175页第五页，共176页。n n(3)(3)按照信息码元和监督码元之间的约束关系可以

5、分为分组码按照信息码元和监督码元之间的约束关系可以分为分组码和卷积码。分组码中，码元序列每和卷积码。分组码中，码元序列每n n位分成一组，其中位分成一组，其中k k个是个是信息码元，信息码元，r=n-kr=n-k个是监督码元，监督码元仅与本组的信息码个是监督码元，监督码元仅与本组的信息码元有关。卷积码中，编码元有关。卷积码中，编码(bin m(bin m)后序列也编为分组，但监后序列也编为分组，但监督码元不仅与本组信息码元有关，还与前面码组的信息码元督码元不仅与本组信息码元有关，还与前面码组的信息码元有关。有关。n n(4)(4)按照纠正错误的类型不同，可以分为纠正随机错误的码和按照纠正错误的

6、类型不同，可以分为纠正随机错误的码和纠正突发错误的码。纠正突发错误的码。第5页/共175页第六页，共176页。n n(5)(5)按照构成差错控制编码的数学方法来分类，可以分为代数按照构成差错控制编码的数学方法来分类，可以分为代数码、几何码和算术码。其中码、几何码和算术码。其中(qzhng)(qzhng)代数码建立在近代数学代数码建立在近代数学基础上，是目前发展最为完善的编码，其中基础上，是目前发展最为完善的编码，其中(qzhng)(qzhng)线性码线性码是是代数码的一个最重要的分支。是是代数码的一个最重要的分支。n n(6)(6)按照每个码元的取值不同，可以分为二进制码和多进制码。按照每个码

7、元的取值不同，可以分为二进制码和多进制码。第6页/共175页第七页，共176页。n n11.1.2 11.1.2 差错控制基本原理。差错控制基本原理。n n 纠错编码的基本思想就是在被传送的信息码纠错编码的基本思想就是在被传送的信息码元中附加一些监督码元，在两者之间建立某种校元中附加一些监督码元，在两者之间建立某种校验关系，当这种校验关系因传输验关系，当这种校验关系因传输(chun sh)(chun sh)错误错误而受到破坏时，可以被发现并予以纠正。在引入而受到破坏时，可以被发现并予以纠正。在引入差错编码控制后，实际传输差错编码控制后，实际传输(chun sh)(chun sh)的息序列的息序

8、列=(信息码元信息码元+监督码元），称为码组。监督码元），称为码组。n n 由此可知，差错控制的基本原理在于增加冗由此可知，差错控制的基本原理在于增加冗余度使得原来的信息可以检测传输余度使得原来的信息可以检测传输(chun sh)(chun sh)差差错，从而降低误码率。错，从而降低误码率。第7页/共175页第八页，共176页。n n 以一组二进制码为例：三位二进制码元有以一组二进制码为例：三位二进制码元有23=823=8个码个码组，如果用来表示颜色的组，如果用来表示颜色的8 8种情况种情况000000（红），（红），001001（黄），（黄），010010（绿），（绿），011011（蓝），

9、（蓝），100100（白），（白），101101（黑），（黑），110110（青）（青），111111（橙），如果有一个误码，接收端则认为（橙），如果有一个误码，接收端则认为(rnwi)(rnwi)是另一条信息，这种编码没有检错和纠错能力。是另一条信息，这种编码没有检错和纠错能力。第8页/共175页第九页，共176页。n n 如果这如果这8 8种码组只用来传送种码组只用来传送4 4条信息，即只准使用其中的条信息，即只准使用其中的4 4种种码组码组000000（红），（红），011011（白），（白），101101（绿），（绿），110110（蓝）。如果（蓝）。如果000000有一位误码，可能为

10、有一位误码，可能为100100，010010或或001001，但这三种都不是信，但这三种都不是信息吗，由此可知传输出错。当出现三个错误息吗，由此可知传输出错。当出现三个错误(cuw)(cuw)时时000000将将变为变为111111，它也不是信息码。但若发生两个错，如，它也不是信息码。但若发生两个错，如000000变为变为011011，则无法判断对错。上述方法只能识别错误，则无法判断对错。上述方法只能识别错误(cuw)(cuw)但无法但无法纠错，因为在收到纠错，因为在收到100100时，时，000000，110110和和101101都可能就为都可能就为100100。第9页/共175页第十页，共

11、176页。n n 4 4个状态只用个状态只用2 2位二进制码就可以表达，所增加的第位二进制码就可以表达，所增加的第3 3位，就称位，就称为监督码元。增加为监督码元。增加1 1位监督码元，只能检出位监督码元，只能检出1 1位误码，对于上例，位误码，对于上例，如果有如果有2 2位误码，将发生位误码，将发生(fshng)(fshng)误判。如将误判。如将000000（晴）误传成（晴）误传成101101（云）。要想抗多位误码，就要增加监督码元的个数，即增（云）。要想抗多位误码，就要增加监督码元的个数，即增加冗余度。加冗余度。第10页/共175页第十一页，共176页。n n为了说明以上的方法的正确性，下

12、面引入香为了说明以上的方法的正确性，下面引入香农定理：每个信道都具有确定的信道容量农定理：每个信道都具有确定的信道容量C C，只要信息传输速率：只要信息传输速率：，则理论上就一，则理论上就一定存在定存在(cnzi)(cnzi)一种编码方式，使其译码差一种编码方式，使其译码差错概率（即误码率）错概率（即误码率）满足：满足：n n式中，式中，nn码字长度（码长）；码字长度（码长）；n n 误差指数误差指数(当当 时，时，）；）；n n A A正系数；正系数；第11页/共175页第十二页，共176页。n n 误码率是指二进制码元在数据传输误码率是指二进制码元在数据传输(chun sh)(chun s

13、h)系统中被传错的概率；系统中被传错的概率；NN为传输为传输(chun sh)(chun sh)的二进制码元的二进制码元总数，总数，为被传错的码元数。为被传错的码元数。第12页/共175页第十三页，共176页。n n 可见要使可见要使 满足要求：一是增加信道容量满足要求：一是增加信道容量C C，从而使，从而使 增加（通信硬件系统设计人员通常采用的方法）增加（通信硬件系统设计人员通常采用的方法）;另一种方法另一种方法是只要是只要 增加码长增加码长n n可使随可使随n n的增加而指数下降，如果的增加而指数下降，如果n n增增大则大则 减小。香农信道编码定理是差错控制编码的理论基础，减小。香农信道编

14、码定理是差错控制编码的理论基础，通过编译通过编译(biny)(biny)码过程来降低误码率。码过程来降低误码率。第13页/共175页第十四页，共176页。n n11.1.3 11.1.3 差错控制编码性能差错控制编码性能n n 海明码是一种多重海明码是一种多重(复式复式)奇偶奇偶(q(q u)u)检错系统。它将检错系统。它将信息用逻辑形式编码，以便能够检错和纠错。用在海明码信息用逻辑形式编码，以便能够检错和纠错。用在海明码中的全部传输码字是由原来的信息和附加的奇偶中的全部传输码字是由原来的信息和附加的奇偶(q(q u)u)校校验位组成的。每一个这种奇偶验位组成的。每一个这种奇偶(q(q u)u

15、)位被编在传输码字的位被编在传输码字的特定位置上。实现得合适时，这个系统对于错误的数位无特定位置上。实现得合适时，这个系统对于错误的数位无论是原有信息位中的，还是附加校验位中的都能把它分离论是原有信息位中的，还是附加校验位中的都能把它分离出来。出来。第14页/共175页第十五页，共176页。n n1.1.海明距离海明距离n n 一个一个(y(y )编码系统中任意两个合法编码之间不同的二进编码系统中任意两个合法编码之间不同的二进制位数，简称码距。用制位数，简称码距。用d d表示，可以写做表示，可以写做n n （8-78-7）n n式中式中 表示模表示模2 2加（异或）加（异或）n n表示码组长度

16、，表示码组长度，和和 表示第表示第k k个码组和第个码组和第j j个码组的第个码组的第i i位码元。位码元。n n例如：例如：111111和和000000，码距为，码距为3 3，111111和和100100码距为码距为2 2，111111和和110110码距为码距为1 1。第15页/共175页第十六页，共176页。n n2.2.最小距离最小距离n n 一个一个(y(y )码组集合中，任何两个码组间海明距离码组集合中，任何两个码组间海明距离(即码距即码距)的最小值称为码组集合的最小距离。用的最小值称为码组集合的最小距离。用 表示表示:n n （8-88-8）n n式中，式中，和和 的定义与式（的

17、定义与式（8.58.5）相同。）相同。第16页/共175页第十七页，共176页。n n 从码距的概念出发，来看一下从码距的概念出发，来看一下8 8个码组，个码组，如果用（如果用（000000，001001，010010，011011，100100，101101，110110，111111），可知最小码距为），可知最小码距为1 1。如果只有。如果只有4 4个个码组可用，选（码组可用，选（010010，111111，100100，001001）或）或（110110，011011，000000，101101），则最小码距为），则最小码距为2 2。如果只有如果只有2 2个码组可用，分别个码组可用，分别

18、(fnbi)(fnbi)选选（111111，000000）（）（100100，011011）（）（110110，001001）（）（101101，010010），侧最小码距为），侧最小码距为3 3。由此可。由此可知：码距越大，纠错能力越强，但数据冗余知：码距越大，纠错能力越强，但数据冗余也越大，即编码效率低了。所以，选择码距也越大，即编码效率低了。所以，选择码距要取决于特定系统的要求。数字系统的设计要取决于特定系统的要求。数字系统的设计者必须考虑信息发生差错的概率和该系统能者必须考虑信息发生差错的概率和该系统能容许的最小差错率等因素。容许的最小差错率等因素。第17页/共175页第十八页，共17

19、6页。n n3.3.检错和纠错能力的关系检错和纠错能力的关系n n 如上所述，一种编码的最小码距直接关系到这种码的检错和如上所述，一种编码的最小码距直接关系到这种码的检错和纠错能力，因此最小码距是信道编码的一个纠错能力，因此最小码距是信道编码的一个(y(y )重要参数。在一重要参数。在一般情况下，对于分组码有如下几个定理表达式：般情况下，对于分组码有如下几个定理表达式：n n定理定理8.1 8.1 若一种码的最小距离为若一种码的最小距离为 ，则它能检查传输错误个数，则它能检查传输错误个数（检错能力）（检错能力）e e应满足：应满足：（8-9）第18页/共175页第十九页，共176页。n n定理

20、定理8.2 8.2 若一种码的最小距离为若一种码的最小距离为 ，则它能纠，则它能纠正传输错误个数（纠错能力）正传输错误个数（纠错能力）t t应满足：应满足：n n （8-108-10）n n定理定理8.3 8.3 若一种码的最小距离为若一种码的最小距离为 ，则能检错，则能检错e e个错误，同时又能纠正个错误，同时又能纠正t t个以下错误的条件是：个以下错误的条件是：n n （etet）（）（8-118-11）n n由定理由定理3 3可知，当传输差错等于或小于时，该码可可知，当传输差错等于或小于时，该码可以自动以自动(zdng)(zdng)纠正这些差错。当传输差错大于纠正这些差错。当传输差错大于

21、时但小于时，该码只能检测出错误。时但小于时，该码只能检测出错误。第19页/共175页第二十页，共176页。n n例例8-4 8-4 求码集合求码集合(000),(011),(101),(110)(000),(011),(101),(110)和和(000),(111)(000),(111)最最小距离小距离 及纠（检）错的能力及纠（检）错的能力(nngl)(nngl)。n n解：（解：（1 1）最小距离）最小距离n n第一组：（第一组：（000000 011011）=2=2，（，（011011 101101）=2=2，（，（101101 110110）=2=2n n(110(110 000)=20

22、00)=2，（，（011011 110110）=2=2，（，（101101 000000）=2=2n n所以最小距离所以最小距离 =2 =2。第20页/共175页第二十一页，共176页。第21页/共175页第二十二页，共176页。11.2 检错码检错码n n 为了提高通信系统的检错和纠错能力为了提高通信系统的检错和纠错能力(nngl)(nngl)，人们创造出许多差错控制编码，人们创造出许多差错控制编码，比较常用的有奇偶校验编码、方阵校验码、比较常用的有奇偶校验编码、方阵校验码、循环冗余校验码、恒比码等。循环冗余校验码、恒比码等。第22页/共175页第二十三页，共176页。n n11.2.1 1

23、1.2.1 奇偶校验码奇偶校验码n n 奇偶校验又称奇偶监督编码，也叫垂直冗余校验奇偶校验又称奇偶监督编码，也叫垂直冗余校验（VRCVRC，Vertical Redundancy CheckVertical Redundancy Check），是奇校验码和偶校），是奇校验码和偶校验码的统称，是一种最基本的检错码，在计算机数据传输验码的统称，是一种最基本的检错码，在计算机数据传输中广泛应用中广泛应用,它是由它是由n-1n-1位信息位信息(xnx)(xnx)元和元和1 1位校验元组成，位校验元组成，可以表示成为（可以表示成为（n n，n-1n-1）。其特点是）。其特点是:构成简单，而且插入构成简单

24、，而且插入的冗余度又低。的冗余度又低。第23页/共175页第二十四页，共176页。n n奇偶校验编码规则:n n 发送端:将所要传输的数据码元分组，在分组数据后面加一位监督码（校验位），使得该组码连同监督码在内的码组中“1”的个数为奇数（奇校验）或偶数（偶校验）。n n 接收端:按照编码规则检查如果发现不符，就说明产生差错(chcu)，但不能明确差错(chcu)的具体位置即不能纠错。第24页/共175页第二十五页，共176页。第25页/共175页第二十六页，共176页。n n 在奇校验中在奇校验中,若结果为若结果为“1”,“1”,则传送无误；否则则传送无误；否则,传送出错。传送出错。偶检验的判

25、断偶检验的判断(pndun)(pndun)与奇校验的判断与奇校验的判断(pndun)(pndun)相反。这种相反。这种校验无论信息位为多少位，监督位只有一位。但这种校验只能校验无论信息位为多少位，监督位只有一位。但这种校验只能检测信息码组中奇数个错误，对偶数个错误无能为力。检测信息码组中奇数个错误，对偶数个错误无能为力。第26页/共175页第二十七页，共176页。n n例例8-1 8-1 写出二进制序列写出二进制序列101101000110110101101000110110的偶的偶校验码和奇校验码。校验码和奇校验码。n n该二进制序列的偶校验码是该二进制序列的偶校验码是:1011010001

26、101100:1011010001101100n n该二进制序列的奇校验码是该二进制序列的奇校验码是:1011010001101101:1011010001101101n n 在接收方在接收方,可以可以(ky(ky)对二进制序对二进制序列中的列中的1 1的个数进行统计。在偶校验中的个数进行统计。在偶校验中,如如果统计结果是偶数，说明传送正确，否则果统计结果是偶数，说明传送正确，否则失败；在奇校验中，如果统计结果是奇数，失败；在奇校验中，如果统计结果是奇数，说明传送正确，否则失败。若传送失败，说明传送正确，否则失败。若传送失败，系统会要求进行重传。系统会要求进行重传。第27页/共175页第二十八

27、页，共176页。n n11.2.2 11.2.2 方阵校验码方阵校验码n n 方阵校验码又称行列监督码，矩阵码，纵向冗余校验码方阵校验码又称行列监督码，矩阵码，纵向冗余校验码（LRCLRC，Lognitudinal Redundancy CheckLognitudinal Redundancy Check），它的码元受到行和列），它的码元受到行和列两个方向奇偶监督，又称二维奇偶校验码。这种编码可以克服两个方向奇偶监督，又称二维奇偶校验码。这种编码可以克服奇偶监督码不能发现偶数个差错的缺点奇偶监督码不能发现偶数个差错的缺点,并且并且(bngqi)(bngqi)是一种用是一种用以纠正突发错误的纠正

28、编码。其基本原理与奇偶监督码相似以纠正突发错误的纠正编码。其基本原理与奇偶监督码相似,不不同的是每个码元要受到纵向和横向两次监督。编码规则如下：同的是每个码元要受到纵向和横向两次监督。编码规则如下：第28页/共175页第二十九页，共176页。n n 将欲发送的信息码按行排成一个矩阵，矩阵中每一行为一码将欲发送的信息码按行排成一个矩阵，矩阵中每一行为一码组，每行的最后加上一个奇偶组，每行的最后加上一个奇偶(q(q u)u)监督码元；矩阵中的每一列监督码元；矩阵中的每一列是由不同码组相同位置的码元组成，在每列最后也加上一个监督是由不同码组相同位置的码元组成，在每列最后也加上一个监督码元，进行奇偶码

29、元，进行奇偶(q(q u)u)校验；最后按行或列码组的顺序发送。如校验；最后按行或列码组的顺序发送。如果用表示信息位果用表示信息位,表示监督位表示监督位,则矩阵码的结构如图则矩阵码的结构如图8.78.7所示所示.这样这样,它的一致监督关系按行及列组成它的一致监督关系按行及列组成,每一行每列都有一个奇偶每一行每列都有一个奇偶(q(q u)u)监督码元。监督码元。第29页/共175页第三十页，共176页。n n 当某一行当某一行(或某一列或某一列)出现偶数个差错时出现偶数个差错时,该行该行(或该列或该列)虽不能虽不能发现发现,但只要但只要(zh(zh yo)yo)差错所在的列差错所在的列(或行或行

30、),),没有同时出现偶数没有同时出现偶数个差错个差错,则这种差错仍然能发现。矩阵码中有一种情况不能发则这种差错仍然能发现。矩阵码中有一种情况不能发现错误现错误,即差错数正好是即差错数正好是4 4的倍数的倍数,而且差错位正好构成矩形的四而且差错位正好构成矩形的四个角个角,如图如图8-18-1所示所示,此时行、列均不能发现错误。由此可见此时行、列均不能发现错误。由此可见,矩矩阵码发现错码的能力十分强阵码发现错码的能力十分强,但它的编码效率要比奇偶监督码但它的编码效率要比奇偶监督码要低。要低。第30页/共175页第三十一页，共176页。图11-1 矩阵(j zhn)码结构第31页/共175页第三十二

31、页，共176页。n n例例11-2 11-2 设要发送的信息设要发送的信息(xnx)(xnx)码序列是码序列是(11100101101001100001100010001100111),(11100101101001100001100010001100111),现将每七个码为现将每七个码为一组分开一组分开,编成矩阵编成矩阵,每一组都采用偶数校验每一组都采用偶数校验,刚在在发送端可刚在在发送端可骗成如下结构的码矩阵骗成如下结构的码矩阵:第32页/共175页第三十三页，共176页。第33页/共175页第三十四页，共176页。n n经过编码后送到信道经过编码后送到信道(xn do)(xn do)上的

32、将是一个新序列上的将是一个新序列:n n111001001101001010000111000100011100111101101111111001001101001010000111000100011100111101101111n n序列中带下划线的为新加上的码元。接收端仍将码元排成发序列中带下划线的为新加上的码元。接收端仍将码元排成发送时方阵形式，然后按行、列进行奇偶校验。例如送时方阵形式，然后按行、列进行奇偶校验。例如,接收端接收端接收到的编码是接收到的编码是:n n11100100 11010010 10000111 00010001 11001111 01101111 111001

33、00 11010010 10000111 00010001 11001111 01101111 n n则可排列成如下矩阵则可排列成如下矩阵:第34页/共175页第三十五页，共176页。第35页/共175页第三十六页，共176页。n n 上边的矩阵中虽然第四行出错上边的矩阵中虽然第四行出错,但由于但由于1 1的个数仍为奇数的个数仍为奇数,所所以偶校验位仍为以偶校验位仍为1.1.但列但列3,4,6,73,4,6,7却出现了错误却出现了错误,所以可以发现所以可以发现(fxin)(fxin)错码。错码。n n 通过上面分析可知通过上面分析可知,方阵监督码具有如下特点方阵监督码具有如下特点:n n （1

34、 1）可以检测出某行或某列上的奇可以检测出某行或某列上的奇(偶偶)数个错误和长度数个错误和长度不大于行（列）数的突发错误。不大于行（列）数的突发错误。第36页/共175页第三十七页，共176页。n n（2 2）常用于纠正突发性出错）常用于纠正突发性出错,但长度有限。但长度有限。n n （3 3）不能纠正差错数正好是）不能纠正差错数正好是4 4的倍数且位置在行列矩阵的倍数且位置在行列矩阵(j(j zhn)/zhn)/子矩阵子矩阵(j(j zhn)zhn)的的4 4个顶点上的差错。个顶点上的差错。n n （4 4）可使误码率降到原来的）可使误码率降到原来的1%1%0.01%0.01%。第37页/共

35、175页第三十八页，共176页。n n11.2.3 11.2.3 循环冗余循环冗余(r(r n n y)y)校验码校验码n n 循环冗余循环冗余(r(r n n y)y)校验校验(CRC,Cyclic(CRC,Cyclic Redundancy checking)Redundancy checking)，又称多项式码。在循环，又称多项式码。在循环冗余冗余(r(r n n y)y)校验中，不是通过将各比特位相校验中，不是通过将各比特位相加来得到期望的校验，而是通过在数据单元末加来得到期望的校验，而是通过在数据单元末尾加一串冗余尾加一串冗余(r(r n n y)y)比特，称作循环冗余比特，称作循环

36、冗余(r(r n n y)y)校验码或循环冗余校验码或循环冗余(r(r n n y)y)校验余数，校验余数，使得整个数据单元可以被另一个预定的二进制使得整个数据单元可以被另一个预定的二进制数所整除数所整除CRCCRC码是由两部分组成，前部分是信码是由两部分组成，前部分是信息码，就是需要校验的信息，后部分是校验码，息码，就是需要校验的信息，后部分是校验码，如果如果CRCCRC码共长码共长n n个个bitbit，信息码长，信息码长k k个个bitbit，就称，就称为为(n,k)(n,k)码。它的编码规则是：码。它的编码规则是：第38页/共175页第三十九页，共176页。n n（1 1）首先将原信息

37、码）首先将原信息码(kbit)(kbit)左移左移r r位位(k+r=n)(k+r=n)。n n（2 2）运用一个生成多项式）运用一个生成多项式g(x)g(x)（也可看成二进制数）（也可看成二进制数）用模用模2 2除上面的式子，得到的余数除上面的式子，得到的余数n n就是校验码。就是校验码。n n（3 3）根据欲发送的）根据欲发送的k k位信息位构成的报文，发送器位信息位构成的报文，发送器生成一个生成一个r r比特的序列，称为帧校验序列比特的序列，称为帧校验序列FCSFCS（Frame Frame checking Serieschecking Series），将），将r r位位FCSFCS（

38、即（即CRCCRC码）附加到码）附加到k k位位信息序列之后作为实际发送的数据帧（信息序列之后作为实际发送的数据帧（k+rk+r位），这位），这个个(zh ge)(zh ge)帧所对应二进制序列恰好能够被某个预先帧所对应二进制序列恰好能够被某个预先确定的数（生成多项式）整除。确定的数（生成多项式）整除。第39页/共175页第四十页，共176页。n n（4 4）接收器用相同的数去除传来的帧。如）接收器用相同的数去除传来的帧。如果果(rgu(rgu)无余数，则认为无差错；如果无余数，则认为无差错；如果(rgu(rgu)余数不为余数不为0 0，则认为传输出错。，则认为传输出错。n n 奇偶校验对一个

39、字符校验一次，适合奇偶校验对一个字符校验一次，适合异步通讯；而异步通讯；而CRCCRC对一个数据块（对一个数据块（frameframe）校验一次，适合同步通讯。在串行同步通校验一次，适合同步通讯。在串行同步通信中，几乎都使用这种校验方法。如磁盘信中，几乎都使用这种校验方法。如磁盘信息的读信息的读/写等写等n n 任何一个任何一个n n位的二进制数都可以用一位的二进制数都可以用一个个n-1n-1次的多项式来表示。次的多项式来表示。n n n n n n (8-1)第40页/共175页第四十一页，共176页。n n例如例如,二进制数二进制数1011011101,1011011101,可写成为可写成

40、为n n n n。此多项式称为码多项式。此多项式称为码多项式(或信息多项式或信息多项式)。n n二进制码多项式的加减运算为模二进制码多项式的加减运算为模2 2加减运算加减运算,也就是逻辑上的也就是逻辑上的异或运算异或运算,即加法和减法即加法和减法(ji(ji nfnf)造价。造价。(8-2)第41页/共175页第四十二页，共176页。n n 二进制码多项式的乘除法运算与普通代数多项式的乘除法二进制码多项式的乘除法运算与普通代数多项式的乘除法运算是一样的运算是一样的,符合同样符合同样(tngyng)(tngyng)的规律。的规律。n n =Q(X)+=Q(X)+第42页/共175页第四十三页，共

41、176页。n n 其中其中,Q(X),Q(X)为为B1(X)B1(X)除以除以B2(X)B2(X)的商的商,亦称整数多项式亦称整数多项式,R(X),R(X)为余数多项式。若能除尽为余数多项式。若能除尽,则则R(X)=0R(X)=0。一个。一个(y(y )n)n位的循环码是由位的循环码是由k k位信息位加上位信息位加上r r位校验位组成的位校验位组成的,其中其中r=n-r=n-k k。这样新组成的二进制位序列叫做循环冗余码。这样新组成的二进制位序列叫做循环冗余码(CRC)(CRC)。表。表示示CRCCRC码的多项式叫生成多项式码的多项式叫生成多项式G(x)G(x)。k k位二进制数加上位二进制数

42、加上r r位位CRCCRC码后码后,即信息位要向左移即信息位要向左移(n-k)(n-k)位位,B(X),B(X)乘以乘以 。被生成多项式被生成多项式G(X)G(X)除除,得整数多项式得整数多项式Q(X)Q(X)加上余数多项式加上余数多项式R(X),R(X),即即第43页/共175页第四十四页，共176页。n n移项移项(y xin(y xin)得得:n n根据式根据式(8-2)(8-2)上式可写为上式可写为 (8-4)第44页/共175页第四十五页，共176页。n n 上式说明，信息多项式上式说明，信息多项式B(X)B(X)和余数多项式和余数多项式R(X)R(X)可以合可以合并成一个新的多项式

43、并成一个新的多项式V(X)(V(X)(称为循环码的码多项式称为循环码的码多项式),),则该多则该多项式是生成多项式项式是生成多项式G(X)G(X)的整数倍的整数倍,即能被即能被G(X)G(X)整除。因此整除。因此,在发送在发送(f sn(f sn)端用信息码多项式端用信息码多项式B(X)B(X)除以生成多项式所除以生成多项式所得的余数多项式得的余数多项式R(X),R(X),就是所要加的监督位。将循环码的码就是所要加的监督位。将循环码的码多项式多项式V(X)V(X)除以生成多项式除以生成多项式G(X),G(X),若能除尽若能除尽,说明传送正确说明传送正确,否则传送出错。否则传送出错。n n CR

44、C CRC校验码的生成器和校验器如图校验码的生成器和校验器如图8-28-2所示。所示。第45页/共175页第四十六页，共176页。图11.2第46页/共175页第四十七页，共176页。n n由图由图11-211-2可知可知,CRC,CRC码生成和校验基本分为三步：码生成和校验基本分为三步：n n第一步：在数据单元第一步：在数据单元(k(k位）的末尾加上位）的末尾加上r r个个0 0。r r是一个比预定是一个比预定除数的比特位数除数的比特位数(r(r十十1)1)少少1 1的数。的数。n n第二步：采用二进制除法将新的加长的数据单元（第二步：采用二进制除法将新的加长的数据单元（k+rk+r位位)除

45、除以除数。由此除法产生以除数。由此除法产生(ch(ch nshng)nshng)的余数就是循环冗余码的余数就是循环冗余码校验码。校验码。第47页/共175页第四十八页，共176页。n n第三步：用从第二步得到的第三步：用从第二步得到的r r个比特个比特(b(b t)t)的的CRCCRC码替换数据码替换数据单元末尾附加的单元末尾附加的r r个个0 0。如果余数位数小于。如果余数位数小于r r，最左的缺省位数，最左的缺省位数为为0 0。如果除法过程根本未产生余数（也就是说，原始的数。如果除法过程根本未产生余数（也就是说，原始的数据单元本身就可以被除数整除）那么以据单元本身就可以被除数整除）那么以r

46、 r个个0 0作为作为CRCCRC码替换码替换余数所在的位置。产生的比特余数所在的位置。产生的比特(b(b t)t)模式正好能被除数整除。模式正好能被除数整除。第48页/共175页第四十九页，共176页。n n 到达接收方的数据单元首先到达的是数据，然后是到达接收方的数据单元首先到达的是数据，然后是CRCCRC校验校验码。接收方将整个数据串当作一个整体去除以用来产生码。接收方将整个数据串当作一个整体去除以用来产生(ch(ch nshng)nshng)循环冗余校验余数的同一个除数循环冗余校验余数的同一个除数G(X)G(X)。n n 如果数据串无差错地到达接收方，循环冗余校验器将产生如果数据串无差

47、错地到达接收方，循环冗余校验器将产生(ch(ch nshng)nshng)余数余数0 0。因此数据单元将通过检验。如果在传输中数。因此数据单元将通过检验。如果在传输中数据单元被改变，除法将产生据单元被改变，除法将产生(ch(ch nshng)nshng)非零余数，因此数据单元非零余数，因此数据单元将通不过检验。将通不过检验。第49页/共175页第五十页，共176页。n n例例11-3 11-3 在循环冗余校验码系统中在循环冗余校验码系统中,设其生成多项式为设其生成多项式为 ,试求出信息序列试求出信息序列1101011011010110的的CRCCRC循环冗余校验码循环冗余校验码,并说明并说明(

48、shumng)(shumng)在接收端如何判断传输的正确性。在接收端如何判断传输的正确性。n n(1)(1)把生成多项式转换成二进制数把生成多项式转换成二进制数n n(2)(2)计算计算CRCCRC余数余数,如图如图11.311.3所示。所示。第50页/共175页第五十一页，共176页。n n 首先首先,要在数据位要在数据位(被除数被除数)后边补后边补0,00,0的个数比除数的个数比除数(生生成多项式成多项式)少一位。少一位。n n 其次其次,从被除数的头五位送去五位的除数。除数的每一从被除数的头五位送去五位的除数。除数的每一位都与被除数的对应位在不位都与被除数的对应位在不n n 涉及上一位的

49、情况下独立进行模涉及上一位的情况下独立进行模2 2加法。在被除数中下加法。在被除数中下一个一个(y(y )没有使用过的比特接着被抄录下来没有使用过的比特接着被抄录下来,使得余数的使得余数的位数和除数的位数相同。如果位数不够位数和除数的位数相同。如果位数不够,在商位补在商位补0,0,依此类推。依此类推。第51页/共175页第五十二页，共176页。图11.3 计算余数(ysh)的二进制除法第52页/共175页第五十三页，共176页。n n 如果余数是如果余数是3 3位的话位的话,要在余数前加个要在余数前加个0,0,因为余数应比除数因为余数应比除数少一位少一位,在这个在这个(zh ge)(zh ge

50、)例子中余数是例子中余数是4 4位位,于是可求出该信息码于是可求出该信息码的循环冗余码为的循环冗余码为110101101000110101101000。n n 为了判断传输的正确性为了判断传输的正确性,在接收端要有一个在接收端要有一个CRCCRC校验器。校验器。它的功能和发生器一样它的功能和发生器一样,当收到冗余校验码后当收到冗余校验码后,做同样的模做同样的模2 2加除加除法。如果余数是法。如果余数是0,0,则传输正确则传输正确;否则传输错误否则传输错误,应重传。图应重传。图11-411-4是是上例的校验结果。上例的校验结果。第53页/共175页第五十四页，共176页。图11-4 校验(xio