数据校验.ppt

《数据校验.ppt》由会员分享，可在线阅读，更多相关《数据校验.ppt（33页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、数据校数据校验验“冗余校验冗余校验”：即除原数据信息外，还增加若干位：即除原数据信息外，还增加若干位编码，编码，这些新增的代码被称为校验位。这些新增的代码被称为校验位。减少、避免错误减少、避免错误数据校数据校验验数据校数据校验验“码字码字”：由若干位代码组成的一个字。：由若干位代码组成的一个字。“距离距离”：将两个码字逐位比较，具有不同代码：将两个码字逐位比较，具有不同代码的位的个数。的位的个数。“码距码距”：各码字间的最小距离：各码字间的最小距离 在数据校验码中，一个码字是指数据位和校验位按照在数据校验码中，一个码字是指数据位和校验位按照某种规律排列得到的代码。某种规律排列得到的代码。数据校

2、数据校验验循环冗余校验码循环冗余校验码 循环冗余校验码（循环冗余校验码（Cyclic Redundancy CheckCyclic Redundancy Check），），简称简称CRCCRC码。通过某种数学运算来建立数据和校验位码。通过某种数学运算来建立数据和校验位之间的约定关系。之间的约定关系。循环冗余校验码常用于外存储器的数据校验以及计算循环冗余校验码常用于外存储器的数据校验以及计算机通信中。机通信中。数据校数据校验验-循环冗余校验码循环冗余校验码假设要进行校验的数据信息假设要进行校验的数据信息M(x)M(x)为一个为一个n n位的二进制位的二进制数据，将数据，将M(x)M(x)左移左移

3、k k位后，用一位后，用一个约定的个约定的“生成多项生成多项式式”G(x)G(x)相除，相除，G(x)G(x)是一个是一个k+1k+1位的二进制数，相除后位的二进制数，相除后得到的得到的k k位余数就是校验位。这些校验位拼接到位余数就是校验位。这些校验位拼接到M(x)M(x)的的n n位数据后面，形成一个位数据后面，形成一个n+kn+k位的代码，称这个代码位的代码，称这个代码为循环冗余校验（为循环冗余校验（CRCCRC）码，也称（）码，也称（n+k,nn+k,n）码。）码。数据（数据（n n校验位（校验位（k kCRCCRC码码(n+k(n+k 1.CRC1.CRC码的检错方法码的检错方法 数

4、据校数据校验验-循环冗余校验码循环冗余校验码2.校校验位的生成验位的生成 假假设设：要要传传送的数据信息送的数据信息为为：100011100011，即，即报报文文多多项项式式为为：M(x)=M(x)=x x5 5+x+1+x+1；约约定的生成多定的生成多项项式式为为：G(x)=xG(x)=x3 3+1+1，则则数据信息位数数据信息位数n=6n=6，生成多，生成多项项式位数式位数为为4 4位，所以校位，所以校验验位位数位位数k=3k=3。生成校生成校验验位位时时，用，用x x3.3.M(x)M(x)去除以去除以G(x)G(x)，相除，相除时时采用采用“模运算模运算”的多的多项项式除法。式除法。3

5、.利用利用“模模”多项式除法计算多项式除法计算xM(x)xM(x)G(x)G(x)的过程。的过程。数据校数据校验验-循环冗余校验码循环冗余校验码100011000100111100100110000011100001110100111101001111010011111001校验位X X3.3.M(x)M(x)G(x)G(x)(x(x8 8+x+x4 4+x+x3 3)(x(x3 3+1)+1)x x2 2+x+1+x+1 校验位为校验位为111111，CRCCRC码为码为100011 111100011 111。数据校数据校验验-循环冗余校验码循环冗余校验码如果要校验如果要校验CRCCRC码

6、，则可将码，则可将CRCCRC码用同一个码用同一个多项式相除，若余数为，则说明无错；多项式相除，若余数为，则说明无错；若余数不为，则说明有错。若余数不为，则说明有错。例如：若在接收方的例如：若在接收方的CRCCRC码与发送方一致，即为码与发送方一致，即为100011 111100011 111时，用同一个多项式相除后余数为；时，用同一个多项式相除后余数为；若在接收方的若在接收方的CRCCRC码有一位出错而变为码有一位出错而变为101011 111101011 111时，时，用同一个多项式相除后余数不为。用同一个多项式相除后余数不为。上商原则：部分余数首位是上商原则：部分余数首位是1商取商取1反

7、之商取反之商取0数据校数据校验验-循环冗余校验码循环冗余校验码100011111100111100100110000011100001111100111011001100110010001001余数为101011111101110100101110000111110011101100110011001000100000011001余数不为数据校数据校验验-循环冗余校验码循环冗余校验码3.CRC3.CRC码的纠错码的纠错 在接收方将收到的在接收方将收到的CRCCRC码用约定的生成多项式码用约定的生成多项式G(x)G(x)去除，如果码字没有错误，则余数去除，如果码字没有错误，则余数为为0 0，若有

8、一，若有一位出错，则余数不为位出错，则余数不为0 0，而且不同的出错位置其余数，而且不同的出错位置其余数不同。不同。更换不同的码字，余数和出错位的关系不变。更换不同的码字，余数和出错位的关系不变。只和码制与生成多项式有关。只和码制与生成多项式有关。如果如果CRCCRC码中有一位出错，用特定的码中有一位出错，用特定的G(x)G(x)作模作模2 2除，除，则会得到一个不为则会得到一个不为0 0的余数。的余数。数据校数据校验验-循环冗余校验码循环冗余校验码4.4.生成多项式的选取生成多项式的选取 从查错和纠错的要求来看，选取的一个从查错和纠错的要求来看，选取的一个生成多项式应满足以下几个条件：生成多

9、项式应满足以下几个条件：任何一位发生错误时，都应使余数不为任何一位发生错误时，都应使余数不为0 0。不同位发生错误时，余数应该不同。不同位发生错误时，余数应该不同。对余数作模对余数作模2 2 除时，应使余数循环。除时，应使余数循环。下面是几种常用的生成多项式：下面是几种常用的生成多项式：CRC-CCITT:G(x)=xCRC-CCITT:G(x)=x1616+x+x1212+x+x5 5+1+1CRC-16:G(x)=xCRC-16:G(x)=x1616+x+x1515+x+x2 2+1+1CRC-12:G(x)=xCRC-12:G(x)=x1212+x+x1111+x+x3 3+x+x2 2

10、+x+1+x+1 CRC-32:CRC-32:G(x)=x G(x)=x3232+x+x2626+x+x2323+x+x1616+x+x1212+x+x1111+x+x1010+x+x8 8+x+x7 7+x+x5 5+x+x4 4+x+x2 2+x+1+x+1 数据校数据校验验-循环冗余校验码循环冗余校验码ECCECC能纠正能纠正1 1个比特错误和检测个比特错误和检测2 2个比特错误，而个比特错误，而且计算速度很快，但对且计算速度很快，但对1 1比特以上的错误无法纠比特以上的错误无法纠正，对正，对2 2比特以上的错误不保证能检测。比特以上的错误不保证能检测。ECC的全称是的全称是ErrorC

11、heckingandCorrection，是一种用于，是一种用于Nand的差错检测和修正算法。的差错检测和修正算法。（NANDFlash是目前市场上主要的非易失闪存芯是目前市场上主要的非易失闪存芯片）片）数据校数据校验验-ECC校验校验校验码生成算法：校验码生成算法：ECC校验每次对校验每次对256字节的数据字节的数据进行操作，包含列校验和行校验。对每个待校验的进行操作，包含列校验和行校验。对每个待校验的Bit位求异或，若结果为位求异或，若结果为0，则表明含有偶数个，则表明含有偶数个1；若；若结果为结果为1，则表明含有奇数个，则表明含有奇数个1。256字节数据形成字节数据形成256行、行、8列

12、的矩阵，矩阵每个元素表示一个列的矩阵，矩阵每个元素表示一个Bit位。位。数据校数据校验验-ECC校验校验数据校数据校验验-ECC校验校验其中其中CP0 CP5 CP0 CP5 为六个为六个BitBit位，表示位，表示Column Column ParityParity（列极性），（列极性），CP0 CP0为第为第0 0、2 2、4 4、6 6列的极性，列的极性，CP1CP1为第为第1 1、3 3、5 5、7 7列的极性，列的极性，CP2 CP2为第为第0 0、1 1、4 4、5 5列的极性，列的极性，CP3CP3为第为第2 2、3 3、6 6、7 7列的极性，列的极性，CP4 CP4为第为第0

13、 0、1 1、2 2、3 3列的极性，列的极性，CP5CP5为第为第4 4、5 5、6 6、7 7列的极性。列的极性。用公式表示就是：用公式表示就是：CP0=Bit0Bit2Bit4Bit6CP0=Bit0Bit2Bit4Bit6，表示第表示第0 0列内部列内部256256个个BitBit位异或之后再跟第位异或之后再跟第2 2列列256256个个BitBit位异或，再跟第位异或，再跟第4 4列、第列、第6 6列的每个列的每个BitBit位位异或，这样，异或，这样，CP0CP0其实是其实是256*4=1024256*4=1024个个BitBit位异或位异或的结果。的结果。CP1 CP5 CP1

14、CP5 依此类推。依此类推。数据校数据校验验-ECC校验校验数据校数据校验验-ECC校验校验 其中其中RP0 RP15 RP0 RP15 为十六个为十六个BitBit位，表示位，表示Row ParityRow Parity（行（行极性），极性），RP0 RP0为第为第0 0、2 2、4 4、6 6、.252.252、254 254 个字节的极性个字节的极性 RP1-1 RP1-1、3 3、5 5、7 7253253、255 255 RP2-0RP2-0、1 1、4 4、5 5、8 8、9 9.252.252、253 253（处理（处理2 2个个ByteByte，跳过，跳过2 2个个ByteBy

15、te）RP3-2 RP3-2、3 3、6 6、7 7、1010、1111.254.254、255 255（跳过（跳过2 2个个ByteByte，处理，处理2 2个个ByteByte）RP4-RP4-处理处理4 4个个ByteByte，跳过，跳过4 4个个ByteByte；RP5-RP5-跳过跳过4 4个个ByteByte，处理，处理4 4个个ByteByte；RP6-RP6-处理处理8 8个个ByteByte，跳过，跳过8 8个个ByteByte RP7-RP7-跳过跳过8 8个个ByteByte，处理，处理8 8个个ByteByte；RP8-RP8-处理处理1616个个ByteByte，跳过

16、，跳过1616个个ByteByte RP9-RP9-跳过跳过1616个个ByteByte，处理，处理1616个个ByteByte；数据校数据校验验-ECC校验校验RP10-RP10-处理处理3232个个ByteByte，跳过，跳过3232个个ByteByte RP11-RP11-跳过跳过3232个个ByteByte，处理，处理3232个个ByteByte；RP12-RP12-处理处理6464个个ByteByte，跳过，跳过6464个个ByteByte RP13-RP13-跳过跳过6464个个ByteByte，处理，处理6464个个ByteByte；RP14-RP14-处理处理128128个个B

17、yteByte，跳过，跳过128128个个ByteByte RP15-RP15-跳过跳过128128个个ByteByte，处理，处理128128个个ByteByte；可见，可见，RP0 RP15 RP0 RP15 每个每个BitBit位都是位都是128128个字节（也就是个字节（也就是128128行）即行）即128*8=1024128*8=1024个个BitBit位求异或的结果。位求异或的结果。数据校数据校验验-ECC校验校验 综上所述，对综上所述，对256256字节的数据共生成了字节的数据共生成了6 6个个BitBit的的列校验结果，列校验结果，1616个个BitBit的行校验结果，共的行校

18、验结果，共2222个个BitBit。在在NandNand中使用中使用3 3个字节存放校验结果，多余的两个个字节存放校验结果，多余的两个BitBit位置位置1 1。存放次序如下表所示：。存放次序如下表所示：数据校数据校验验-ECC校验校验 在在LinuxLinux内核中内核中ECCECC校验算法所在的文件为校验算法所在的文件为drivers/mtd/nand/nand_ecc.cdrivers/mtd/nand/nand_ecc.c，其实现有新、旧两种，其实现有新、旧两种，在在2.6.272.6.27及更早的内核中使用的程序，从及更早的内核中使用的程序，从2.6.282.6.28开始开始已经不再

19、使用，而换成了效率更高的程序。已经不再使用，而换成了效率更高的程序。可以在可以在Documentation/mtd/nand_ecc.txtDocumentation/mtd/nand_ecc.txt 文件中找到对新程序的详细介绍。文件中找到对新程序的详细介绍。3.2：drivers/mtd/nand/nand_ecc.c数据校数据校验验-ECC校验校验当往当往NAND FlashNAND Flash的的pagepage中写入数据的时候，每中写入数据的时候，每256256字节我们生成一个字节我们生成一个ECCECC校验和，称之为原校验和，称之为原ECCECC校验和，保校验和，保存到存到OOBO

20、OB数据区中。数据区中。（传输层协议使用带外数据（传输层协议使用带外数据out-of-bandout-of-band，OOBOOB来发送一些重要的来发送一些重要的数据，如果通信一方有重要的数据需要通知对方时，协议能够将数据，如果通信一方有重要的数据需要通知对方时，协议能够将这些数据快速地发送到对方）这些数据快速地发送到对方）当从当从NAND FlashNAND Flash中读取数据的时候，每中读取数据的时候，每256256字节我字节我们生成一个们生成一个ECCECC校验和，称之为新校验和，称之为新ECCECC校验和。校验和。将从将从OOBOOB区中读出的原区中读出的原ECCECC校验和新校验和

21、新ECCECC校验和按位校验和按位异或，若结果为异或，若结果为0 0，则表示不存在错（或是出现了，则表示不存在错（或是出现了 ECC ECC无法检测的错误）；若无法检测的错误）；若3 3个字节异或结果中存在个字节异或结果中存在1111个比个比特位为特位为1 1，表示存在一个比特错误，且可纠正；若，表示存在一个比特错误，且可纠正；若3 3个字个字节异或结果中只存在节异或结果中只存在1 1个比特位为个比特位为1 1，表示，表示 OOB OOB区出错；区出错；其他情况均表示出现了无法纠正的错误。其他情况均表示出现了无法纠正的错误。数据校数据校验验-ECC校验校验例例 假设待校验的数据为两个字节，假设

22、待校验的数据为两个字节，0 x450 x45（二进制为（二进制为0100 01010100 0101）和）和0 x380 x38（二进制为（二进制为0011 10000011 1000），其行列），其行列校验码如下表所示：校验码如下表所示：数据校数据校验验-ECC校验校验从表中可以计算出从表中可以计算出CP5 CP0CP5 CP0的值，列在下表的的值，列在下表的第一行（原始数据）。假设现在有一个数据位发生变第一行（原始数据）。假设现在有一个数据位发生变化，化，0 x380 x38变为变为0 x3A0 x3A，也就是，也就是Byte1Byte1的的Bit 1Bit 1由由0 0变成了变成了1 1

23、，计算得到新的，计算得到新的CP5 CP0CP5 CP0值放在下表第值放在下表第2 2行（变化后行（变化后数据）。新旧校验码求异或的结果放在下表第三行。数据）。新旧校验码求异或的结果放在下表第三行。数据校数据校验验-ECC校验校验可见，当可见，当 Bit1Bit1发生变化时，列校验值中只有发生变化时，列校验值中只有CP1CP1，CP2CP2，CP4CP4发生了变化，而发生了变化，而CP0CP0，CP3CP3，CP5CP5没变没变化，也就是说化，也就是说6 6个个BitBit校验码有一半发生变化，则校验码有一半发生变化，则求异或的结果中有一半为求异或的结果中有一半为1 1。同理，行校验求异。同理

24、，行校验求异或的结果也有一半为或的结果也有一半为1 1。这就是为什么前面说。这就是为什么前面说256256字节数据中的一个字节数据中的一个BitBit位发生变化时，新旧位发生变化时，新旧22Bit22Bit校验码求异或的结果中会有校验码求异或的结果中会有1111个个Bit Bit 位为位为1 1。数据校数据校验验-ECC校验校验再来看怎么定位出错的再来看怎么定位出错的BitBit位。以列地址为例，若位。以列地址为例，若CP5CP5发生变化（异或后的发生变化（异或后的CP5=1CP5=1），则出错处肯定在），则出错处肯定在 Bit 4 Bit 7Bit 4 Bit 7中；若中；若CP5CP5无变

25、化（异或后的无变化（异或后的CP5=0CP5=0）,则出错处在则出错处在 Bit 0 Bit 3 Bit 0 Bit 3 中，这样就筛中，这样就筛选掉了一半的选掉了一半的BitBit位。剩下的位。剩下的4 4个个BitBit位中，再看位中，再看CP3CP3是否发生变化，又选出是否发生变化，又选出2 2个个BitBit位。剩下的位。剩下的2Bit2Bit位中位中再看再看CP1CP1是否发生变化，则最终可定位是否发生变化，则最终可定位1 1个出错的个出错的BitBit位。下面的树形结构更清晰地展示了这个判决过程：位。下面的树形结构更清晰地展示了这个判决过程：数据校数据校验验-ECC校验校验数据校数

26、据校验验-ECC校验校验这样，我们从异或结果中抽取出这样，我们从异或结果中抽取出CP5CP5，CP3CP3，CP1CP1位，便可定位出错位，便可定位出错BitBit位的列地址。比如上面的位的列地址。比如上面的例子中例子中CP5/CP3/CP1=001CP5/CP3/CP1=001，表示，表示Bit 1Bit 1出错。出错。同理，行校验同理，行校验RP1RP1发生变化，抽取发生变化，抽取RP1RP1，可知，可知Byte 1Byte 1发生变化。这样定位出发生变化。这样定位出Byte 1Byte 1的的Bit 0Bit 0出出错。错。当数据位当数据位256256字节时，行校验使用字节时，行校验使用

27、RP0 RP15RP0 RP15，抽取异或结果的，抽取异或结果的RP15RP15，RP13RP13，RP11RP11，RP9RP9，RP7RP7，RP5RP5，RP3RP3，RP1RP1位便可定位出哪个位便可定位出哪个ByteByte出出错，再用错，再用CP5,CP3,CP1CP5,CP3,CP1定位哪个定位哪个BitBit出错。出错。数据校数据校验验-ECC校验校验谢谢!数据校数据校验验完完例：需要校验数据1010 生成多项式G(x)=1011校验位：011 被除数 余数 除数：1011正确：1010011 000 错误：1010010 001（第七位错）1010001 010（第六位错）1010111 100（第五位错）1011011 011（第四位错）1000011 110（第三位错）1110011 111（第二位错）0010011 101（第一位错）假设第七位错误 余数001；001后补零成0010 除数1011继续除 余数010010后补零成0100 余100.照此法动作依次得到001 010 100 011 110 111 101 001.