ECC纠错算法

ECC的全称是Error Checking and Correction。以NAND Flash为例，ECC每次对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表示第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);

以此类推。可见，RP0~RP15 每个Bit位都是128个字节（也就是128行）即128*8=1024个Bit位求异或的结果。

综上所述，对256字节的数据共生成了6个Bit的列校验结果，16个Bit的行校验结果，共22个Bit。256字节数据中的一个Bit位发生变化时，新旧22Bit校验码求异或的结果中会有11个Bit 位为1。

当往NAND Flash的page中写入数据的时候，每256字节我们生成一个ECC校验和，称之为原ECC校验和，保存到PAGE的OOB（out-of-band）数据区中。当从NAND Flash中读取数据的时候，每256字节我们生成一个ECC校验和，称之为新ECC校验和。将从OOB区中读出的原ECC校验和新ECC校验和按位异或，若结果为0，则表示不存在错（或是出错了，ECC无法检测的错误）；若3个字节异或结果中存在11个比特位为1，表示存在一个比特错误，且可纠正；其他情况均表示出现了无法纠正的错误。

举个更简单的ECC校验例子：

假设待校验的数据为两个字节，0x45（二进制为0100 0101）和0x38（二进制为0011 1000），假设现在有一个数据位发生变化，0x38变为0x3A。

Bit7

Bit6

Bit5

Bit4

Bit3

Bit2

Bit1

Bit0

0

1

0

0

0

1

0

1

0

0

1

1

1

0

0

0

Bit7

Bit6

Bit5

Bit4

Bit3

Bit2

Bit1

Bit0

0

1

0

0

0

1

0

1

0

0

1

1

1

0

1

0

按照：

其中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=0，CP1=0，CP2=1，CP3=1，CP4=1，CP5=1；

数据变化后，CP0=0，CP1=1，CP2=0，CP3=1，CP4=0，CP5=1；

当Bit1发生变化时，列校验值中只有CP1，CP2，CP4发生了变化，而CP0，CP3，CP5没变化，也就是说6个Bit校验码有一半发生变化，则求异或的结果中有一半为1。

*数据变化前，RP0=1, RP1=1*；

*数据变化后，RP0=1, RP1=0*；

同理，行校验求异或的结果也有一半为1。这就是为什么前面说256字节数据中的一个Bit位发生变化时，新旧22Bit校验码求异或的结果中会有11个Bit 位为1。

再来看怎么定位出错的Bit位？

以列地址为例，若CP5发生变化（异或后的CP5=1），则出错处肯定在Bit 4~Bit 7中；若CP5无变化（异或后的CP5=0）,则出错处在Bit0~Bit3中，这样就筛选掉了一半的Bit位。剩下的4个Bit位中，再看CP3是否发生变化，又选出2个Bit位。剩下的2Bit位中再看CP1是否发生变化，则最终可定位1个出错的Bit位。

转载：全栈芯片工程师