Nand-ECC-校验和纠错-详解

ECC的全称是ErrorCheckingandCorrection，是一种用于Nand的差错检测和修正算法。如果操作时序和电路稳定性不存在问题的话，NANDFlash出错的时候一般不会造成整个Block或是Page不能读取或是全部出错，而是整个Page（例如512Bytes）中只有一个或几个bit出错。ECC能纠正1个比特错误和检测2个比特错误，而且计算速度很快，但对1比特以上的错误无法纠正，对2比特以上的错误不保证能检测。校验码生成算法：ECC校验每次对256字节的数据进行操作，包含列校验和行校验。对每个待校验的Bit位求异或，若结果为0，则表明含有偶数个1；若结果为1，则表明含有奇数个1。列校验规则如表1所示。256字节数据形成256行、8列的矩阵，矩阵每个元素表示一个Bit位。其中CP0~CP5为六个Bit位，表示ColumnParity（列极性），CP0为第0、2、4、6列的极性，CP1为第1、3、5、7列的极性，CP2为第0、1、4、5列的极性，CP3为第2、3、6、7列的极性，CP4为第0、1、2、3列的极性，CP5为第4、5、6、7列的极性。用公式表示就是：CP0=Bit0^Bit2^Bit4^Bit6，表示第0列内部256个Bit位异或之后再跟第2列256个Bit位异或，再跟第4列、第6列的每个Bit位异或，这样，CP0其实是256*4=1024个Bit位异或的结果。CP1~CP5依此类推。行校验如下图所示其中RP0~RP15为十六个Bit位，表示RowParity（行极性），RP0为第0、2、4、6、….252、254个字节的极性RP1-----1、3、5、7……253、255RP2----0、1、4、5、8、9…..252、253（处理2个Byte，跳过2个Byte）RP3----2、3、6、7、10、11…..254、255（跳过2个Byte，处理2个Byte）RP4----处理4个Byte，跳过4个Byte；RP5----跳过4个Byte，处理4个Byte；RP6----处理8个Byte，跳过8个ByteRP7----跳过8个Byte，处理8个Byte；RP8----处理16个Byte，跳过16个ByteRP9----跳过16个Byte，处理16个Byte；RP10----处理32个Byte，跳过32个ByteRP11----跳过32个Byte，处理32个Byte；RP12----处理64个Byte，跳过64个ByteRP13----跳过64个Byte，处理64个Byte；RP14----处理128个Byte，跳过128个ByteRP15----跳过128个Byte，处理128个Byte；可见，RP0~RP15每个Bit位都是128个字节（也就是128行）即128*8=1024个Bit位求异或的结果。综上所述，对256字节的数据共生成了6个Bit的列校验结果，16个Bit的行校验结果，共22个Bit。在Nand中使用3个字节存放校验结果，多余的两个Bit位置1。存放次序如下表所示：以K9F1208为例，每个Page页包含512字节的数据区和16字节的OOB区。前256字节数据生成3字节ECC校验码，后256字节数据生成3字节ECC校验码，共6字节ECC校验码存放在OOB区中，存放的位置为OOB区的第0、1、2和3、6、7字节。文件:MakeEccTable.rar大小:0KB下载:下载校验码生成算法的C语言实现在Linux内核中ECC校验算法所在的文件为drivers/mtd/nand/nand_ecc.c，其实现有新、旧两种，在2.6.27及更早的内核中使用的程序，从2.6.28开始已经不再使用，而换成了效率更高的程序。可以在Documentation/mtd/nand_ecc.txt文件中找到对新程序的详细介绍。首先分析一下2.6.27内核中的ECC实现，源代码见:*44*Pre-calculated256-way1bytecolumnparity45*/46staticconstu_charnand_ecc_precalc_table[]={470x00,0x55,0x56,0x03,0x59,0x0c,0x0f,0x5a,0x5a,0x0f,0x0c,0x59,0x03,0x56,0x55,0x00,480x65,0x30,0x33,0x66,0x3c,0x69,0x6a,0x3f,0x3f,0x6a,0x69,0x3c,0x66,0x33,0x30,0x65,490x66,0x33,0x30,0x65,0x3f,0x6a,0x69,0x3c,0x3c,0x69,0x6a,0x3f,0x65,0x30,0x33,0x66,500x03,0x56,0x55,0x00,0x5a,0x0f,0x0c,0x59,0x59,0x0c,0x0f,0x5a,0x00,0x55,0x56,0x03,510x69,0x3c,0x3f,0x6a,0x30,0x65,0x66,0x33,0x33,0x66,0x65,0x30,0x6a,0x3f,0x3c,0x69,520x0c,0x59,0x5a,0x0f,0x55,0x00,0x03,0x56,0x56,0x03,0x00,0x55,0x0f,0x5a,0x59,0x0c,530x0f,0x5a,0x59,0x0c,0x56,0x03,0x00,0x55,0x55,0x00,0x03,0x56,0x0c,0x59,0x5a,0x0f,540x6a,0x3f,0x3c,0x69,0x33,0x66,0x65,0x30,0x30,0x65,0x66,0x33,0x69,0x3c,0x3f,0x6a,550x6a,0x3f,0x3c,0x69,0x33,0x66,0x65,0x30,0x30,0x65,0x66,0x33,0x69,0x3c,0x3f,0x6a,560x0f,0x5a,0x59,0x0c,0x56,0x03,0x00,0x55,0x55,0x00,0x03,0x56,0x0c,0x59,0x5a,0x0f,570x0c,0x59,0x5a,0x0f,0x55,0x00,0x03,0x56,0x56,0x03,0x00,0x55,0x0f,0x5a,0x59,0x0c,580x69,0x3c,0x3f,0x6a,0x30,0x65,0x66,0x33,0x33,0x66,0x65,0x30,0x6a,0x3f,0x3c,0x69,590x03,0x56,0x55,0x00,0x5a,0x0f,0x0c,0x59,0x59,0x0c,0x0f,0x5a,0x00,0x55,0x56,0x03,600x66,0x33,0x30,0x65,0x3f,0x6a,0x69,0x3c,0x3c,0x69,0x6a,0x3f,0x65,0x30,0x33,0x66,610x65,0x30,0x33,0x66,0x3c,0x69,0x6a,0x3f,0x3f,0x6a,0x69,0x3c,0x66,0x33,0x30,0x65,620x00,0x55,0x56,0x03,0x59,0x0c,0x0f,0x5a,0x5a,0x0f,0x0c,0x59,0x03,0x56,0x55,0x0063};为了加快计算速度，程序中使用了一个预先计算好的列极性表。这个表中每一个元素都是unsignedchar类型，表示8位二进制数。表中8位二进制数每位的含义：这个表的意思是：对0~255这256个数，计算并存储每个数的列校验值和行校验值，以数作数组下标。比如nand_ecc_precalc_table[13]存储13的列校验值和行校验值，13的二进制表示为00001101，其CP0=Bit0^Bit2^Bit4^Bit6=0；CP1=Bit1^Bit3^Bit5^Bit7=1；CP2=Bit0^Bit1^Bit4^Bit5=1;CP3=Bit2^Bit3^Bit6^Bit7=0;CP4=Bit0^Bit1^Bit2^Bit3=1;CP5=Bit4^Bit5^Bit6^Bit7=0;其行极性RP=Bit0^Bit1^Bit2^Bit3^Bit4^Bit5^Bit6^Bit7=1；则nand_ecc_precalc_table[13]处存储的值应该是01010110，即0x56.注意，数组nand_ecc_precalc_table的下标其实是我们要校验的一个字节数据。理解了这个表的含义，也就很容易写个程序生成这个表了。程序见附件中的MakeEccTable.c文件。有了这个表，对单字节数据dat，可以直接查表nand_ecc_precalc_table[dat]得到dat的行校验值和列校验值。但是ECC实际要校验的是256字节的数据，需要进行256次查表，对得到的256个查表结果进行按位异或，最终结果的Bit0~Bit5即是256字节数据的CP0~CP5./*Buildupcolumnparity*/81for(i=0;i256;i++){82/*GetCP0-CP5fromtable*/83idx=nand_ecc_precalc_table[*dat++];84reg1^=(idx&0x3f);8586//这里省略了一些，后面会介绍91}Reg1在这里，计算列极性的过程其实是先在一个字节数据的内部计算CP0~CP5,每个字节都计算完后再与其它字节的计算结果求异或。而表1中是先对一列Bit0求异或，再去异或一列Bit2。这两种只是计算顺序不同，结果是一致的。因为异或运算的顺序是可交换的。行极性的计算要复杂一些。nand_ecc_precalc_table[]表中的Bit6已经保存了每个单字节数的行极性值。对于待校验的256字节数据，分别查表，如果其行极性为1，则记录该数据所在的行索引（也就是for循环的i值），这里的行索引是很重要的，因为RP0~RP15的计算都是跟行索引紧密相关的，如RP0只计算偶数行，RP1只计算奇数行，等等。/*Buildupcolumnparity*/81for(i=0;i256;i++){82/*GetCP0-CP5fromtable*/83idx=nand_ecc_precalc_table[*dat++];84reg1^=(idx&0x3f);8586/*AllbitXOR=1?*/87if(idx&0x40){88reg3^=(uint8_t)i;89reg2^=~((uint8_t)i);90}91}这里的关键是理解第88和89行。Reg3和reg2都是unsignedchar型的变量，并都初始化为零。行索引（也就是for循环里的i）的取值范围为0~255，根据表2可以得出以下规律：RP0只计算行索引的Bit0为0的行，RP1只计算行索引的Bit0为1的行；RP2只计算行索引的Bit1为0的行，RP3只计算行索引的Bit1为1的行；RP4只计算行索引的Bit2为0的行，RP5只计算行索引的Bit2为1的行；RP6只计算行索引的Bit3为0的行，RP7只计算行索引的Bit3为1的行；RP8只计算行索引的Bit4为0的行，RP9只计算行索引的Bit4为1的行；RP10只计算行索引的Bit5为0的行，RP11只计算行索引的Bit5为1的行；RP12只计算行索引的Bit6为0的行，RP13只计算行索引的Bit6为1的行；RP14只计算行索引的Bit7为0的行，RP15只计算行索引的Bit7为1的行；已经知道，异或运算的作用是判断比特位为1的个数，跟比特位为0的个数没有关系。如果有偶数个1则异或的结果为0，如果有奇数个1则异或的结果为1。那么，程序第88行，对所有行校验为1的行索引按位异或运算，作用便是：判断在所有行校验为1的行中，属于RP1计算范围内的行有多少个------由reg3的Bit0指示，0表示有偶数个