nand flash ecc, oob
发布时间：2020-12-15 07:01:06 所属栏目：百科 来源：网络整理
导读：极详细的ECC讲解 ECC的全称是Error Checking and Correction，是一种用于 Nand 的差错检测和修正算法。 如果操作时序和电路稳定性不存在问题的话， NAND Flash 出错的时候一般不会造成整个 Block 或是 Page 不能读取或是全部出错，而是整个 Page （例如 512B
极详细的ECC讲解
ECC的全称是Error Checking and Correction，是一种用于
Nand
的差错检测和修正算法。如果操作时序和电路稳定性不存在问题的话，
NAND Flash
出错的时候一般不会造成整个
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 位，表示 Column Parity （列极性）， 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 位，表示 Row Parity （行极性）， RP0 为第 0 、 2 、 4 、 6 、….252、 254 个字节的极性 RP1-----1、 3 、 5 、 7……253、 255 RP2----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 个 Byte RP7---- 跳过 8 个 Byte ，处理 8 个 Byte ； RP8---- 处理 16 个 Byte ，跳过 16 个 Byte RP9---- 跳过 16 个 Byte ，处理 16 个 Byte ； RP10----处理 32 个 Byte ，跳过 32 个 Byte RP11---- 跳过 32 个 Byte ，处理 32 个 Byte ； RP12----处理 64 个 Byte ，跳过 64 个 Byte RP13---- 跳过 64 个 Byte ，处理 64 个 Byte ； RP14----处理 128 个 Byte ，跳过 128 个 Byte RP15---- 跳过 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 字节。 ?校验码生成算法的C语言实现
这个表的意思是：对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 ] 处存储的值应该是 0101 0110，即0x56. 注意，数组nand_ecc_precalc_table的下标其实是我们要校验的一个字节数据。 理解了这个表的含义，也就很容易写个程序生成这个表了。程序见附件中的 MakeEccTable.c文件。 有了这个表，对单字节数据dat，可以直接查表 nand_ecc_precalc_table[ dat ] 得到 dat的行校验值和列校验值。 但是ECC实际要校验的是256字节的数据，需要进行256次查表，对得到的256个查表结果进行按位异或，最终结果的 Bit0 ~ Bit5 即是256字节数据的 CP0 ~ CP5. /* Build up column parity */ ??81? ?? ???for(i = 0; i < 256; i++) { ??82 /* Get CP0 - CP5 from table */ ??83 idx = nand_ecc_precalc_table[*dat++]; ??84 reg1 ^= (idx & 0x3f); ??85 ??86? ?? ?? ?? ?//这里省略了一些，后面会介绍 ??91? ?? ???} Reg1
在这里，计算列极性的过程其实是先在一个字节数据的内部计算CP0 ~ CP5,每个字节都计算完后再与其它字节的计算结果求异或。而表1中是先对一列Bit0求异或，再去异或一列Bit2。 这两种只是计算顺序不同，结果是一致的。 因为异或运算的顺序是可交换的。 行极性的计算要复杂一些。 nand_ecc_precalc_table[] 表中的 Bit6 已经保存了每个单字节数的行极性值。对于待校验的256字节数据，分别查表，如果其行极性为1，则记录该数据所在的行索引（也就是for循环的i值），这里的行索引是很重要的，因为RP0 ~ RP15 的计算都是跟行索引紧密相关的，如RP0只计算偶数行，RP1只计算奇数行，等等。 /* Build up column parity */ ??81? ?? ???for(i = 0; i < 256; i++) { ??82 /* Get CP0 - CP5 from table */ ??83 idx = nand_ecc_precalc_table[*dat++]; ??84 reg1 ^= (idx & 0x3f); ??85 ??86 /* All bit XOR = 1 ? */ ??87? ?? ?? ?? ?? ? if (idx & 0x40) { ??88 reg3 ^= (uint8_t) i; ??89 reg2 ^= ~((uint8_t) i); ??90? ?? ?? ?? ?? ? } ??91? ?? ???} 这里的关键是理解第88和89行。Reg3和reg2都是unsigned char 型的变量，并都初始化为零。 行索引（也就是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 的Bit 0指示，0表示有偶数个，1表示有奇数个； 属于RP 3 计算范围内的行有多少个------由 reg3 的Bit 1 指示，0表示有偶数个，1表示有奇数个； 属于RP 5 计算范围内的行有多少个------由 reg3 的Bit 2 指示，0表示有偶数个，1表示有奇数个； 属于RP 7 计算范围内的行有多少个------由 reg3 的Bit 3 指示，0表示有偶数个，1表示有奇数个； 属于RP 9 计算范围内的行有多少个------由 reg3 的Bit 4 指示，0表示有偶数个，1表示有奇数个； 属于RP 1 1计算范围内的行有多少个------由 reg3 的Bit 5 指示，0表示有偶数个，1表示有奇数个； 属于RP1 3 计算范围内的行有多少个------由 reg3 的Bit 6 指示，0表示有偶数个，1表示有奇数个； 属于RP1 5 计算范围内的行有多少个------由 reg3 的Bit 7 指示，0表示有偶数个，1表示有奇数个； 所以， reg3 每个Bit位的作用如下表所示： R eg3
第89行，对所有行校验为1的行索引按位取反之后，再按位异或，作用就是判断比特位为0的个数。比如reg2的Bit0为0表示：所有行校验为1的行中，行索引的Bit0为0的行有偶数个，也就是落在RP0计算范围内的行有偶数个。所以得到结论： 在所有行校验为1的行中， 属于RP0计算范围内的行有多少个------由 reg 2的Bit 0指示，0表示有偶数个，1表示有奇数个； 属于RP2计算范围内的行有多少个------由 reg 2的Bit 1 指示，0表示有偶数个，1表示有奇数个； 属于RP4计算范围内的行有多少个------由 reg 2的Bit 2 指示，0表示有偶数个，1表示有奇数个； 属于RP6计算范围内的行有多少个------由 reg 2的Bit 3 指示，0表示有偶数个，1表示有奇数个； 属于RP8计算范围内的行有多少个------由 reg 2的Bit 4 指示，0表示有偶数个，1表示有奇数个； 属于RP 1 0计算范围内的行有多少个------由 re g2的Bit 5 指示，0表示有偶数个，1表示有奇数个； 属于RP12计算范围内的行有多少个------由 reg2 的Bit 6 指示，0表示有偶数个，1表示有奇数个； 属于RP14计算范围内的行有多少个------由 reg2 的Bit 7 指示，0表示有偶数个，1表示有奇数个； 所以， reg2 每个Bit位的作用如下表所示： R eg 2
至此，只用了一个查找表和一个for循环，就把所有的校验位 CP0 ~ CP5 和RP 0 ~ RP15 全都计算出来了。下面的任务只是按照表3的格式，把这些比特位重新排列一下顺序而已。 从 reg2 和 reg3 中抽取出 RP8~RP15 放在tmp1中，抽取出 RP0~RP7 放在tmp2中， Reg1 左移两位，低两位置1， 然后把 tmp2,tmp1,reg1 放在 ECC码的三个字节中。 程序中还有 CONFIG_MTD_NAND_ECC_SMC ， 又进行了一次取反操作，暂时还不知为何。 ? ?ECC纠错算法
对ecc_code_raw[3] 和 ecc_code_new[3] 按位异或，得到的结果三个字节分别保存在s0,s1,s2中，如果s0s1s2中共有11个Bit位为1，则表示出现了一个比特位错误，可以修正。定位出错的比特位的方法是，先确定行地址（即哪个字节出错），再确定列地址（即该字节中的哪一个Bit位出错）。 确定行地址的方法是，设行地址为unsigned char byteoffs，抽取s1中的Bit7,Bit5,Bit3,Bit1，作为 byteoffs的高四位， 抽取s0中的Bit7,Bit1 作为byteoffs的低四位， 则byteoffs的值就表示出错字节的行地址（范围为0 ~ 255）。 确定列地址的方法是：抽取s2中的Bit7,Bit3 作为 bitnum 的低三位，bitnum其余位置0，则bitnum的表示出错Bit位的列地址 （范围为0 ~ 7）。 下面以一个简单的例子探索一下这其中的奥妙。 假设待校验的数据为两个字节，0x45（二进制为0100 0101）和0x38（二进制为0011 1000），其行列校验码如下表所示：
从表中可以计算出CP5 ~ CP0的值，列在下表的第一行（原始数据）。假设现在有一个数据位发生变化，0x38变为0x3A，也就是Byte 1的Bit 1由0变成了1，计算得到新的CP5 ~ CP0值放在下表第2行（变化后数据）。新旧校验码求异或的结果放在下表第三行。 可见，当 Bit 1发生变化时，列校验值中只有CP1，CP2，CP4发生了变化，而CP0，CP3，CP5没变化，也就是说6个Bit校验码有一半发生变化，则求异或的结果中有一半为1。同理，行校验求异或的结果也有一半为1。这就是为什么前面说256字节数据中的一个Bit位发生变化时，新旧22Bit校验码求异或的结果中会有11个Bit 位为1。
再来看怎么定位出错的Bit位。以列地址为例，若CP5发生变化（异或后的CP5=1），则出错处肯定在 Bit 4 ~ Bit 7中；若CP5无变化（异或后的CP5=0）,则出错处在 Bit 0 ~ Bit 3 中，这样就筛选掉了一半的Bit位。剩下的4个Bit位中，再看CP3是否发生变化，又选出2个Bit位。剩下的2Bit位中再看CP1是否发生变化，则最终可定位1个出错的Bit位。下面的树形结构更清晰地展示了这个判决过程：
图表 1??出错Bit列地址定位的判决树 注意：图中的CP指的是求异或之后的结果中的CP 为什么只用CP4，CP2，CP0呢？其实这里面包含冗余信息，因为CP5=1则必有CP4=0，CP 5=0 则必有CP4=1，也就是CP5跟CP4一定相反，同理， CP3 跟CP2一定相反，CP1跟CP0一定相反。所以只需要用一半就行了。 这样，我们从异或结果中抽取出CP5，CP3，CP1位，便可定位出错Bit位的列地址。比如上面的例子中 CP5/CP3/CP1 = 001 ，表示Bit 1出错。 同理，行校验RP1发生变化，抽取RP1，可知Byte 1发生变化。这样定位出Byte 1的Bit 0出错。 当数据位256字节时，行校验使用RP0 ~ RP15，抽取异或结果的 RP 15， RP13 ， RP11 ， RP 9， RP 7， RP 5，RP3，RP1位便可定位出哪个Byte出错，再用CP5,CP3,CP1定位哪个Bit出错。 ? ? ? TestEcc.rar (2.12 KB) ?? 用ECC定位出错Bit的实验程序? http://linux.chinaunix.net/bbs/attachment.php?aid=231922 ?MakeEccTable.rar? Make_Ecc_Table.c 代码?? http://linux.chinaunix.net/bbs/attachment.php?aid=231869 （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
