关注+星标公众号，不错过精彩内容
来源 | nhczp
编排 | strongerHuang
大家应该都在用U盘，而U盘中的存储芯片就是，你买的64G的U盘，实际并没有64G，其中一个原因就是存在坏块。
因为工艺和其他方面的原因，不能保证NandFlash不存在坏块，因此就需要“挑选出坏块”。
本文就为大家讲述一下用于NandFlash的ECC校验原理与实现。
ECC简介
由于NAND Flash的工艺不能保证NAND的Memory Array在其生命周期中保持性能的可靠，因此，在NAND的生产中及使用过程中会产生坏块。为了检测数据的可靠性，在应用NAND Flash的系统中一般都会采用一定的坏区管理策略，而管理坏区的前提是能比较可靠的进行坏区检测。
对数据的校验常用的有奇偶校验、CRC校验等，而在NAND Flash处理中，一般使用一种比较专用的校验——ECC。ECC能纠正单比特错误和检测双比特错误，而且计算速度很快，但对1比特以上的错误无法纠正，对2比特以上的错误不保证能检测。
ECC原理
ECC一般每256字节原始数据生成3字节ECC校验数据，这三字节共24比特分成两部分：6比特的列校验和16比特的行校验，多余的两个比特置1，如下图所示：
ECC的列校验和生成规则如下图所示：
用数学表达式表示为：
P4=D7(+)D6(+)D5(+)D4 P4`=D3(+)D2(+)D1(+)D0P2=D7(+)D6(+)D3(+)D2 P2`=D5(+)D4(+)D1(+)D0P1=D7(+)D5(+)D3(+)D1 P1`=D6(+)D4(+)D2(+)D0备注：这里(+)表示“位异或”操作ECC的行校验和生成规则如下图所示：
用数学表达式表示为：
P8 = bit7(+)bit6(+)bit5(+)bit4(+)bit3(+)bit2(+)bit1(+)bit0(+)P8备注：这里(+)表示“位异或”操作当往NAND Flash的page中写入数据的时候，每256字节我们生成一个ECC校验和，称之为原ECC校验和，保存到PAGE的OOB（out-of-band）数据区中。
当从NAND Flash中读取数据的时候，每256字节我们生成一个ECC校验和，称之为新ECC校验和。
校验的时候，根据上述ECC生成原理不难推断：将从OOB区中读出的原ECC校验和新ECC校验和按位异或，若结果为0，则表示不存在错（或是出现了ECC无法检测的错误）；若3个字节异或结果中存在11个比特位为1，表示存在一个比特错误，且可纠正；若3个字节异或结果中只存在1个比特位为1，表示OOB区出错；其他情况均表示出现了无法纠正的错误。
ECC算法的实现
这里附上算法代码：static const u_char nand_ecc_precalc_table[] = { 0x00, 0x55, 0x56, 0x03, 0x59, 0x0c, 0x0f, 0x5a, 0x5a, 0x0f, 0x0c, 0x59, 0x03, 0x56, 0x55, 0x00, 0x65, 0x30, 0x33, 0x66, 0x3c, 0x69, 0x6a, 0x3f, 0x3f, 0x6a, 0x69, 0x3c, 0x66, 0x33, 0x30, 0x65, 0x66, 0x33, 0x30, 0x65, 0x3f, 0x6a, 0x69, 0x3c, 0x3c, 0x69, 0x6a, 0x3f, 0x65, 0x30, 0x33, 0x66, 0x03, 0x56, 0x55, 0x00, 0x5a, 0x0f, 0x0c, 0x59, 0x59, 0x0c, 0x0f, 0x5a, 0x00, 0x55, 0x56, 0x03, 0x69, 0x3c, 0x3f, 0x6a, 0x30, 0x65, 0x66, 0x33, 0x33, 0x66, 0x65, 0x30, 0x6a, 0x3f, 0x3c, 0x69, 0x0c, 0x59, 0x5a, 0x0f, 0x55, 0x00, 0x03, 0x56, 0x56, 0x03, 0x00, 0x55, 0x0f, 0x5a, 0x59, 0x0c, 0x0f, 0x5a, 0x59, 0x0c, 0x56, 0x03, 0x00, 0x55, 0x55, 0x00, 0x03, 0x56, 0x0c, 0x59, 0x5a, 0x0f, 0x6a, 0x3f, 0x3c, 0x69, 0x33, 0x66, 0x65, 0x30, 0x30, 0x65, 0x66, 0x33, 0x69, 0x3c, 0x3f, 0x6a, 0x6a, 0x3f, 0x3c, 0x69, 0x33, 0x66, 0x65, 0x30, 0x30, 0x65, 0x66, 0x33, 0x69, 0x3c, 0x3f, 0x6a, 0x0f, 0x5a, 0x59, 0x0c, 0x56, 0x03, 0x00, 0x55, 0x55, 0x00, 0x03, 0x56, 0x0c, 0x59, 0x5a, 0x0f, 0x0c, 0x59, 0x5a, 0x0f, 0x55, 0x00, 0x03, 0x56, 0x56, 0x03, 0x00, 0x55, 0x0f, 0x5a, 0x59, 0x0c, 0x69, 0x3c, 0x3f, 0x6a, 0x30, 0x65, 0x66, 0x33, 0x33, 0x66, 0x65, 0x30, 0x6a, 0x3f, 0x3c, 0x69, 0x03, 0x56, 0x55, 0x00, 0x5a, 0x0f, 0x0c, 0x59, 0x59, 0x0c, 0x0f, 0x5a, 0x00, 0x55, 0x56, 0x03, 0x66, 0x33, 0x30, 0x65, 0x3f, 0x6a, 0x69, 0x3c, 0x3c, 0x69, 0x6a, 0x3f, 0x65, 0x30, 0x33, 0x66, 0x65, 0x30, 0x33, 0x66, 0x3c, 0x69, 0x6a, 0x3f, 0x3f, 0x6a, 0x69, 0x3c, 0x66, 0x33, 0x30, 0x65, 0x00, 0x55, 0x56, 0x03, 0x59, 0x0c, 0x0f, 0x5a, 0x5a, 0x0f, 0x0c, 0x59, 0x03, 0x56, 0x55, 0x00 };
// Creates non-inverted ECC code from line parity static void nand_trans_result(u_char reg2, u_char reg3,u_char *ecc_code) { u_char a, b, i, tmp1, tmp2;
/* Initialize variables */ a = b = 0x80; tmp1 = tmp2 = 0;
/* Calculate first ECC byte */ for (i = 0; i < 4; i++) { if (reg3 & a) /* LP15,13,11,9 --> ecc_code[0] */ tmp1 |= b; b >>= 1; if (reg2 & a) /* LP14,12,10,8 --> ecc_code[0] */ tmp1 |= b; b >>= 1; a >>= 1; }
/* Calculate second ECC byte */ b = 0x80; for (i = 0; i < 4; i++) { if (reg3 & a) /* LP7,5,3,1 --> ecc_code[1] */ tmp2 |= b; b >>= 1; if (reg2 & a) /* LP6,4,2,0 --> ecc_code[1] */ tmp2 |= b; b >>= 1; a >>= 1; }
/* Store two of the ECC bytes */ ecc_code[0] = tmp1; ecc_code[1] = tmp2; }
// Calculate 3 byte ECC code for 256 byte block void nand_calculate_ecc (const u_char *dat, u_char *ecc_code) { u_char idx, reg1, reg2, reg3; int j;
/* Initialize variables */ reg1 = reg2 = reg3 = 0; ecc_code[0] = ecc_code[1] = ecc_code[2] = 0;
/* Build up column parity */ for(j = 0; j < 256; j++) { /* Get CP0 - CP5 from table */ idx = nand_ecc_precalc_table[dat[j]]; reg1 ^= (idx & 0x3f);
/* All bit XOR = 1 ? */ if (idx & 0x40) { reg3 ^= (u_char) j; reg2 ^= ~((u_char) j); } }
/* Create non-inverted ECC code from line parity */ nand_trans_result(reg2, reg3, ecc_code);
/* Calculate final ECC code */ ecc_code[0] = ~ecc_code[0]; ecc_code[1] = ~ecc_code[1]; ecc_code[2] = ((~reg1) << 2) | 0x03; }
// Detect and correct a 1 bit error for 256 byte block int nand_correct_data (u_char *dat, u_char *read_ecc, u_char *calc_ecc) { u_char a, b, c, d1, d2, d3, add, bit, i;
/* Do error detection */ d1 = calc_ecc[0] ^ read_ecc[0]; d2 = calc_ecc[1] ^ read_ecc[1]; d3 = calc_ecc[2] ^ read_ecc[2];
if ((d1 | d2 | d3) == 0) { /* No errors */ return 0; } else { a = (d1 ^ (d1 >> 1)) & 0x55; b = (d2 ^ (d2 >> 1)) & 0x55; c = (d3 ^ (d3 >> 1)) & 0x54;
/* Found and will correct single bit error in the data */ if ((a == 0x55) && (b == 0x55) && (c == 0x54)) { c = 0x80; add = 0; a = 0x80; for (i=0; i<4; i++) { if (d1 & c) add |= a; c >>= 2; a >>= 1; } c = 0x80; for (i=0; i<4; i++) { if (d2 & c) add |= a; c >>= 2; a >>= 1; } bit = 0; b = 0x04; c = 0x80; for (i=0; i<3; i++) { if (d3 & c) bit |= b; c >>= 2; b >>= 1; } b = 0x01; a = dat[add]; a ^= (b << bit); dat[add] = a; return 1; } else { i = 0; while (d1) { if (d1 & 0x01) ++i; d1 >>= 1; } while (d2) { if (d2 & 0x01) ++i; d2 >>= 1; } while (d3) { if (d3 & 0x01) ++i; d3 >>= 1; } if (i == 1) { /* ECC Code Error Correction */ read_ecc[0] = calc_ecc[0]; read_ecc[1] = calc_ecc[1]; read_ecc[2] = calc_ecc[2]; return 2; } else { /* Uncorrectable Error */ return -1; } } }
/* Should never happen */ return -1; } 参考文档：
http://blogimg.chinaunix.net/blog/upfile2/080702112233.pdf
免责声明：本文素材来源网络，版权归原作者所有。如涉及作品版权问题，请与我联系删除。
------------ END ------------
后台回复『软件算法』『科普知识』阅读更多相关文章。
欢迎关注我的公众号，回复“加群”按规则加入技术交流群，回复“1024”查看更多内容。
欢迎关注我的视频号：
点击“阅读原文”查看更多分享，欢迎点分享、收藏、点赞、在看。