CN102568607A - 一种优化的bch解码器 - Google Patents

Abstract

本发明提供闪存控制器中一种优化的BCH解码方法和装置，方法包括：读取闪存信息，存储到FIFO中，并且根据读取信息计算伴随子；关键方程求解，即根据伴随子利用迭代算法计算错误位置多项式；根据错误位置多项式通过钱搜索(Chien Search)验根决定错误位置；对错位位置上的错误信息取反纠错，得到闪存中纠正信息。在关键方程求解步骤中，利用二进制BCH码的特性，对现有的riBM算法优化，使逻辑几乎减小一半，迭代延迟只有原始算法的1/2，解决闪存控制器中ECC逻辑复杂的技术难点。本发明的电路高度对称、结构化，一方面有利于采用叠层的方式在逻辑复杂和译码延迟上权衡，另一方有利于VLSI后端布局布线。优化后的riBM算法亦可用于数字电视广播、空间通信等其他应用领域。

Description

一种优化的BCH解码器

技术领域：本发明属于纠错控制编码的技术领域，主要涉及BCH解码器的优化，可用于闪存控制器、数字视频广播系统、空间通信等应用场合。

背景技术：

与非闪存(nand flash memory)是一种非易失(non-volatile)的存储芯片，在功耗、速度、散热等方面具有明显的优势，广泛用于消费电子产品和便携式存储等领域。随着工艺的进步和新的接口标准推出，闪存的存储速度得到极大的提高，目前推出的ONFI3.0标准已经支持400MB/s的存储速度。据预计，基于闪存的固态硬盘(SSD)，也会代替机械硬盘，成为数据存储的主流发展方向。

根据每个浮栅存储的信息比特数，闪存可分为单层单元SLC(Single Layer Cell)、多层单元MLC(Multi-Level Cell)两种。相比于SLC，MLC存储密度大，成本低，但误码率较高，需要差错控制编码(ECC)支持，例如，美光(Micron)的MT29F32G08CBABA系列要求每540字节12比特的纠错能力。BCH码是闪存控制器中常用的差错控制编码。BCH码是循环码的一个重要子类，有着严密的代数理论，其编码相对简单，而译码可分为伴随子计算、关键方程求解、钱搜索验根、纠错四个步骤。

在BCH编解码的各个环节，关键方程求解是技术难点。Dilip V.Sarwate等人在《High-speedarchitectures for Reed-Solomon decoders》一文中推导出riBM算法和RiBM算法，解决传统的iBM算法硬件实现时速度问题，改善时序，除去不必要的逻辑。对纠错能力为T的RS码，riBM算法硬件实现时需要3T个加法器、6T个乘法器，迭代延迟为2T个时钟周期，相对于欧几里德算法面积更优化。在这两种算法的基础上，又衍生出其它算法，例如采用叠层(FOLDER)形式复用逻辑等。

发明者注意到，riBM、RiBM算法是针对RS码提出的通用算法，如果不加修改使用在BCH码上，会忽略BCH码许多特有的性质，造成硬件资源的浪费。在闪存控制器中，ECC纠错能力强，硬件消耗大，成为设计的瓶颈，所以面积上的优化非常重要。

本发明在riBM算法的基础上，利用BCH码的特性，提出优化的关键方程求解算法和硬件实现方案，面积和译码的迭代延迟均减小为1/2，从较高层次上解决闪存控制器中ECC逻辑的技术难点；此外，电路实现时逻辑对称、规则，结构清晰，一方面有利于采用叠层的方式在逻辑复杂和译码延迟上权衡，另一方有利于VLSI后端布局布线。

发明内容：

本发明设施提供了一种闪存控制器中BCH解码器的设施和装置，能够占用较少的硬件资源，完成BCH的解码过程。

为达到上述目的，本发明采用的技术方案有：

对纠错能力为T比特的BCH码，解码过程采用如下的方法：读取闪存信息，存储到FIFO中，根据读取信息只计算前2T-1个伴随子，不需要计算第2T个伴随子；关键方程求解，即根据伴随子利用迭代算法计算错误位置多项式；根据错误位置多项式通过钱搜索(ChienSearch)验根决定错误位置；对错位位置上的错误信息取反纠错，得到闪存中纠正信息。图1是解码的流程图。其中，关键方程求解采用的优化的riBM算法，输入信息是接收信息的伴随子S_i(i＝0，1，……，2T-2)，求解主要流程包括：首先在零次迭代下根据伴随子设置差值多项式

(

表示小于等于T/2的最大整数)及具辅助多项式

的系数初值，达代系数κ为0，迭代限制条件γ为1；其次根据设定的初始值迭代T次，每次迭代更新差值多项式系数、辅助多项式系数、迭代系数、迭代限制条件；在迭代完毕后输出最终的错误位置多项式系数λ₀，λ₁，……，λ_T。图2是关键方程求解的流程图。

在关键方程求解算法中，发明人在riBM算法的基础上做了三点优化：一是在riBM算法中，对BCH码，奇次迭代时差值多项式系数δ₀(r)≡0，奇偶两次迭代可以合并为一次迭代；二是对BCH码，错误位置的信息的纠正值必定为1，可以除去riBM算法中的求纠正值多项式的部分；三足第r次迭代时，错误位置多项式Λ(x)＝∑λ_ixⁱ为次数不超过

的多项式，可以去除冗余的存储单元。基于以上三点优化，可以使求解的延迟和逻辑复杂度分别减小为1/2，优化后的算法伪代码描述如下：

为小于等于

的最大整数

该算法直接实现需要

个加法器，

个乘法器，相对于原始的riBM算法，面积几乎减小一半，并且迭代次数只有riBM算法的1/2。

BCH码的译码装置包括：第一个计算单元，用于接收闪存中读取信息，并计算前2T-1伴随子；第二个计算单元基于优化后的riBM算法，根据伴随子迭代计算出接收信息对应的错误位置多项式；第三个计算单元根据错误位置多项式，利用钱搜索算法，逐位验根，判断该位置是否是错误位置；第四个计算单元将闪存的读取信息中对应错误位置的信息取反，得到纠正后的信息。其中，第二个计算单元包括以下电路：两组寄存器组，第一组寄存器组用来保存差值多项式系数δ₀，……，δ_T+R，第二组寄存器组用来保存辅助多项式系数θ₀，……，θ_T+R；T+R+1个基本处理单元(Process Element)，用来描述迭代前后δ_i，θ_i的变化关系；控制逻辑，用于产生其他模块的控制信号，这其中包括迭代系数κ值，迭代限制条件γ值，基本处理单元的两组控制信号。电路图如图5所示。第二个计算单元工作过程如下：在迭代初始前，根据输入的伴随子，初始化保存错误位置多项式系数和辅助多项式系数的寄存器组，将迭代系数κ为0，迭代限制条件γ为1；每次迭代时，寄存器组通过基本处理单元更新下个时刻数值，直到迭代T次结束；输出计算得到的错误位置多项式系数。

与现有的技术相比，本发明在译码的关键方程求解步骤上，对BCH码做了减小迭代次数和减小面积两方面的优化，在同样的纠错能力T下，比常用的riBM、RiBM算法面积上几乎有1/2的优化，同时迭代延迟只有一半，从而解决闪存控制器中BCH码硬件实现时技术难点。同时，电路实现时采用对称、规格的结构，一方面有利于采用叠层的结构，分时复用逻辑，另一方面，有利于VLSI后端布局布线。

附图说明：

此处所说明的附图用来提供对本发明的进一步理解，构成中请的一部分，并不对本发明的限定。在附图中：

图1是本发明设施的BCH译码方法流程图。

图2是关键方程求解的流程图。

图3是本发明设施的BCH解码器电路结构框图。

图4是本发明设施中BCH解码器的第一个计算单元，即现有技术的伴随子计算电路。

图5是本发明设施中BCH解码器的第二个计算单元，即关键方程求解电路。

图6是本发明设施中关键方程求解电路的基本处理单元。

图7是本发明设施中关键方程求解电路的控制逻辑电路图。

图8是本发明设施的优化riBM算法采用(T+R+1)层叠层的电路实现结构框图，需要使用1个基本处理单元，迭代延迟增加(T+R+1)倍。

图9是本发明设施的BCH解码器的第三个计算单元，即现有技术的钱搜索电路。

具体实施方式：

下面结合附图和具体实施例，对本发明做详细的描述。

具体实施例中涉及到许多参数，其含义描述如下：

(1)N：BCH码中码字长度，即信息加上冗余校验位的长度，在闪存控制器中，N＝K+MT。

(2)K：BCH码中信息的长度，在闪存控制器中，信息是缩短码，K通常是8192＝1KB。

(3)T：BCH码的纠错能力。

(4)

表示小于等于T/2的最大整数。

(5)M：BCH码是基于伽罗华域GF(2^M)上的运算，如果K＝8192，M＝14。

(6)L：BCH码的并行度，由于闪存是以字节为单位操作的，所以L＝8。

(7)S_i(i＝0，1，……，2T-1)：闪存中读取信息的伴随子，本发明只需要用到前面的(2T-1)个伴随子。

(8)

接收码多项式，其系数r_i是闪存中读取信息，由于闪存固有性质，读取信息中包含错误翻转比特。

(9)

关键方程中涉及到的差值多项式多项式，每个系数都是GF(2^M)上的数。

(10)

关键方程中涉及到的辅助多项式，每个系数都是GF(2^M)上的数。

(11)错位位置多项式，每个系数都是GF(2^M)上的数，其根对应错误位置。

(12)κ：关键方程中涉及到的迭代系数。

(13)γ：关键方程中涉及到的迭代限制条件。

结合译码流程图图1，译码方法包括以下步骤：

译码第一步：从闪存中读取[N/L]个字节，存储到FIFO中，并且根据读取信息计算伴随子。伴随子的计算公式为 $S_i=R\left({\mathrm{\α}}^{i+1}\right)=\underset{j=0}{\overset{N-1}{\mathrm{\Σ}}}{r}_j{\left({\mathrm{\α}}^{i+1}\right)}^j(i=0,......,2T-2),$ 其中α是GF(2^M)的本原元，

系数为闪存中读取信息。而第2T个伴随子S_2T-1不需要计算。

译码第二步：关键方程求解，根据伴随子S_i(i＝0，1，……，2T-2)通过优化的riBM算法计算出错误位置多项式

结合流程图图2和优化riBM算法的伪码，该步骤包含以下内容：首先，根据输入的伴随子S_i(i＝0，1，……，2T-2)初始化差值多项式

及其辅助多项式

的系数，数学表达式为δi(0)＝S2i(i＝0，……，T-1)，δ_T(0)＝1，δ_i(0)＝0(i＝T+1，……，T+R)，θ_i(0)＝S_2i+1(i＝0，……，T-2)，θ_i(0)＝0(i＝T-1，……，T+R-1)，θ_T+R(0)＝1，初始化迭代系数κ为0，迭代限制条件γ为1；其次，迭代T次更新错误位置多项式系数、辅助多项式系数、迭代系数、迭代限制条件，迭代的具体形式参考发明内容算法相关部分，不再重复；最后，输出错误位置多项式系数λ₀，λ₁，……，λ_i，偶次幂系数λ_2i＝δ_i(T)(i＝0，1，……，R)，奇次幂系数λ_2i+1＝δ_i+1+R(T)(i＝0，1，……，T-R-1)。

译码第三步：钱搜索(Chien Search)逐位验根，如果表明接收信息的第i比特有错，需要纠正。

译码第四步：从FIFO中读取原始信息，根据钱搜索确定的错误位置，将对应错误位置的比特翻转，得到纠正后的信息。

根据上面的译码方法，本发明实施例提供了一种译码装置图，装置图如图3所示，其中包括：第一个计算单元，完成伴随子计算；第二个计算单元，根据伴随子基于优化的riBM算法，迭代计算出错位位置多项式，完成关键方程求解；第三个计算单元，根据错位位置多项式，利用钱搜索(Chien Search)逐位验根，确定错误位置；第四个计算单元，根据错误位置，将原始信息中对应错误位置的比特翻转，得到正确信息；FIFO，先进先出的储存逻辑，用来保存闪存中读取信息。

第一个计算单元为伴随子计算电路，输入是闪存的读取信息，共[N/L]个字节，输出为伴随子S_i(i＝0，1，……，2T-2)。由于闪存是通过字节与系统交换信息，出于带宽的考虑，常用并行的计算电路。每一个伴随子S_i计算电路如图4所示，其中，

为有限域GF(2^M)上的固定系数乘法器，可以参考相关文献，

为M比特的寄存器，用来保存伴随子S_i。对(i＝0，1，……，2T-2)，分别构造这样的电路图，从而实现伴随子计算电路。而第2T个伴随子S_2T-1不需要计算，因为在优化的riBM算法中没有使用到。

第二个计算单元为关键方程求解电路，输入是伴随子S_i(i＝0，1，……，2T-2)，输出是错误位置多项式系数λ₀，λ₁，……，λ_T，如图5所示。该计算单元包括以下部分：T+R+1个基本处理单元，T+R+1个储存差值多项式系数的寄存器

(i＝0，1，……，T+R)，T+R+1个储存辅助多项式系数的寄存器

(i＝0，1，……，T+R)，控制逻辑。其中：

(1)每一个基本处理单元由2个有限域乘法器

1个有限域加法器

2个复选器组成，如图6所示。对第i个基本处理单元，输入信息是当前迭代的差值多项式系数δ_i+1(r)、δ₀(r)，辅助多项式系数θ_i(r)，迭代限制条件γ(r)，以及两组控制信号c₀＝(δ₀(r)≠0&&κ(r)≥0)，c1(i)＝(i＝＝T-r-2)||(i＝＝R+T-r-1)。在图6中，无论c₀和c1(i)为何值，两个乘法器和一个加法器总是实现δ_i(r+1)＝γ(r)δ_i+1(r)+δ₀(r)θ_i(r)的运算，这就是优化riBM算法中差值多项式系数δ_i(r)的迭代跟新关系。而当c1(i)＝＝1时，复选器1选择0输出到θ_i(r+1)，对应着θ_T-2-r(r+1)≡0，θ_T+R-1-r(r+1)≡0；如果c1(i)＝＝0，复选器2将根据c₀＝(δ₀(r)≠0&&κ(r)≥0)选择δ_i+1(r)或θ_i(r)输出到θ_i(r+1)。也就是说，c₀和c1(i)恰好决定在优化riBM算法中辅助多项式系数θ_i(r)的更新关系。

(2)在关键方程求解电路中，控制逻辑需要生成基本处理单元的控制信号c₀、c1(i)＝(i＝＝T-r-2)||(i＝＝R+T-r-1)(i＝0，……，T+R)，迭代系数κ，迭代限制条件γ，其中，c1(i)(i＝0，……，T+R)只有两个比特为1，并且1的位置在每次迭代后向低位移动2位，这可以使用长度为R+T+1比特的移位寄存器实现。图7是控制逻辑电路的示意图，主要包括：迭代系数的寄存器

及其组合逻辑，迭代限制条件的寄存器

及其组合逻辑，控制信号c₀产生逻辑，用于产生c1(i)(i＝0，……，T+R)的移位寄存器，和有限状态机。

(3)在迭代开始时，R+T+1个储存差值多项式系数的寄存器分别初始化为δ_i(0)＝S_2i(i＝0，……，T-1)，δ_T(0)＝1，δ_i(0)＝0(i＝T+1，……，T+R)，而R+T+1个储存辅助多项式系数的寄存器

分别被初始化为θ_i(0)＝S_2i+1(i＝0，……，T-2)，θ_i(0)＝0(i＝T-1，……，T+R-1)，θ_T+R(0)＝1。在迭代过程中，寄存器间都是通过基本处理单元连接，以实现优化的riBM迭代算法。寄存器和基本处理单元的具体连接关系可以参考图5。该电路高度对称，结构化，非常容易实现。

(4)迭代T次后，第二个计算单元将部分的差值多项式系数输出为错误位置多项式系数，具体关系为λ_2i＝δ_i(T)(i＝0，1，……，R)，λ_2i+1＝δ_i+1+R(T)(i＝0，1，……，T-R-1)。

(5)在实际应用中，可以采用叠层(FOLDER)的结构，分时复用基本处理单元。叠层的层数理论上可以选择任意值，可以参考riBM/RiBM的叠层形式。在本发明中，叠层可以采用(R+T+1)层，面积减小为1/(R+T+1)，但迭代的延迟增加为T(R+T+1)，图8是采用(R+T+1)层的叠层结构图。实际的情况需要在硬件消耗和迭代的延迟上权衡，要根据具体的闪存控制器需求，选择合适的叠层层数。

第三个计算单元为钱搜索电路，输入是错误位置多项式系数λ₀，λ₁，……，λ_i，输出是错误位置信息。在闪存控制器中，采用并行度为8的钱搜索，电路图如图9所示，该电路为现有技术，不属于本发明的内容，具体可以参考相关文献。

第四个计算单元为纠错逻辑，根据第三个单元提供的错误位置信息，将错误位置上的信息取反，输出正确的信息。

本发明实施例中BCH译码方法和装置，根据二进制的RS码特点，对riBM算法做出三点优化，一是BCH码错误位置的纠正值始终为1，可以去除riBM算法中错误值多项式部分；二是第r次迭代时，错误位置多项式Λ(x)＝∑λ_ixⁱ必定为次数不超过

的多项式，结合第一点优化，可以使逻辑几乎减小为原来的1/2；三是BCH码奇次迭代时，差值多项式系数δ₀(r)≡0，可以将奇偶两次迭代合并为一次，这样迭代的延迟减小为原来的1/2。相对于其他算法，这样优化的riBM算法，性能优越，实现简单，非常适合闪存控制、数字电视广播、空间通信等应用场合。

Claims (8)

1.一种BCH码译码方法，其特征在于，所述方法包括：

读取接收信息，存储到FIFO中，并且根据读取信息计算伴随子；

关键方程求解，即根据伴随子利用迭代算法计算错误位置多项式，对纠错能力为T的BCH码，该步骤包括：首先在零次迭代下根据伴随子设置差值多项式系数及其辅助多项式系数初值，迭代系数为0，迭代限制条件为1；其次根据设定的初始值迭代T次，每次迭代更新差值多项式、辅助多项式、迭代系数、迭代限制条件；在迭代完毕后输出最终的错误位置多项式系数。

通过钱搜索(Chien Search)验根决定错误位置。

对错位位置上的错误信息取反纠错，得到闪存中纠正信息。

2.根据权利要求1所述，伴随子计算过程的特征在于：

对纠错能力为T的BCH码，只需要计算前2T-1个伴随子S_i＝∑r_j(αⁱ⁺¹)ⁱ(i＝0，1，...，2T-2)，不需要计算第2T个伴随子S_2T-1。

3.根据权利要求1所述，关键方程求解的方法、特征在于：根据伴随子设置差值多项式

(

表示小于等于T/2的最大整数)及其辅助多项式

的系数初值，数学表达式为δ_i(0)＝S_2i(i＝0，……，T-1)，δ_T(0)＝1，δ_i(0)＝0(i＝T+1，……，T+R)，θ_i(0)＝S_2i+1(i＝0，……，T-2)，θ_i(0)＝0(i＝T-1，……，T+R-1)，θ_T+R(0)＝1。

迭代系数在零次迭代下的初始值为0，数学表达式为κ＝0。

迭代限制条件在零次迭代下的初始值为0，数学表达式为γ＝0。

4.根据权利要求3所述方法，关键方程求解的方法、特征在于：

根据权利要求3所设置的初始值迭代计算差值多项式系数、辅助多项式系数、迭代系数和迭代限制条件：

在第r(r＝0，1，...，2T-1)次迭代过程中，总是有δ_i(r+1)＝γ(r)δ_i+1(r)+δ₀(r)θ_i(r)(i＝0，1，2，...，T+R)θ_T-2-r(r+1)＝0，θ_T+R-1-r(r+1)＝0

如果δ₀(r)≠0&&κ(r)≥0，则：

θ_i(r+1)＝δ_i+1(r)(i≠T-2-r，T+R-1-r)

γ(r+1)＝λ₀(r)

κ(r+1)＝-κ(r)

否则：

θ_i(r+1)＝θ_i(r)(i≠T-2-r，T+R-1-r)

γ(r+1)＝γ(r)

κ(r+1)＝κ(r)+1

迭代结束后，输出错位位置多项式系数λ_2i＝δ_i(T)(i＝0，1，……，R)，λ_2i+1＝δ_i+1+R(T)(i＝0，1，……，T-R-1）。

5.一种BCH译码装置，其特征在于，所述装置包括：

第一个计算单元，用于接收闪存中读取信息，计算前2T-1个伴随子。相对于传统的伴随子计算电路，该计算单元只需要前2T-1个伴随子计算逻辑，而第2T个伴随子的计算逻辑可以移去。

第二个计算单元接收第一个单元计算出的伴随子，利用权利要求3、4中所描述的方法，迭代计算出接收信息对应的错误位置多项式。该计算单元包括：两组寄存器组，第一组寄存器组用来保存差值多项式系数δ₀，……，δ_T+R，第二组寄存器组用来保存辅助多项式系数θ₀，……，θ_T+R；T+R+1个基本处理单元(Process Element)，用来描述迭代前后δ_i，θ_i的变化关系；控制逻辑，用于产生其他模块的控制信号和判断迭代结束条件。

第三个计算单元根据错误位置多项式，利用钱搜索算法，逐位验根，判断该位置是否是错误位置。

第四个计算单元将读取信息中对应错误位置的信息取反，得到纠正后的信息。

6.根据权利要求5所述装置，其特征在于，所述设置模块的初始值具体为：

存储差值多项式系数的寄存器组

(i＝0，1，……，T+R)在零次迭代时分别初始化为δ_i(0)＝S_2i(i＝0，……，T-1)，δ_T(0)＝1，δ_i(0)＝0(i＝T+1，……，T+R)。

存储辅助多项式系数的寄存器组

(i＝0，1，……，T+R)在零次迭代时分别初始化为θ_i(0)＝S_2i+1(i＝0，……，T-2)，θ_i(0)＝0(i＝T-1，……，T+R-1)，θ_T+R(0)＝1。

迭代系数的寄存器

在零次迭代时初始化为κ＝0。

迭代限制条件的寄存器在零次迭代时初始化为γ＝0。

7.根据权利要求5所述装置，其特征在于，基本处理单元包括：

两个有限域上的乘法器，一个有限域上的加法器，两个复选器。

两个乘法器和一个加法器总是实现δ_i(r+1)＝γ(r)δ_i+1(r)+δ₀(r)θ_i(r)的运算，即实现权利要求3、4中所描述算法中差值多项式系数δ_i的更新。

在两组控制信号c₀＝(δ₀(r)≠0&&κ(r)≥0)和c1(i)＝(i＝＝T-r-2)||(i＝＝R+T-r-1)控制下，复选器1、复选器2实现权利要求3、4中所描述算法中辅助多项式系数θ_i的更新。而当c1(i)＝＝1时，复选器1选择0输出到θ_i(r+1)，对应着θ_T-2-i(r+1)≡0，θ_T+R-1-r(r+1)≡0；如果c1(i)＝＝0，复选器2将根据c₀＝(δ₀(r)≠0&&κ(r)≥0)选择δ_i+1(r)或θ_i(r)输出到θ_i(r+1)。

8.根据权利要求5所述装置，其特征在于，控制逻辑包括：

迭代系数的寄存器

及其组合逻辑，达代限制条件的寄存器

及其组合逻辑，控制信号c₀的产生逻辑，用于产生c1(i)(i＝0，……，T+R)的移位寄存器，和自限状态机。在迭代开始前，移位寄存器中第(T-2)、(T+R-1)比特为1，其他比特均为0，每次迭代，移位寄存器中数值右移一位，而移位寄存器中每一个比特就是控制信号c1(i)(i＝0，……，T+R)。

Images