《数据校验码》PPT课件

2020/5/20,1,第4章存储器,补充内容：数据校验码,2020/5/20,2,数据校验码是什么？,数据在传输或存储过程中常因受到某种随机干扰而发生错误（即误码）：10或01为了保证数据的正确性，必须及时发现并纠正数据中的错误。数据校验码：一种具有检错能力或自动改错能力的数据编码方法。,2020/5/20,3,“冗余校验”思想：（以数据传输为例）（1）编码：在原始数据（即有效数据位）的基础上增加冗余数据（即校验位），按照某种规律将有效数据位和校验位一起编码，得到数据校验码；（2）译码：按同一约定规律对收到的数据校验码进行分析，并判断约定规律是否被破坏。若未被破坏，则正确，从中取出有效数据即可；若被破坏，则有错，根据约定规律被破坏后的某些特征对出错位进行定位，从而可自动纠正错误。,2020/5/20,4,本质：加进一些冗余码，使合法编码出现某些错误时，就成为非法编码。这样，可通过检测编码的合法性来达到发现错误的目的。举例：假设有效数据用3位二进制编码，表示某个地区八个城市的代号。码距：一个编码系统中任意两个合法编码之间对应二进制位状态不同的位数，称为这两个编码的距离。任意两个编码的最小距离就是该编码系统的码距，通常用d表示。例子中的d=？,01101001,P,2020/5/20,5,为了使一个编码系统能发现并纠正一位错，其码距至少应为3。此时，或能纠正一位错，或能发现二位错。但不能同时兼有这两种能力。为了进一步提高编码系统的检错和纠错能力，必须进一步增加码距。码距d=,2020/5/20,6,结论：,增加的校验位越多，码距越大，纠错能力越强；但数据冗余也越大，代价越高。数据校验码设计原则：在不过多增加硬件开销的情况下，尽可能多地发现和纠正错误。设计者要综合考虑信息发生差错的概率以及具体应用系统所能容许的最小差错率等因素来选择合适的码距。,2020/5/20,7,一、奇偶校验码,最简单、开销最小，广泛应用于存储器读写校验。编码规律：偶校验：配一个校验位，使整个校验码（包括有效数据位和校验位）中“1”的个数为偶数；奇校验：配一个校验位，使整个校验码（包括有效数据位和校验位）中“1”的个数为奇数；采用奇校验还是偶校验，应事先约定好。,2020/5/20,8,以偶校验为例介绍其编、译码方法,编码：统计有效数据中“1”的个数，若为奇数（偶数），则令增加的校验位为“1”（“0”），由有效数据和校验位构成整个校验码。（写入存储器）形如D8D7D6D5D4D3D2D1D校其中D校=D8D7D6D5D4D3D2D1例如：,2020/5/20,9,译码：（从存储器读出）统计整个校验码中“1”的个数，若仍为偶数，则表明约定规律未被破坏，读出的数据是正确的，从中取出有效数据即可；否则，表明出错。出错条件可表示为：偶校验错=D8D7D6D5D4D3D2D1D校检错纠错能力分析：码距d=2；只能发现1位错，而不能纠正错误；不能发现偶数个错误。因一位出错的几率大，故有实用价值。,2020/5/20,10,逻辑实现：,编码,译码,2020/5/20,11,二、海明校验码,1950年，RichardHamming提出。目前仍应用广泛。实质：是一种多重奇偶校验码。实现原理：按一定规律将有效数据位划分为若干组，分组进行奇偶校验。各组的检错信息构成一个指错字，不但可以发现出错，还能指出是哪一位出错，为自动纠错提供依据。,2020/5/20,12,(1)分成几组？增加多少校验位？设待编信息k位，分为r组，每组增加一个校验位，则r位校验位构成一个r位的指错字。,r位校验位能表示2r种状态：用全0表示“没有错误”；用其余2r-1种状态指出错误发生在哪一位。,具体实现,2020/5/20,13,需要满足：2r1k+r,若设k=4，则r3，组成7位海明码。,2020/5/20,14,(2)分组方法？设有效数据4位：A4A3A2A1，增加3位校验位：P3P2P1，构成一个3位的指错字G3G2G1。,Pi在海明码中位序号为2i-1的位置上。,2020/5/20,15,“”表示某位海明码参加某组。有效数据位Ai分别参加2组以上，且满足如下关系：其位序号要等于所参与各组的校验位的位序号之和。每个校验位Pi只参加本组。,2020/5/20,16,(3)编码（以偶校验为例）？,第1组：P1=A1A2A4G1=P1A1A2A4,第2组：P2=A1A3A4G2=P2A1A3A4,第3组：P3=A2A3A4G3=P3A2A3A4,(4)查错与纠错,若G3G2G1000，若G3G2G1000，,则无错；,则G3G2G1的值即指明出错位，将该位取反即可纠正。,2020/5/20,17,G1=P1A1A2A4=1110=1,G2=P2A1A3A4=0110=0,G3=P3A2A3A4=1110=1,101,2020/5/20,18,(5)逻辑实现(译码电路),2020/5/20,19,由于每一个有效数据位至少要参加两个校验组的奇偶检测，因此当两个有效数据只有一位不相同时，该位至少引起两个校验位的不同！故码距d3。,(6)分析,d3的码能够检测2位错，或用来检测并纠正1位错，但两者只能择一。,如要能检测并纠正1位错，同时能发现2位错，此时应增加一个校验位，即应满足：2r-1k+r,2020/5/20,20,校验规则：让校验码能被某一约定代码除尽。若能除尽，表明代码无错；若除不尽，余数将指明出错位置。,三、循环冗余校验码（CRC码）,实现原理：在k位信息位之后拼接r位校验位。问题1：如何从k位信息位简便地得到r位校验位？问题2：如何从k+r位信息码判断是否有错？,2020/5/20,21,模2运算：以按位模2相加为基础，运算时不考虑进位和借位。模2加减（异或）000011101110模2乘（用模2加求和）例如：1010101101000001010100010,CRC码是基于模2运算来建立编译码规律的校验码，在计算机外存储器校验和通信等方面应用广泛。,2020/5/20,22,模2除（用模2减求余数）每求1位商使部分余数减少1位。上商原则：部分余数的首位为1，商取1；部分余数的首位为0，商取0。当部分余数位数小于除数位数时，该余数为最后余数。例如：10110110000101010000010010101,2020/5/20,23,设：被除数M(x)：k位待编信息除数G(x)：r+1位？余数R(x)：r位校验位商Q(x)(1)CRC码的编码方法,具体实现,a.将待编码的k位有效信息位组写成表达式：M(x)=Ck-1Xk-1+Ck-2Xk-2+C1X+C0(Ci=0或1),b.将信息位组左移r位，变成多项式M(x)Xr；,c.用M(x)Xr除以G(x)，所得余数作为校验位。,d.有效的CRC码为：M(x)Xr+R(x)=Q(x)G(x)+R(x)+R(x)=Q(x)G(x)。,所以：CRC码能够被G(x)除尽。,2020/5/20,24,例如：对M(x)=1100，用G(x)=1011，求CRC码。,a.将待编码的k=4位有效信息位组写成表达式：M(x)=Ck-1Xk-1+Ck-2Xk-2+C1X+C0=X3+X2=1100,b.将信息位组左移r=3位,M(x)Xr=M(X)X3=1100000,c.用M(x)Xr除以G(x)，所得余数作为校验位。,d.有效的CRC码此处为(7,4)码为：M(x)Xr+R(x)=1100000+010=1100010。,2020/5/20,25,(2)CRC码的译码与纠错,译码：用收到的CRC码除以G(x)。若码字无误，则余数为0；若有某1位错，则余数不为0且不同位出错时的余数不同。,注意：余数与出错位的对应关系不变，它只与码制和生成多项式G(x)有关，而与待测码字无关。,2020/5/20,26,(7，4)循环码的出错模式(生成多项式G(x)=1011),2020/5/20,27,纠错：对于用G(x)作模2除得到的余数R(x)，若补0继续除下去，发现各次的余数按上表的顺序循环。所以，可以采用一种节省硬件的纠错办法：,如只设置余数101的译码输出，对应于第1位A1出错。在求出余数不为0后，对余数一边补0一边作模2除，同时将