一种优化的BCH编解码器的设计与实现∗

雷水艳 焦继业 陈亚南

（西安邮电大学电子工程学院 西安 710121）

1 引言

随着汽车电子技术的广泛应用，用于海量汽车数据存储的 NAND Flash［1］，因其自身缺点，在使用时会出现差错，这种差错主要来自两种情况:一是由于工艺原因在生产及使用过程中会产生坏块；二是由于存储单元问题使用时会发生位反转，以及空间环境的辐射也会导致位反转［2］。因此，如何纠错成为汽车电子NAND Flash可靠存储的关键问题。文献［3］中设计一种校正4位出错位的BCH编解码器，但校正位数较少。文献［4］中设计一种校正8位出错位的BCH编解码器，相比文献［3］校正位数有所增加，但还不能满足大容量存储的数据校正；文献［5］中设计一种校正32位出错位的BCH编解码器，其校正位数较多，但因为电路复杂度的增加，导致编解码速度降低。在此基础上，本文提出一种优化的BCH编解码器的设计，在保证编解码速度的同时，最高校正位数达到48位。

2 BCH编解码器整体设计

BCH码取自Bose、Ray-Chaudhuri与Hocquenghem的缩写［6～7］，是一种有限域中的线性分组码，具有纠正多个随机错误的能力，通常用于通信和存储领域中的纠错编码。定义如下:给定任意一个有限域GF(q)及其扩展域GF(qm)，其中q是素数或素数的幂，m为正整数，对于任意一个码元取自扩展域GF(qm)的循环码（n，k），其中 n=2m-1，其生成多项式 g(x)具有2t个连续的根为，则由生成多项式g(x)编码产生的循环码称为q进制的BCH码，记为（n，k，t）［8～9］。

本文使用MICRON NAND devices，页可配置为4KB+128B，并且每页又分为4个子页，即每个子页为1KB+32B，内部存储结构如图1。

图1 内部存储结构

校正一个出错位需要14个校验位，所以校正48个出错位需要48*14=672个校验位，由此可得该BCH码的参数为

1）码元长度:n=4*1024*8+672=33440bits

2）检验位长度:r=14*48=672bits

3）纠错能力:t=48bits

4）信息位长度:k=n-r=32768bits

其电路模块框图如图2。

图2 BCH算法模块框图

数据在写入NAND Flash时进行编码，生成校验位，编码完成后，将结果送入解码模块。在读取数据时进行解码，首先进入伴随式计算模块，完成伴随式的计算，然后将结果送入错误位置多项式模块，其次进入错误位置多项式模块，完成错误位置多项式系数的计算，然后将结果送入Chien搜索模块，最后进入Chien搜索模块，完成错误位置多项式根的计算，然后找到出错位，完成纠错。对于二进制BCH码，纠错就是对相应位进行取反操作［10］。

2.1 编码器设计

令信息位多项式为m(x)=m0x0+m1x1+…+mk-2xk-2+mk-1xk-1，假定生成多项式为 g(x)=g0x0+g1x1+…+gn-k-2xn-k-2+gn-k-1xn-k-1，则码字表达式如下:

可以看出，校验位是由-m(x)xr对g(x)求模得到，由于二进制BCH的码元都取自二元域GF（2），在二元域中减法操作等同于加法操作，因此码字表达式也可以写成下式:

BCH码的编码过程就是一次有限域的模乘运算 m(x)xrmod g(x)，可以利用LFSR 电路实现［11］。一般的串行LFSR电路，在每个时钟周期只能输入1位数据，对于数据端口为16位的NAND Flash存储器来说，这就意味着编码的速率只有数据端口速率的1/16，为了等待编码，数据写入的速率不得不降低到原来的1/16。因此，为了提高编码速度，将一般的串行LFSR电路改为16位并行，即在每个时钟周期可以输入16位数据，正好等于数据端口的速率，这样编码过程就与数据的写入完全同步，最后一个字节写入后，编码也随之结束如图3所示。

图3 并行化的线性反馈移位寄存器

2.2 解码器设计

解码模块包括三个子模块，分别是伴随式计算模块、错误位置多项式计算模块和Chien搜索模块［12］，在一次解码过程中，这三个子模块只能顺序执行，不能使用流水线操作。所以本设计采用把NAND Flash的每页都均匀的划分为四组子页的方法，使每组子页都有数据区和校验区，并且不同组的数据的解码过程没有任何联系，使得三个子模块可以采用3级流水线模式工作。第一级是伴随式计算模块，第二级是错误位置多项式计算模块，第三级是Chien搜索模块，这样提高了纠正速度。除此之外，在解码完成后，解码模块能够检测出错位是否被全部校正，以及出错位的数量是否超过了设计的校正能力。三级流水线结构如图4所示。

图4 三级流水线结构

2.2.1 伴随式计算

设解码模块接收到的信息多项式为

接收端接收到的码元多项式为

错误多项式为

则有:

设ai(i=0,1,2,…,2t)是生成多项式 g(x)的根，其中t为最大纠错位数，伴随式的计算就是将ai代入接收到的码元多项式R(x)中，求出R(ai)的值，si=R(ai)，若计算得到的si的值全部为0，则认为信息在传输过程中没有发生错误，否则为发生错误。由此可得伴随式多项式:

2.2.2 错误位置多项式计算

设错误位置多项式为

要求的就是错误位置多项式的系数ℴi（i=0，1…，t），而错误位置多项式ℴ(x)与伴随式多项式S(x)存在如下关系:

代入关键方程可得:

由上式可知，关键方程的奇次项系数都为0，偶次项系数未知，所以可将迭代次数减少为t次，把经过简化的伯利坎普-梅西算法称之为简化的无求逆伯利坎普-梅西算法，其迭代过程如下。

2）j=j+2 ，判断 dj是否等于0，若是则转3），否则转4）；

6）判断 j是否等于2t-2，是则终止迭代，否则转到2）继续迭代。

2.2.3 Chien搜索

上一步求出了错误位置多项式:

Chien搜索算法的基本思路是通过遍历的方法求解错误位置多项式的根，要确定第k位是否为出错位，只需将a-k代入ℴ(x)，然后判断ℴ(x)是否为0，若为0则证明第k位是出错位，否则，不是出错位。

3 设计仿真验证

用verilog语言完成BCH编解码电路的RTL级设计，并用Questasim完成仿真验证。编码模块主要完成校验位的计算，校验位为672位。伴随式计算模块主要完成伴随式的计算，伴随式为96组，每组为14位。错误位置多项式计算模块主要完成错误位置多项式系数的计算，Chien搜索模块主要完成错误位置多项式根的计算。仿真验证结果表明:在人为注入48位出错位后，电路可以正确地对所有出错位完成校正。

4 ASIC设计综合

使用SMIC 0.11μm工艺库，工艺角为tt，温度为25℃，借助Synopsys公司的DC工具完成电路综合，当工作频率为200MHz时，面积为716520μm2，功耗为479mW。性能比较如表1，可以看出本文设计的BCH编解码器数据容量最大，可校正位数最多，工作频率最高，功耗优于文献［14］，次于文献［13］。由于电路功耗主要来源于时钟单元、运算单元和存储单元，对于本设计而言，时钟频率高，运算复杂，存储容量大，所以电路功耗相对较大。

表1 性能比较

5 结语

本文在分析BCH编解码原理的基础上，提出一种优化的BCH编解码设计，用于汽车电子存储NAND Flash的校验，所设计的BCH编解码器最大可纠错48位，提高了NAND Flash中数据存储的可靠性。完成电路的功能仿真和DC综合，分析电路性能可知，优化后的设计在校正位数、工作频率和电路功耗方面都有很大的改善，为了得到更好的纠错性能，今后将会对算法做进一步的优化，平衡工作频率和电路功耗之间的关系，使得电路延时达到最小并且功耗最低。