ECC纠错算法.doc

《ECC纠错算法.doc》由会员分享，可在线阅读，更多相关《ECC纠错算法.doc（40页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、前段时间，由于工作需要，学习了ECC校验与纠错算法（主要用于NAND FLASH中）。下面的文章是我转自chinaunix论坛的，略有点点的改动（由于图比较多，我就不上传了，有需要的朋友，可以到原帖上面看）。主要的ECC算法，我看懂了，但是其中有个问题一直搞不懂，一直也没有得到高手指点，故贴下来。还望等待高手指点。具体转自地址： Nand ECC校验和纠错 详解(转)ECC的全称是Error Checking and Correction，是一种用于Nand的差错检测和修正算法。如果操作时序和电路稳定性不存在问题的话，NAND Flash出错的时候一般不会造成整个Block或是Page不能读取

2、或是全部出错，而是整个Page（例如512Bytes）中只有一个或几个bit出错。ECC能纠正1个比特错误和检测2个比特错误，而且计算速度很快，但对1比特以上的错误无法纠正，对2比特以上的错误不保证能检测。校验码生成算法：ECC校验每次对256字节的数据进行操作，包含列校验和行校验。对每个待校验的Bit位求异或，若结果为0，则表明含有偶数个1；若结果为1，则表明含有奇数个1。列校验规则如表1所示。256字节数据形成256行、8列的矩阵，矩阵每个元素表示一个Bit位。其中CP0 CP5 为六个Bit位，表示Column Parity（列极性），CP0为第0、2、4、6列的极性，CP1为第1、3、

3、5、7列的极性，CP2为第0、1、4、5列的极性，CP3为第2、3、6、7列的极性，CP4为第0、1、2、3列的极性，CP5为第4、5、6、7列的极性。用公式表示就是：CP0=Bit0Bit2Bit4Bit6， 表示第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、7253、255 RP2-

4、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）RP4- 处理4个Byte，跳过4个Byte；RP5- 跳过4个Byte，处理4个Byte；RP6- 处理8个Byte，跳过8个ByteRP7- 跳过8个Byte，处理8个Byte；RP8- 处理16个Byte，跳过16个ByteRP9- 跳过16个Byte，处理16个Byte；RP10-处理32个Byte，跳过32个ByteRP11-跳过32个Byte，处理32个Byte；RP12-处理64个Byte，跳过64个ByteRP

5、13-跳过64个Byte，处理64个Byte；RP14-处理128个Byte，跳过128个ByteRP15-跳过128个Byte，处理128个Byte；可见，RP0 RP15 每个Bit位都是128个字节（也就是128行）即128*8=1024个Bit位求异或的结果。综上所述，对256字节的数据共生成了6个Bit的列校验结果，16个Bit的行校验结果，共22个Bit。在Nand中使用3个字节存放校验结果，多余的两个Bit位置1。存放次序如下表所示：以K9F1208为例，每个Page页包含512字节的数据区和16字节的OOB区。前256字节数据生成3字节ECC校验码，后256字节数据生成3字节E

6、CC校验码，共6字节ECC校验码存放在OOB区中，存放的位置为OOB区的第0、1、2和3、6、7字节。校验码生成算法的C语言实现在Linux内核中ECC校验算法所在的文件为drivers/mtd/nand/nand_ecc.c，其实现有新、旧两种，在2.6.27及更早的内核中使用的程序，从2.6.28开始已经不再使用，而换成了效率更高的程序。可以在Documentation/mtd/nand_ecc.txt 文件中找到对新程序的详细介绍。首先分析一下2.6.27内核中的ECC实现，源代码见:http:/lxr.linux.no/linux+v2.6.27/drivers/mtd/nand/na

7、nd_ecc.c/*Pre-calculated 256-way 1 byte column parity*/static const u_charnand_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,

8、 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, 0x

9、55, 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,

10、 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, 0x

11、66, 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,

12、 0x66, 0x33, 0x30, 0x65,0x00, 0x55, 0x56, 0x03, 0x59, 0x0c, 0x0f, 0x5a, 0x5a, 0x0f, 0x0c, 0x59, 0x03, 0x56, 0x55, 0x00;为了加快计算速度，程序中使用了一个预先计算好的列极性表。这个表中每一个元素都是unsigned char类型，表示8位二进制数。表中8位二进制数每位的含义：这个表的意思是：对0255这256个数，计算并存储每个数的列校验值和行校验值，以数作数组下标。比如 nand_ecc_precalc_table 13 存储13的列校验值和行校验值，13的二进制表示为 00

13、001101， 其CP0 = Bit0Bit2Bit4Bit6 = 0；CP1 = Bit1Bit3Bit5Bit7 = 1；CP2 = Bit0Bit1Bit4Bit5 = 1;CP3 = Bit2Bit3Bit6Bit7 = 0;CP4 = Bit0Bit1Bit2Bit3 = 1;CP5 = Bit4Bit5Bit6Bit7 = 0;其行极性RP = Bit0Bit1Bit2Bit3Bit4Bit5Bit6Bit7 = 1；则nand_ecc_precalc_table 13 处存储的值应该是 0101 0110，即0x56.注意，数组nand_ecc_precalc_table的下标其

14、实是我们要校验的一个字节数据。理解了这个表的含义，也就很容易写个程序生成这个表了。程序见附件中的 MakeEccTable.c文件。有了这个表，对单字节数据dat，可以直接查表 nand_ecc_precalc_table dat 得到 dat的行校验值和列校验值。 但是ECC实际要校验的是256字节的数据，需要进行256次查表，对得到的256个查表结果进行按位异或，最终结果的 Bit0 Bit5 即是256字节数据的 CP0 CP5./* Build up column parity */for(i = 0; i 256; i+) /* Get CP0 - CP5 from table */

15、idx = nand_ecc_precalc_table*dat+;reg1 = (idx & 0x3f);/这里省略了一些，后面会介绍Reg1在这里，计算列极性的过程其实是先在一个字节数据的内部计算CP0 CP5, 每个字节都计算完后再与其它字节的计算结果求异或。而表1中是先对一列Bit0求异或，再去异或一列Bit2。 这两种只是计算顺序不同，结果是一致的。 因为异或运算的顺序是可交换的。行极性的计算要复杂一些。nand_ecc_precalc_table 表中的 Bit6 已经保存了每个单字节数的行极性值。对于待校验的256字节数据，分别查表，如果其行极性为1，则记录该数据所在的行索引（也

16、就是for循环的i值），这里的行索引是很重要的，因为RP0 RP15 的计算都是跟行索引紧密相关的，如RP0只计算偶数行，RP1只计算奇数行，等等。/* Build up column parity */for(i = 0; i 1) & 0x55) = 0x55 &(s1 (s1 1) & 0x55) = 0x55 &(s2 (s2 1) & 0x54) = 0x54) 。这个判断的作用应该就是，判断s0s1s2中是否共有11个Bit位为1？我就看不明白，为什么判断这s0s1s2是否有11个1，上面的if条件就可以判断出来？里面有什么玄机呢？望高手指点，呵呵！40 作呵，手，？机习么里断以

17、件 面与 有是算0断（什，看我于 共 断是 应的。）) =的 文 ) 转 & = 自点手等。来点高得也懂搞一有是，我算 主看原可朋需，上我较于（的略论 & (& = 0 )0 ( :断判下 面， _ _ 错有里 码 ）错 -个的节 （地， 出个（ 行先法.位的出 。以，位一 示 ，位 共/ 如 存 节三结得异 _ ._ 话段面 。就的 /-/ / / /./ /错 个位 ,用， 位便 ， ， 或抽 用验时 数错 这。 知 取化发 校同出 表 / 子验的比地列 位可 转转， 取中异们样。半需以的。定称 相一 跟 ，一跟 是 则 ，= 有必 因 信冗 里其呢 用，为 中后或指 算节字、和、的 放中

18、 放验 字 验 成字 ， 节 数 前 的 的 含页 ，例 ：表序存。 余，校字用中 结校的 ，验 个成据节字，述。的求 = 行 也字个是 0，见 个 理 个过- 跳 - ； ， 跳- 个跳 - 处 - 过 个 -0 理 过 - 跳 - ； 理 个 - 过 个处-；个处 过- 个过 - 个理 跳 、 、- 过， 理（ .、 0- 、 - 极的 、 、为 ）极 示， 十为 图验类 。或 个0 实 这或 每列列 或位个 后异 部0表 0 是表公。列、 极的、为，列、 性、 0 极列 第 ，的、为 ，列 示位 为 0其位个素个阵阵、 形节字。 规验个有表则为若数含则果，求 验待。行校列操行节 对校 ：

19、码检保错以比正纠错以 快速且误比测误比 纠。 几只 如 个而出是读不 整会般候出 ，在性路序操果正和差 于用图决的的定 言 程过判展清 结的 。 的核 定则 变发 再算中 下在位 出化为生 看， 剩 位的了 筛这中 /在出 , 的或变 若中 其 现肯出）、 异变 在 为列以 出 定及来为 中或求0 _ _ / /. ./: _ + + /. . : * - / / / . / 见， 内 .析首绍详新找件 ._ / 。高率换，不已 从的中核 新，,发 个的节 ,前为这 为有也,或校理 一中或异0变 半有 说，化0 ，,0而变 发 ， 0中 列化生, 当，行第 在结 异求旧0。后行 表在 值 ,新

20、到， 变由 的 0就 , 变位数 在设,据始一第0在0的 计中表验校） , , , 0 , , , , 0 , 0 , 0 , 0 0 , , 0 0制 ）,00为进（ ，,节为的 设。妙,这索例简 以 0范址列 , 0 , , , 0 0 , , , 0 , , , 0 , , 00, 错表 则余 位的 , , 中取是方 址,） 范（节 , 0 ,0, , , , , ,0错就 的 , 四 为, , 中 四高 0 , , 抽，, ,为地，的 地定。 错 一中0该,即地， 出个即行 确是 的比出。 以误比0一示,，为 中 ,0，中 ,存分 三结，0位 按 _ 表式， 的, , 0 0 , 0

21、, 0 0 , , , 计保 _ _ ，验的 存 _ 误正法出表情；0 0 , , 0 00 , , 区 表位个 0果 结个；纠 误比一0表为比 存 结异个,误的无 现 是,在示则果，0异验 和 原读, 。校新称 , , , , , 0 , 0 , , , 00, 00 0, , ,000, , , , ,00 , 0 , ,0, 和校 个生 字 候据读0 从,中据 0 到验校为，0校 个我, 每时的写 的 算 何知时，反0 , , 00 0 , , 了 进， , _ , ,_ _ _ , /. 0/ ,/ 中。个的 , , , , , , , , , 后 两两 在 抽 + /. /: + /

22、 . : 0 +. + ./: / *等，算 行偶只如关紧行是的 0为的重索里）的循是也引在该记 极其表别节 的校值行节个了已 中 一复性。换序算异因致是，序是种。 异或0 对中而或结的它与完节每 内的节在实的极，这 绍面一了这/)0 _ . / = = + + / ; _ = /. + / ./: * _ _ _ + .+ / / = _ + . : * - ) = / + / 0 _ + /. * 0的字 是 果最或行表 得表 需的 校实 验校校的 得 _ 接以 节对个. 的见序表成程易也，个解。数字验们实的 _ 数意. 0 0 应值 ； 极其 = = ; = = 0 00制二 校和验的

23、如标数作值校校数储算数 ：意个的每制中。进二表 都个表。表的先个用程度计加; 0 , ,0, 0, , 0 00, , , , 0 , , , , , , , , , 0 , 0 出 中 - 。序 一新重 这把 的照是的。 算 都 0和 位的， 循 个表查 一此 示下的 * * 0 /. /: _ = /. + / + = / . / * _ _ = .+ . . : /. / 个 ， 个有表数有， 的; . . . / ./ = = / ; _ +/ . / +. / = = / )0& = + . : -理-解个行围 范 于 奇 个有表 -少行围算 于个奇 数示表 的 由-少行内计 于个有

24、 个偶， 的 -少有围算 属数有 数表示 -多行范 于奇示个有示，行 引只 ，为 引行 ；为 引算只 行为 引算 的 的计 ，的为的索计 ； 行计 ， 索计 行 行计 ， 的计 行 的行计 的 的行 的行计 的 引计 ； 的索算 行0 索算 律下以表， 0值取的循 （行始并量型 都 ， 运 -的-多的判算 比属；有为示数有个表示 跟 -位-少行内计数 没属数有系，个示果示0 数 由-则-多的范结0 为属行为如有到所数有围计 落，数行0 的， 校有表0 的 数的位判用，按后取引的验行， 所表用 每 ，；有表数有，示 由-个行内算 于有示个偶，示 的 -少行围计 于数 数有0 -个有围计 属个数 ，有，指 -个行内计 属数示 数表， 由-多的内 于数有 偶示示 的 -个有内算 ；数表个示， -少行内算 属个有表数有，指 -多有围 于，的验行所是用算按索的行有 第程。 的 数