焦新泉，武慧军，单彦虎，秦菲

（中北大学电子测试技术国家重点实验室，太原030051）

0 引 言

随着目前武器系统和航天系统对发射或飞行过程中的环境参数数据量需求越来越大，NAND FLASH以其小体积、大容量、低成本、擦除次数多、保存寿命长等优点，被广泛应用到固态记录设备中［1］，但是由于其生产工艺方面的缺陷或受空间辐射等影响，在数据存储和传输过程中位翻转的几率很大，优秀的数据校验方法可以极大地提高数据存储的可靠性。传统的汉明校验方法硬件实现占用的逻辑资源小，并可以提供1bit的纠错能力，对于SLC类型Nand Flash汉明校验法是一种性价比非常高的纠错方法，但是随着目前MLC类型Nand Flash的发展和SLC类型的Nand Flash容量的提高，汉明校验仍然存在诸多缺陷，比如相对较差的编码效率，编码后的信息码总量较大，对校验位数目要求不合理，且纠错位数有限等严重影响了数据存储的可靠性。

为此国内外研究学者提出了很多改进校验方法，其中有代表性的有LPDC、RS和BCH校验算法。LPDC编码是一种逼近Shannon理论极限优异性能的纠错码，但是由于构造难、分析难、实现难很长时间内未能得到很好的发展；RS码适用于连续数据位纠错（如大数据块或整个硬盘失效时的数据恢复）；与之相比BCH码更适用于Nand Flash的随机错误纠错，且校验码更短，存储利用率更高，自1959年提出以来，因其在短码纠错方面的优异表现被得到大力发展。其中较为先进的且具有代表性的算法有文献［2］提出的一种基于5bit纠错的非流水BCH编／译码器结构，其采用特殊指令的微控制器实现，缺点是硬件开销大且译码时间长；文献［3］设计了一种带流水结构的4bit纠错的BCH编／译码器，由于采用按页预取的译码方式，较前一种结构译码速度提升了很多，但译码时间依然很长；文献［4］提出一种可配置的多比特纠错控制器结构，可选用不同的纠错算法，提升了译码效率，但是实现多种算法带来了巨大的硬件开销。本文设计了一种（4200，4096，8）的BCH码ECC校验方法，减少了编码器中线性反馈移位寄存器电路的高扇出瓶颈，译码器方面对伴随式求解模块和钱氏搜索模块采用并行处理方式，节省了8倍的译码时间，采用二级流水线分块译码极大地提高了译码效率，是一种可靠高效的校验方法。

1 Flash闪存结构

数据校验的编译码需要对FLASH闪存结构有深入的研究，它的内部结构决定了码元的长度及纠错的位数，NAND Flash是以页为最小存储单元的存储阵列，传统闪存的页面大小一般为512 B目前闪存的容量以经扩展到4 KB甚至8 KB（都为512 B的倍数）本文以某公司的MT29F128G08AJAAAWP为例，其单片存储容量为16 GB，每页包含8KB的数据存储区和448 B的数据备用区，其内部的组织形式［5］如图1所示。所以以512 B为一组数据编码可同时满足不同页容量NAND Flash的ECC需求。

图1 Nand Flash内部结构Fig.1 Internal structure of the Nand Flash memory

2 ECC校验方法

2.1 BCH并行编码

BCH编码是一种线性分组码，其结构是建立在有限域多项式基础上的，特别是将多项式特性和纠错能力联系起来，使得这一类码具有较强的纠错能力。BCH码能针对随机发生的错误位进行纠错，特别适合硬件实现，该编码方式极大的提高了数据的可靠性。

在有限域 GF（2m）中，满足 n＝k+mt，n≤2m-1。其中n为码长，k为信息位长度，t为可纠错位长。GF（2m）域中纠错能力为 t的生成多项式为 g（x）＝m1（x）m3（x）…m2t-1（x），其中 mi（x）为本原元 ai的最小多项式，BCH编码是由信息位计算得到校验和，信息位和校验和共同组成一组BCH码，其码型格式如图2所示。

设k位信息码多项式为m（x）＝mk-1xk-1+…mk-2xk-2+…+m1x1+m0。

n位BCH码多项式为c（x）＝cn-1xn-1+cn-2xn-2+… +c1x1+c0c（x）＝m（x）xn-k+Rem（m（x）xnk）g（x）其中 Rem（m（x）xn-k）g（x）为 m（x）xn-k对g（x）取余。

图2 BCH码型格式Fig.2 BCH code format

根据多项式除法电路中线性反馈寄存器原理，可以得到T+1时刻和T时刻移位寄存器中的数据与T+1时刻信息码码元输入之间的关系［6］。

矩阵表示为：

上述关系可简化成R（T+1）＝F×（R（T）+m（T+1）），然后扩展为单字节并行输入后寄存器R（T+8）和当前R（T）和8位信息数据之间的关系为R（T+8）＝F8×R（T）+F8×m（T+1）+F7×m（T+2）+…+F×m（T+8）。

基于MT29F128G08AJAAAWP型NAND Flash本文设计一种（4 200，4 096，8）的校验码，m＝13，k＝4 096，t＝8该码是（8 191，8 087，8）的缩短码，其本原多项式m1（x）＝x13+x4+x3+x+1。利用 Matlab迭代运算求得其生成多项式g（x）＝x104+x100+x98+x96+x95+x94+x93+x92+x91+x88+x84+x82+x79+x78+x77+x70+x69+x68+x67+x65+x64+x59+x58+x52+x49+x48+x47+x42+x41+x40+x38+x32+x31+x30+x26+x24+x23+x22+x18+x15+x14+x13+x12+x11+x9+x8+x5+x+1。

按字节编码的关键组件如图3所示，最终移位寄存器中的值为生成的BCH校验码。

图3 字节编码关键组件Fig.3 Key component of byte coding

2.2 BCH译码方法

译码对数据的读取速度至关重要，设计高吞吐率的译码器非常关键［7］。译码过程通常分为伴随式求解、错误位置多项式求解、钱氏搜索电路设计。

（1）伴随式求解

设发送码字的多项式c（x）＝cn-1xn-1+cn-2xn-2+…+c1x1+c0

接收码字的多项式r（x）＝rn-1xn-1+rn-2xn-2+…+r1x1+r0

则 r（x）＝c（x）+e（x），其中 e（x）为错误多项式。

BCH码的生成多项式g（x）必定含有2t个连续幂次的根，设 a、a2、…、a2t是 GF（2m）有限域上生成多项式 g（x）的根，伴随式多项式 Si＝r（ai），若 Si＝0则接收码无比特错误，否则：

Si＝r（ai）＝rn-1（ai）n-1+rn-2（ai）n-2+...+r1（ai）1+r0＝（r0（ai）0+r1（ai）1+… +r7（ai）7）（ai）0+（r8（ai）0+r9（ai）1+… +r15（ai）7）（ai）8+...+（rn-8（ai）0+rn-7（ai）1+...+rn-1（ai）7）（ai）n-8并行伴随式求解电路如图4所示。

图4 伴随式求解电路Fig.4 Adjoint solution circuit

（2）错误位置多项式求解

由上述求解可知伴随式 Si＝r（ai）＝c（ai）+e（ai）＝e（ai）＝e1（ai）1+e2（ai）2+… +et（ai）t，令xt＝at，表示错误位置，则 Si＝e1（x1）i+e2（x2）i+…+et（xt）i，该式计算 t个未知数的 2t个方程比较困难，因此引入错误多项式 σ（x）＝（1+e1x1x）（1+e2x2x）…（1+etxtx）＝1+σ1x1+σ2x2+… +σtxt。

可知：

无求逆BM算法，是在经典BM算法的基础上，简化迭代次数，替代逆元求解运算，简化后的无求逆BM算法迭代运算与传统的BM迭代算法［8］类似，是目前应用最多且最高效的的求解算法。

认为w（x）是求解错误值多项式σ（x）的关键方程。

错误位置多项式系数的硬件求解电路如图5所示，起始是 R寄存器中的值为（S1，0，0，0，…0），σ和k寄存器中的值为（1，0，0...0），dq的值设为 1，每个时钟并行输入两位Si，放入R0，R1中，并将R寄存器中的内容隔级右移位，达到迭代次数后，σ寄存器中的内容即是错误位置多项式的系数。

图5 错误位置多项式系数求解电路Fig.5 Error position polynomial coefficient solution circuit

（3）钱氏搜索电路设计

钱氏搜索电路的主体思想是穷举法求错误位置多项式 σ（x）的根，设 an-1的倒数是 σ（x）的根，则σ（a-（n-1））＝0＝1+σ1a+σ2a2+… +σvav，译码器通过计算 σ1a，σ2a2，…，σvav，将他们相加求和，结果若为-1，则接收码元中错误位置的那一位发生错误，通过对接收码元的每一位进行验证来查找错误位置，最终求得错误多项式e（x）。

本文设计为（4 200，4 096，8）的码元，该码元为（8 191，8 087，8）的缩短码，在缩短码前添加3 991个0，为缩短搜索范围，搜索只对有效数据进行搜索［9］。搜索起点设置为a3991，为优化搜索速率采用8 bit并行搜索，搜索时间只需525个时钟周期。对Chien搜索电路的寄存器进行初始化，由搜索起点设置为3 991，当i的幂的数值大于 8 191，i的值变为 i对8 191取余，所以它的初始值分别为 σ1a3191，σ2a7982，…，σ8a7355，搜索电路如图6所示。

图6 钱氏搜索电路Fig.6 Chien search circuit

3 ECC校验过程及FPGA验证

BCH编译码的最终目的是对flash读写操作过程中进行错误位的纠正。

数据校验模块功能框图如图7所示。由四个部分组成，分别为主控模块、BCH编码模块、BCH译码模块、纠错模块。在对flash进行读操作时，主控模块使能译码模块，译码模块中的伴随式求解模块判断读出的数据是否有错，如果检查出错，则通过错误位置多项式求解模块、和钱氏搜索模块找到位翻转的位置，最后到纠错模块进行纠错。

图7 ECC校验模块Fig.7 Verification module of ECC

当向Flash存储数据时，每512 B数据字节产生的13 B校验码依次存放。根据Nand Flash的结构特点，备用区通常不用来存放数据信息，但它的内部结构与数据存储一样，这样可以将一页划分为8块，编码过程可以理解为运算后对Flash的写入过程，计算主要是逻辑运算和移位运算这里不再赘述，在读取过程中可以连续读出525 B字节的信息数据，然后进行译码，这样即避免了读地址之间来回切换，这种分块译码的方法保证了各块之间的相互独立，对他们的读取和译码可采用流水线的方式来操作如图8所示。通过计算采用流水线结构的译码过程可以缩减译码时间，极大的提升了整个译码的效率，译码流程如图9所示。

图8 流水线结构Fig.8 Pipeline structure

此次验证以某公司XC6SLX150芯片为硬件平台，用每组512 B自加数（数据从00～FB，两个字节的帧计数，EB90为帧尾，每两帧组成一组信息码）进行数据验证［10］，使读取数据”8F”H时出现错误，将第5位和第4位出现位翻转，读出的数据变为”BF”H，用传统汉明码校验仿真波形如图10所示，ecc_old_code为存储一组数据时产生的校验码，ecc_new_code为读取一组数据时产生的校验码，若读取数据没有错误，两组校验码的值应完全一样。简化运算后为当 ECC_result（ECC_result＝ECC_old_result xor ECC_new_result）为全‘0’时证明存入的数据和读出的数据无错误，若为全‘1’，证明发生了一位错误，其他值为两位错误，对于两位以上的错误则不能检测。由仿真结果可以看出 ecc_result＝”011 000 000 000”，证明出现两位错误，但汉明校验的算法并不能确定错误位置，因此不能对其纠错。图11为应用BCH校验的仿真，data_in为Nand Flash阵列读出来的数据，data_final为纠错模块输出的数据，当数据字节的sum1为全‘0’则代表第7位发生了错误，验证实验为从“8F”H翻转成“BF”H，第5位和第4位出现翻转，因此sum4和sum3变为了全‘0’。大数据量验证后用上位机读取数据并解包校验，结果如图12所示。

图9 译码流程Fig.9 Decoding process

图10 数据写入和读出仿真Fig.10 Simulation about data read

图11 BCH译码Fig.11 Decoding of BCH

图12 测试结果Fig.12 Test result

4 结束语

本文论述了一种适用于NAND闪存控制器的ECC校验方法，该方法具有随机纠错多位的能力。该校验结构采用模块化的设计思路，利用并行编码译码方法，充分考虑到了速度与面积的折中，可以实现对当前主流NAND闪存的基本操作，并保证在预定纠错能力范围内的可靠存取，目前该方法已成功应用于某航天数据记录设备，经试验证明该校验方法可以实现数据的可靠存储与回收，具有一定的参考价值。