【适合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 本文为全文原貌 未安装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浏览器用户请先下载安装 原版全文