基于BCH码的快闪存储器控制器设计BCH

《基于BCH码的快闪存储器控制器设计BCH》由会员分享，可在线阅读，更多相关《基于BCH码的快闪存储器控制器设计BCH（57页珍藏版）》请在装配图网上搜索。

1、毕 业 论 文（设 计）论文（设计）题目： 快闪存储器控制器设计姓 名 学 号 学 院 专 业 年 级 指引教师 5 月 4 日目录目录1摘要3Abstract4第1章 引言51.1 快闪存储器简介51.2 闪存中的纠错码（ECC）技术51.3 论文的研究内容与组织构造6第2章 ECC整体设计82.1 ECC简介82.2 功能规定82.3 本章总结10第3章 BCH码113.1 伽罗华域113.2 BCH码的编码133.3 BCH码的解码163.3.1 随着式的求解措施163.3.2 错误位置多项式的高速求解法183.3.3 全并行钱氏搜索机203.4 本章总结21第4章 BCH编解码器的设计

2、234.1 BCH编码器234.2 BCH解码器254.2.1 随着式计算模块264.2.2 错误位置多项式计算模块284.2.3 钱氏搜索机314.3 ECC模块的验证324.4 本章总结33第5章 总结35谢辞36参照文献37附录A 英文翻译原文39附录 B 译文48摘要论文对于 flash存储器控制器的设计，重要是针对于其中的错误检查与纠错（ECC）模块.ECC模块是存储器控制器的核心模块，重要对输入和输出数据进行编解码并纠正其中的错误。本论文中的ECC模块重要采用了BCH（15，7，2）码。对于编码采用了线性反馈电路移位寄存器的措施，对于解码采用了三个模块：随着式计算模块、错误位置多项

3、式模块和钱氏搜索机。BCH码以其较强的纠错能力和构造以便的长处，在无线寻呼和无线数据通信中被广泛应用。运用单片机用软件的措施实现BCH（15，7，2）码的ECC模块诸多资料都已经简介。但由于采用单片机以软件的措施实现，其译码器具有速度慢、系统稳定性差等缺陷，本论文简介了采用FPGA设计的采用BCH(15,7,2)码的ECC模块。先对ECC模块进行VHDL代码的编写，然后运用ALTERA的QUARTUS II集成开发环境进行了综合、仿真。采用硬件的措施实现的ECC模块具有速度快、性能稳定以及易于大规模集成等长处。核心词：快闪存储器控制器；ECC模块；BCH码；FPGA；AbstractThis

4、thesis mainly introduced the module of the error correction code(ECC), which is the most important module in the flash controller. The module of ECC can accomplish the event that encode the data-in and decode the data-out and correct the error data. The module of ECC use the BCH(15,7,2) code in this

5、 thesis. For the encode, the module of linear feedback shift register can make it work. For the decode, it has three modules: finding polynomials, finding the coefficient of the error locator polynomial and chien. Because of its strong ability of correcting errors and convenient construction ,the BC

6、H code is widely used in the radio paging and Wireless data communication. Much material has introduced the way of accomplishing the BCH(15,7,2) code using the MCU in the software. Because the way of accomplishing the code of BCH(15,7,2) using the MCU in the software is very slow and the stability o

7、f the system is bad ,this thesis introduced the BCH(15，7，2) code in the module of ECC designed by FPGA. Firstly, we write the code of VHDL of the module of the ECC, then we will accomplish the synthesis and verification and so on. The advantage of using hardware to accomplish the module of ECC is th

8、e fast speed and good stability and easy large-scale integration and so on.Keywords: flash controller ; ECC ; BCH code ; FPGA第1章 引言1.1 快闪存储器简介在当今数字技术飞速发展的时代，flash因其非易失性和可擦除性，以及具有更小的体积、更快的写入和擦除速度、更多的可擦除次数以及更低廉的每比特价格等特点得到了迅速发展，在数码相机、手机、移动存储卡、掌上电脑和MP3播放器等设备中得到广泛的使用。随着flash单片存储容量的不断提高和目前flash擦写速度的不断提高，数

9、据存储与读取的可靠性变得越来越低，迫切需要一种实时、高速的技术对flash中存储和读取的数据进行纠错以保证数据的可靠性。在flash的差错类型设计中错误是以位的形式分散在整个数据块中的，因此具有可控、随机错误纠错能力的BCH码合用于flash的纠错。目前大部分flash的PER为，为使PER低于这个行业安全原则，需要的纠错能力为15 bit左右。因此必须提高编码译码器的纠错能力。1.2 闪存中的纠错码（ECC）技术ECC校验是一种内存纠错技术，它是目前比较先进的内存错误检查和改正手段。ECC是“Error Checking and Correcting”的简写，中文名称是“错误检查和纠正”。E

10、CC是一种可以实现“错误检查和纠正”的技术，ECC内存就是应用了这种技术的内存，一般多应用在服务器及图形工作站上，这将使整个电脑系统在工作时更加趋于安全稳定。在ECC技术浮现此前，内存中应用最多的是奇偶校验（Parity）。但Parity有个缺陷，当内存查到某个数据有错误时，并不一定能拟定在哪一种位，也就不一定能修正错误，因此带有奇偶校验的内存的重要功能仅仅是“发现错误”，并能纠正部分简朴的错误。Parity内存是通过在本来数据位的基本上增长一种数据位来检查目前8位数据的对的性，但随着数据位的增长Parity用来检查的数据位也成倍增长，就是说当数据位为16位时它需要增长2位用于检查，当数据位为

11、32位时则需增长4位，依此类推。特别是当数据量非常大时，数据出错的几率也就越大，对于只能纠正简朴错误的奇偶检查的措施就显得力不从心了，因此浮现了一种新的错误检查与纠正（ECC）技术，这种技术也是在本来的数据位上外加校验位来实现的。不同的是两者增长的措施不同样，这也就导致了两者的重要功能不同样。它与Parity不同的是如果数据位是8位，则需要增长5位来进行ECC错误检查和纠正，数据位每增长一倍，ECC只增长一位检查位，也就是说当数据位为16位时ECC位为6位，32位时ECC位为7位，数据位为64位时ECC位为8位，依此类推，数据位每增长一倍，ECC位只增长一位。总之，在内存中ECC可以容许错误，

12、并可以将错误改正，使系统得以持续正常的操作，不致因错误而中断，且ECC具有自动改正的能力。 1.3 论文的研究内容与组织构造随着快闪存储器工艺技术的不断进步，快闪存储器单元的可靠性严重下降，因此通过设计措施提高系统的可靠性变得更加严重。纠错码作为一种可以有效提高系统可靠性的技术，虽然广发应用于通信系统中，但快闪存储器在数据存储过程中产生错误的机制与通信系统在数据传播过程中产生错误的机制并不同，因而两者的错误率特点有着明显的差别。随着快闪存储器的不断使用，错误比特率呈现出单调递增的趋势。快闪存储器中的纠错系统必须采用硬件实现。快闪存储器的随机访问时间短，对解码器的解码延迟，数据吞吐量等指标有着非

13、常苛刻的规定，ECC有更强的纠错性能和动态可调节的能力。论文的后续章节就应用于快闪存储器控制器中的ECC模块进行了进一步的分析和研究。采用了BCH(15,7,2)码，可对7位的信息码纠正2比特的错误，生成15位的码字。第1章是引言。第2章重要简介整个ECC模块的顶层原理图设计，简介顶层模块的构成以及各个底层模块在顶层模块中的位置和作用。第3章重要简介ECC模块中BCH编解码器的原理和相应的运算。第4章重要简介ECC模块中BCH编解码器的电路构造设计，对于编码器采用了线性反馈移位寄存器的措施，避免了复杂的除法运算。对于解码器采用了三级流水线的措施，先对解码器的三个模块：随着式计算模块、错误位置多

14、项式计算模块和钱氏搜索机进行设计，再将三个模块与编码器进行连接，并进行了仿真验证。其中，随着式计算模块采用了线性反馈移位寄存器的措施；错误位置多项式计算模块采用了基于PETERSON矩阵的直接求解法，整个电路有AND和XOR逻辑实现，设计简朴，速度高；钱氏搜索机采用了全并行的措施，由XOR树实现，提高了速度。第5章为本论文的总结。 第2章 ECC整体设计2.1 ECC简介 ECC第一次提出是在1948年Claude Shannon的论文“A Mathematical Theory of Communication ” 中，通过几十年的发展，ECC技术目前已广发应用于通信系统、无线应用、光盘存储

15、等领域。ECC技术的原理是：向原始的信息数据中添加冗余位，进行编码；对接受到的信息，运用冗余位可以找出接受信息中的错误位置，并进行纠正，从而恢复原始的存储数据，这个过程也称为解码。纠错码一般分为两大类：线性码和卷积码。线性码的特点是进行数据解决的单位是码字（codeword）,码字是具有固定长度的信息块。一种n位线性码的码字是由原始的k位信息加上相应的冗余位构成，如图2.1所示。此外，对于线性码，码字中每位信息受到的噪声互相独立，因此码字中的错误具有随机性的特点。相反，卷积码是将信息数据当作持续的比特流，因而卷积进行数据解决的单位是比特。在存储系统中，存储器以码字为单位进行数据的写入和读取操作

16、的，因而采用线性码实现存储系统的纠错。本论文所关注的是线性码在快闪存储器控制器中的应用。本论文所采用的BCH码就是线性码的一种。 图2.1 ECC码字的构成2.2 功能规定应用于快闪存储器中的ECC模块重要由编码器和解码器两部分构成。本论文中的ECC技术采用了BCH(15,7,2)码。BCH（15，7，2）码实现对7位的信息码字进行2位的纠错，生成8位的校验码。将7位的数据写入到闪存时，一方面编码器产生相应的冗余位，形成一种15位的码字。读取时，解码器搜索码字中的错误，并在其纠错能力范畴内纠正相应的错误，从而恢复对的的数据信息，输出7位的信息码。论文中的ECC整体设计如图2.2所示。图2.2

17、快闪存储器控制器的ECC系统编码器重要对输入信息进行编码，对输入的7比特信息位按照BCH码的原则增长8比特的校验位构成一种15比特的码字，具有2比特的纠错能力。编码器采用线性反馈移位寄存器的措施实现，实现数据的串行输入和串行输出。对数据进行编码之后，当输出数据时，需要先进行解码和纠错。BCH解码器可以实现解码和纠错的功能。本论文中的BCH解码器涉及三个模块：随着式计算模块，错误位置多项式系数计算模块和钱氏搜索机模块。随着式模块的作用是通过接受码字和校验矩阵来计算随着式S,随着式也是采用线性反馈移位寄存器的措施实现，实现对数据的串行输入和串行输出。由于错误位置多项式系数采用的是并行输入，而它的输

18、入是随着式模块的输出，因此在随着式模块和错误位置多项式模块之间加了一种串并转换电路。实现了端口的匹配。错误位置多项式系数采用了直接求解法，整个电路有AND和XOR逻辑构成，编码简朴，易于实现。错误位置多项式系数模块的输入是随着式模块的输出经串并转换电路后的输出，使用的是并行输入和并行输出。解码部分的最后一种模块式钱氏搜索机。本论文采用了全并行的措施实现钱氏搜索。钱氏搜索机的作用是寻找错误位置多项式的根，便于拟定错误的位置并纠正码字中的错误。钱氏搜索模块是由XOR逻辑实现的。2.3 本章总结本章简介了快闪存储器控制器的ECC模块的顶层电路设计。简介了ECC的构成和ECC的各模块的功能和在ECC中

19、的位置。简介了各个模块的实现措施和中间转换电路。第3章 BCH码二进制BCH码是建立在伽罗华域(Galois field, GF)的基本上的，本章将具体论述BCH码编解码的原理。3.1 伽罗华域闪存中存储的数据信息均为二进制数，因而应用在闪存中的BCH码为二进制BCH码。二进制BCH码建立在伽罗华域(GF)的基本上。伽罗华域是有限域，因Evariste Galois 一方面发明而得名，其数学理论广泛的应用在纠错码系统、密码系统中。下面一方面简介伽罗华域的有关理论。伽罗华域是有限域，其数学理论属于群论范畴。伽罗华域有如下性质：（1） 伽罗华域具有有限性。伽罗华域中有有限个元素。（2） 伽罗华域具

20、有封闭性。伽罗华域定义了“加”和“乘”两种操作。将域中任意两个元素进行相加或相乘的成果仍然是这个域中的元素，其中，域中有一种零元素“0”，对域中的任意元素,有；域中有一种单位元素 “1”，对域中任意元素，有。（3） 伽罗华域具有可逆性。对于域中的任意元素，存在可逆的逆加元素，使得；存在可逆的逆乘元素，使得。（4） 伽罗华域满足结合律，互换律和分派律。结合律：；互换律： ；分派律：；闪存中存储的数据为二进制数，因此应用于闪存中的纠错码技术均基于阶伽罗华域，其中为伽罗华域的度(degree)，这时伽罗华域可以表达为。是的扩域，是最简朴的有限域，只有两个元素，其上的加法和乘法就是布尔加法和布尔乘法。

21、即 表3.1 中的加法和乘法运算 + 0 1 0 1 0 0 1 0 0 0 1 1 0 1 0 1共有个元素。中存在一种称为本原域元素的，使得构成伽罗华域中的所有个非零个元素。其中 定义3.1：对于，如果满足，则称为伽罗华域的本原元。定义3.2：表达一组多项式的集合，其中多项式的系数为中的元素。成果多项式除了常数和自身外，不能再被其她多项式除尽，则称多项式为不可约多项式。定义3.3： 对于最高次幂为的不可约多项式，若是的因子，并且的最小值为，则称为上的本原多项式。定义3.4：中任一元素的最小多项式定义为以该元素为根的具有最小阶数的多项式。的本原多项式是本原域元素的最小多项式。通过上述的定义可

22、以看出，为的根，即。令 ，由于上的减法操作等同于加法操作，可以得到：，该式表白，对于伽罗华域中的任何一种元素()，可以转换为一种最高次幂不超过的多项式。因此伽罗华域中的元素可以有三种表达形式：指数形式，多项式形式，以及由多项式各项系数构成的二进制矢量体现式。作为例子，表3.2中给出上某些元素的三种体现方式。对于，本原多项式为。 表3.2 上元素不同的体现方式指数形式二进制形式多项式形式00001010003.2 BCH码的编码BCH码是循环码的一种重要子类，它具有纠多种错误的能力，BCH码有严密的代数理论，是目前研究的最透彻的一类码。BCH 码是1959 年由Hocquenghem、1960

23、年由Bose和Chandhari 分别独立提出的。BCH码是纠正多种随机错误的循环码，可以用生成多项式的根来描述。 给定任一有限域及其扩域， 其中是素数或素数的幂， 为某一正整数。 若码元取自上的一循环码，它的生成多项式的根集合中具有如下个持续根：1、 时， 则由生成的循环码称为进制BCH码。 设和分别是()元素的最小多项式和级， 则BCH码的生成多项式和码长分别是： (3.1) (3.2) 其中为的最小多项式，LCM表达最小公倍数 (least common multiple)。 如果生成多项式的根中，有一种中的本原域元素， 则， 称这种码长的BCH码为本原BCH码；否则，称为非本原BCH码

24、。 中元素的级一定是的因子，因此非本原BCH码的码长也一定是的因子。二进制BCH码是建立在域上的，加法可以用异或表达，除法可以用移位表达。BCH(n，k, t)码的定义如下：码字长度： 数据的长度： 校验信息的长度： 纠错能力： 所有不不小于或等于位错误的状况。有些状况下实际应用中的信息数据长度并不正好等于BCH（n, k，t）码定义中的信息数据长度。例如，在快闪存储器中一般信息个数为而根据上述BCH码的定义所计算出的,在这种状况下，可以使用缩短的BCH码。所谓缩短的BCH码，是指在BCH(n, k, t)码的码字中使最高位的个信息位均置为0，这样传播时就可以不用送它们，只要传递背面的位码字即

25、可，这样构成了一种（,）的码，称为BCH的缩短码。需要指出的是BCH缩短码有着与BCH码同样的纠错能力，均为,即BCH(n-p, k-p, t)。此外，BCH码属于循环码。循环码是线性码的一种重要子类，顾名思义，循环码的码字具有循环的特性。其循环特性使它的编码算法变得比较简朴，编码电路也易于实现。对于二进制BCH码，和的最小多项式相似，因此式（3.1）可以写成如式(3.3)的形式： (3.3)由于最小多项式的最高次幂为,因此生成多项式的最高次幂为.同步BCH码为循环码，因此对于任何BCH码的码字，都是的倍式，即。假设BCH的信息数据为，其相应的多项式为；相应的生成多项式为：；码字为，则码字多项

26、式可以表达为 （3.4） 式中。显然的最高次幂不不小于，通过移项上式可以变为：。其实就是BCH码中的冗余位多项式。此外，在伽罗华域中，减法操作等同于加法操作，将等式两边同除以，可以得到计算的体现式： (3.5) 因此BCH(15,7，2)码的编码的产生环节为：(1) 将信息多项式预乘;(2) 将除以,得余式，此余式就是编码需要得到的校验位多项式;(3) 得到循环码的码字多项式为的形式。由上述BCH（15，7，2）码编码的产生过程可以看出：构造一种BCH（15，7，2）码的核心是要找出该码的生成多项式。当码长及纠错能力给定后可以用MATLAB求出生成多项式。下面是求解生成多项式的MATLAB代码

27、： Gen_gf=bchgenpoly(15,7).3.3 BCH码的解码3.3.1 随着式的求解措施如前所述，BCH码的生成多项式是个最小多项式的乘积，因而具有个持续幂次的根：。而BCH码的码字又是生成多项式的倍式，因此码字也是这些持续幂次的根，即： for (3.6)写成矩阵的形式为： (3.7) 其中H定义为BCH码的检查矩阵，为码字矢量。设接受到的码字多项式为：，则BCH码随着式S的定义如下： (3.8)如果个随着式均为零，则阐明接受到的码字没有错误，反之，则阐明接受到的码字中有错误。此外，随着式S还可以通过此外一种措施获得：先用相应的最小多项式除接受到的码字多项式： for (3.9

28、)再根据最小多项式的定义，可以得到，将上式移项带入后得： for (3.10)可以看出，对于随着式的每一种分量，式(3.8)和(3.10)的体现式一致，因此两种措施均可以用来计算随着式。此外，对于式(3.9)求解随着式的运算与BCH编码的体现式(3.5) 有着相似的数学体现式，都需要多项式的除法运算。因此硬件实现也有着相似的电路构造，在电路中均采用线性反馈移位寄存器构造实现。本论文中求解BCH(15,7,2)码的随着式，采用的是式(3.9)，即通过线性反馈移位寄存器的措施来求得随着式S。但是硬件实现与式(3.5)不同。BCH编码是先将输入量乘以因子进行除法取余操作，而随着式的产生是直接将接受量

29、进行除法取余操作。这在电路实现上反映出的差别是前者电路的输入端与最高位的寄存器进行相加后形成反馈信号，并连接到最低位的寄存器上，而后者电路的输入端则是与最低位的寄存器相加后形成反馈信号。最后寄存器中的内容就是随着式的值。由于BCH码是二进制BCH码，因而偶数项的随着式等于前项随着式的平方，即。因此可以减少计算量和复杂度。上述BCH(15,7,2)是建立在伽罗华域上的，最小多项式可以用 MATLAB生成，其中产生最小多项式的代码为：m=4,t=2;x=gf(2,m);for i=1:2 :(2*t-1)minpol_gf=minpol(xi);end；得到，。3.3.2 错误位置多项式的高速求解

30、法BCH解码中的错误位置多项式为： (3.11)错误位置多项式的个根就是码字中错误位置的倒数。错误位置多项式的系数与随着式分量之间的关系有下列牛顿恒等式给出： (3.12) 该步的任务就是通过上述牛顿恒等式，计算出的各项系数。1960年Peterson初次提出了通过矩阵运算求解多项式系数的措施，然而由于需要计算矩阵的逆运算，实现较为复杂。1966年Berlekamp提出了采用迭代运算求解多项式系数的措施，1969年Massey将此算法进行了简化，使其实现比较简朴，成为了出名的B-M(Berlekamp-Massey)算法。该算法的核心思想是：先给出最低次多项式，让其系数满足第一种牛顿恒等式；在

31、检查与否满足第二个牛顿恒等式，若不满足，则向中添加一种修正项构成，以满足第二个牛顿恒等式；反之则使，迭代过程始终进行下去，直到得到为止。B-M算法中需规定逆运算，而求逆运算的硬件实现较为复杂，为了便于硬件实现，后来者对Berlekamp迭代算法进行了相应的改善，并提出了免求逆的运算，目前较为广泛的是RiBM(Reformulated Inversionless B-M)算法，RiBM算法具有硬件实现时单元构造有较好的规则性的长处。 本论文中的BCH(15,7,2)码的错误位置多项式的体现式，如下： （3.13） 一般求解错误位置多项式的系数的措施是采用RiBM算法。RiBM算法的核心思想是将本

32、次时钟周期计算出的值与上一种时钟周期的值进行比较，根据比较的成果决定下一种时钟周期体现式系数的值，这样通过2t个时钟周期的迭代，最后计算出核心方程系数的值。显然，这种RiBM算法，不适于闪存高速解码的规定，因此，我们提出了一种直接求解法来计算错误位置多项式的系数。直接求解法的数学理论源于Peterson矩阵。Peterson矩阵是Peterson于1960年提出的矩阵求解错误位置多项式系数的措施，Peterson矩阵的体现式为式(3.14)，可以看出，求解需要用到矩阵的逆运算，并且随着纠错位数t的增长，矩阵运算复杂度急剧增长，因此实际应用中的BCH码译码时没有采用Peterson矩阵的措施。

33、(3.14)然而，对于t=2的BCH（15,7,2）码，Peterson矩阵的变量很少，因此一种可行的措施是根据矩阵方程直接求解出系数、的值。采用这种直接求解法时，求解出的核心系数和的体现式为 (3.15) 因此，错误位置多项式的体现式为 (3.16) 可见，通过采用直接求解法，避免了老式RiBM算法的迭代过程，然而上述体现式中仍然存在着伽罗华域的除法运算，除法运算的硬件复杂度高、延迟大。为了进一步减少解码的延迟，需要通过对的的且合适的变换消除伽罗华域的除法运算。 有文献证明，对于任意的BCH码，如果码字中存在错误，则有，因此可以将上述等式的两边同步乘以系数，从而消除了伽罗华域的除法运算，生成

34、的新体现式为 ： (3.17) BCH解码的最后一步钱氏搜索是在伽罗华域中寻找错误位置多项式的根，也就是满足的。显然，当, 同样也有，因此错误位置多项式通过消除除法的变换后与变换前有着相似的根，也就是仍搜索到相似的错误位置，从而保证了消除除法变换的对的性。在伽罗华域上，每个随着式矢量都可以表达到相相应的多项式的形式： 根据伽罗华域的封闭性，可以求出系数，如下： (3.18) (3.19) （3.20） 可以看出，上述的系数计算体现式中只涉及了模2的加法运算和模2的乘法运算，而模2的加法运算和乘法运算可以分别用XOR逻辑和AND逻辑实现。因此，对于应用于t=2的BCH（15,7,2）码，采用直接

35、求解法计算错误位置多项式的系数时，消除了老式RiBM算法的迭代运算及伽罗华域复杂的除法运算，使最后可以用组合逻辑电路中的XOR和AND逻辑就可以实现多项式系数的求解，最后实现了高速的系数求解。3.3.3 全并行钱氏搜索机BCH解码的最后一步就是寻找错误位置。错误位置多项式的根就是错误位置的倒数。然而，工程上实现的求解伽罗华域的多项式的根非常困难。1964年华裔科学家钱闻天了易于工程实现的求解根的措施。其思想是将求解错误位置多项式的根转化为检查错误位置多项式的根。将伽罗华域的元素()依次带入到错误位置多项式中，如果该元素是的根，即存在，那么就可以找到码字中的一种错误，错误位置为，这种措施称为钱氏

36、搜索（Chien search），已成为BCH解码过程中寻找错误位置多项式的最常用的措施。钱氏搜索机的运营过程如下：对接受到的码字多项式，先检查第一位比特是不是有错误，也就是检查与否为的根，即 如果，则比特为错误的比特，否则该比特对的。由于钱氏搜索的措施是从第一位比特开始检测，始终遍历到整个码字空间，因此具有逐位译出，先译先出的特点。这一特点也使得BCH译码的过程可以采用三级流水线的措施实现，从而明显的提高了译码器的吞吐率，通过钱氏搜索机寻找出码字中的所有错误用矢量表达，将与接受到的矢量相加，便完毕了BCH的译码。下面针对于BCH(15,7,2)码，对钱氏搜索机做一简介。对于BCH(15,7,

37、2)码，计算出错误位置多项式的系数之后，就进入钱氏搜索。钱氏搜索通过在伽罗华域中搜寻多项式的根来拟定错误位置，体现式如下： for (3.21)假设通过搜索发现，那么就是错误的位置。3.4 本章总结本章一方面简介了伽罗华域的基本概念和相应的理论，接着简介了BCH码编码的原理和编码的实现环节。对于BCH码解码，采用了三级流水线的形式，因此分别简介了随着式计算的原理和措施、错误位置多项式的高速求解的措施和并行钱氏搜索机的措施。第4章 BCH编解码器的设计本章将论述BCH码编码器的设计，采用了线性反馈移位寄存器（linear feedback shift register）的电路构造来实现串行BCH

38、(15,7,2)码编码器的设计。论文中ECC模块的BCH(15,7,2)码解码器的设计采用了三级流水线的措施，解码分三个模块：随着式模块、错误位置多项式模块、钱氏搜索模块。论文先对各个模块进行设计和VHDL代码的编写，仿真通过后，将解码器与编码器连接起来，实现总的功能。运用这种措施实现编解码，运算程序大为简化，具有解码速度快，硬件实现复杂度低等特点。4.1 BCH编码器BCH码的编码可以用硬件实现也可以用软件实现，硬件实现法速度快，合用于实时解决，但是需要反复实验，制作周期长；用软件实现，可以运用计算机模拟，节省时间，提高效率，但是运营速度慢，需要寻找最佳算法进行最优化。BCH码是线性循环码的

39、一种，其编码方式和一般的循环码编码方式相似，容易实现的方式是将信息码多项式升次幂后除以生成多项式，然后将所得余式置于升幂后的信息多项式之后，即采用式(3.5)的措施进行编码。 将生成多项式和信息码字带入式(3.5), 就可构造BCH(15,7，2)循环码的编码方式。求解需要伽罗华域的除法运算，除法电路一般是使用线性反馈移位寄存器来实现的。BCH(15,7，2)循环码编码器的电路构造如图4.1所示。 图4.1 BCH（15，7，2）码的编码器的电路构造图图中代表模2的相加，可以用异或门实现。第一步：当rst=1时，信息数据移入线路中，同步送出。信息从线路的前段移入等价于用乘信息多项式。当k位信息

40、数据所有移入线路，在寄存器中的个数据就够成了余项，因此它们就是校验码。第二步：移出校验码，并把它们送出。这个校验码与k个信息一起构成一种完整的数据码字。 BCH（15,7,2）码编码器电路模块涉及输入数据data_in,输出数据data_out,控制信号rst,时钟信号clk和除法电路五部分构成。当rst=1时，实现对数据的编码，rst=0时实现复位。BCH(15,7,2)的电路框图如图4.2所示。 图4.2 BCH（15，7，2）码的编码器的电路框图电路的工作方式如下：先使得控制信号rst=1，反馈回路开始工作，每个时钟周期串行输入1位的信息data_in，这样通过8个时钟周期，各寄存器的值

41、就是BCH码字的冗余位，此时变化控制信号，令rst=0,再通过n-k个时钟周期就可以输出冗余位，这样就生成BCH(15,7,2)码的一种长度为15的码字。对于BCH(15,7,2)码，输入0011001，通过编码后输出110，运用ALTERA的QUARTUSII软件对BCH(15,7,2)码编码器的进行时序仿真，成果如图4.3所示。 图4.3 BCH(15,7,2)码编码器的时序仿真成果 对于BCH(15,7,2)码,输入信息位0011000，通过编码后输出111，运用ALTERA的QUARTUSII软件对BCH(15,7,2)码编码器的时序进行仿真，成果如图4.4所示： 图4.4 BCH(1

42、5,7,2)码编码器的时序仿真成果以上仿真成果看出，第2到8个时钟周期输出的是信息码，第9到16个时钟输出的校验码，实现了串行输入和串行输出。4.2 BCH解码器论文采用了三级流水线的措施进行BCH(15,7,2)码的解码码，解码分三个模块：随着式模块、错误位置多项式模块、钱氏搜索模块。4.2.1 随着式计算模块根据上一章的简介，随着式的求解措施有两种。一种是基于矩阵的运算，一种是除法运算。除法运算可以采用线性反馈移位寄存器的措施来实现，简朴，复杂度低。因此本论文的随着式的求解是用线性反馈移位寄存器实现的。DDDDd_inrst 根据式(3.9)，采用线性反馈移位寄存器的措施来构建BCH(15

43、,7,2)码随着式产生器，电路构造图如图4.5所示。a. 随着式S1产生器的电路构造图DDDDd_inrstb. 随着式S3产生器的电路构造图图4.5 随着式产生器的电路构造图开始时4级移位寄存器中的寄存数据所有清零；接着输入接受的码字，同步输出，通过16个周期后，寄存器内的数据就是错误位置多项式；最后通过移位，再通过4个周期，随着式的值被移出。随着式产生器模块涉及输入数据data_in,事实上是编码器的输出，时钟信号clk, 控制信号rst, 输出数据data_out和除法电路五部分,当rst=0时实现复位，当rst=1时，由输入15位信息，求出随着式S，模块构造如图4.6。 图4.6 随着

44、式S1产生器的电路模块图 图4.7 随着式S3产生器的电路模块图电路的工作方式如下：先使得控制信号rst=1，反馈回路开始工作，每个时钟周期串行输入1位的输入信息data_in，这样通过16个时钟周期，各寄存器的值就是随着式的值，此时变化控制信号，令rst=0,再通过4个周期就可以输出随着式。对于图4.3中的输出序列110，随着式为：0000，运用ALTERA的QUARTUSII软件对BCH(15,7,2)码的随着式产生器的时序进行仿真，成果如图4.8所示。 (S1)( S3)图4.8 BCH(15,7,2)码的随着式产生器的时序仿真成果从图4.8看出，第2到第16个周期输出的是编码器编码后的

45、码字，即编码器的输出，第17到第20个周期输出的是随着式。4.2.2 错误位置多项式计算模块对于BCH（15，7，2）码，m=4，在伽罗华域上，使用上一章简介的直接求解法，根据式(3.18)，(3.19),(3.20),可以得到系数的RTL级电路图，如图4.9所示，该电路基本上是用XOR和AND逻辑实现了求解错误位置多项式的功能。 图4.9 BCH（15，7，2）码中错误位置多项式系数的电路实现错误位置多项式模块涉及输入数据, 实际是随着式产生器模块的输出data_out1、data_out3，时钟信号clk, 控制信号rst， 输出数据data_out 。当rst=0时实现复位，当rst=1

46、时，由输入的4位信息，求出错误位置多项式的系数。内部电路由XOR和AND逻辑实现。BCH(15,7,2)码中错误位置多项式系数的模块图如图4.10所示。图4.10 BCH（15，7，2）码中错误位置多项式系数的模块图电路的工作方式如下：当rst=1时，并行输入,在时钟上升沿时输出错误位置多项式的系数。设随着式=1010,=0110,输出是1010，1000，1001，则运用ALTERA的QUARTUSII软件对BCH(15,7,2)码错误位置多项式模块的时序仿真成果如图4.11所示图4.11 BCH(15,7,2)码错误位置多项式模块的时序仿真成果从图4.11可以看出，对于给定的通过大概18n

47、s后开始得到对的的。4.2.3 钱氏搜索机一般采用反馈寄存器的电路实现方式实现钱氏搜索，这需要较多的时钟周期才干完毕，为了满足闪存对高速解码的规定，本论文中将钱氏搜索进行了并行化，采用了全并行的钱氏搜索的实现措施，其电路构造为全并行的XOR-树构成的组合逻辑。先计算至这15个多项式中各项的成果，通过求和计算后输出，将求和成果与相应的码字进行异或，即在一种时钟周期内完毕了码字的纠错。全并行钱氏搜索机的电路模块涉及输入data_in ,实际是编码器输出的数据，复位rst,时钟信号clk,错误位置多项式的系数d0、d1、d2和纠错后的输出data_out七部分，如图4.12所示。 图4.12 全并行

48、钱氏搜索机的电路模块图当rst=0时，实现复位，模块的输出为零；当rst=1时，实现对输入数据进行XOR 和AND逻辑运算后，输出成果，及最后解码并纠错后的成果。运用ALTERA的QUARTUS软件对BCH(15,7,2)码钱氏搜索机模块的时序仿真成果如图4.12所示 图4.12 BCH(15,7,2)码钱氏搜索机模块的时序仿真成果4.3 ECC模块的验证第三章和本章前几种章节简介了BCH（15，7，2）码的编码和解码的措施和相应的电路设计。本节重要完毕这两个模块的总的设计，实现数据的编解码。一方面，将各个模块进行连接，在时序上进行统一。由于错误位置多项式的系数模块和钱氏搜索模块的输入是并行输

49、入，而与此相应的相应的随着式模块和编码模块的输出是串行输出，因此一方面通过移位寄存器进行了串并的转换，再将相应的端口进行相连。快闪存储器控制器中的ECC的各模块设计完毕后，将各模块连接成一种顶层模块，如图 4.13所示。 图4.13 ECC顶层模块原理图 对整个模块进行验证： 输入码字：0011001 通过大概103.5ns后，输出解码后的码字：001101 仿真成果如图4.14所示： 图4.14 顶层模块仿真成果 从仿真成果可以看出：最后输出理解码后的码字：0011001.4.4 本章总结论文简介的BCH(15,7,2)码编码器是运用线性反馈移位寄存器的措施实现的，采用了串行输入和串行输出的

50、方式。然后写出相应的VHDL代码，生成了相应的模块图，并在FPGA上进行了仿真。论文中的解码措施与原先的查找表措施不同，解码器分为三个模块：解随着计算式、解错误位置多项式计算模块和钱氏搜索机。其中，随着式计算模块采用了线性反馈移位寄存器电路实现，解错误位置多项式计算模块采用了基于Peterson矩阵的直接求解法实现，钱氏搜索机采用了全并行的措施实现。求解随着式，一方面规定解最小多项式，最小多项式可以由MATLAB自动求出；直接求法求解错误位置多项式的系数只用AND和XOR逻辑，避免了迭代运算，消除了伽罗华域的除法运算，最后实现了高速的系数求解；求解错误位置多项式的根，采用了全并行的措施，提高理

51、解码速度。本章先对BCH码编解码器的各个模块进行设计，接着给出了相应的电路模块图，并进行了相应的仿真成果。第5章 总结随着快闪存储器存储单元尺寸不断缩小、存储容量不断增长、以及多电平技术的广发使用，快闪存储器的存储单元发生错误的概率越来越大，因此必须加强快闪存储器控制器的纠错能力和纠错速度。本论文对于 flash存储器控制器的设计，重要是针对于其中的错误检查与纠错（ECC）模块.ECC模块是存储器控制器的核心模块，重要实现对输入和输出数据进行编解码、纠正数据的错误。一方面，论文的每一章节，先对编解码的基本知识进行简介，然后对相应的模块做出了设计，并进行了仿真和验证。对于BCH（15，7，2）码

52、，编码采用了线性反馈移位寄存器的措施，避免了老式措施中的除法运算，简朴易实现，实现了串行数据的输入和串行数据的输出；解码采用了三级流水线操作，分三个模块：随着式模块，错误位置多项式模块和钱氏搜索模块。其中随着式模块也是采用了线性反馈移位寄存器的措施，错误位置多形式模块没有采用老式的RIBM算法，而是采用了直接求解的算法，由XOR 和 AND逻辑实现，设计简朴，提高了速度，钱氏搜索采用了全并行的措施，其电路构造为全并行的XOR-树构成的组合逻辑，在一种时钟周期内完毕了码字的纠错，大大提高了速度。论文中的设计，采用了模块化的手法，先对各模块进行设计，最后将各模块连接起来，在时序上进行统一，形成一种

53、顶层模块。并对每一种模块和顶层模块进行了仿真，得到了预期的仿真成果。谢辞本研究作为我的毕业论文是在专家精心指引和大力支持下完毕的，她渊博的知识、开阔的视野和敏锐的思维给了我深深的启迪，论文凝结着她的汗水。王专家以其严谨求实的治学态度、孜孜以求的敬业精神和大胆创新的进取精神深深感染了我，对我此后的工作和学习也产生了深远影响，在此，我要向她表达衷心的感谢。 此外，本论文在选题及整个研究过程中还得到本专业研究生三年级学生秦盼学姐的悉心指引，她们多次询问论文进程，帮我开拓思路，为我指点迷津，精心点拨，热忱鼓励，为我完毕这篇论文提供了巨大的协助。 最后，要向我的爸爸、妈妈道谢！“父兮生我，母兮鞠我，拊我

54、蓄我，长我育我，顾我复我，出入腹我，欲报之德，昊天罔极”，十月怀胎生我，含辛茹苦养我，长大又教我勤奋尽责、正直做人，这生我、养我、教我之恩，纵有三生我也无以回报！毕业后还要读研，又要远离你们了，我在心中默默祈祷：但愿你们可以平安，健康。目前，通过几种月的努力，我终于完毕了我的毕业设计，这篇论文就是我的成果。在这个过程中，我要特别感谢我的导师王祖强教师，感谢她的悉心指引，感谢她给我的协助和支持，谢谢！参照文献1 Liu W, Rho J, Sung W. Low-power high-throughput BCH error correction VLSI design for multi-le

55、vel cell NAND flash memories. Proc. IEEE workshop on Signal Processing Systems Design and Implementation,:303-308.2 Duann N. Error correcting techniques for future NAND flash memory in SSD applications Proceedings of Flash Memoty Summit,.3 Vigoda B. Lyric error correction for flash memory. Proceedin

56、g of Flash Memory Sunnit,.4 Parhi K. K. Eliminating the Fan-out Bottleneck in Parallel long BCH Encoders, IEEE Trans. Circuits &Systems I,51:512-516.5 Choi H, Liu W, Sung W. et al, VLSI implementation of BCH error correction for multilevel cell NAND flash memory. IEEE Trans. Very Large Scale Integr

57、. (VLSI)Systems,18(5):843-847.5 王雪强. 快闪存储器的低压高可靠性技术研究博士学位论文. 北京： 清华大学微电子与纳电子研究所， .6 许锦.NAND FLASH 迅速BCH编解码算法及硬件实现研究生学位论文.上海：复旦大学电子与通信工程，.7 王杰，沈海滨.NAND Flash 控制器的BCH编/译码器设计.杭州：浙江大学超大规模集成电路设计研究所，.8 汪建国.BCH编译码器的设计及验证研究生学位论文.上海：上海交通大学电子信息与电气工程学院，.9 张军，王志功，胡庆生，肖洁.高速并行BCH(2184,2040)编码器的VLSI优化设计.南京：东南大学，.1

58、0胡江.基于FPGA的BCH(23,11)码编译码器的实现.宁波：浙江万里学院，.11孙延鹏，李轩，王丽.基于FPGA的BCH(31,21)码译码器的设计.沈阳：沈阳航空工业学院电子工程系，.12 陈志，黄世震，曾献君.BCH解码器面积优化的VLSI设计.福州：福州大学，.13陈宏铭，程玉华.多通道NAND闪存控制器的硬件实现.上海.北京大学上海微电子研究所.13魏韬.Flash控制芯片算法及软件设计.北京.北京工业大学微电子学与固体电子学.14Lin S, Costello D. J. Error Control Coding: Fundamentals and Applications, second edition. NJ: Prentice-Hall,1983.15李璐，周海燕.一种含BCH编解码器的SLC/MLC NAND FLASH 控制器的VLSI设计.南京：东南大学专用集成电路系统国家工程研究中心.16张宗橙.纠错码原理与应用M.北京：电子工业出版社，.17肖建.在SoC中实现NAND FLASH 控制器的一种措施J.电气电子教学学报，24(4):40-43.18张翌维，郑新建，沈绪榜.一种支持预搜索的面积紧凑型BCH并行译码电路.西安：西安微电子研究所.19张军，王志功，胡庆生，肖洁.高速Berlekamp-Ma