基于FPGA的BCH编解码装置及其编解码方法

摘要

本发明公开了一种基于FPGA的BCH编解码方法，思路为：通过接收模块接收信号数据，并将所述信号数据发送至BCH编码模块，BCH编码模块对所述信号数据进行分段编码，得到所述信号数据对应的r个比特校验位，然后将所述信号数据和所述比特校验位分别存储到存储模块中；从存储模块中获取所述信号数据和所述校验位后进行BCH解码，得到码字多项式R(x)，并据此得到码字多项式R(x)的Q个伴随式，进而得到所述信号数据在存储过程中产生错误的错误位置多项式；根据所述信号数据在存储过程中产生错误的错误位置多项式，以及钱搜索遍历算法求解所述错误位置多项式的根，并据此纠正所述信号数据在存储过程的错误数据位，得到存储在存储模块中的正确信号数据。

说明书

技术领域

本发明属于存储系统数据的错误检查和纠正(ECC)校验技术领域，具体涉及一种基 于FPGA的BCH编解码装置及其编解码方法，即基于一种现场可编程逻辑门阵列(FPGA) 的线性循环码编解码装置及其编解码方法，适用于数据信号在存储系统中的可靠存储。

背景技术

随着NAND闪存存储器的制造工艺和存储单元架构的发展，使得NAND闪存存储器 的NANDFLASH存储介质产生误码的概率大大增加，这是由于FLASH存储芯片会发生“位 交换”现象，NANDFLASH存储介质发生“位交换”主要原因是漂移效应，即：NANDFLASH 存储介质中的电压逐渐发生变化，导致存储在NANDFLASH存储介质中的数据发生逻辑 上的交换，芯片制造工艺以及架构的发展使得一个存储单元能够存储更多的数据位，电压 微小的变化都有可能引起存储数据逻辑上的改变，使得漂移效应引起的位交换就更容易发 生，也就要求具有纠错能力更好的存储器。

目前纠错码的数据编码位数少，串行编码效率低，纠错位数少，而且早期的汉明码已 经无法满足NANDFLASH存储介质对纠错能力的要求，其特殊的物理结构决定了NAND FLASH(闪存)存储介质容易发生随机性错误。

因此，本发明人发现，相对于其他编码，BCH码是一种可以纠正多个随机性错误的有 限域中的线性分组码，能够适用于作为NANDFLASH存储介质中的纠错编码。

发明内容

针对以上存在问题，本发明的目的在于提出一种基于FPGA的BCH编解码装置及其 编解码方法，该编解码装置及其编解码方法采用8位并行设计编码与解码，不仅能够提高 编解码速度，而且采用并行设计能够降低计算复杂度，提高编解码效率。

为达到上述技术目的，本发明采用如下技术方案予以实现。

技术方案1：

一种基于FPGA的BCH编解码装置，搭建于FPGA芯片上，包括：接收模块、BCH 编码模块、存储模块和BCH解码模块；所述接收模块的输出端连接所述BCH编码模块的 输入端，所述BCH编码模块的输出端连接所述存储模块的输入端，所述存储模块的输出 端连接所述BCH解码模块的输入端；

所述接收模块接收信号数据，并将信号数据发送至BCH编码模块，BCH编码模块对 所述信号数据进行编码，并将编码后的信号数据发送存储模块进行存储，BCH解码模块获 取存储在存储模块中的编码后的信号数据，然后对所述编码后的信号数据进行解码处理， 得到解码后的编码信号数据。

技术方案2：

一种基于FPGA的BCH编解码方法，基于搭建于FPGA芯片上的接收模块、BCH编 码模块、存储模块和BCH解码模块，所述基于FPGA的BCH编解码方法，包括以下步骤：

步骤1，通过接收模块接收信号数据，并将所述信号数据发送至BCH编码模块，BCH 编码模块对所述信号数据进行分段编码，得到所述信号数据对应的r个比特校验位，然后 将所述信号数据和所述r个比特校验位分别存储到存储模块中；其中，r表示自然数；

步骤2，从存储模块中获取所述信号数据和所述r个比特校验位，得到码字多项式 R(x)，并将所述码字多项式R(x)发送至BCH解码模块，BCH解码模块对所述码字多项式 R(x)进行解码，计算得到码字多项式R(x)的Q个伴随式；其中，Q表示自然数；

步骤3，根据码字多项式R(x)的Q个伴随式，计算得到所述信号数据在存储过程中产 生错误的错误位置多项式；

步骤4，根据所述信号数据在存储过程中产生错误的错误位置多项式纠正所述信号数 据在存储过程的错误数据位，进而得到存储在存储模块中的正确信号数据。

本发明的有益效果为：本发明在FPGA数据校验、BCH编码、伴随式求解以及错误位 置多项式求解中，分别采用了8bits并行计算，大大降低了编译码的周期，并且在求解错误 位置多项式时采用无求逆的BM算法，使得无须进行矩阵运算，降低了逻辑设计的复杂度， 提高了模块的可移植性。

附图说明

下面结合附图和具体实施方式对本发明作进一步详细说明。

图1为本发明的一种基于FPGA的BCH编解码方法的实现流程框图；

图2为使用带反馈的线性移位寄存器进行BCH并行编码的过程示意图；

图3为使用无求逆BM算法求解错误多项式的系数的迭代步骤示意图；

图4为简化的无求逆算法电路图

图5为钱搜索模块原理图；

图6为使用钱搜索遍历检查出的第一个错误示意图；

图7为使用钱搜索遍历检查出的第二个错误示意图。

具体实施方式

本发明的一种基于FPGA的BCH编解码装置，搭建于FPGA芯片上，包括：接收模 块、BCH编码模块、存储模块和BCH解码模块；所述接收模块的输出端连接所述BCH编 码模块的输入端，所述BCH编码模块的输出端连接所述存储模块的输入端，所述存储模 块的输出端连接所述BCH解码模块的输入端；

所述接收模块接收信号数据，并将信号数据发送至BCH编码模块，BCH编码模块对 所述信号数据进行编码，并将编码后的信号数据发送存储模块进行存储，BCH解码模块获 取存储在存储模块中的编码后的信号数据，然后对所述编码后的信号数据进行解码处理， 得到解码后的编码信号数据；本实施例是在FPGA芯片上利用verilog语言分别实现BCH 编码和BCH解码的，并且接收模块和存储模块分别使用的是FLASH控制模块。

参照图1，为本发明的一种基于FPGA的BCH编解码方法的实现流程框图，一种基于 FPGA的BCH编解码方法，基于搭建于FPGA芯片上的接收模块、BCH编码模块、存储 模块和BCH解码模块，所述基于FPGA的BCH编解码方法包括以下步骤：

步骤1，通过接收模块接收信号数据，并将所述信号数据发送至BCH编码模块，BCH 编码模块对所述信号数据进行分段编码，得到所述信号数据对应的r个比特校验位，然后 将所述信号数据和所述r个比特校验位分别存储到存储模块中；其中，r表示自然数；

具体地，通过接收模块接收信号数据，并将所述信号数据发送至BCH编码模块，BCH 编码模块对所述信号数据进行分段编码；本实施例中是将所述信号数据中的每1KB信号分 为一段进行BCH编码，所述信号数据进行分段编码后的数据位长度k＝8192，所述信号数 据进行分段编码后所能纠错的位数t为32，对二元域的m次扩展域GF(2^m)；由于 2¹³-1<8192<2¹⁴-1，所以m＝14。

根据BCH码的编码原理，分别设定BCH码的生成多项式g(x)，待BCH编码数据为 C(x)，其表达式为：

C(x)＝C₀+C₁x+...+C_k-3x^k-3+C_k-2x^k-2+C_k-1x^k-1

其中，C₀表示待BCH编码数据C(x)的第零位数据位系数，C₁表示待BCH编码数据 C(x)的第一位数据位系数，….,C_k-1表示待BCH编码数据C(x)的第k-1位数据位系数。

进而得到BCH编码的校验公式r(x)为：

r(x)＝x^rC(x)modg(x)

＝((((C_k-1x+C_k-2)x+C_k-3)x+...+C₁)x+C₀)x^rmodg(x)

＝((((((C_k-1x+C_k-2)x+C_k-3)x+...+C₁)x+C₀)+0)x+...0)modg(x)

设k个数据位的第8i+0到8i+7的八位数据M_i的表达式为：

M_i＝C_8i+7x⁷+C_8i+6x⁶+...+C_8i+2x³+C_8i+1x+C_8i

其中，0≤i<k/8，k表示所述信号数据进行分段编码后的数据位长度，本实施例中 k＝8192；然后计算得到所述信号数据进行分段编码后的数据位长度为i的并行BCH编码校 验公式r_i(x)，其表达式为：

r_i(x)＝(r_i-1(x)x⁸+M_i)modg(x)＝r_i-1(x)x⁸modg(x)+M_i，0≤i<k/8

其中，0≤i<k/8，k表示所述信号数据进行分段编码后的数据位长度，M_i表示设定 的k个数据位的第8i+0到8i+7的八位数据，r_i-1(x)表示所述信号数据进行分段编码后的数 据位长度为i-1的并行BCH编码校验式，g(x)表示设定的BCH码的生成多项式，mod(i) 表示取模操作。

根据所述信号数据进行分段编码后的数据位长度为i的并行BCH编码校验公式r_i(x)， 计算得到所述信号数据对应的r个比特校验位，其计算过程为：

1.1初始化：r_-1(x)表示所述信号数据进行分段编码后对生成多项式求余所得到的初 始值，r_-1(x)＝0，M₀表示所述信号数据的第1组八位数据，M₁表示所述信号数据的第2 组八位数据，…，M_k/8表示所述信号数据的第(k/8)+1组八位数据，0≤i<k/8，k表示 所述信号数据进行分段编码后的数据位长度，g(x)表示设定的BCH码的生成多项式，p表 示迭代次数，且p的初始值为1；

1.2根据所要进行编码的第1组八位数据M₀和接收信号数据对生成多项式求余所得到 的初始值r_-1(x)，计算得到第1次迭代后的第2组八位数据对生成多项式求余所得到的值 r₀(x)，r₀(x)为r_-1(x)x⁸+M₀对g(x)求余所得；

1.3令p的值加1；

1.4根据所要进行编码的第p组八位数据M_p-1和第p-1次迭代后的第p-1组八位数 据对生成多项式求余所得到的值r_p-2(x)，计算得到第p次迭代后的第p+1组八位数据对生 成多项式求余所得到的值r_p-1(x)，r_p-1(x)为r_p-2(x)x⁸+M_p-1对g(x)求余所得；

1.5依次重复执行子步骤1.3和1.4，直到得到第k/8次迭代后的第(k/8)+1组八位数 据对生成多项式求余所得到的值r_(k/8)-1(x)，迭代停止，此时得到所述信号数据对应的r个 比特校验位；其中，p∈{1,2,…,k/8}，k表示所述信号数据进行分段编码后的数据位长度。

参照图2，为使用带反馈的线性移位寄存器进行BCH并行编码的过程示意图；根据所 述信号数据进行分段编码后的数据位长度为i的并行BCH编码校验公式r_i(x)实现八位并行 编码，并经过(k/8+r/8)个周期迭代，得到所述信号数据对应的r个比特校验位，然后将 所述信号数据和所述信号数据对应的r个比特校验位分别存储到存储模块中；本实施例中， r＝m*t＝14×32＝448，经过BCH编码模块后的信号数据码长n＝k+r＝8192+448＝8640。

步骤2，从存储模块中获取所述信号数据和所述r个比特校验位，得到码字多项式 R(x)，并将所述码字多项式R(x)发送至BCH解码模块，然后根据BCH编码算法，对所述 码字多项式R(x)进行解码，计算得到码字多项式R(x)的Q个伴随式；其中，Q表示自然数。

具体地，从存储模块中获取所述信号数据和所述r个比特校验位，得到码字多项式 R(x)，并将所述码字多项式R(x)发送至BCH解码模块，然后根据BCH编码算法，对所述 码字多项式R(x)进行解码，计算得到码字多项式R(x)的Q个伴随式；本实施例中所述码字 多项式R(x)纠错的位数为32，所述BCH码的伴随式Q＝32×2个。

计算BCH码的Q个伴随式的子步骤为：

2.1从存储模块中获取所述信号数据和所述校验位，得到码字多项式R(x)，并设定第l 个最小项多项式为m_l(x)，l∈{1,2,…,2t}，然后将接收码元多项式R(x)对所述第l个最小项 多项式m_l(x)进行求余运算，得到第l个余式rm_l(x)；

具体地，为了提高BCH码的编码速度，本实施例采用八位数据并行编码，从存储模 块中获取所述信号数据和所述校验位，得到码字多项式R(x)，其表达式为：

R(x)＝r₀+r₁x+r₂x²+r₃x³+...+r_n-1x^n-1

其中，n表示经过BCH编码模块后的信号数据码长，r₀表示接收的码字多项式码元的 第零位数据，r₁表示接收的码字多项式的第一位数据，...，r_n-1表示接收的码字多项式的第 n-1位数据，n＝k+r，k表示所述信号数据进行分段编码后的数据位长度，r表示所述信 号数据对应的比特校验位个数。

将从存储模块中接收的码字多项式R(x)中每八位数据，分别对第l个最小项多项式 m_l(x)求余，然后基于并行思想，设定从存储模块中接收的码字多项式R(x)的第8g位到第 8g+7位的八位数据E_g为：

E_g＝R_8g+7x⁷+R_8g+6x⁶+R_8g+5x⁵+R_8g+4x⁴+R_8g+3x³+R_8g+2x²+R_8g+1x¹+R_8g

据此得到第l个余式rm_l(x)，其表达式为：

rm_l(x)＝R(x)modm_l(x)

＝((R_8g+7x⁷+R_8g+6x⁶+R_8g+5x⁵+...+R_8g)x⁸+...+R₁x+R₀)modm_l(x)

其中，0≤g<n/8，n表示经过BCH编码模块后的信号数据码长，且n＝k+r，k表 示所述信号数据进行分段编码后的数据位长度，r表示所述信号数据对应的比特校验位个 数，R₁表示接收的码字多项式R(x)中第2位数据，R₀表示接收的码字多项式R(x)中第1 位数据。

2.2根据码字多项式R(x)设定BCH码的生成多项式g(x)，求解设定的BCH码的生成 多项式g(x)的根，并将其代入第l个余式rm_l(x)中，然后计算得到第l个伴随式S_l，进而得 到Q个伴随式；其中，l∈{1,2,…,Q}。

具体地，求解设定的BCH码的生成多项式g(x)的根，获取Q个根，依次为 τ¹,τ²,...,τ⁶³,τ^Q，并将所述Q个根代入第l个余式rm_l(x)中，计算得到第l个伴随式S_l，其表 达式为：S_l＝rm_l(τ^l)。

根据第l个伴随式S_l，进而得到Q个伴随式；其中，l∈{1,2,…,Q}，r表示所述信号数 据对应的比特校验位个数；本实施例中Q＝64。

在得到BCH码的伴随式时，计算得到的第l个伴随式S_l属于串行编码，若计算第l个伴 随式S_l，必须使得所述信号数据中的每段信号数据进行编码后的k个数据位都能够接收得 到。采用本实施例方法进行设计并行求解伴随式的电路，需448个寄存器，可以节省一半 寄存器。

另外，由于在求解伴随式以及余式的过程中，电路的硬件消耗较大，所以本发明在设 计时采用了共享表达式方法，首先找出求解余式以伴随式的求解电路中将被共用的表达 式，然后利用共享表达式的方法可以有效的减小伴随式求解时的硬件消耗。

步骤3，根据码字多项式R(x)的Q个伴随式和无求逆的BM算法，计算得到所述信号 数据在存储过程中产生错误的错误位置多项式。

具体地，参照图3，为使用无求逆BM算法求解错误多项式的系数的迭代步骤示意图； 求解所述码字多项式R(x)的Q个伴随式的值，并需要通过所求的Q个伴随式的值计算得到 错误位置多项式，目前最优的改进算法为无求逆的BM算法(SIBM)，该算法中无须对矩 阵求逆，逻辑设计简单。

设定错误位置多项式为：

σ(x)＝σ₁x+σ₂x²+....σ_t-1x^t-1+σ_tx^t

其中，σ₁,σ₂,...,σ_t-1,σ_t分别表示所述错误多项式的第1位、第2位、…、第t-1位、 第t位系数。

设定错误多项式的伴随式多项式：

S(x)＝S₁x+S₂x²+...+S_Qx^Q

其中，S₁,S₂,...,S_Q分别表示第1个，第2个,...,第Q个错误多项式的伴随式。

则BCH译码中的关键方程w(x)为：

w(x)＝S(x)×σ(x)

其中，t表示所述信号数据中的每1KB信号数据进行编码所能纠错的位数，此处t为 32；由BCH译码原理可得BCH译码中的关键方程w(x)的奇数项系数为零，比如：

S_q+S_q-1σ₁+S_q-2σ₂+...+S₂σ_q-2+S₁σ_q-1+σ_q＝0

其中，S₁表示第1个伴随式，S₂表示第2个伴随式，σ₁表示错误多项式的第1位系数， σ_q-1表示错误多项式的第q-1位系数，σ_q-2表示错误多项式的第q-2位系数，σ_q表示错误 多项式的第q位系数，S_q-1表示第q-1个伴随式，S_q-2表示第q-2个伴随式，S_q表示第q个 伴随式。

采用无求逆的BM算法，计算得到所述错误位置多项式系数的子步骤为：

3.1初始化：j表示迭代次数，且j＝1，当j＝1时，σ₁＝d₁-S₁；d₁表示BCH译码中 的关键方程w(x)的起始系数，设为1，σ₁表示错误位置多项式计算系数时的起始值，σ₁＝1；

3.2计算关键方程的第1位系数d₁；由于d₁为1，然后根据错误多项式的第1位系数σ₁的 计算公式σ₁＝d₁-S₁，得到错误多项式的第1位系数σ₁，令错误多项式的第2位系数σ₂和 错误多项式的第3位系数σ₃分别等于错误多项式的第1位系数σ₁，获得错误多项式的第2 位系数σ₂和错误多项式的第3位系数σ₃，然后据此计算关键方程的第3位系数d₃，且 d₃＝S₃+S₂σ₁+S₁σ₂+σ₃，进而得到错误多项式的系数第1位系数σ₁、错误多项式的第2位 系数σ₂、错误多项式的第3位系数σ₃和关键方程的第3位系数d₃。

3.3令j的值加2；

3.4计算关键方程的第j位系数d_j，且d_j＝S_j+S_j-1σ₁+...+S₁σ_j-1+σ_j，然后判断所述 关键方程的第j位系数d_j是否为零，

若关键方程的第j位系数d_j为零，则计算错误多项式的第j项系数σ_j，并且所求出的 错误多项式的第j位系数σ_j满足d_j＝S_j+S_j-1σ₁+...+S₁σ_j-1+σ_j时，令错误多项式的第j+1 位系数σ_j+1和错误多项式的第j+2位系数σ_j+2分别等于错误多项式的第j位系数σ_j，获得 第j+1位系数σ_j+1和错误多项式的第j+2位系数σ_j+2。

若关键方程的第j位系数d_j不为零，则计算错误多项式的第j项系数σ_j，并且所求出 的错误多项式的第j项系数σ_j不满足d_j＝S_j+S_j-1σ₁+...+S₁σ_j-1+σ_j时，则将所求出的错误 多项式的第j项系数σ_j改为修正公式σ_j＝d_j-(S_j+σ₁S_j-1+...+σ_j-1S₁)，据此计算出错误多 项式的第j项系数σ_j，然后令错误多项式的第j+1位系数σ_j+1和错误多项式的第j+2位系 数σ_j+2分别等于错误多项式的第j位系数σ_j，获得错误多项式的第j+1位系数σ_j+1和错误 多项式的第j+2位系数σ_j+2。

3.5依次重复执行子步骤3.3和3.4，直到错误位置多项式的系数个数j>t，重复操作 停止，此时获得所述错误位置多项式的第1位-第t位系数值；其中，j∈{1,2,…,t}，t表 示所述信号数据进行分段编码后所能纠错的位数，S_j表示第j个错误多项式的伴随式；此 处t为32。

步骤4，根据所述信号数据在存储过程中产生错误的错误位置多项式，以及钱搜索遍 历算法求解所述错误位置多项式的根，并据此纠正所述信号数据在存储过程的错误数据 位，进而得到存储在存储模块中的正确信号数据。

具体地，参照图5，为钱搜索模块原理图；从FLASH中接收的码字多项式是 R(x)＝r₀+r₁x+r₂x²+r₃x³+...+r_n-1x^n-1，根据图5得知，要检验第n-i位是否出错，只要判 断τ^-(n-i)即τⁱ是否是错误位置多项式σ(x)的根即可。钱搜索算法是计算所述错误位置多项 式σ(x)的根的经典算法之一，其采用遍历思想将τ^l代入所述错误位置多项式σ(x)中，从 而求出错误码的位置，设定的BCH码的生成多项式g(x)的根，所述生成多项式g(x)的根 有f个，依次为τ¹,τ²,...,τ^l,…,τ^f，τ^l表示生成多项式g(x)的第l个根，n表示经过BCH编 码模块后的信号数据码长，r₀表示接收的码字多项式码元的第零位数据，r₁表示接收的码 字多项式的第一位数据，...，r_n-1表示接收的码字多项式的第n-1位数据，0≤i<k/8，k表 示所述信号数据进行分段编码后的数据位长度，0≤l≤f，f表示自然数；此处f＝64。

由于BCH编码设计采用(16383,15935,32)的缩短码(8640,8192,32)，比原码缩短7743 位，因此在进行钱搜索计算时，钱搜索从τ⁷⁷⁴³开始，并需将第一寄存器1-第32寄存器分 别初始化成以下值：

σ₁τ⁷⁷⁴³,σ₂τ^7743×2,σ₃τ^7743×3...,σ₃₂τ^7743×t

钱搜索采用8位并行搜索方式提高搜索效率，进行第u个钱搜索周期时的8位并行搜 索第i位的等式为σ(τ^u*8+i)，其表达式为：

σ(τ^u*8+i)＝σ₀+σ₁τ⁷⁷⁴³(τ^u*8+i)+σ₂τ⁷⁷⁴³(τ^u*8+i)²+...+σ₃₂τ⁷⁷⁴³(τ^u*8+i)³²

当进行第u个钱搜索周期时的8位并行搜索第u位的等式σ(τ^u*8+i)的值是0时，那么 τ^u*8+i是错误多项式σ(x)的根，即r_n-(u*8+i)错误，u∈{1,2,…,k/8}；由于所述信号数据进行 分段编码后的数据位长度为k个，并且为八位并行，所述信号数据进行分段编码后的数据 周期为k/8，使得所述信号数据中的每段信号数据经过k/8个周期后，就能够找出所述信 号数据在存储过程的错误数据位，并对其错误位进行纠正；由于编码数据为二进制，即不 是1就是0，如果找出所述信号数据在存储过程的错误数据位，只需改为相反的位即可； 若继续从存储模块中获取所述信号数据，则转到步骤2，否则所述信号数据获取完毕，最 终得到存储在存储模块中的正确信号数据；其中，0≤i<k/8，n＝k+r，k表示所述信号 数据进行分段编码后的数据位长度，r表示所述信号数据对应的比特校验位个数。

本发明效果可以通过以下仿真实验进一步验证说明。

(一)仿真条件

实验环境：大容量高速存储板，FPGA为主控制器，NANDFLASH作为存储板卡的存 储介质。

(二)实验内容

由预处理板获取信号数据，并随机加入错误，然后通过BCH编译码模块进行数据校 验，观察错误位是否被检查出来。

参照图6与图7，图6为使用钱搜索遍历检查出的第一个错误示意图；图7为使用钱 搜索遍历检查出的第二个错误示意图。从图6与图7可以看出，使用BCH译码模块数据 校验后检查出的错误位，分别为第262字节的第零位与第985字节的第四位，然后进行错 误位的纠错，可以看出本发明能够有效的进行数据校验，并且可靠性较好。

本领域的技术人员可以对本发明进行各种改动和变型而不脱离本发明的精神和范围。 这样，倘若本发明的这些修改和变型属于本发明权利要求及其等同技术的范围之内，则本 发明也意图包含这些改动和变型在内。