Hanming,RS,BCH —— NAND Flash中常用的纠错方式
因为闪存中会有出错的可能,如果没有使用ECC模块,读出的数据和写入的数据会有不匹配的可能,也许一个文件中只有一两个bit不匹配,这也是不能容忍的。相对来说SLC中出错概率比较低,所以使用一个纠错能力不强的Hanming码就可以了,在MLC中Hanming码就显得力不从心了,需要纠错能力更强的RS或者BCH纠错方式了。
Hanming码原理算法都不算复杂,网上应该都能找到hdl代码。
RS(Reed-Solomon)应用也非常广泛,按多位的组合编码,而BCH按位编码,比如在NAND Flash中某个字节应该是0x00,但是从NAND Flash读出却是0xf0; RS只认为出现了一个错误,而BCH却认为出现了4个错误。RS方式有着不错的突发随机错误和随机错误的能力,算是两者的折中。BCH擅长处理随机错误,由于NAND Flash自身的特点,出现随机错误的概率更大一些,所以在MLC中目前应用最多的还是BCH方式。
大家知道即使是校验错误如奇偶校验或者CRC校验都需要在原始信息数据的基础上增加一些额外的数据。能够纠正错误的ECC需要额外的数据空间保存纠错码生成的校验数据。所以在NAND Flash中Page的1K数据并不是1024Byte,大多数是1024+32Byte, 有的是更多的额外空间;额外空间越多意味着可以使用纠错能力越强的ECC,因为对于同一ECC算法纠错能力越强需要的额外空间越大。
对于BCH算法
目前通常以512Byte或者1024Byte为单位处理,因为BCH按位处理数据,所以是4096bit或者8192bit,这里的4096/8192bit是原始数据,BCH需要生成一定的校验数据。下面简要介绍下原理。
设最大纠错能力为t
如果选用4096bit的原始数据长度,则模式为BCH(8191,8191-13×t,t,13)
如果选用8192bit的原始数据长度,则模式为BCH(16383,16383-14×t,t,14)
校验数据长度就是13×t,或者14×tbit
所以平均1024+32Byte的MLC 大多建议使用8bit/512Byte ECC
平均1024+45Byte的MLC大多建议使用24Bit/1024Byte ECC, 此时需要14×24bit=42Byte的检验数据空间
以8bit/512Byte BCH方式的ECC为例,控制器写数据到NAND Flash时,每512Byte数据经过BCH模块就会生成13Byte的校验数据(当然剩下的16-13=3Byte也可以作为某种用途的数据,可以任意使用0-3Byte而不会改变ECC的使用),这些数据一起写入到NAND Flash中。控制器从NAND Flash中读取数据的时候需要将原始数据和校验数据一起读出经过BCH模块,BCH模块计算伴随矩阵首先可以判断出是否出现了错误,如果出现了错误需要计算错误位置多项式,然后解多项式,得到错误位置(目前主要使用Chien-search方法),因为是位错误,找到错误的位置以后取反以后就是正确的数据。只要是错误个数小于等于8,BCH都能够找到错误的位置,但是如果错误个数超过了8,对于BCH来说已经没有办法纠正错误了,只能报告出现了不可以纠正的情况。