适合NAND闪存控制器的BCH纠错编译码器VLSI实现

摘要：随着大容量MP3播放器、PMP播放器、数码相机、智能手机等消费电子产品的需求持续增长，MLC的NAND闪存已经取代SLC的NAND闪存成为市场主流。而存储容量的增大所带来良率与可靠性的下降，意味着我们需要纠错能力更强大的硬件编译码器来处理可能发生的错误。针对固态硬盘需要支持多通道的NAND闪存，纠错编译码器也要有能够处理并行I/O总线的能力，本文实现了可由软件配置、最大纠错能力t为可变的1~16 b的BCH纠错编译码器，在计算错误位置多项式的过程中使用了修正的欧几里德算法。

关键词：MLC；NAND；BCH

VLSI Implementation of BCH Codec for NAND Flash Controller

CHEN Hong-ming, CHENG Yu-hua

（Shanghai Research Institute of Microelectronics （SHRIME）, Peking University, Shanghai, 201203）

Abstract: Along with the increasing demand of mass storage in MP3 player, PMP player, Digital still camera, MLC NAND flash had replaced SLC NAND flash and become the main stream. The increasing storage capacity results in the decreasing of yield and reliability. It means that we need a powerful error correction hardwire codec to handle the possibility of error happened. The Error correction codec for multi-channel solid state disk need the capability to do parallel processing for parallel I/O. In this paper, we implemented the BCH codec with the error correction capability t vary from 1 to 16b which can be configurable by software. A modified version of the Euclidean Algorithms that is specifically adapted to the RS decoding error location.

Keywords: MLC; NAND; BCH

1引言

NAND闪存在工厂制作过程存在缺陷产生的可能性，特别是越先进的工艺导致储存单元的节距越来越近，漏电明显，甚至采用单位记忆储存单元的多位化（Multi-Bit per Cell）的结构导致的良率与可靠性的下降，或者是对其进行擦写操作时可能产生数据错误，资料写入也可能导致电性改变，以上所述在特性上就是随机发生的错误比特，所以在数据被读出来的时候我们需要确认数据是否与写入时是一致的。资料写入时需要编码器产生ECC奇偶（Parity）存在NAND闪存数据区域之外的冗余（Redundancy）区域，数据读出的时候再由译码器译码，确认接收的数据没有错误，或者已经被噪声所干扰了。如果确认数据有错误，还需要将错误位置找出后，把错误的“0”与“1”互换。MLC闪存增加比特密度也降低了每MB的单位成本，但高比特密度会造成性能下降以及耐用性（Endurance）变差。为了解决这些问题，我们需要纠错能力更强的编译码器才能享受到MLC闪存增加比特密度的好处。

纠错编码（FEC）主要分为分组码和卷积码两大类。1949年汉明（Hamming）提出了可纠正单个随机差错的汉明码是一种基本的“线性分组码”。循环码是线性分组码的最重要的一类码，它的结构完全建立在有限域多项式的基础上。1960年Hoopueghem、Bose和Chaudhum三人首先提出的一类循环码，这一类码具有较强的纠错能力。特别是它将多项式的特性与码字的纠错能力联系了起来，使设计者可以根据需要选择码字。Reed与Solomon又提出里德-所罗门误码校正编码，是BCH码的一个重要的子类，在q进制BCH码中，每个码元的取值在GF（q）上，而g（x）的根却在GF（q）的扩域GF（qm）上。如果码元取值的域和g（x）的根所在的域相同，则这类BCH码称为RS码，被使用在硬盘跟光盘上的突发错误。BCH码能针对随机发生的错误比特，而且特别合适硬件电路实现，在NAND闪存控制器的纠错编译码器普遍被作为首选，常用于提高NAND闪存存储系统的数据可靠性。

2应用规格与算法，结构

分组码是一种代数编码，一个码字包括独立的信息元和监督元，其监督元与信息元之间是一种代数关系，如果这种代数关系为线性的则称为线性分组码。分组码编码器的模型如图1所示。

[m]为编码器的输入，称为信息码元（信息位），它由k位码元组成。[C]为编码器的输出，称为码字矢量，它由n位码元组成，其中有k位信息元，r = n-k位监督元。对于二元编码来说，k位信息码元共有2k个不同组合，根据编码器一一对应关系，输出的码字矢量也应当有2k种码字。对于长度为n的二元序列来说，共有2n个可能的码字矢量，编码器只是在这2n个可能码矢中选择2k个码字，被选中的2k个n-重称为许用码字，其余的2n-2k个码字称为禁用码字，称这2k个码字矢量的集合为（n, k）分组码。根据所要纠错的NAND闪存规格制定出我们要实现的BCH编译码器规格如表１。

图2说明面向字节（Byte-oriented） BCH编码的脉动阵列示意图。脉动阵列能够有效地解决NAND闪存并行I/O总线所需要的并行BCH纠错能力，还保证了提供大纠错能力为16比特的设计。

脉动阵列是由处理组件组成，处理组件的输出out是由gi与r1, r2, d等输入通过&（与门）以及^（异或门）设计而成。

3.2 BCH译码器设计

BCH译码器针对从NAND闪存读数据出来时，针对纠错奇偶计算错误症状。译码器工作流程说明如图3，里面包括了三个子模块，分别是计算错误症状模块，计算错误位置多项式模块以及钱式搜索模块，而n级移位存储器是用来根据译码器执行纠错步骤的延迟来缓冲接收码字。

3.2.1计算错误症状模块

接收码字多项式R（x）是发送码字多项式C（x）和差错多项式E（x）之和，即：

R（x） = C（x） + E（x）

BCH译码首先由生成错误症状多项式S（x）开始，也就是要求出其2t个伴随式Si，单个计算错误症状模块的算法如下:

从（3-11）式我们得到2t个未知数（t个错误值跟t个位置）），还有不能够用一般方法解出的2t个同时发生的非线性多项式。我们考虑两种最常用的算法为伯利坎普一梅西算法BMA （Berlekamp-Massey Algorithm）[3]和修正的欧几里德算法MEA （Modified Euclidean Algorithm）[4,5,6]。BMA算法有最低的电路复杂度[7]，而MEA算法的优点在规律性的脉动阵列设计[8]能够缩短关键路径致使电路速度加快。因为先进工艺下门数不再是问题，译码的吞吐量才是关键。因此本文在“计算错误位置多项式模块”的硬件实现中选了“MEA”算法来增加译码的速度。MEA算法是一种递归的技巧，在两个多项式中找出最大公约数。错误位置多项式

本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文

根据上述算法整理出修正的欧几里德算法流程如图7所示，如果degA>degB的话，U与L需要互换，这里采用比较器来实现。这个算法主要是ωU，ωL，σU，σL四个多项式的运算，直到degB

图8说明MEA处理单元模块，单元模块的主要功能是实现（3-11）式，目标是增加吞吐量以及减少延迟。因此设计里包含了一个加法器和两个乘法器。算法里的“交换”就是电路里复用器2, 3的选择信号。单元模块是O（2T），每个周期算法都能反复运作，造成了吞吐量以及延迟都是O（2T）周期。

3.2.3钱式搜索模块

传统的“串行Chien搜索”把寻找错误位置多项式σ（x）根的运算转化为验根计算，通过遍历GF（2m ） 域的所有元素做为输入值，通过“验根”的方法，从高位开始逐位输出校验是否为零，找出满足1=0的根αk，从而确定错误比特的发生位置为 ，这样很大程度上减少了计算量，简化了电路。因为不必等全部差错数验算完毕再译码输出，大大降低了译码延时。当发现错误后，该错误位将保存到相应的寄存器提取错误信息。并行的钱式搜索模块一般来说很占面积，甚至可能占到纠错电路65%的面积[10] ，上面提到的αk里的0 ≤ k ≤ （n-1）），所有的乘法器在第一个时钟周期选择σ（x），再选择后来寄存器的数据，因为求σ（x）的值有n个可能位置需要花费n个时钟周期来完成钱式搜索，为了加快这个步骤，我们使用了并行因子p的直接展开（unfolded）钱式搜索架构[11]，如图9所示，钱式搜索的硬件实现共有 （t+1） 阶段，每个阶段（图中红色虚线内由p个乘法器, 复用器和寄存器组成） 代表钱式搜索里每个不同的值。每个时钟周期表示一个不同的t 值, 加法器的输出σ（αpi）用来检查是否为零，如果为零的话，侦测零模块会输出”1”, 否则就输出”0” ，如此一来钱式搜索的输出就是一个p比特带有”0”或”1”的字符串，每个“1 ”代表的位置有错误。对第一个周期，复用器会发送出错误位置多项式的系数σ1到加法器，其他（p - 1） 时钟周期，乘法器输出的值会经由复用器发送到加法器。在并行处理的帮助下，完成钱式搜索的时钟周期数目从n降到了[n/p]，P又称钱式搜索展开因子。

3.2.4执行周期说明

我们实现了并行结构三级流水线BCH译码器时序图如图10所示，其中钱式搜索与纠错在第三个阶段同时执行。在整个码字接收后，错误症状立刻被计算再被放到下一个阶段，错误症状的计算需要512个时钟周期来完成，修正的欧几里德算法需要1122个时钟周期来完成，钱式搜索与纠错需要512个时钟周期来完成，在进行钱式搜索的同时可以进行下一帧数据的译码。利用Ping-Pong FIFO可以实现连续译码，执行译码时，先读取第1组BCH码的528 Bytes 数据存储在FIFO1中，错误症状计算和数据读取过程同时进行。当FIFO1装满后，开始读取第2组BCH 码的数据并存储在FIFO2中，与此同时MEA算法单元开始计算第1组BCH 码的错误位置多项式，然后交由钱式搜索电路完成对第1组BCH 码的搜索，并将FIFO1中的数据搬运到缓冲控制器的缓存中。因为错误症状计算过程和数据读取过程同时进行，所以因错误症状计算而给读操作带来的延时可以被隐藏。而第2组BCH码的错误症状计算和第1组BCH码的MEA运算以及钱式搜索过程重叠进行，即第1组BCH码的译码过程对整个数据读取操作的没有延时，只有最后一组BCH码的译码过程对整个数据读取操作带来一个MEA运算时间和钱式搜索时间的延时，总共为1634个时钟周期。

4仿真实验与结果分析

在Matlab软件中基于功能强大的Simulink平台，构建一个BCH编译码的系统仿真架构，用以产生BCH编码数据。randint 产生均匀分分布的乱数矩阵，randerr 产生位误码形。当执行测试代码，命令视窗会要求输入可纠错的值t，我们输入16，Matlab会制造1~10个错误场景来测试我们的算法，一开始会建构生成多项式，接着BCH编码器展开（unfolding），采用前述的面向字节BCH编码产生奇偶。然后对接受的信息码元译码，在编码得到的码字利用Matlab呼叫函数randerr加入随机错误，在1068个周期完成错误症状计算，在18~32个周期后完成MEA，在1052个周期完成钱式搜索，纠错后得到的码元与randint所产生的信息码元一致。

本设计使用XilinxXC4VLX100_FF1148 FPGA验证Verilog HDL编写的设计，MLC NAND 闪存芯片选用三星的K9L8G08U0M，K9HAG08U1M， K9HBG08U1M，K9G8G08U0M，K9L8G08U0M，K9LA G08U0M，K9F8G08U0M等七种，SLC NAND闪存芯片选用三星的K9KAG08U0M，经过实测，在规范要求内的多种错误比特引入都可以成功纠正，当超过规范要求时会通过信号变化显示纠错失败，在正常读写情况下可保证数据无误传输，我们将编译码器放入NAND闪存控制器如图11所示。

使用Synopsys的Design Compiler针对0.13μm工艺库综合后的报告表明，单通道配置，电路内部的时钟频率最高可以达到210 MHz，逻辑门数约49.8 k（不包含SRAM） 。针对固态硬盘的4个通道配置下时钟频率最高可以达到220 MHz，最大吞吐量在NAND闪存数据位宽8 比特时达到7.04 Gb/s，逻辑门数约121.3 k（不包含SRAM） 。表2列举了三级流水的BCH译码器和另外两种BCH译码器之间的性能比较，可以看出文献[13]所设计的BCH 译码器消耗的硬件面积最少，但是其译码时间开销却是本文译码器的1.69倍。特别是本文所能纠错的最大位数比另外两种BCH译码器高很多, 能刚好满足备用区大小208 b的条件。

纠错模块能够使用接口信号与缓冲控制器做数据交流，一旦一个2 k 数据包从闪存被读进来，纠错模块能够检查奇偶校验并且提供译码结果给缓冲控制器。如果结果正确，所读进来的数据就能够被送进AHB控制器的FIFO，否则的话纠错模块就纠正错误的比特。图12说明纠错模块纠正数据的时序，纠错模块拉高“e2b_req” 和“e2b_dir” 两个信号用以向缓冲控制器发送一个读请求, e2b_addr 信号是2 k数据包的条目索引，缓冲控制器响应“b2e_ack”信号并将所请求的数据放到b2e_data总线上。如果数据被纠正过, 纠错模块会拉高“e2b_req”信号将这些纠错过的数据包写进缓冲控制器内。在缓冲控制器内有两个两级的FIFO 来存放不正确的2K 数据包的地址，当“ecc_dec_cp” ，“ecc_dec_cp” 以及 “ecc_err_occur”等信号同时拉高，2 k 数据包的地址被送进FIFO。当“ecc_corr_cp” 信号拉高，表示纠错模块已经完成所有纠正的操作，2 k数据包的地址会从同一个FIFO被推出来。

5结束语

本文提出了一种适用于MLC NAND 闪存控制器的并行BCH编译码器结构，着重论述了其中纠错模块的BCH编译码器的实现。该电路实现采用优化的MEA算法求解错误位置多项式，规则化的脉动阵列电路结构和模块化的设计思路，通过采用分组预取译码的操作方式，尤其是在译码过程中引入三级流水操作，提高了BCH 码的译码效率。本研究提出的BCH译码器，在电路不变的情形下，最大纠错位数t是可变的，只需软件配置来改变设定值1~16即可，不必增加额外的电路面积。FPGA测试后证明功能无误，可以实现对当前主流MLC NAND 闪存的各种基本操作，并保证在设计预定纠错能力范围内的无误传输。今后将在此基础上进一步提高最大纠错位数到24位，采用IBM算法来缩短译码时钟周期，并探究在性能面积上的折衷。

本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文

参考文献

[1]Error Control Coding: Fundamentals and Appl- ications,Shu Lin, Daniel J. Costello Prentice Hall 1983 page 171

[2] Tong-Bi Pei and Charles Zukowski, High Speed Parallel CRC Circuit in VLSI[J]. IEEE Transactions on Communications, April 1992

[3] R.E. Blahut, "A Universal Reed-Solomon Decoder," IBM J. Research and Development, vol. 28, no. 2, pp. 150-158, Mar. 1984

[4] Hanho Lee, High-Speed VLSI Architecture for Parallel Reed-Solomon Decoder[J]．IEEE Transactions on VLSI system，2003，11（2）：288-294．

[5] H. M. Shao and I. S. Reed, On the VLSI Design of a Pipeline Reed-Solomon Decoder Using Systolic Arrays[J]．IEEE Transactions on Computer，1988，vol. 37, no. 10, pp. 1273-1280．

[6] H. H. Lee, M. L. Yu, and L. Song, “VLSI design of Reed-Solomon decoder architectures,” in Proc. IEEE Int. Symp. Circuits and Systems （ISCAS ’00）, vol. 5, pp. 705-708, Geneva, Switzerland, May 2000.

[7] I. Reed, M. Shih, and T. Truong, “VLSI design of inverse-free Berlekamp-Massey algorithm,” Proc. IEE, pt. E, vol. 138, pp. 295-298, Sept. 1991.

[8] R. P. Brent and H. T. Kung, “Systolic VLSI arrays for polynomial GCD computation,” IEEE Trans. Comput., vol. C-33, pp. 731-736, Aug. 1984.

[9] Reed-Solomon codes and their applications, edited by Stephen B Wicker and Vijay K Bhargava, IEEE Press, 1994. pages 205-241.

[10] L. Song, M.-L. Yu, and M. S. Shaffer, “10- and 40-Gb/s forward error correction devices for optical communications,” IEEE J. Solid-State Circuits, vol. 37, pp. 1565-1573, Nov. 2002

[11] Y. Chen and K. K. Parhi, “Small area parallel Chien search architectures for long BCH codes,” IEEE Trans. Very Large Scale Integr. （VLSI） Syst., vol. 12, no. 5, pp. 545-549, May 2004.

[12] Micheloni R, Ravasio R, Marelli A, et al. A 4Gb 2b/cell NAND Flash Memory with Embedded 5b BCH ECC for 36 MB/s System Read Throughput[C]//Proc. of 2006 IEEE International Solid-state Circuits Conference. San Jose, CA, USA: IEEE Press, 2006: 497-506.

[13] Wei Liu, Junrye Rho, Wonyong Sung. Low-power High-Throughput BCH Error Correction VLSI Design for Multi-level Cell NAND Flash Memories[C]//Proc. of 2006 IEEE Workshop on Signal Processing Systems Design and Implementation. Banff, Canada: IEEE Press, 2006: 303-308.

作者简介

陈宏铭，博士研究生，研究方向为SoC芯片设计。

程玉华，教授，北京大学上海微电子研究院。

注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文

本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文