CN1561005B - 快速纠双错bch码译码器 - Google Patents

Abstract

本发明公开了一种快速纠双错BCH码译码器，所述的译码器工作在有限域GF(2⁵)上，由伴随式计算电路、误差数目判断电路、误差位置计算电路组成，并为顺序连接，译码器中BCH码为BCH(N，N-10)，码长N是11～31中任意整数。本发明利用BCH码纠双错的特点，给出了一种无需Chien搜索法，也不用查询表ROM，直接从伴随式结果即可计算出误差位置的快速译码算法。具有译码结构简单，硬件复杂度低、控制信号简单、译码速度快并且不受码长影响等优点。非常适合于要求产品功耗低、吞吐率快及可靠性高的应用系统中，如便携式FLASH存储系统产品中。

Description

快速纠双错BCH码译码器

技术领域

本发明是涉及一种在数字通信、数据存储、网络数据传输等技术领域内进行纠错的一种芯片装置。

背景技术

在数字通信系统和数据存储系统中，误差控制编码(Error ControlCoding)技术作为数据完整性保护的重要手段，得到广泛应用。数字影音光碟(DVD)，数字式广播(DVB)、大容量存储(Mass-Storage)等系统多采用BCH码作为误差控制编码来提高数据的可靠性与完整性。

一些消费类应用系统(如采用FLASH存储器的Mass-Storage系统)基于产品的性能和成本的考虑，以纠双错的BCH码作为差错控制编码，保证数据的可靠性和安全性。它们希望BCH码的译码电路计算速度快，硬件实现代价小。

目前，对于纠正两位误差的BCH码的译码电路通常采用两种方法：第一种是用Berlekamp-Massey算法(或者Euclidian算法)和Chien搜索算法确定误差的具体位置。这种方法通用性好，但是算法复杂，硬件实现代价高。Chien搜索法需要花费正比于码长的运算时间，译码速度慢。第二种方法是查询表(look-up-table)，它是把预先算好的结果存放在只读存储器(ROM)中，确定误差的位置比较快。但是，当码长较长时，ROM的容量较大，硬件实现成本高。

通常的BCH码的译码过程包括三个步骤：

1.伴随式(Syndrome)的计算；

2.利用伴随式计算误差寻址多项式(error-locator polynomial)；

3.根据误差寻址多项式计算出误差位置(error locations)；

步骤2的求解，通常采用Berlekamp-Massey算法或者Euclidian算法。实现Berlekamp-Massey算法或者Euclidian算法电路的硬件复杂度和码长有关，和纠错的数目无关。第3步误差位置的求解通常采用Chien搜索算法实现，算法的迭代次数正比于码长。这些译码算法都未能充分利用纠错个数较少的特点，实现的硬件代价大，运算速度慢。

步骤2和3的确定误差位置也可以用查询表技术实现，它是利用预先在ROM中存放误差位置的查询表。这样可以较快地得出发生误差的位置，但是当码长较长时，需要大容量的ROM，硬件代价大。

发明内容

针对目前纠正两位误差BCH码译码器的缺点，本发明提出了一种无需Chien搜索法，也不用查询表ROM的直接求解的硬件译码器，该译码器工作在有限域GF(2⁵)上，具有译码速度快，硬件代价小的优点。

一种快速纠双错BCH码译码器，所述的译码器工作在有限域GF(2⁵)上，由伴随式计算电路、误差数目判断电路、误差位置计算电路组成，并为顺序连接；译码器中BCH码为BCH(N，N-10)，码长N是11～31中任意整数；

所述的伴随式计算电路，由输入的数据流计算出伴随式S₀、S₁、S₂和S₃；

所述的误差数目判断电路，其步骤包括：

(a)由式(1)计算出A、B、C；

$A=S_0{S}_2+S_1^2,$ B＝S₁S₂+S₀S₃， $C=S_1{S}_3+S_2^2$

(b)根据S₀、S₁、S₂、S₃、A、B和C的值判断发生误差数目；

所述的误差位置计算电路，是根据发生误差数目分别计算出误差位置，根据计算出的误差位置，取反数据得到纠正后的正确值。

单个误差情形下：所述的误差位置计算电路对误差位置的计算，其方法是根据式X₁＝S₁/S₀计算。

两个误差情形下：所述的误差位置计算电路对误差位置的计算，其方法是采用符合式

的硬件电路直接求解z²+z+K＝0根Z₁和Z₂，用式

计算出σ₁，再用式X₁＝σ₁Z₁，X₂＝σ₁Z₂得到两个误差位置X₁和X₂。

本发明利用BCH码纠双错的特点，给出了一种无需Chien搜索法，也不用查询表ROM，直接从伴随式结果即可计算出误差位置的快速译码算法。具有译码结构简单，硬件复杂度低、控制信号简单、译码速度快并且不受码长影响等优点。非常适合于要求产品功耗低、吞吐率快及可靠性高的应用系统中，如便携式FLASH存储系统产品中。

附图说明

图1有限域GF(2⁵)二次方程z²+z+K＝0根的求解电路框图。

图2有限域GF(2⁵)二次方程z²+z+K＝0的根求解电路的一种实现方式。

图3快速BCH译码器整体电路框图。

图4BCH(31，21)码的数据格式图。

图5有限域GF(2⁵)BCH(31，21)译码器电路框图。

具体实施方式

设在有限域GF(2⁵)可纠正两个误差的BCH码的一般形式为：

BCH(N，N-10)

其中N(10＜N≤31)为码长；N-10为信息元长度；码距d＝5。

设r(x)、c(x)和e(x)分别表示接收多项式、码字(code word)多项式和误差多项式。那么，它们之间满足：

r(x)＝c(x)+e(x)                (1)

定义伴随式为S_i(i＝0，1，2，3)，那么

$S_j=\underset{i=0}{\overset{N-1}{\mathrm{\Σ}}}{r}_i{\left({\mathrm{\α}}^j\right)}^i---\left(2\right)$

假设两个误差的位置为i₁和i₂，令

定义寻址多项式σ(x)为：

σ(x)＝(x-X₁)(x-X₂)＝x²+σ₁x+σ₀         (3)

其中，σ₁＝X₁+X₂，σ₀＝X₁X₂

                                         (4)

所以，

S₂＝S₁σ₁+S₀σ₀                          (5)

S₃＝S₂σ₁+S₁σ₀                          (6)

可以得出：

${\mathrm{\σ}}_0=(S_2^2+S_1{S}_3)/(S_1^2+S_0{S}_2)---\left(7\right)$

${\mathrm{\σ}}_1=(S_1{S}_2+S_0{S}_3)/(S_1^2+S_0{S}_2)---\left(8\right)$

BCH码误差数据检测、误差位置的求解方法如下：

1.如果没有误差发生，那么

S₀＝S₁＝S₂＝S₃＝0                    (9)

2.如果单个误差发生，假设误差的位置为i₁，计算A、B和C如下：

$A=S_0{S}_2+S_1^2,$ B＝S₁S₂+S₀S₃， $C=S_1{S}_3+S_2^2---\left(10\right)$

所以：

S₀＝1≠0，S₁＝X₁≠0， $S_2=X_1^2\≠0,$ $S_3=X_1^3\≠0---\left(11\right)$

A＝0，B＝0，C＝0

那么，可以求出误差的位置为：

X₁＝S₁                               (12)

3.如果两个误差发生，假设两个误差的位置为i₁和i₂，那么：

$\begin{array}{c}{S}_0=0\\ S_1=X_1+X_2\≠0\\ S_2=X_1^2+X_2^2\≠0\\ S_3=X_1^3+X_2^3\≠0\end{array}---\left(13\right)$

$\begin{array}{c}A=S_0{S}_2+S_1^2={(X_1+X_2)}^2\≠0\\ B=S_1{S}_2+S_0{S}_3=(X_1+X_2)(X_1^2+X_2^2)\≠0\\ C=S_1{S}_3+S_2^2=X_1{X}_2(X_1^2+X_2^2)\≠0\end{array}---\left(14\right)$

将x＝σ₁z代入寻址多项式σ(x)中，可得：

z²+z+K＝0                            (15)

式中，

式(15)的两个根Z₁、Z₂和K之间的关系式为：

$\begin{array}{c}{Z}_1\left[4\right]=Z_2\left[4\right]=K\left[0\right];\\ Z_1\left[3\right]=Z_2\left[3\right]=K\left[4\right]\⊕K\left[2\right]\⊕K\left[1\right];\\ Z_1\left[2\right]=Z_2\left[2\right]=K\left[4\right]\⊕K\left[0\right];\\ Z_1\left[1\right]=Z_2\left[1\right]=K\left[4\right]\⊕K\left[2\right];\\ Z_1\left[0\right]=0,Z_2\left[0\right]=1;\end{array}---\left(16\right)$

图1为求解二次方程z²+z+K＝0根的电路框图，其中K[4:0]为方程的常数，Z₁[4:0]和Z₂[4:0]为求出的两个根。

图2是有限域GF(2⁵)二次方程z²+z+K＝0两个根的求解电路形式中的一种电路，图中的逻辑门均为异或门。

求出Z₁和Z₂后，可以求出误差位置X₁和X₂的值：

X₁＝σ₁Z₁，X₂＝σ₁Z₂                        (17)

对误差位置的数取反，就得到纠正后的数据，这样完成了纠正两个误差BCH码的译码过程。

图3为本发明快速BCH译码器的整体电路框图。图中I为伴随式计算电路，它从输入的译码数据计算得到S₀、S₁、S₂、S₃；II为误差数目判断电路，它根据伴随式的值之间的关系，判断出误差发生的数目Error_Number；III为误差位置计算电路，它是根据发生误差的数目，分别计算得到误差的位置X₁和X₂。

以BCH(31，21)码为例说明本发明的具体实施方法。

BCH(31，21)码，采用有限域GF(2⁵)，可纠正t＝2个随机误差。数据的格式如图4所示。

最高的10位为校验位，后面21位为信息位。

BCH(31，21)译码器的框图如图5所示，图5中左边为输入信号，DataIn[7:0]为输入的译码数据，CLK为工作时钟。右边为译码输出结果，E_Count[1:0]为发生误差的数目，ErrAdr1[4:0]为第一个误差的地址，ErrAdr2[4:0]为第二个误差的地址。

一、没有误差时的译码结果

输入的31位数据(二进制表示)为：

0000100_00101110_00100010_00111011

其中最前面的10位数据为校验位，后面的21位为信息位。所以校验位和信息位分别为：

校验位：0000100001；

信息位：01110_00100010_00111011(十六进制为0E223B)；

1.译码结果为：

E_Count＝0；

Err_Adr1＝0；

Err_Adr2＝0；

2.结果分析

译码结果表明没有误差发生。

二、单个误差时的译码结果

输入的31位数据(二进制表示)为：

0000100_00101110_01100010_00111011

其中最前面的10位数据为校验码，后面的21位为信息码。所以校验码和信息码分别为：

校验码：0000100001；

信息码：01110_01100010_00111011(十六进制为0E623B)；

1.译码结果为：

E_Count＝1；

Err_Adr1＝0E；

Err_Adr2＝0；

2.结果分析

此时有一个误差发生。误差的位置在第14位，将第14位数据取反后的信息码为0110_00100010_00111011(十六进制为0E223B)。

三、两个误差时的译码结果

输入的31位数据(二进制表示)为：

0000100_00101110_01100011_00111011

其中最前面的10位数据为校验码，后面的21位为信息码。所以校验码和信息码分别为：

校验码：0000100001；

信息码：01110_01100011_00111011(十六进制为0E633B)；

1.译码结果为：

E_Count＝1；

Err_Adr1＝0E；

Err_Adr2＝08；

2.结果分析

此时有两个误差发生。误差的位置在第14位和第8位，将第14位和第8位的数据取反后的信息码为0110_00100010_00111011(十六进制为0E223B)。

Claims (3)

1.一种快速纠双错BCH译码器，其特征在于：所述的译码器工作在有限域GF(2⁵)上，由伴随式计算电路(I)、误差数目判断电路(II)、误差位置计算电路(III)组成，并为顺序连接；译码器中BCH码为BCH(N，N-10)，码长N是11～31中任意整数；

所述的伴随式计算电路，由输入的数据流计算出伴随式S₀、S₁、S₂和S₃；

所述的误差数目判断电路，其相应的工作步骤包括：

(a)由式(1)计算出A、B、C，

$A=S_0{S}_2+S_1^2,$ B＝S₁S₂+S₀S₃， $C=S_1{S}_3+S_2^2$

(b)根据S₀、S₁、S₂、S₃、A、B和C的值判断发生误差数目；

所述的误差位置计算电路，是根据发生误差数目分别计算出误差位置，根据计算出的误差位置，取反数据得到纠正后的正确值。

2.根据权利要求1所述的一种快速纠双错BCH译码器，其特征在于：在单个误差情形下：

所述的误差位置计算电路(III)对误差位置的计算，其方法是根据式X₁＝S₁/S₀计算。

3.根据权利要求1所述的一种快速纠双错BCH译码器，其特征在于：在两个误差情形下：

所述的误差位置计算电路(III)对误差位置的计算，其方法是采用符合式的硬件电路直接求解z²+z+K＝0根Z₁和Z₂，用式计算出σ₁，再用式X₁＝σ₁Z₁，X₂＝σ₁Z₂得到两个误差位置X₁和X₂。

Images