NandFlash ECC校验原理与实现

绝地灬酷狼 2022-08-29 14:48 211阅读 0赞

**关注+****星标公众****号**，不错过精彩内容

![e9419861f05bdd1e59ccb5f680cbacfe.gif][]

来源 | nhczp

编排 | strongerHuang

大家应该都在用U盘，而U盘中的存储芯片就是[**NandFlash**][NandFlash]，你买的64G的U盘，实际并没有64G，其中一个原因就是存在坏块。

因为工艺和其他方面的原因，不能保证NandFlash不存在坏块，因此就需要“挑选出坏块”。

本文就为大家讲述一下用于NandFlash的ECC校验原理与实现。

**ECC简介**

由于NAND Flash的工艺不能保证NAND的Memory Array在其生命周期中保持性能的可靠，因此，在NAND的生产中及使用过程中会产生坏块。**为了检测数据的可靠性，在应用NAND Flash的系统中一般都会采用一定的坏区管理策略，而管理坏区的前提是能比较可靠的进行坏区检测。**

如果操作时序和电路稳定性不存在问题的话，NAND Flash出错的时候一般不会造成整个Block或是Page不能读取或是全部出错，而是整个Page（例如512Bytes）中只有一个或几个bit出错。

对数据的校验常用的有奇偶校验、CRC校验等，而在NAND Flash处理中，一般使用一种比较专用的校验——ECC。**ECC能纠正单比特错误和检测双比特错误，而且计算速度很快，但对1比特以上的错误无法纠正，对2比特以上的错误不保证能检测。**

**ECC原理**

ECC一般每256字节原始数据生成3字节ECC校验数据，这三字节共24比特分成两部分：6比特的列校验和16比特的行校验，多余的两个比特置1，如下图所示：

![7ede6aa1e5d35ec80742dbf56bf92254.png][]

ECC的列校验和生成规则如下图所示：

![b29618f42ba1cc4e96174724c84570f7.png][]

用数学表达式表示为：

P4=D7(+)D6(+)D5(+)D4　　P4`=D3(+)D2(+)D1(+)D0
    P2=D7(+)D6(+)D3(+)D2　　P2`=D5(+)D4(+)D1(+)D0
    P1=D7(+)D5(+)D3(+)D1　　P1`=D6(+)D4(+)D2(+)D0

**备注：**这里(+)表示“位异或”操作

ECC的行校验和生成规则如下图所示：

![075878e801c2a9da12631747789daf2b.png][]

用数学表达式表示为：

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**”查看更多内容。

**欢迎关注我的视频号：**

![2dfd42963ed6b69876a7c355e02afd5b.png][]

点击“**阅读原文**”查看更多分享，欢迎**点分享、收藏、点赞、在看。**

[e9419861f05bdd1e59ccb5f680cbacfe.gif]: /images/20220829/a613924e47ec4ba88f68d7cce9d39e36.png
[NandFlash]: http://mp.weixin.qq.com/s?__biz=MzI4MDI4MDE5Ng%3D%3D&chksm=ebbbb7cddccc3edbca4404b9b20ade455f497d840301f184303beaf75d6a20e0dfee9f2f1886&idx=2&mid=2247490086&scene=21&sn=dd20c6a5bbb31a923edc8d230cba50c9#wechat_redirect
[7ede6aa1e5d35ec80742dbf56bf92254.png]: /images/20220829/a43b593d6d804e278c6032a1117245eb.png
[b29618f42ba1cc4e96174724c84570f7.png]: /images/20220829/31326144086b4343a39ef0fc815f0677.png
[075878e801c2a9da12631747789daf2b.png]: /images/20220829/747c0aa507014d2b8c476111e05615dc.png
[2dfd42963ed6b69876a7c355e02afd5b.png]: /images/20220829/31c1f407adda4e01b5843f2de1e84020.png