NAND FLASH 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，如下图所示：

　　ECC的列校验和生成规则如下图所示（Parity Generation ( In case of 256 byte input )）：

　 ?用数学表达式表示为：
　　　　P1=bit7(+)bit5(+)bit3(+)bit1(+)P1

? ? ? ? ? ? ? P2=bit7(+)bit6(+)bit3(+)bit2(+)P2

? ? ? ? ? ? ? P4=bit7(+)bit6(+)bit5(+)bit4(+)P4

　　用数学表达式表示为：
　　　　 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区出错；其他情况均表示出现了无法纠正的错误。

? ? - The result of XOR : all ECC code is `0`

* Correctable Error

? ?- The result of XOR : total 11bits are `1`

? ?- When main area has 1 bit error,each parity pair (ex. P8 & P8`) has 1 & 0 or 0 & 1

*ECC Error

? - The result of XOR : only 1bit is `1`

? - When ECC area has an error,call it ECC error

* Uncorrectable Error

? - The result of XOR : random data

? - When the flash memory has more than 2 bits error,data couldn’t be corrected

ECC算法的实现
　　static?const?u_char?nand_ecc_precalc_table[]?=
　　{
　　　　0x00,?0x55,?0x56,?0x03,?0x59,?0x0c,?0x0f,?0x5a,?0x00,
　　　　0x65,?0x30,?0x33,?0x66,?0x3c,?0x69,?0x6a,?0x3f,?0x65,
　　　　0x66,
　　　　0x03,
　　　　0x69,
　　　　0x0c,
　　　　0x0f,
　　　　0x6a,
　　　　0x00,?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,?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; 　　}?