CN103886915A - 用于校正包括邻近2比特错误的3比特错误的电路和方法 - Google Patents

Abstract

本发明涉及用于校正包括邻近2比特错误的3比特错误的电路和方法。提出了一种用于相对于代码字v＝v₁，...，v_n校正可能错误的二进制字v’＝v₁’，...，v_n’中的错误、特别是包含邻近2比特错误(区间错误)的3比特错误的电路。该电路包括校正子生成器和解码器。使用修改的BCH码，其中第一BCH码子矩阵的n’个列向量被配对作为列向量对，使得每个列向量对的两个列向量的逐分量的异或组合产生相同的列向量K，所述列向量K与第一BCH子矩阵的所有列向量不同。第二BCH子矩阵包括根据Galois域算法作为第一BCH子矩阵的列向量的三次幂的对应列向量。可以针对第一和第二子矩阵的列检查由校正子生成器所生成的校正子。

Description

用于校正包括邻近2比特错误的3比特错误的电路和方法

背景技术

已知在具有一定长度N的二进制序列或二进制字中通过组合错误校正电路利用BCH码来校正1比特错误和任意2比特错误，例如如其在Okano，H.和Imai，H.的“A construction method of high speed decoders using ROM’s forBose-Chadhuri-Hocquenghem and Reed Solomon Codes”，IEEE Trans.Comp.C36(10)1165-1175，1987中被描述的。

如果BCH码被在Galois域GF(2^m)上，那么N≤2^m-1，且错误校正子(errorsyndrome)s可以包括2m个分量，其中前m个分量形成子校正子s₁，并且另外的m个分量形成子校正子s₃，如其在使用BCH码时是常见的。如果考虑总体奇偶性，那么错误校正子包括将通过s_p被表示的另外的二进制分量。

还已知利用BCH码通过组合错误校正电路来校正任意3比特错误，如其例如也在Okano，H.和Imai，H.的“A construction method of high speed decoders usingROM’s for Bose-Chadhuri-Hocquenghem and Reed Solomon Codes”，IEEE Trans.Comp.C36(10)1165-1175，1987中被描述的。当校正任意3比特错误时，除了子校正子s₁和s₃，还可以使用另一个子校正子s₅，其类似于s₁和s₃，通常也包括m比特的字宽，使得错误校正子s＝s₁，s₃，s₅通常包括3·m的字宽，并且考虑到总体奇偶性而包括3m+1的字宽。

这里，通过组合错误校正电路的任意3比特错误的校正与相对高的硬件工作量和用于确定对应的错误校正信号的相对大的信号运行时间有联系，这可能是不利的。特别是，用于校正信号的相对长的信号运行时间可能针对时钟率是有限制的。

对于某些电路，更有可能的是，当二进制字中的3个比特是错误的时，与全部三个错误比特是随机分布的情况相比，这些错误比特中的两个发生在特定比特位置处。

一种这样的情况的示例可以是数据存储器，其存储单元可以呈现出大于两个状态，通常每个是一个多值状态。如果数据存储器例如呈现出4个不同状态，那么单元的存储状态存储两个特定比特的信息。这些存储在相同存储单元中的比特在这里被命名为相邻比特。通常，这些比特在要被存储的数据字中还将在空间上邻近。当然还可以存储在一个存储单元中的数据字中并不直接邻近的两比特的信息，例如第一个和第七个比特、第二个和第十三个比特的值，等。从这种方式来说，第一个和第七个比特、以及第二个和第十三个比特是邻近的。为了使描述尽可能简单，在下面通常假定，例如被存储在存储单元中的相邻比特在所考虑的数据字中在空间上也是相邻的。如果不是这种情况，则可以通过简单地交换数据字的比特以使得相邻比特在空间上也相邻来获得。因此，以下不必要在由于例如被存储在相同的存储单元中而相邻的相邻比特以及在所考虑的二进制字中空间上相邻或邻近的相邻比特之间进行区分。

如果现在发生了存储状态(其可以例如呈现四个状态)的错误，那么对应于这个状态的两个相邻比特可能同时都是错误的。如果通过Gray码完成了存储单元的多值状态到二进制值的分配，如其例如在Rupprecht，W.，Steinbuch，K.的“Nachrichtentechnik”的第339-341页、Springer Verlag1967中被提出且是一般惯例的那样，那么仅仅是将存储状态变化成物理上相邻的状态值的存储单元的状态值错误导致被分酏给该存储状态的二进制值之一中的1比特错误。

存储单元的将正确的存储状态误用为非相邻存储状态的存储状态错误导致被分配给该存储状态的二进制数据的相邻二进制值中的2比特错误。

可能的是，要被校正的字的比特是三态存储器或者多值存储器的辅助二进制读取值，如其在2012年10月31日提交的、题为“Circuit and Method for Multi-BitCorrection”的美国专利申请号13/664,495中被描述的那样，该专利申请的全部内容通过引用在这里被包括在此说明书中。

将有利的是，以相对低的硬件工作量和/或相对短的信号运行时间来提供两个相邻比特(或以其它方式彼此相关)中的2比特错误的错误校正。还将有利的是，提供两个相邻比特中的2比特错误以及任意比特位置处的附加1比特错误的错误校正。

发明内容

本发明的实施例提供了一种用于相对于代码字v＝v₁，...，v_n校正可能错误的二进制字v’＝v₁’，...，v_n’中的错误的电路。该电路包括校正子生成器，其用于根据修改的BCH码来确定错误校正子s＝(s₁，s₃)，该修改的BCH码具有包括第一BCH子矩阵

和第二BCH子矩阵

的H矩阵H^mod，并且具有码距d≥5，其中子矩阵

的n’个列向量被配对作为列向量对，使得每个列向量对的两个列向量的逐分量的XOR组合产生相同的列向量K，列向量K与第一BCH子矩阵

的所有列向量不同，并且其中n’是偶数且4≤n’≤n适用。第二BCH子矩阵

包括针对第一BCH子矩阵中的每个列向量的对应列向量，使得根据Galois域算法，该对应列向量是第一BCH子矩阵中的列向量的三次幂。校正子生成器被配置为，通过将H矩阵H^mod与可能错误的二进制字v’相乘来确定错误校正子s，使得通过

而得到第一错误校正子部分以及通过

而得到第二错误校正子部分。该电路还包括解码器，其用于生成校正向量e＝(e₁，...e_n)，其中，如果第一错误校正子部分s₁等于相同的列向量K与第一BCH矩阵

的列位置1处的列向量的逐分量的XOR组合，并且如果第二错误校正子部分s₃等于第二BCH子矩阵

的列位置j、j+1和1处的列向量的逐分量的XOR组合，则校正值e_j＝e_j+1＝e₁＝1以及针对t≠j，j+1，1，e_t＝0。

本发明的其它实施例提供了一种用于相对于代码字v＝v₁，...，v_n校正可能错误的二进制字v’＝v₁’，...，v_n’中的错误的方法。该方法包括：确定修改的BCH码的错误校正子s＝(s₁，s₃)，该修改的BCH码具有包括第一BCH子矩阵和第二BCH子矩阵

的H矩阵H^mod，并且具有码距d≥5，其中子矩阵

的n’个列向量被配对作为列向量对，使得每个列向量对的两个列向量的逐分量的XOR组合产生相同的列向量K，其与第一BCH子矩阵

的所有列向量不同，并且其中n’是偶数且4≤n’≤n适用。第二BCH子矩阵

包括针对第BCH子矩阵

中的每个列向量的对应列向量，使得根据Galois域算法，该对应列向量是第一BCH子矩阵中的列向量的三次幂。通过将H矩阵H^mod与可能错误的二进制字v’相乘来确定错误校正子s，使得通过

得到第一错误校正子部分以及通过

得到第二错误校正子部分。该方法还包括步骤：生成校正向量e＝(e₁，...e_n)，其中，如果s₁等于相同的列向量K与第一BCH矩阵

的列位置l处的列向量的逐分量的XOR组合并且如果s₃等于第二BCH子矩阵

的列位置j、j+1和l处的列向量的逐分量的XOR组合，则校正值e_j＝e_j+1＝e₁＝1且对于t≠j，j-1，1，e_t＝0。

附图的简要说明

将利用附图来描述本发明的实施例，在附图中：

图1a示出了根据实施例的用于校正二进制字中的错误的电路的示意框图；

图1b示出了根据其它实施例的用于校正错误的电路的示意框图，在该实施例中，二进制字的总体奇偶性被评估和使用；

图1c示出了根据其它实施例的用于校正错误的电路的示意框图，在该实施例中，可以从子校正子s₁确定总体奇偶性，这是因为子矩阵

仅仅具有包括奇数个1的列；

图1d示出了包括错误指示电路的用于校正错误的电路的示意框图；

图1e示出了用于校正错误的电路的示意框图，该电路使用另一矩阵

以便在和2比特错误相邻的3比特错误与其它(不可校正的)3比特错误之间进行区分；

图2a示出了根据某些实施例的解码器的示意框图；

图2b示出了用于形成辅助信号的子电路的示意框图；

图2c示出了用于形成辅助信号的另一子电路的示意框图；

图3a示出了图2a中用于形成辅助信号的子电路的可能实施方式；

图3b示出了图2b中用于形成辅助信号的子电路的可能实施方式；

图3c示出了图2a中用于形成辅助信号的子电路的可能实施方式，该子电路具有其它输出，用于输出信号“1比特错误”、“2比特错误”和“3比特错误”；

图4示出了用于单个校正值e_j的解码器子电路的可能实施方式的示意逻辑门图；

图5示出了用于实现函数

的子电路的示意实施方式；

图6示出了用于实现函数

的子电路的示意实施方式；以及

图7示出了根据实施例的用于校正二进制字中的错误的方法的示意流程图。

具体实施方式

首先将描述本发明实施例的理论背景。

对于随机分布的多比特错误的错误校正，可以使用BCH码，如这是本领域技术人员公知的并例如在Lin，S.，Costello，D.的“Error Control Code”PrenticeHall，1983中被描述的那样，其中特别参见第143-160页。同样，对Okano，H.和Imai，H.的文档“A construction method of high speed decoders using ROM’s forBose-Chadhuri-Hocquenghem and Reed Solomon Codes”，IEEE Trans.Comp.C36(10)1165-1175，1987进行参考，其中提出了一种用于BCH码的错误校正的组合电路。

BCH码是一种特殊的线性码，其可以通过奇偶校验矩阵H以及可从奇偶校验矩阵导出的生成器矩阵G来描述。如果码包括长度N，且如果它包括k个信息比特，那么H是包括M行和N列的M，N矩阵，其中M＝N-k。生成器矩阵G则是包括k行和N列的k，N矩阵，且该码包括M个校验比特。

可以通过H矩阵来描述未缩短2比特错误校正BCH码：

$H=\left(\begin{array}{c}H1\\ H3\end{array}\right)=(h_1,...,h_N)$

其中，H矩阵被表示为分离形式。通常，当该码没有被缩短时，H₁和H₃被选择为：

$H_1=({\mathrm{\α}}^0,{\mathrm{\α}}^1,...,{\mathrm{\α}}^i,...,{\mathrm{\α}}^{N-1})=(h_1^1,...,h_i^1,...,h_N^1),$ 以及

$H_3=({\mathrm{\α}}^0,{\mathrm{\α}}^3,...,{\mathrm{\α}}^{3i},...,{\mathrm{\α}}^{3(N-1)})=(h_1^3,...,h_i^3,...,h_N^3).$

这里，α是Galois域GF(2^m)的元素并且可以被选择作为有限域GF(2^m)、也被称为Galois域的本原元素。这里，N＝2^m-1适用。α^j和α^3j的指数在这里被确定为是模2^m-1。

H₁和H₃每个都是具有m行和N＝2^m-1列的(m，N)矩阵。它们的向量表达式中的Galois域GF(2^m)的元素αⁱ是m数位二进制列向量。

如果未缩短BCH码的H矩阵的L个列被消除，则获得长度为n＝N-L的缩短BCH码的H矩阵。为了缩短码，在以下应用n＝N-L＜2^m-1。

可以通过只有1的行来补充H矩阵H。总体奇偶性的额外合并对应于H矩阵中只有1的额外行。

考虑了总体奇偶性的H矩阵可以对应于H矩阵：

$H=\left(\begin{array}{c}{H}_1\\ H_3\\ P\end{array}\right)$

其中P是只有1的行。

现在考虑长度n的缩短BCH码，其中n＝N-L＜2^m-1适用。这个码的代码字v＝v₁，...，v_n(也被称为码向量)由n个分量v₁，...，v_n组成。这里，码向量可以被描述为行向量或者列向量。如果矩阵被从右边与向量相乘，那么该向量被解释为列向量，并且结果是列向量。在这样的情况下，不需要明确地突出所述对应向量是列向量，因为从上下文中这已经清楚了。如果特别突出了向量w被表示为列向量，那么将其写为w^T。如果代码字v＝v₁，...，v_n被误用成字v’＝v₁’，...，v_n’，那么v和v’之间的差别可以通过错误向量e来描述，其中

$e(e_1,...,e_n)=(v_1\⊕{v_1}^{\′},...,v_n\⊕{v_n}^{\′})=v\⊕v^{\′}$

当v_i和v′i不同，且

适用时，错误向量e的分量e_i等于1。当v_j和v_j’相同且当v_j＝v_j’适用时，错误向量e的分量e_j等于0。

如果通过错误校正电路可以对错误进行校正，那么错误校正电路的校正值输出等于错误向量的分量，且校正电路在其n个输出端的第i个输出端输出校正值e_i。校正值e_i还可以被组合成校正向量。如果可以通过该码对错误进行校正，那么校正向量等于该错误向量。

字v’的错误校正子s＝(s₁，s₃，s_p)通过以下确定：

s＝H·v′                         (1)

其中

s₁＝H₁·v′                               (2)

s₃＝H₃·v′                              (3)

以及

$s_p=P\·v^{\′}=(1,...,)\·v^{\′}={v_1}^{\′}\⊕{v_2}^{\′}\⊕...\⊕{v_n}^{\′}---\left(4\right)$

适用。

代码字v的错误校正子等于0，使得对于代码字v适用以下：

s＝H·v＝0                        (5)

并且对于非代码字

$s=H\·v^{\′}=H\·(v\⊕e)=H\·v\⊕H\·e=H\·e---\left(6\right)$

且错误校正子s通过错误向量e而被确定。

为了从被非代码字v’干扰的错误代码字中确定所分配的正确代码字，应将e_j＝1适用的那些分量v_j’求逆，使得e_j是通过错误校正电路确定的对应校正值。

针对所考虑的缩短BCH码，利用如下H矩阵从错误校正子s＝s₁，s₃，s_p来确定e。

$H=\left(\begin{array}{c}{H}_1\\ H_3\\ P\end{array}\right)$

这里，以下公式适用：

$H_1=(h_1^1,h_2^1,...,h_n^1)=({\mathrm{\α}}^{i_1},{\mathrm{\α}}^{i_2},...,{\mathrm{\α}}^{i_n})---\left(7\right)$

$H_3=(h_1^3,h_2^3,...,h_n^3)=({\mathrm{\α}}^{3\left(i_1\right)},{\mathrm{\α}}^{3\left(i_2\right)},...,{\mathrm{\α}}^{3\left(i_n\right)})$

以及

其中如已经指示的，α的指数被确定为模2^m-1，且指数i₁，i₂，...，i_n都是不同的成对的。这里无需针对j＝1，...n适用i_j＝j。

如果在第j比特中存在1比特错误，则以下公式适用：

$s_1={\mathrm{\α}}^{i_j}---\left(10\right)$

$s_3={\mathrm{\α}}^{3\left(i_j\right)}---\left(11\right)$

s_P＝1                         (12)

且如果在比特位置j和l中存在2比特错误，则以下公式适用：

$s_1={\mathrm{\α}}^{i_j}\⊕{\mathrm{\α}}^{i_l}---\left(13\right)$

$s_3={\mathrm{\α}}^{3\left(i_j\right)}\⊕{\mathrm{\α}}^{3\left(i_l\right)}---\left(14\right)$

s_P＝0                              (15)

且 $s_1^3\≠s_3.$

对于BCH码，从BCH码的校正子分量s₁和s₃确定1比特错误或任意2比特错误的错误位置。在这方面，描述用于确定错误位置的特定处理。

从(13)，结果得到以下

${\mathrm{\α}}^{3\left(i_l\right)}=s_1^3\⊕s_1{\mathrm{\α}}^{2\left(i_j\right)}\⊕s_1^2{\mathrm{\α}}^{i_j}\⊕{\mathrm{\α}}^{3\left(i_j\right)}$

以及利用(14)

$s_1^3\⊕s_3\⊕s_1{\mathrm{\α}}^{2\left(i_j\right)}\⊕s_1^2{\mathrm{\α}}^{i_j}=0---\left(16\right)$

以及完全类似于

$s_1^3\⊕s_3\⊕s_1{\mathrm{\α}}^{2\left(i_l\right)}\⊕s_1^2{\mathrm{\α}}^{i_l}=0---\left(17\right)$

使得通过Galois域GF(2^m)中的以下二次方程的两个零值或根值来确定位置j和l处的2比特错误

$s_1^3\⊕s_3\⊕s_1{x}^2\⊕s_1^{2}x=0---\left(18\right)$

其中， $s_1={\mathrm{\α}}^{i_j}\⊕{\mathrm{\α}}^{i_l},$ 且 $s_3={\mathrm{\α}}^{3i_j}\⊕{\mathrm{\α}}^{3i_l}.$

如果现在在第j比特位置处存在1比特错误，那么

且在这种情况下等式(18)的两个解是x＝0和

使得1比特错误的位置j也被确定为等式(18)不等于0的解。

假定只出现了1比特、2比特和3比特错误，则以下适用：

当

s₁≠0且s_P＝1时，存在1比特错误。

当且s_P＝0时，存在2比特错误。

当且s_P＝1时，存在3比特错误。

如果s₁＝s₃＝0，不存在错误。

总之，在1比特错误或2比特错误的情况下，通过等式(18)的不等于0的解并且因此从子校正子s₁和s₃来确定错误的比特位置。

直至今日，已知没有方法和电路能够通过知晓BCH码的子校正子s1、s3和sP来确定3比特错误的错误位置并因此校正该3比特错误。

令人惊讶地，根据本发明，当3比特错误包括相邻比特中的2比特错误时，可以从子校正子s₁、s₃和s_P来确定3比特错误的错误位置，其中2比特错误发生在一定比特对中。例如，当二进制序列的比特被存储在可以呈现出大于两个的状态的存储单元中时，这样的2比特错误是引起关注的。

为了能够校正所述的具有相邻2比特错误的3比特错误，从缩短BCH码的原始H矩阵H，通过重新排列原始H矩阵H＝(h₁’，...，h_n’)的列h₁’，...，h_n’来形成具有子矩阵

和

的修改H矩阵H^mod。

修改H矩阵H^mod的列h₁，h₂，...，h_n被确定为使得对于子矩阵的列

针对n是偶数，以下公式适用

$h_1^1+h_2^1=h_3^1\⊕h_4^1=h_5^1\⊕h_6^1=...=h_{n-1}^1\⊕h_n^1=K---\left(19\right)$

并且针对n是奇数，以下公式适用

$h_1^1+h_2^1=h_3^1\⊕h_4^1=h_5^1\⊕h_6^1=...=h_{n-2}^1\⊕h_{n-1}^1=K---\left(20\right)$

这里，将K选择为使得K不是子矩阵H₁的任何列。

在

的情况下，等式(19)和(20)对应于等式：

${\mathrm{\α}}^{i_1}\⊕{\mathrm{\α}}^{i_2}={\mathrm{\α}}^{i_3}\⊕{\mathrm{\α}}^{i_4}={\mathrm{\α}}^{i_5}\⊕{\mathrm{\α}}^{i_6}=...={\mathrm{\α}}^{i_{n-1}}\⊕{\mathrm{\α}}^{i_n}=K---\left(21\right)$

以及

${\mathrm{\α}}^{i_1}\⊕{\mathrm{\α}}^{i_2}={\mathrm{\α}}^{i_3}\⊕{\mathrm{\α}}^{i_4}={\mathrm{\α}}^{i_5}\⊕{\mathrm{\α}}^{i_6}=...={\mathrm{\α}}^{i_{n-2}}\⊕{\mathrm{\α}}^{i_{n-1}}=K---\left(22\right)$

为了可能最简单的说明，相邻比特的不同对这里被指定为对[1，2]、[3，4]、[5，6]……。如果相邻比特对例如被指定为[1，7]、[2，11]、[3，5]……，那么等式(19)或(20)中的

$h_1^1\⊕h_2^1=h_3^1\⊕h_4^1=h_5^1\⊕h_6^1=...=K$

通过该条件被简单替换为

$h_1^1\⊕h_7^1=h_2^1\⊕h_{11}^1=h_3^1\⊕h_5^1=...=K.$

如果在位置j、j+1和l处存在3比特错误，其中j∈{1，3，5...，}，那么对于子校正子s₁以下公式适用

$s_1={\mathrm{\α}}^{i_j}\⊕{\mathrm{\α}}^{i_{j+1}}\⊕{\mathrm{\α}}^{i_l}---\left(23\right)$

以及其中

${\mathrm{\α}}^{i_j}\⊕{\mathrm{\α}}^{i_{j+1}}=K---\left(24\right)$

${\mathrm{\α}}^{i_l}=s_1\⊕K---\left(25\right)$

根据以上得到以下结果

${\mathrm{\α}}^{3\left(i_l\right)}=s_1^3\⊕s_1{K}^2\⊕s_1^{2}K\⊕K^3---\left(26\right)$

对于子校正子s₃，以下公式适用

$s_3={\mathrm{\α}}^{3\left(i_j\right)}\⊕{\mathrm{\α}}^{3\left(i_{j+1}\right)}\⊕{\mathrm{\α}}^{3\left(i_l\right)}---\left(27\right)$

$={\mathrm{\α}}^{3\left(i_j\right)}\⊕{\mathrm{\α}}^{3\left(i_{j+1}\right)}\⊕s_1^3\⊕s_1{K}^2\⊕s_1^{2}K\⊕K^3.---\left(28\right)$

从等式(24)，结果得到以下

${\mathrm{\α}}^{3\left(i_{j+1}\right)}={(K\⊕{\mathrm{\α}}^{i_j})}^3=K^3\⊕{\mathrm{K\α}}^{2\left(i_j\right)}\⊕K^2{\mathrm{\α}}^{i_j}\⊕{\mathrm{\α}}^{3\left(i_j\right)}---\left(29\right)$

并且从等式(28)，对于

得到以下

$s_1^3\⊕s_3\⊕s_1{K}^2\⊕s_1^{2}K\⊕{\mathrm{K\α}}^{2\left(i_j\right)}\⊕K^2{\mathrm{\α}}^{i_j}=0.---\left(30\right)$

完全类似于其，对于

结果得到以下

$s_1^3\⊕s_3\⊕s_1{K}^2\⊕s_1^{2}K\⊕{\mathrm{K\α}}^{2\left(i_{j+1}\right)}\⊕K^2{\mathrm{\α}}^{i_{j+1}}=0.---\left(31\right)$

使得，在Galois域GF(2^m)中和

是以下二次方程的解。

$s_1^3\⊕s_3\⊕s_1{K}^2\⊕s_1^{2}K\⊕{\mathrm{Kx}}^2\⊕K^{2}x=0---\left(32\right)$

因此可以仅仅通过知晓校正子分量s₁和s₃来确定包括相邻2比特错误的3比特错误，其中对于1比特错误，以下公式适用

$s_1^3=s_3$ 且P＝1                            (33)

对于2比特错误，以下公式适用

$s_1^3\≠s_3$ 且P＝0                             (34)

以及对于3比特错误，以下公式适用

$s_1^3\≠s_3$ 且P＝1。               (35)

当与在n个比特上随机分布的3比特错误相比具有相邻2比特错误的3比特错误发生得更加频繁时，对作为包含相邻2比特错误的3比特错误的3比特错误的校正可能是特别有用的，因为这可能是二进制编码数据的比特被存储在每存储单元存储大于1比特(例如每存储单元2比特或者4个值)的存储单元中时发生的情况。

如果仅仅是相邻2比特错误的子集要被校正，则以使得仅仅针对n’列的子集(其中4≤n’≤n适用)确定子矩阵

的对应列

1≤i≤n’以使得下式成立的方式来确定修改的H矩阵H^mod是足够的

$h_1^1\⊕h_2^1=h_3^1\⊕h_4^1=...=h_{n^{\′}-1}^1\⊕h_{n^{\′}}^1=K.$

由此K不是子矩阵

的任何列。

对于

的剩余的n-n’个列，无需这个条件是有效的。

这里，子矩阵

的对应列被表示为

对于任意其它n’个列，可以用公式表达相似的条件。

例如对于n’＝6，如果仅仅在位置(5，6)、(9，10)和(12，13)上的相邻2比特错误以及任意位置上的1比特错误需要被校正，那么子矩阵

必须被确定为使得我们具有

$h_5^1\⊕h_6^1=h_9^1\⊕h_{10}^1=...=h_{12}^1\⊕h_{13}^1=K$

其中K不是子矩阵

的列。

例如，如果只有数据比特中的错误需要被校正，那么列

是子矩阵

对应于校正字的数据比特的列。

还可能有益的是，尽可能快速地并且利用最小可能的硬件工作量来校正包括相邻2比特错误的3比特错误以及将没有包括相邻2比特错误的3比特错误检测为不校正的3比特错误或者不足以校正的3比特错误。具有

$H^{\mathrm{mod}}=\left(\begin{array}{c}{H}_1^{\mathrm{mod}}\\ H_3^{\mathrm{mod}}\\ P\end{array}\right)$

且具有

的H矩阵H^mod可以通过另一子矩阵 $H_5^{\mathrm{mod}}=({\mathrm{\α}}^{5\left(i_1\right)},{\mathrm{\α}}^{5\left(i_2\right)},...,{\mathrm{\α}}^{5\left(i_n\right)})$ 而被补充成

$H^{\mathrm{mod}}=\left(\begin{array}{c}{H}_1^{\mathrm{mod}}\\ H_3^{\mathrm{mod}}\\ H_5^{\mathrm{mod}}\\ P\end{array}\right)---\left(36\right)$

校验比特的数目则可以不大于3m+1。可能的是，子矩阵

的行是线性相关的以使得只有矩阵的线性无关的行在s₅的计算中被考虑。通过子矩阵

然后通过下式确定另一校正子分量s₅

$s_5=H_5^{\mathrm{mod}}{v}^{\′}---\left(37\right)$

其可以包括不多于m个分量。

如果现在执行3比特错误的错误校正(假定是具有相邻2比特错误的3比特错误)，那么现在可以利用子矩阵来检查该校正是否被正确地执行了。如果只是基于校正子分量s₁和s₃来确定具有相邻2比特错误的3比特错误的位置j，j+1和l，那么在已经执行了将数据字v’错误校正为校正后的字v^cor之后，仅继续检查下式对于校正后的字v^cor是否适用

$H_5^{\mathrm{mod}}\·v^{\mathrm{cor}}=H_5^{\mathrm{mod}}\·(v^{\′}\⊕e)=0---\left(38\right)$

如果满足这个关系，那么3比特错误被正确地校正了。如果不满足这个关系，那么3比特错误被表示为未被正确校正的3比特错误。

除此之外，可以检测4比特错误(以及区分其与2比特错误)，对于4比特错误

$s_1^3{s}_3\⊕s_1\·s_5\⊕s_3^2\⊕s_1^6\≠0,$ 且P＝0                  (39)

以及对于2比特错误

$s_1^3{s}_3\⊕s_1\·s_5\⊕s_3^2\⊕s_1^6=0,$ P＝0，且 $s_1^3\⊕s_3\≠0---\left(40\right)$

适用。

现在将描述确定校正的3比特错误是具有相邻2比特错误的3比特错误的一个另外的可能性。

对于比特位置j，l，r处的3比特错误，下式适用

$s_1={\mathrm{\α}}^{i_j}\⊕{\mathrm{\α}}^{i_l}\⊕{\mathrm{\α}}^{i_r}---\left(41\right)$

$s_3={\mathrm{\α}}^{3i_j}\⊕{\mathrm{\α}}^{3i_l}\⊕{\mathrm{\α}}^{3i_r}---\left(42\right)$

$s_5={\mathrm{\α}}^{5i_j}\⊕{\mathrm{\α}}^{5i_l}\⊕{\mathrm{\α}}^{5i_r}---\left(43\right)$

如果相邻2比特错误存在于位置j和l处，那么

并且因此 ${\mathrm{\α}}^{i_r}=s_1\⊕K,$ 使得下式适用

$s_1^{\′}={\mathrm{\α}}^{i_j}\⊕{\mathrm{\α}}^{i_l}=s_1\⊕{\mathrm{\α}}^{i_r}=K,---\left(44\right)$

$s_3^{\′}={\mathrm{\α}}^{{3i}_j}\⊕{\mathrm{\α}}^{3i_l}=s_3\⊕{\mathrm{\α}}^{3i_r}=s_3\⊕s_1^3\⊕s_1{K}^2\⊕K{s}_1^2\⊕K^3,---\left(45\right)$

$s_5^{\′}={\mathrm{\α}}^{{5i}_j}\⊕{\mathrm{\α}}^{5i_l}=s_5\⊕{\mathrm{\α}}^{5i_r}=s_5\⊕s_1^5\⊕s_1{K}^4\⊕s_1^{4}K\⊕K^5,---\left(46\right)$

并且错误校正子的分量s₁’，s₃’和s₅’描述2比特错误，使得

$s_1^{\′3}{s}_3^{\′}\⊕s_1^{\′}{s}_5^{\′}\⊕s_3^{\′2}\⊕s_1^{\′6}=0---\left(47\right)$

必须适用，根据上式，利用等式(44)、(45)和(46)，对于具有相邻2比特错误的3比特错误结果得到下式

$s_1^6\⊕s_3^2\⊕s_1^{5}K\⊕{\mathrm{Ks}}_5\⊕K^3{s}_3\⊕K^3{s}_1^3=0---\left(48\right)$

如果这是原来不包括相邻2比特错误的3比特错误，则下式适用

$s_1^6\⊕s_3^2\⊕s_1^{5}K\⊕{\mathrm{Ks}}_5\⊕K^3{s}_3\⊕K^3{s}_1^3\≠0---\left(49\right)$

现在应该再次概括一下错误检测的可能性。首先，考虑总体奇偶性P没有被确定的情况下。

1、对于1比特错误，下式适用

· $s_1^3=s_3.$

2、对于2比特错误，下式适用

· $s_1^3\≠s_3,$

· $s_1^3{s}_3\⊕s_1{s}_5\⊕s_3^2\⊕s_1^6=0.$

3、对于随机3比特错误，下式适用

· $s_1^3\≠s_3,$

· $s_1^3{s}_3\⊕s_1{s}_5\⊕s_3^2\⊕s_1^6\≠0.$

4、对于具有相邻2比特错误的3比特错误，下式适用

· $s_1^6\⊕s_3^2\⊕s_1^{5}K\⊕{\mathrm{Ks}}_5\⊕K^3{s}_3\⊕K^3{s}_1^3=0..$

现在考虑总体奇偶性P已被确定的情况。

1、对于1比特错误，下式适用

· $s_1^3=s_3,$

·P＝1。

2、对于2比特错误，下式适用

· $s_1^3\≠s_3,$

·P＝0。

3、对于随机3比特错误，下式适用

· $s_1^3\≠s_3,$

·P＝1

4、对于另外具有相邻2比特错误的3比特错误，下式适用

· $s_1^6\⊕s_3^2\⊕s_1^{5}K\⊕K{s}_5{K}^3{s}_1^3\⊕K^3{s}_1^3=0.$

4比特错误与2比特错误的不同之处可以在于：对于4比特错误，下式适用

$s_1^3{s}_3\⊕s_1\·s_5\⊕s_3^2\⊕s_1^6\≠0,$ 且P＝0

以及对于2比特错误

$s_1^3{s}_3\⊕s_1\·s_5\⊕s_3^2\⊕s_1^6=0,$ 且P＝0

适用。

根据本发明的可能的一方面，二进制数据字中的1比特、2比特和3比特错误的校正被促进，并且特别地这里所要求的错误校正电路可被改进以使得需要最少可能的硬件工作量并且用于确定校正值的信号运行时间尽可能地低。

除此之外，在本发明的一部分方面中，将使得能够对不可校正的错误、尤其是不可校正的3比特错误进行错误检测。

根据本发明的另一方面，可以采用简单的方式来使得能够进行对任意1比特错误、任意2比特错误、以及包括相邻2比特错误的3比特错误的错误校正。

现在针对实施例来解释本发明。

图1a示出了发明的电路，其包括校正子生成器Synd12和下游解码器Dec14。校正子生成器Synd12包括用于输入n数位二进制字v’＝v₁’，...，v_n’的n比特宽的输入端11，以及用于输出具有两个m数位子校正子s₁和s₃的m’数位错误校正子s的m’个二进制输出端13。校正子生成器Synd12的m’个二进制输出端13被连接到解码器Dec14的m’个二进制输入端，解码器Dec14在其n数位输出端15处输出n数位校正向量e＝e₁，...e_n。这里，m’≥2m且n≤2^m-1适用。校正子生成器Synd12在这里被配置为使得当输入二进制字v’时，它在m’个二进制输出端输出m’分量错误校正子。这里，s是根据以下关系确定的：

s＝H^mod·v′                              (50)

矩阵H^mod＝h₁′，...，h_n′是具有n个列h₁’，...，h_n’的(m’，n)矩阵，每个列包括m’个分量。这些列的2m个第一分量通过h₁，...，h_n来指定。对于这些2m分量列h_j，针对j＝1，...，n，下式适用

$h_j=\left\{\begin{array}{c}{\mathrm{\α}}^{i_j}\\ {\mathrm{\α}}^{3\left(i_j\right)}\end{array}\right..---\left(51\right)$

此外，针对n’为偶数，对于j＝1，3，5，...，n’-1且对于n’≤n，对于在数据字v’＝v₁’，...，v_n’中相邻的比特对[j，j+1]，将H矩阵H确定为使得下式适用

${\mathrm{\α}}^{i_j}\⊕{\mathrm{\α}}^{i_{j+1}}=K.---\left(52\right)$

子校正子s₁，s₃通过下式确定

$s_1=H_1^{\mathrm{mod}}\·v^{,}---\left(53\right)$

$s_3=H_3^{\mathrm{mod}}\·v^{,}---\left(54\right)$

其中，通过下式确定(m，n)子矩阵

和

$H_1^{\mathrm{mod}}=({\mathrm{\α}}^{i_1},...,{\mathrm{\α}}^{i_n})$

$H_3^{\mathrm{mod}}=({\mathrm{\α}}^{3\left(i_1\right)},...,{\mathrm{\α}}^{3\left(i_n\right)}).$

这里，α是Ga1ois域GF(2^m)的元素，在向量表达式中是m分量的二进制向量，并且α的指数应被解释为模2^m-1。K是m数位二进制向量，其不等于子矩阵

的任何列，即对于其，针对j＝1，...，n，

适用。优选地，α是Galois域GF(2^m)的本原元素。如果n是偶数，n’＝n可以适用，并且对于n是奇数，n’＝n-1可以适用。为了表示的简单起见，我们描述针对n为偶数的n’＝n的情况，以及针对n为奇数的n’＝n-1的情况。

为了使表示尽可能容易地可理解，这里在校正子生成器Synd12的每个相邻输入端处输入相邻比特，使得相邻比特对通过对[1，2]，[3，4]，[5，6]...被描述。当然也可以交换v’的比特v₁’，v₂’，...，v_n’，使得随后得到二进制字

其中

i(vert)＝π(i)

适用并且π(i)可以描述索引1，...，n的置换π。

根据条件在索引的置换之后，随后简单地产生条件 ${\mathrm{\α}}^{\mathrm{\π}\left(i_j\right)}\⊕{\mathrm{\α}}^{\mathrm{\π}(i_j+1)}=K.$

例如，如果第一个比特没有被交换，并且第二个比特被第七个比特交换，那么代替 ${\mathrm{\α}}^{i_1}\⊕{\mathrm{\α}}^{i_2}=K,$ 现在简单地是 ${\mathrm{\α}}^{i_1}\⊕{\mathrm{\α}}^{i_7}=K.$

此外：如果数据字v’＝v₁’，...，v_n’是例如从其存储单元可以存储大于两个状态(例如三个或四个状态)的存储器中被读出的，那么对应于所存储的二进制数据字中的存储单元的状态的那些比特可以被称为是相邻比特。为了不使描述比需要的更复杂，相邻比特对在这里被描述为对[1，2]，[3，4]，[5，6]...。数据字v’＝v₁’，...，v_n’可以从具有H矩阵H^mod的码的代码字v的错误中得出。如果不存在错误，那么v’＝v并且对于错误校正子s，以下适用s＝H^mod·v＝0。

如果存在错误，那么v′≠v，或者

，其中，已经描述的，e＝e₁，...，e_n如可以被称为错误向量。如果v’和v相差r比特，这就是r比特错误。在这种情况下，错误向量e的对应r个分量等于1。错误向量的全部其它分量则等于0。

实现解码器Dec14，以使得：

·当将错误校正子s＝0应用到其输入端时，在其输出端其输出校正向量e＝0，

·当将具有子校正子s₁，s₃的错误校正子s应用到其输入端时，在

$s_1={\mathrm{\α}}^{i_j},s_3={\mathrm{\α}}^{3\left(i_j\right)},$

的情况下(并且奇数个数的比特被误用)，其输出e_j＝1，且e₁＝0(针对t≠j)，

·当将具有子校正子s₁，s₃的错误校正子s应用到其输入端时，在

$s_1={\mathrm{\α}}^{i_j}\⊕{\mathrm{\α}}^{i_r},s_3={\mathrm{\α}}^{3\left(i_j\right)}\⊕{\mathrm{\α}}^{3\left(i_r\right)}$

的情况下(并且偶数个数的比特被误用)，其输出e_j＝1，e_r＝1，且e₁＝0(针对t≠j，r)，

·当将具有子校正子s₁，s₃的错误校正子s应用到其输入端时，在

$s_1={\mathrm{\α}}^{i_j}\⊕{\mathrm{\α}}^{i_j+1}\⊕{\mathrm{\α}}^{i_l},s_3={\mathrm{\α}}^{3i_j}\⊕{\mathrm{\α}}^{3i_{j+1}}\⊕{\mathrm{\α}}^{3i_l}$

的情况下且在的情况下，其中K不是矩阵

的任何列，并且奇数个数的比特被误用，并且对于n是偶数时j∈{1，3，...，n-1}且n是奇数时j∈{1，3，...，n-2}适用，其输出校正向量的比特e_j＝1，e_j+1＝1且e₁＝1和e_t＝0(t≠j，j+1，l)。

为了确定偶数或者奇数个数的比特是否已经被误用，可以使用数据字v’的总体奇偶性 $s_P=v_1^{\′}\⊕...\⊕v_n^{\′}.$

这可以通过例如H矩阵H^mod来完成，H矩阵H^mod现在包括m’＝2m+1行，并且H矩阵H^mod的列h₁’，...，h_n’被确定为

$h_j^{\′}=\left\{\begin{array}{c}{\mathrm{\α}}^{i_j}\\ {\mathrm{\α}}^{3\left(i_j\right)}\\ 1\end{array}\right.$

并且H矩阵H^mod具有形式

$H^{\mathrm{mod}}=\left(\begin{array}{c}{H}_1^{\mathrm{mod}}\\ H_3^{\mathrm{mod}}\\ P\end{array}\right)$

其中，

图1b中示出了发明的电路的相应实施方式。在图1b中m’＝2m+1适用。校正子生成器12a包括用于输入数据字v’的n个二进制输入端，以及被供给到解码器14a的(2m+1)个二进制输入端且载有分量s₁，s₃和s_P的(2m+1)个二进制输出端。这里，当数据字的偶数个数的分量被误用时，s_P＝0。当数据字v’的奇数个数的分量被误用时，s_P＝1适用。数据字v’在XOR电路16a中被一个分量接一个分量地(即，逐分量地)与校正向量的分量e＝e₁，...，e_n相组合成v^cor，其中v^cor是校正后的数据字。

确定偶数个数或者奇数个数的分量或比特是否已在数据字v’中被误用的另一种可能性可以是仅仅选择包括奇数个1的列

作为子矩阵

的列。在这种情况下，子校正子

在偶数个数的比特在v’中已被误用时包括偶数个数的1，以及在奇数个数的比特在v’中已被误用时包括奇数个数的1，使得那么对于奇偶性s_P，下式适用

$s_P=s_{1_1}\⊕...\⊕s_{1_m}$

并且该奇偶性是从错误校正子的子校正子s₁确定的。

在图1c的电路中，m’＝2m。H矩阵H^mod是由子矩阵

和

组成的，其中子矩阵

只包括具有奇数个数1的列。校正子生成器Synd12b在其m’＝2m比特宽的输出端上输出每个都是m比特宽的子校正子s₁和s₃，其中将子校正子作为输入值应用到解码器Dec14b的2m比特宽的输入端，解码器Dec14b通过s₁分量的XOR组合从子校正子s₁确定奇数或者偶数个数的分量在v’中是否被误用。

为了确定偶数个数或者奇数个数的数据字的分量是否被误用，还可以仅仅选择包括奇数个1的这样的列作为子矩阵

的列。在这种情况下，子校正子

在偶数个数的比特在v’中已被误用时包括偶数个数的1以及在奇数个数的比特在v’中已被误用时包括奇数个数的1，使得随后对于奇偶性s_P下式适用

$s_P=s_{3_1}\⊕...{\⊕s}_{3_m}.$

为了确定偶数个数或者奇数个数的数据字的分量是否被误用，还可以将H矩阵H^mod的列选择为使得可能既属于

又属于

的列的分量的某子集包括奇数个数的1。然后通过子校正子s₁和s₃的对应分量可以再次通过XOR组合确定奇偶性s_P。

当校正子生成器除了校正子分量s₁和s₃还输出形成奇偶性的附加校正子分量s_P时，则奇偶性s_P被提供作为解码器Dec14a的输入端处的输入值。如果可以从校正子s＝s₁，s₃的分量确定奇偶性s_P，例如通过XOR从s₁分量来确定，那么奇偶性s_P可以通过解码器被内部地确定，例如通过错误校正子的分量的简单XOR组合。

解码器Dec14，14a，14b可以如下那样被实现。解码器Dec14a可以包括m’＝2m+1个输入端，它们是来自校正子生成器Syn12a的2m+1个输出端的下游，当奇偶性s_P是通过校正子生成器直接提供时，校正子生成器载有错误校正子s＝s₁，s₃，s_P的分量，或者解码器Dec14b可以包括连接到校正子生成器Synd12的2m个输出端的m’＝2m个输入端。提供解码器Dec14，14a，14b的n个二进制输出端，以用于输出n个二进制校正值e₁，...，e_n，以便用于校正二进制字v’的相应比特v₁’，...，v_n’，其中校正值e₁，...，e_n是从错误校正子s和二进制向量K的值被确定的。解码器Dec被配置为使得在数据字v’中的1比特错误或2比特错误的情况下，当满足以下等式时，其在其第j个输出端处输出校正值e_j＝1(j＝1，...，n)

$s_1^3\⊕s_3\⊕s_1^2{\mathrm{\α}}^{i_j}\⊕s_1{\mathrm{\α}}^{2i_j}=0$

并且当满足以下等式时，其在其第i个输出端处输出校正值e_j＝0

$s_1^3\⊕s_3\⊕s_1^2{\mathrm{\α}}^{i_j}\⊕s_1{\mathrm{\α}}^{2i_j}\≠0.$

在3比特错误的情况下，当满足以下等式时，解码器在其第j个输出端处输出校正值e_i＝1(j＝1，...，n)

$s_1^3\⊕s_3\⊕s_1^{2}K\⊕s_1{K}^2\⊕K^2{\mathrm{\α}}^{i_j}\⊕{\mathrm{K\α}}^{{2i}_j}=0$

或者

$s_1\⊕K={\mathrm{\α}}^{i_j}$

并且在3比特错误的情况下，当以下两个等式都适用时，它在其第j个输出端处输出校正值e_j＝0(j＝1，...，n)

$s_1^3\⊕s_3\⊕s_1^{2}K\⊕s_1{K}^2\⊕K^2{\mathrm{\α}}^{i_j}\⊕{\mathrm{K\α}}^{2i_j}\≠0$

以及还有

$s_1\⊕K\≠{\mathrm{\α}}^{i_j}$

这里，形成矩阵

中的第j列。

图2a示出了发明的解码器Dec2的一种可能的实施方式。在图2a中，假定类似于图1b中的校正子生成器Synd12a的校正子生成器在其(2m+1)比特宽的输出端处输出错误校正子s＝s₁，s₃，s_P，该错误校正子被应用于解码器2的对应输入行。图2a中的解码器是从子电路Dec1(21)和n个其它子电路Dec2₁(221)...，Dec2_j(22j)...，Dec2_n(22n)而建立的。子电路Dec1(21)充当辅助子电路，其被配置为基于第一校正子部分s₁、第二校正值部分s₃和相同的列向量K而形成至少一个辅助信号。所述n个其它子电路Dec2₁(221)到Dec2_n(22n)形成多个解码器子电路。每个解码器子电路Dec2₁(221)到Dec2_n(22n)与二进制字v’的特定比特关联。每个解码器子电路Dec2₁到Dec2_n被配置为用于接收所述至少一个辅助信号并用于确定校正向量e的对应校正值。为此，每个解码器子电路Dec2_j被配置为针对奇偶矩阵H^mod的特定列向量分析辅助信号“3比特错误”、

以及第一校正子分量s₁，其中列向量h_j对应于二进制字v’的特定关联比特。通常，所述多个解码器子电路包括n个解码器子电路，即，对于二进制字v’的每个比特有一个解码器子电路。根据某些实施例，然而可能的是，存在小于n个的解码器子电路。所述多个解码器子电路还可以被称为比特相关(bit-related)或比特关联(bit-associated)子电路。所述多个解码器子电路Dec2₁到Dec2_n提供关于校正值e₁到e_n的并行处理，这能够提供对错误校正向量e的快速和高效的确定。例如，在通过商业合成工具进行的电路优化之后，这些电路可以被联合地优化。

载有子校正子s1，s3，sP的值的解码器的输入端被直接连接到子电路Dec121的2m+1＝m’个输出端，以用于形成信号：

·“3比特错误”

·

·

这些信号是子电路Dec121在其连接到每个子电路Dec2_j(j＝1，...，n)的对应三个输入端的输出端处所提供的。在每个子电路Dec2_j的第四输入端上，应用子校正子s₁。

1比特宽的信号“3比特错误”指示是否存在3比特错误。m比特宽的信号

在(s₁，s₃)≠0时等于

并且在(s₁，s₃)＝0时等于

m比特宽的值是通过子校正子s₁，s₃和常量向量K而被确定的。子电路Dec2_j22_j在它们的每个1比特宽的输出端处输出校正值e_j。

在图2b中，示出了用于形成以下信号的子电路Dec1’21a

·3比特错误

·

·

该子电路在子校正子s₁，s₃被应用到其m’＝2m比特宽的输入端时在其输出端输出这些信号。这里假定奇偶性s_P是由子电路Dec1’根据校正子分量s₁，s₃内部地导出的。否则，子电路Dec1’实现与图2a的子电路Dec1相同的功能。(辅助)子电路Dec1，Dec1’确定解码器子电路Dec2₁到Dec2_n中的若干个所需的一个或多个辅助信号。通常，子电路Dec1，Dec1’所提供的辅助信号被全部解码器子电路Dec2₁到Dec2_n所使用。以这种方式，所提出的用于校正错误的电路是高效的，因为多次被需要的信号仅仅被生成一次并且使得对于解码器子电路Dec2₁到Dec2_n可用以用于其它用途。

图3a示出了图2a的子电路Dec1的特定实施方式，其中如图2a所示，奇偶性s_P由图1b中的校正子生成器Synd12a提供。图2a中的解码器Dec2的子电路Dec121继而由以下组成，或者包括以下：用于确定值的子电路31、用于确定值

的子电路32、具有m个输入端和一个输出端的OR(或)电路33，具有两个二进制输入端和一个输出端的AND(与)门34、具有2m个输入端和一个输出端的NOR(或非)电路35、具有两个输入端(每个是m比特宽)和m比特宽的一个输出端的XOR(异或)电路36以及具有两个1比特宽的输入端和一个1比特宽的输出端的XOR门37。

子电路31包括两个m比特宽的输入端，子校正子s₁和s₃被应用到这两个输入端。它确定值

并在其m比特宽的输出端处将该值输出。如果那么

将这个电路作为具有给定功能的组合电路来实现对于本领域技术人员而言并不困难。例如，这个子电路可以实现为组合电路。例如可以合成具有m个输入端和m个输出端以用于经由函数

的值的表格来形成

的组合电路。这个电路的m个输出随后可以利用s₃被一个分量接一个分量地被异或。

NOR电路35的2m比特宽的输入端被连接到载有子校正子s₁和s₃的行。这个电路恰好在s₁＝s₃＝0且不存在错误时输出值1。NOR电路35的输出端被供给到XOR门37的第一输入端，XOR门37的第二输入端例如被连接到子电路31的m数位输出端的最低有效位并且其输出端载有值

的最低有效位。当s₁＝s₃＝0时，m比特宽的值

和

的差别在于它们的最低有效位。在这种情况下，

的最低有效位的值等于1，而

的最低有效位的值等于0。如果s₁，s₃≠0，那么

和

不会不同。

这是当s₁，s₃＝0时用于

的特殊实施方式，其可以采用不同的方式来实现。例如XOR门可以由OR门替换。同样，NOR门35的输出信号可以与子电路31的输出端的较高有效位相组合，或者NOR门35的输出信号可以与子电路31的输出端的若干比特相组合。

子电路31的m比特宽的输出端被供给到OR电路33的m比特宽的输入端，OR电路33的1比特宽的输出端被连接到AND门34的第一输入端，并且其第二输入端被连接到载有奇偶性信号s_P的输入端，并且其输出端载有信号“3比特错误”。当

且s_P＝1时，这个信号“3比特错误”等于1。

载有子校正子s1的输入端还被连接到子电路32的m比特宽的输入端以用于确定值

子电路32的m比特宽的输出端被供给到XOR电路36的2m比特宽的第一输入端，XOR电路36的第二m比特宽的输入端被连接到子电路31的输出端，并且XOR电路36在其输出端处输出信号

在图3b中，示出了用于实现图2b的子电路Dec1’21a的的实施例，其中与子电路Dec121相对照，在子电路的输入端处没有提供奇偶性信号s_P，而是从子校正子s₁将其导出。这里假定子矩阵H₁的每列包括奇数个1。

与图3a的相应电路部分没有不同的图3b的电路部分用相同的参考数字来表示，并且这里将不再进行描述。在图3b中，载有子校正子s₁的子电路21a的输入端被连接到具有m个输入端和一个二进制输出端的XOR电路38的m比特宽的输入端，XOR电路38在其输出端处输出值

在图3c中，示出了子电路Dec1”21b的一种可能的实现方式，除了图3a的子电路的输出端以外，其还包括用于输出信号“1比特错误”、“2比特错误”和“3比特错误”的输出端。与图3a的相应电路部分没有不同的图3b的电路部分由相同的参考数字来表示，并且这里不再进行描述。载有奇偶信号sP的输入端另外被连接到具有两个输入端和一个输出端的AND门310的第一输入端，且被反向(例如通过反相器)连接到另一个AND门39的第一输入端，该AND门39具有两个输入端和一个输出端。OR电路33的输出端另外被连接到AND门39的第二输入端，并被反向连接到在其输出端处载有信号“1比特错误”的AND门310的第二输入端。AND门39在其输出端处输出信号“2比特错误”。

图4示出了图2a的子电路Dec2_j22_j的一种可能的实现方式。

对于连接到多路复用器44的控制输入端的1比特宽的输入端410，应用二进制信号“3比特错误”，该二进制信号在存在3比特错误时呈现出值1，并且在不存在3比特错误时呈现出值0。

对于连接到XOR电路42的m比特宽的第一输入端的m比特宽的输入端411，应用信号

对于连接到XOR电路45的m比特宽的第一输入端的m比特宽的输入端412，应用信号

对于XOR电路45的m比特宽的第二输入端，应用常量值

这个常量值

是通过矩阵H^mod的列向量h_j的(第一或上面)部分

而被确定的，使得它对于每个独立的解码器子电路Dec2_j而不同。换句话说，列向量h_j的部分

用作参数，或者用参数来表示解码器子电路Dec2_j。XOR电路45的输出端被供给到NOR电路47的m比特宽的输入端，该NOR电路47具有m个二进制输入端和一个连接到OR门47的第一输入端的二进制输出端，并且该OR门的1比特宽的输出被导向多路复用器44的1输入端内。

对于同时被连接到子电路41的m比特宽的输入端以用于实现函数

以及被连接到XOR电路48的m比特宽的第一输入端的m比特宽的输入端413，应用子校正子s₁的m比特宽的值。通过对应于二进制字v’的第j比特的列向量h_j的部分来对函数

进行参数表示。

子电路41的m比特宽的输出端被连接到XOR电路42的m比特宽的第二输入端，XOR电路42的m比特宽的输出被导向NOR电路43的m比特宽的输入端中，NOR电路43的1比特宽的输出端被连接到多路复用器44的0输入端，多路复用器44其输出端41处输出校正值e_j。

对于XOR电路48的m比特宽的第二输入端，应用常量值

(通过

而被参数化)。XOR电路48的m比特宽的输出端被连接到NOR电路49的m比特宽的输入端，NOR电路49的1比特宽的输出端被连接到OR门46的第二输入端。

显而易见，本领域技术人员可以优化图4的子电路Dec2_j。将描述优化可能性的例子。

利用XOR电路45，将应用到输入端412的m数位值

逐分量地与常量m数位二进制向量

进行异或。精确地对于等于1的二进制向量

的那些分量，将的对应分量反相，而对于其二进制向量

的分量等于0的那些分量没有被反相。优化实现可以简单地针对经由相应反相器被连接到NOR电路46的m分量输入端的输入端412，针对其可以实现XOR电路45的功能。

通过XOR电路48，将常量值

逐分量地与具有被应用于输入端413的m分量的子校正子s₁进行异或。这里在功能上等于通过反相器将输入端413的m个输入行连接到NOR电路49的m个二进制输入端，而反相器是NOR电路49的输入端的上游，通过常量向量

对NOR电路49的输入端进行反相，即对于NOR电路49的输入端这个向量的对应分量等于1。

如已经论述的，除了由

和

确定的校正子分量s₁和s₃，可以使用另一校正子分量

以在具有相邻2比特错误的3比特错误和没有包括相邻2比特错误的其它3比特错误之间进行区分。

如果考虑总体奇偶性，则所用的码包括3m+1个校验比特。

如果所用的码包括3m+1个校验比特，则现在将参考图1d说明如何在根据本发明正确校正的具有相邻2比特错误的3比特错误和没有被正确校正且没有包括相邻2比特错误的3比特错误之间，进行区分。

对于具有相邻2比特错误的3比特、2比特和1比特错误的错误校正，在图1d中仅仅使用了全部(2m+1)比特宽的校正子分量s₁，s₃和s_P，它们对应于(2m+1)个第一校验比特，尽管该码包括大于2m+1个且最大是3m+1个的校验比特，其中，其它的校验比特没有被用于校正而仅仅用于确定校正是否被正确执行。

这对于以最简单的方式来实现校正可能是有利的，这可以表现在校正电路的相对有限的面积要求和相对快速的校正中。

因此，校正子生成器Synd12c在其输出端处仅仅输出(2m+1)比特宽的校正子分量s₁，s₃，s_P，该输出端被连接到解码器Dec14c的输入端，并且校正子生成器Synd12c具有(2m+1)数位的输出端，其被连接到解码器Dec14c的(2m+1)比特宽的输入端。从校正子分量s₁，s₃，s_P，解码器Dec14c形成n分量校正向量e＝e₁，...，e_n，该校正向量在XOR电路16c中被逐分量地与数据字v’组合成v^cor并在XOR电路16c的输出端处被输出。除此之外，XOR电路16c的输出端还被导向错误指示电路17c的m比特宽的输入端中，错误指示电路17c在错误被正确校正时输出错误信号q＝q₂且在错误没有被正确校正时输出错误信号q＝q₁≠q₂。错误指示电路可以例如形成错误信号q，其中

该错误信号q是从子校正子

的分量

而被形成的，其中

$s_5^{\′}=H_5^{\mathrm{mod}}\·v^{\mathrm{cor}}=({\mathrm{\α}}^{5i_1},...,{\mathrm{\α}}^{{5i}_n})\·v^{\mathrm{cor}}---\left(56\right)$

并且当s₅′≠0，...，0时，错误指示电路可以输出错误信号q₁＝1。如果q＝q₁＝1，则存在不包括相邻2比特错误且没有被正确校正的3比特错误。当

时，输出q＝q₂＝0。那么存在包括相邻2比特错误且被正确校正的3比特错误。错误信号E(3比特错误)是子校正子s₅’的分量的逐分量异或组合。当然，当没有存在错误且s＝0或者1比特错误或2比特错误已被正确校正时，也输出错误信号q＝q₂＝0。

还可以通过OR操作仅仅将子校正子s₅’的分量的子集组合成错误信号q。当矩阵

的行是线性相关或等于0时，这是特别有用的。还可以形成错误信号

其中F可以是F(0，...，0)＝0的线性或者非线性Boolean函数。

这里，相邻2比特错误总是发生在所述位置[1，2]，[3，4]，[5，6]...的相邻2比特错误。

现在将公开用以在没有包含相邻2比特错误且可能没有被正确校正的3比特错误与包含相邻2比特错误且可利用校正子分量s₅被正确校正的3比特错误之间进行区分的另一种可能性。

当考虑总体奇偶性时，所用码例如同样包括(3m+1)个校验比特，并且当不考虑总体奇偶性时其包括(3m)个校验比特。

图1e示出了发明的电路，其包括校正子生成器Synd12d，校正子生成器Synd12d根据以下矩阵H^mod形成错误校正子s＝s₁，s₃，s₅，s_P

$H^{\mathrm{mod}}=\left(\begin{array}{c}{H}_1^{\mathrm{mod}}\\ H_3^{\mathrm{mod}}\\ H_5^{\mathrm{mod}}\\ P\end{array}\right)$

且在校正子生成器Synd12d的被连接到解码器Dec14d的输入端的输出端处将其输出。

解码器Dec14d包括用于错误指示的信号。用于错误指示的信号可以包括指示是否存在3比特错误的信号，并且它们可以包括指示可能被正确校正或者可能没有被正确校正的具有相邻2比特错误的3比特错误是否存在的信号。

图2c示出了子电路Dec1”21b，子电路Dec1”21b具有用于输入子校正子s₁的m比特宽的第一输入端、用于输入子校正子s₃的m比特宽的第二输入端、用于输入子校正子sx的m比特宽的第三输入端以及用于输入子校正子s_P的1比特宽的第四输入端和用于输出信号“3比特错误”的1比特宽的第一输出端、用于输出值

的m比特宽的第二输出端、用于输出信号

的m比特宽的另一输出端以及用于输出信号“不可校正的3比特错误”的1比特宽的另一输出端。

在下式适用时，信号“不可校正的3比特错误”等于1

$s_1^6\⊕s_3^2\⊕s_1^{5}K\⊕s_1^3{K}^3\⊕K_{s5}\⊕K^3{s}_3\≠0---\left(57\right)$

等式(56)中所述的函数的直接实现可以指示是否存在未校正的3比特错误。

还要注意某些修改。

替代校正子分量

可以仅仅实现校正子分量

的子集，如果其以一定的可能性足以检测存在可校正或不可校正的3比特错误的话。

还可以例如(线性地或者非线性地)将m个分量

压缩成m^*＜m个分量。

还要注意降低解码器的工作量的特定可能性。

如果存在包括相邻2比特错误的3比特错误，那么在可校正3比特错误的情况下，总是在两个连续的比特i_j和i_j+1中进行校正，使得连续的校正值

和

在可校正3比特错误的情况下总是相等。

那么以下两项总是都等于1或都等于0。

以及

这有助于针对每隔一个校正值节省图4中的m输入NOR电路47，因为该NOR电路的输出可以同样被用作子电路22i_j和子电路22i_j+1两者中的相应NOR电路的输出。

还很清楚的是，子电路22i，i＝1，...，n可以通过一个合成工具被一起优化。

以下参考例子，将示出对H矩阵的确定。

作为示例选择m＝4和Galois域GF(2⁴)。在表1中给出了在模多项式m(x)＝1+x+x⁴的情况下Galois域GF(2⁴)的元素在指数表达式、多项式表达式和向量表达式中的常见表达式。

表1示出了GF(2⁴)的元素在指数表达式α⁰，α¹，...，α¹⁴和0中、在具有多项式变量x的作为小于或等于3级的16多项式p(x)＝α₀+α₁x+α₂x²+α₃x³的多项式表达式中、以及作为4数位二进制向量(其分量是相应多项式的系数)的已知表达式。Galois域的模多项式是m(x)＝1+x+x⁴。

由此从表1可以看出，元素p(x)＝1(在多项式表达式中)和二进制向量1，0，0，0(在向量表达式中)对应于元素α⁰(在指数表达式中)，如其在第一行中被描述的那样。可以从第三行推断出表达式p(x)＝x和0，1，0，0对应于α¹。

如已知的，向量表达式中的两个元素的增加被执行为分量的逐分量加模2。

表1：不同形式的表达式中的由本原模多项式m(x)＝1+x+x⁴生成的GF(2⁴)的元素：

通过对多项式变量的幂或基数的相应系数的异或来完成多项式表达式中的加法。

两个元素αⁱ和α^j的相乘产生元素α^k，其中k＝i+j以(2^m-1)为模=i+j以15为模。多项式表达式中的两个多项式p₁(x)和p₂(x)的相乘产生多项式p₃(x)，其中p₃(x)＝p₁(x)·p₂(x)以m(x)为模，其中m(x)是Galois域的模多项式。

在Galois域GF(2⁴)中，有15个不同的列：

$h_1,...,h_{15}=\begin{array}{ccccc}{\mathrm{\α}}^0& {\mathrm{\α}}^1& {\mathrm{\α}}^2& ...& {\mathrm{\α}}^{14}\\ {\mathrm{\α}}^0,& {\mathrm{\α}}^3,& {\mathrm{\α}}^6,& ...,& {\mathrm{\α}}^{12}\end{array}$

如果码长是n＝14，那么可以从这些列中删除例如列[α¹²，α⁶]T，其中

${\mathrm{\α}}^{12}=\left(\begin{array}{c}1\\ 1\\ 1\\ 1\end{array}\right)={\left[\mathrm{1,1,1,1}\right]}^T=K.$

现在可以形成创造性的H矩阵

$H^{\mathrm{mod}}=(h_1,...,h_{14})=\left(\begin{array}{ccccc}{\mathrm{\α}}^{i_1},& {\mathrm{\α}}^{i_2},& {\mathrm{\α}}^{i_3},& ...,& {\mathrm{\α}}^{i_{14}}\\ {\mathrm{\α}}^{{3i}_1},& {\mathrm{\α}}^{{3i}_2},& {\mathrm{\α}}^{{3i}_3}& ...,& {\mathrm{\α}}^{3i_{14}}\end{array}\right)$

$H_1^{\mathrm{mod}}=({\mathrm{\α}}^{i_1},{\mathrm{\α}}^{i_2},{\mathrm{\α}}^{i_3},...,{\mathrm{\α}}^{i_{14}})$

以及

$H_3^{\mathrm{mod}}=({\mathrm{\α}}^{{3i}_1},{\mathrm{\α}}^{{3i}_2},{\mathrm{\α}}^{{3i}_3},...,{\mathrm{\α}}^{3i_{14}})$

使得每个相邻列对[1，2]、[3，4]、[5，6]、[7，8]、[9，10]、[11，12]、[13，14]的前四个分量的逐分量异或总和都等于K＝[1，1，1，1]^T。这里矩阵H^mod的列的前四个分量对应于

的列。因此，可以确定以下矩阵：

校正子生成器Synd实现以下关系：

$s=s_1,s_3=s_{1_1},s_{1_2},s_{1_3},s_{1_4},s_{3_1},s_{3_2},s_{3_3},s_{3_4}=H^{\mathrm{mod}}\·(v_1^{\′},...,v_{14}^{\′})$

或者是以乘法形式

$s_{1_1}=v_1^{\′}\⊕v_4^{\′}\⊕v_6^{\′}\⊕v_8^{\′}\⊕v_9^{\′}\⊕v_{12}^{\′}\⊕v_{13}^{\′},$

$s_{1_2}=v_2^{\′}\⊕v_3^{\′}\⊕v_6^{\′}\⊕v_8^{\′}\⊕v_9^{\′}\⊕v_{11}^{\′}\⊕v_{14}^{\′},$

$s_{1_3}=v_2^{\′}\⊕v_4^{\′}\⊕v_5^{\′}\⊕v_8^{\′}\⊕v_{10}^{\′}\⊕v_{11}^{\′}\⊕v_{13}^{\′},$

$s_{1_4}=v_2^{\′}\⊕v_4^{\′}\⊕v_6^{\′}\⊕v_7^{\′}\⊕v_{11}^{\′}\⊕v_{12}^{\′}\⊕v_{14}^{\′},$

$s_{3_1}=v_1^{\′}\⊕v_8^{\′}\⊕v_9^{\′}\⊕v_{11}^{\′}\⊕v_{12}^{\′}\⊕v_{14}^{\′},$

$s_{3_2}=v_4^{\′}\⊕v_7^{\′}\⊕v_9^{\′}\⊕v_{12}^{\′}\⊕v_{13}^{\′},$

$s_{3_3}=v_5^{\′}\⊕v_6^{\′}\⊕v_9^{\′}\⊕v_{11}^{\′}\⊕v_{14}^{\′},$

$s_{3_4}=v_2^{\′}\⊕v_3^{\′}\⊕v_4^{\′}\⊕v_5^{\′}\⊕v_5^{\′}\⊕v_7^{\′}\⊕v_{10}^{\′}\⊕v_{12}^{\′}\⊕v_{13}^{\′}\⊕v_{14}^{\′},$

对于本领域技术人员而言，以上内容的实现没有困难，例如利用XOR门。

如果考虑总体奇偶性s_P，那么要实现另一

此外，可以通过子矩阵

来补充矩阵H^mod

$H_5^{\mathrm{mod}}=({\mathrm{\α}}^{5i_1},{\mathrm{\α}}^{5i_2},{\mathrm{\α}}^{3i_3},...,{\mathrm{\α}}^{5i_{14}})$

这里，矩阵

的具体形式是：

$\begin{array}{c}{H}_5^{\mathrm{mod}}=\left({\mathrm{\α}}^1{\mathrm{\α}}^8{\mathrm{\α}}^{11}{\mathrm{\α}}^{11}{\mathrm{\α}}^8{\mathrm{\α}}^{11}{\mathrm{\α}}^1{\mathrm{\α}}^{11}{\mathrm{\α}}^{11}{\mathrm{\α}}^1{\mathrm{\α}}^8{\mathrm{\α}}^6{\mathrm{\α}}^8{\mathrm{\α}}^1\right)\\ =\left(\begin{array}{cccccccccccccc}1& 1& 0& 0& 1& 0& 1& 0& 0& 1& 1& 1& 1& 1\\ 0& 1& 1& 1& 1& 1& 0& 1& 1& 0& 1& 1& 1& 0\\ 0& 1& 1& 1& 1& 1& 0& 1& 1& 0& 1& 1& 1& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0\end{array}\right)\end{array}$

第三行等于第二行，并且第四行与0完全相同，使得在校正子生成器的实现中，作为

的另外的校正子分量，仅如下两个校正子分量被实现作为XOR电路，因为这里和

适用。

$s_{5_1}=v_1^{\′}\⊕v_2^{\′}\⊕v_5^{\′}\⊕v_7^{\′}\⊕v_{10}^{\′}\⊕v_{11}^{\′}\⊕v_{12}^{\′}\⊕v_{13}^{\′}\⊕v_{14}^{\′},$

$s_{5_2}=v_2^{\′}\⊕v_3^{\′}\⊕v_4^{\′}\⊕v_5^{\′}\⊕v_8^{\′}\⊕v_9^{\′}\⊕v_{11}^{\′}\⊕v_{12}^{\′}\⊕v_{13}^{\′},$

在下面将说明如何可以实现子电路31以用于实现函数

可以实现函数

作为具有m＝4个二进制输入

和m＝4个二进制输出y₁，y₂，y₃，y₄的组合电路。这个电路的输出然后被逐分量地与校正子分量

进行异或。

函数 $y=y_1,y_2,y_3,y_4=s_1^3$ 的值表被表示在表2中。

表2：GF(2⁴)中的值表

该表是通过读取用于16个4数位二进制向量

(其代表Galois域GF(2⁴)的元素的向量表达式)中的每一个的相应指数表达式α^j、确定k＝3j以15为模并读取用于α^k(其代表

的二进制值)的表中相应的向量表达式而得到的。

对于本领域技术人员而言，将值表实现作为组合电路是没有困难的。

现在将描述用于实现函数

的子电路32的一种可能的实现方式。这里，选择K＝α¹²作为例子。在多项式表达式中，根据表1，α¹²对应于多项式K(x)＝1+x+x²+x³。所考虑的Galois域的模多项式是m(x)＝1+x+x⁴。在多项式表达式中，s₁是由多项式来表示的，且对于多项式表达式中的z(x)，下式适用

$z\left(x\right)=(s_1{\left(x\right)}^{2}K\·\left(x\right)\⊕s_1\left(x\right)\·K^2\left(x\right))\mathrm{mod}(1+x+x^4)$

从上式通过直接计算针对z(x)＝z₁+z₂x+z₃x²+z₄x³得到

$z\left(x\right)=(s_{1_1}+s_{1_4})+(s_{1_2}+s_{1_4})x+(s_{1_1}+s_{1_2}+s_{1_3}+s_{1_4})x^2+(s_{1_2}+s_{1_3})x^3.$

下式适用

$z_1=s_{1_1}+s_{1_4}$

$z_2=s_{1_2}+s_{1_4}$

$z_3=s_{1_1}+s_{1_2}+s_{1_3}+s_{1_4}$

$z_4=s_{1_2}+s_{1_3},$

其中，加法是以2为模，其逻辑上对应于异或组合。在图5中示出了用于本实施例的相应子电路的实施方式。

图5的电路包括载有值

的四个二进制输入端55、56、57和58，以及输出值z₁、z₂、z₃和z₄的四个二进制输出端59、510、511和512，以及四个XOR门51、52、53和54，每个XOR门包括两个输入端和一个输出端。XOR门51的第一输入端被连接到电路输入端55，同时该门的第二输入端被连接到输入端58。XOR门51的输出端被同时连接到电路输出端59以及XOR门54的第一输入端。XOR门54的第二输入端被连接到XOR门53的输出端，XOR门53的输出端同时还被连接到输出端512。XOR门54的输出端被连接到输出端511。

XOR门52的第一输入端被连接到输入端56，输入端56同时还被连接到XOR门53的第一输入端。XOR门52的第二输入端被连接到输入端58。XOR门53的第二输入端被连接到输入端57。XOR门52的第一输入端被连接到输入端56，输入端56同时还被连接到XOR门53的第一输入端。XOR门52的第二输入端被连接到输入端58。门52的输出端被连接到输出端510。XOR门53的第二输入端被连接到输入端57。

此外，将描述用于实现函数

的子电路41的实现方式的例子。

在多项式表达式中，s(x)同样被表达作为多项式

作为例子，选择i_j＝4，即对于α^j，选择α⁴。在矩阵

中，根据等式(58)，α⁴对应于第九列。从表1中可以看出，在多项式表达式中，α⁴对应于多项式α⁴(x)＝1+x。因此，对于u(x)，得到

u(x)＝s₁(x)·(1+x)²+s₁(x)²·(1+x)mod(1+x+x⁴)，

从上式通过直接计算得到下式

$u\left(x\right)=s_{1_4}+(s_{1_1}+s_{1_2}+s_{1_3})x+(s_{1_1}+s_{1_2})x^2+s_{1_4}{x}^3$

并且因此

$u_1=s_{1_4}$

$u_2=s_{1_1}+s_{1_2}+s_{1_3}$

$u_3=s_{1_1}+s_{1_2}$

$u_4=s_{1_4}$

这里，多项式系数的加法中的操作+同样被解释为以2为模，并且它对应于异或(XOR)组合。在图6中示出了用于实现以下函数的相应子电路

$u=s_1\·{\mathrm{\α}}^8+s_1^2\·{\mathrm{\α}}^4$

图6的电路包括四个输入端63、64、65和66(在那里值

和

被输入)以及四个输出端67、68、69和610(在那里值u₁，u₂，u₃和u₄被输出)。它包括两个XOR门61和62，每个具有两个输入端和一个输出端。

输入端63被连接到XOR门61的第一输入端，输入端64被连接到XOR门61的第二输入端。XOR门61的输出端被连接到XOR门62的第一输入端并且同时被连接到输出端69。输入端65被连接到XOR门62的第二输入端，XOR门62的输出端被连接到输出端68。输入端66同时被连接到输出端67和输出端610。

对于表达式

针对K＝α¹²和i_j＝4，得到

${\mathrm{\α}}^{12}\·{\mathrm{\α}}^8\⊕{\mathrm{\α}}^{24}\·{\mathrm{\α}}^4={\mathrm{\α}}^{20}\⊕{\mathrm{\α}}^{28}={\mathrm{\α}}^5\⊕{\mathrm{\α}}^{13}={\mathrm{\α}}^7$

或者在多项式表达式中，根据表1，获得多项式1+x+x³或者向量表达式(1101)。

在图4中，将对于i＝4的

逐分量地与XOR电路45中的常量值

以函数方式进行异或。

特别地，可以通过将NOR电路46的第一、第二和第四输入端反相而不将第三输入端反相来简单地实现这种组合。因此，对于K＝α¹²和

其适用

${\mathrm{\α}}^{12}\⊕{\mathrm{\α}}^4={\mathrm{\α}}^6$

或者在多项式表达式中其等于x²+x³。在向量表达式中α⁶＝(0，1，1，0)适用。因此，可以通过将NOR电路48的第三和第四输入端反相并使第一和第四输入端保持不求反来实现XOR电路48中的s₁和

(其中K＝α¹²且

)的逐分量异或组合。

在下面将针对一个示例来解释如何可以确定H矩阵H^mod，H矩阵H^mod的列的m个第一分量总是包括奇数个数的1。这里作为例子，考虑具有32个元素的Galois域GF(2⁵)。

在表3中表示出了在模多项式m(x)＝1+x²+x⁵的情况下的Galois域GF(2⁵)的元素的不同表达式。

可以直接从表3读出长度为31的未缩短BCH码的未修改子矩阵H₁、H₃和H₅的二进制表达式(以它们的具体形式)，其中

H₁＝(α⁰ α₁ ... α³⁰)，

H³＝(α⁰ α³ ... α^3·30)，

H⁵＝(α⁰ α⁵ ... α^5·30)，

表3：在不同形式的表达式中的通过本原模多项式m(x)＝1+x²+x⁵生成的GF(2⁵)的元素：

这里，α的指数被解释为以31为模。下式适用

$H_1=\left(\begin{array}{ccccccccccccccccccccccccccccccc}1& 0& 0& 0& 0& 1& 0& 0& 1& 0& 1& 1& 0& 0& 1& 1& 1& 1& 1& 0& 0& 0& 1& 1& 0& 1& 1& 1& 0& 1& 0\\ 0& 1& 0& 0& 0& 0& 1& 0& 0& 1& 0& 1& 1& 0& 0& 1& 1& 1& 1& 1& 0& 0& 0& 1& 1& 0& 1& 1& 1& 0& 1\\ 0& 0& 1& 0& 0& 1& 0& 1& 1& 0& 0& 1& 1& 1& 1& 1& 0& 0& 0& 1& 1& 0& 1& 1& 1& 0& 1& 0& 1& 0& 0\\ 0& 0& 0& 1& 0& 0& 1& 0& 1& 1& 0& 0& 1& 1& 1& 1& 1& 0& 0& 0& 1& 1& 0& 1& 1& 1& 0& 1& 0& 1& 0\\ 0& 0& 0& 0& 1& 0& 0& 1& 0& 1& 1& 0& 0& 1& 1& 1& 1& 1& 0& 0& 0& 1& 1& 0& 1& 1& 1& 0& 1& 0& 1\end{array}\right)$

$H_3=\left(\begin{array}{ccccccccccccccccccccccccccccccc}1& 0& 0& 0& 0& 1& 1& 0& 0& 1& 0& 0& 1& 1& 1& 1& 1& 0& 1& 1& 1& 0& 0& 0& 1& 0& 1& 0& 1& 1& 0\\ 0& 0& 1& 1& 1& 1& 1& 0& 1& 1& 1& 0& 0& 0& 1& 0& 1& 0& 1& 1& 0& 1& 0& 0& 0& 0& 1& 1& 0& 0& 1\\ 0& 0& 0& 0& 1& 1& 0& 0& 1& 0& 0& 1& 1& 1& 1& 1& 0& 1& 1& 1& 0& 0& 0& 1& 0& 1& 0& 1& 1& 0& 1\\ 0& 1& 1& 1& 1& 1& 0& 1& 1& 1& 0& 0& 0& 1& 0& 1& 0& 1& 1& 0& 1& 0& 0& 0& 0& 1& 1& 0& 0& 1& 0\\ 0& 0& 0& 1& 0& 1& 0& 1& 1& 0& 1& 0& 0& 0& 0& 1& 1& 0& 0& 1& 0& 0& 1& 1& 1& 1& 1& 0& 1& 1& 1\end{array}\right)$

$H_5=\left(\begin{array}{ccccccccccccccccccccccccccccccc}1& 1& 1& 1& 0& 1& 0& 0& 0& 1& 0& 0& 1& 0& 1& 0& 1& 1& 0& 0& 0& 0& 1& 1& 1& 0& 0& 1& 1& 0& 1\\ 0& 0& 0& 1& 0& 0& 1& 0& 1& 0& 1& 1& 0& 0& 0& 0& 1& 1& 1& 0& 0& 1& 1& 0& 1& 1& 1& 1& 1& 0& 1\\ 0& 1& 0& 1& 1& 0& 0& 0& 0& 1& 1& 1& 0& 0& 1& 1& 0& 1& 1& 1& 1& 1& 0& 1& 0& 0& 0& 1& 0& 0& 1\\ 0& 0& 0& 1& 1& 1& 0& 0& 1& 1& 0& 1& 1& 1& 1& 1& 0& 1& 0& 0& 0& 1& 0& 0& 1& 0& 1& 0& 1& 1& 0\\ 0& 0& 1& 1& 0& 1& 1& 1& 1& 1& 0& 1& 0& 0& 0& 1& 0& 0& 1& 0& 1& 0& 1& 1& 0& 0& 0& 0& 1& 1& 1\end{array}\right)$

作为用于K的示例，这里选择K＝α²⁴。从表3可以推断出，在多项式表达式中下式适用

K(x)＝x+x²+x³+x⁴

并且在向量表达式中(01111)适用。

为了确定H^mod，现在删除H矩阵的在H₁的分量中包括偶数个数的1的所有列，并将其布置为使得在比特位置[1，2]、[3，4]、[5，6]...中的子矩阵H₁的列对的逐分量XOR组合的每个产生[0，1，1，1，1]^T。

以这种方式获得的矩阵H^mod的子矩阵

和

现在是

$H_1^{\mathrm{mod}}=\left(\begin{array}{cccccccccccccccc}1& 1& 0& 0& 0& 0& 0& 0& 0& 0& 1& 1& 1& 1& 1& 1\\ 0& 1& 1& 0& 0& 1& 0& 1& 0& 1& 0& 1& 1& 0& 0& 1\\ 0& 1& 0& 1& 1& 0& 0& 1& 0& 1& 1& 0& 1& 0& 1& 0\\ 0& 1& 0& 1& 0& 1& 1& 0& 0& 1& 1& 0& 0& 1& 0& 1\\ 0& 1& 0& 1& 0& 1& 0& 1& 1& 0& 0& 1& 0& 1& 1& 0\end{array}\right)$

$H_3^{\mathrm{mod}}=\left(\begin{array}{cccccccccccccccc}1& 1& 0& 1& 0& 1& 0& 1& 0& 1& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 1& 1& 1& 0& 1& 0& 1& 0& 0& 0& 0& 1\\ 0& 1& 0& 1& 0& 0& 0& 1& 1& 1& 1& 1& 1& 1& 0& 1\\ 0& 1& 1& 1& 1& 1& 1& 0& 1& 0& 1& 1& 0& 1& 0& 0\\ 0& 1& 0& 0& 0& 0& 1& 1& 0& 0& 1& 0& 0& 1& 1& 0\end{array}\right)$

$H_5^{\mathrm{mod}}=\left(\begin{array}{cccccccccccccccc}1& 0& 1& 0& 1& 1& 1& 1& 0& 1& 0& 1& 0& 0& 1& 1\\ 0& 0& 0& 0& 0& 0& 1& 1& 0& 0& 1& 1& 1& 1& 1& 1\\ 0& 1& 1& 0& 0& 1& 1& 0& 1& 0& 0& 1& 1& 0& 0& 1\\ 0& 1& 0& 1& 0& 1& 1& 1& 1& 1& 1& 1& 1& 0& 0& 0\\ 0& 1& 0& 0& 1& 1& 1& 1& 0& 0& 1& 0& 1& 0& 1& 0\end{array}\right)$

这里，使用子矩阵H₁的包括奇数个数的1的全部16列，使得H^mod的列的数量等于16。

如图3b中所示，现在可以通过XOR电路38从错误校正子s的子校正子s1将总体奇偶性作为XOR组合导出。

现在将首先针对2比特错误的校正以及随后针对具有相邻2比特错误的3比特错误的校正来证明本发明的功能。作为H矩阵，使用以下H矩阵

$H^{\mathrm{mod}}=\left(\begin{array}{c}{H}_1^{\mathrm{mod}}\\ H_3^{\mathrm{mod}}\\ P\end{array}\right)$

其包括14列，其中

和

的列是在模多项式m(x)＝1+x+x⁴并且K＝α¹²＝[1，1，1，1]^T的情况下的GF(2⁴)的元素，如等式(58)中所述。

要被校正的二进制字v’是字v’＝(11010011100101)。对于校正子分量s₁、s₃和s_P，则下式适用

$s_1=H_1^{\mathrm{md}}\·v^{\′}=\left(\begin{array}{c}1\\ 0\\ 1\\ 1\end{array}\right)={\mathrm{\α}}^{13},$

$s_3=H_3^{\mathrm{mod}}\·v^{\′}=\left(\begin{array}{c}1\\ 1\\ 1\\ 0\end{array}\right)={\mathrm{\α}}^{10},$

s_P＝P·v’＝(0)，

如其可以根据等式(58)利用H矩阵被直接地再次计算那样。

由于s_P＝0且s≠0，很明显存在2比特错误。二次等式

的零值是α¹¹和α⁴。

这可以通过放入所有可能的值αⁱ(i＝0，1，...，14)而被最容易地检查。

在图2a中，对于每个分量e_j，存在子电路

j＝1，...，n，其在是等式

的解时随后输出校正值e_j＝1。

这个等式的解是α⁴和α¹¹。

图4示出了子电路Dec2_j的一种可能的实现方式，在通过等式(58)确定的H矩阵中，

且

使得α¹¹对应于H矩阵H^mod的第二列，且α⁴对应于第九列。在数据字v’＝(11010011100101)中，因此第二和第九比特位置将被校正，使得错误向量e＝(01000000100000)必须被逐分量地与v’＝(11010011100101)进行异或。校正后的字v^cor则是v^cor＝(10010011000101)。分量e₂和e₉等于1，而校正向量的所有剩余分量等于0。

为了解释对具有相邻2比特错误的3比特错误的校正，作为示例，对数据字v’＝(10100011001101)的校正进行解释。

对于校正子分量，现在得到下式

$s_1=H_1^{\mathrm{mod}}\·v^{\′}=\left(\begin{array}{c}1\\ 0\\ 0\\ 1\end{array}\right)={\mathrm{\α}}^{14}$

$s_3=H_3^{\mathrm{mod}}\·v^{\′}=\left(\begin{array}{c}1\\ 1\\ 0\\ 0\end{array}\right)={\mathrm{\α}}^4$

s_P＝P·v’＝(1)

由于s_P＝1，且

很明显存在3比特错误。

下式适用

$s_1+K={\mathrm{\α}}^{14}\⊕{\mathrm{\α}}^{12}=\left(\begin{array}{c}1\\ 0\\ 0\\ 1\end{array}\right)\⊕\begin{array}{}\end{array}\left(\begin{array}{c}1\\ 1\\ 1\\ 1\end{array}\right)=\left(\begin{array}{c}0\\ 1\\ 1\\ 0\end{array}\right)={\mathrm{\α}}^5$

以下二次等式的零值是α¹和α¹³，如其可以通过直接再计算而被检查的那样

在通过等式(58)确定的H矩阵中，且

使得α⁵对应于由等式(58)确定的H矩阵的第十一列，α¹对应于第三列且α¹³对应于第四列。

通过将校正向量e＝(00110000001000)与v’逐分量地组合成 $v^{,}\⊕e=$ $\left(10100011001101\right)\⊕\left(00110000001000\right)=\left(10010011000101\right)=v^{\mathrm{cor}},$ 将在第三、第四和第十一比特位置处对数据字v’＝(10100011001101)进行校正。

图7示出了一种用于相对于代码字v＝v₁，...，v_n校正可能错误的二进制字v’＝v₁’，...，v_n’中的错误的方法的示意性流程图。该方法包括步骤902，其用于确定具有H矩阵H^mod的修改的BCH码的错误校正子s＝(s₁，s₃)，该H矩阵H^mod包括第一BCH子矩阵

和第二BCH子矩阵

该修改的BCH码具有码距d≥5。根据修改的BCH码，子矩阵

的n’个列向量被配对作为列向量对，使得每个列向量对的两个列向量的逐分量XOR组合产生相同的列向量K，列向量K与BCH子矩阵

的所有列向量都不同。数字n’是偶数，且4≤n’≤n适用。第二BCH子矩阵

包括针对第一BCH子矩阵

中的每个列向量的对应列向量，使得根据Galois域算法，该对应列向量是第一BCH子矩阵

中的该列向量的三次幂。通过将H矩阵H^mod与可能错误的二进制字v’相乘来确定错误校正子s，使得通过

给出第一错误校正子部分并通过

给出第二错误校正子部分。

该方法还包括生成校正向量e＝(e₁，...e_n)的步骤904，该校正向量具有校正值e_j＝e_j+1＝e_l＝1以及e_t＝0(t≠j，j+1，1)，如果满足以下条件的话：

·s₁等于相同的列向量K与第一BCH子矩阵

的列位置l处的列向量的逐分量的XOR组合，即，以及

·s₃等于在第二BCH子矩阵的列位置j、j+1和l处的列向量的逐分量的XOR组合，即，

这意味着错误校正子s＝(s₁，s₃)满足以下条件：

$s_1={\mathrm{\α}}^{i_j}\⊕{\mathrm{\α}}^{i_j+1}\⊕{\mathrm{\α}}^{i_l},s_3={\mathrm{\α}}^{3i_j}\⊕{\mathrm{\α}}^{{3i}_{j+1}}\⊕{\mathrm{\α}}^{{3i}_l}$

以这种方式，可以校正与另外1比特错误相组合的相邻2比特错误(即，总共3比特错误)。此外，用于校正错误的方法通常还支持1比特错误和2比特错误(相邻或者不相邻)的校正。

如果不满足针对1比特错误、2比特错误或者包括相邻2比特错误的3比特错误的条件，那么所有校正值e_j(j＝1...n)通常被选择为0，使得不执行对二进制字v’的校正。这通常意味着没有检测到可校正的错误。或者是二进制字v’没有错误，或者是它包括太多要被删除和/或以明确的方式进行校正的错误。

可能的是，要被校正的字的比特是三态存储器或者多值存储器的辅助二进制读取值，如其在2012年10月31日提交且题为“Circuit and Method for Multi-BitCorrection”的US专利申请号13/664,495中被描述的那样，该专利申请的全部内容通过引用被包括在此说明书中。辅助二进制读取值是由US13/664,495中的子电路LH基于存储单元的三态(或多值)状态值而提供的，所述存储单元被适配为在特定的时间呈现至少三个状态中的一个。在本公开中，子电路LH被称为“辅助读取值生成器”。因此，三态或多值存储器的技术可以从BCH码的强有力的错误校正能力中受益。由于单个存储单元影响辅助二进制读取值中的两个或者更多，因此三态存储器或多值存储器相对易于遭受相邻比特错误。

尽管已经在装置的背景下描述了某些方面，但很清楚的是，这些方面还代表了相应方法的描述，其中模块或者设备对应于方法步骤或者方法步骤的特征。类似地，在方法步骤的背景下描述的方面也代表相应装置的相应单元或者项或者特征的描述。

所发明的分解的信号可以被存储在数字存储介质上，或者可以在诸如无线传送介质或者诸如因特网的有线传送介质的传送介质上被传送。

取决于某些实现方式要求，可以采用硬件或者软件的方式来实现实施例的实施例。可以利用数字存储介质来执行该实现方式，所述数字存储介质例如软盘、DVD、CD、ROM、PROM、EPROM、EEPROM或闪存，其上存储有电可读控制信号，其与可编程计算机系统协作(或者能够与其协作)以使得执行相应的方法。

根据实施例的某些实施例包括具有电可读控制信号的非瞬时数据载体，所述控制信号能够与可编程计算机系统协作以使得执行这里所述的方法之一。

通常，本发明的实施例可以被实现为具有程序代码的计算机程序产品，当该计算机程序产品在计算机上运行时，该程序代码可操作用于执行方法之一。程序代码可以被存储在例如机器可读载体上。

其它实施例包括存储在机器可读载体上的用于执行这里所述的方法之一的计算机程序。

换句话说，发明的方法的实施例因此是一种具有程序代码的计算机程序，所述程序代码当该计算机程序在计算机上运行时用于执行这里所述的方法之一。

发明的方法的另一个实施例因此是一种数据载体(或者数字存储介质，或者计算机可读介质)，所述数据载体包括存储在其上的计算机程序，所述计算机程序用于执行这里所述的方法之一。

发明的方法的另一个实施例因此是表示用于执行这里所述的方法之一的计算机程序的信号序列或数据流。该数据流或者信号序列可以是例如被配置为经由数据通信连接、例如经由因特网而被传送。

另一个实施例包括例如计算机的处理装置或者可编程逻辑器件，其被配置为或者被适配为执行这里所述的方法之一。

另一个实施例包括计算机，其上安装有用于执行这里所述的方法之一的计算机程序。

在某些实施例中，可编程逻辑器件(例如，现场可编程门阵列)可以被用来执行这里所述方法的某些或者全部功能。在某些实施例中，现场可编程门阵列可以与微处理器协作以便执行这里所述的方法之一。通常，所述方法是通过任何硬件装置来实现的。

尽管已经根据若干有利的实施例描述了本发明，但存在落入本发明的范围内的变化、改变和等同物。应该注意到，存在许多实现本发明的方法和组成的替换方式。因此意图是，以下所附权利要求被解释为包括落入本发明的精神和范围内的所有这些变化、改变和等同物。

上述实施例仅仅是用于说明本发明的原理。应当理解的是，对于本领域技术人员而言，这里所述的布置和细节的修改和变型显而易见的。因此意图是仅由下面的专利权利要求的范围来限制，而不由以说明和解释这里的实施例的方式提出的特定细节来限制。

虽然每个权利要求仅往回引用一个权利要求，但本公开也覆盖权利要求的任何可想到的组合。

Claims (24)

1.一种用于相对于代码字v＝v₁，...，v_n校正可能错误的二进制字v’＝v₁’，...，v_n’中的错误的电路，该电路包括：

校正子生成器，其用于根据修改的BCH码来确定错误校正子s＝(s₁，s₃)，所述修改的BCH码具有包括第一BCH子矩阵

和第二BCH子矩阵

的H矩阵H^mod并且具有码距d≥5，

其中BCH子矩阵的n’个列向量被配对作为列向量对，使得每个列向量对的两个列向量的逐分量的异或组合产生相同的列向量K，所述列向量K与第一BCH子矩阵的所有列向量不同，并且其中n’是偶数，且4≤n’≤n适用，

其中第二BCH子矩阵包括针对第一BCH子矩阵中的每个列向量的对应列向量，使得根据Galois域算法，所述对应列向量是第一BCH子矩阵

中的所述列向量的三次幂，

其中所述校正子生成器被配置为通过将H矩阵H^mod与所述可能错误的二进制字v’相乘来确定所述错误校正子s，使得通过

给出第一错误校正子部分，以及通过给出第二错误校正子部分；以及

解码器，其用于生成校正向量e＝(e₁，...e_n)，如果第一错误校正子部分s₁等于所述相同的列向量K与第一BCH子矩阵

的列位置l处的列向量的逐分量的异或组合，以及如果第二错误校正子部分s₃等于第二BCH子矩阵

的列位置j、j+1和l处的列向量的逐分量的异或组合，则所述校正向量具有校正值e_j＝e_j+1＝e_l＝1以及针对t≠j，j+1，l的e_t＝0。

2.根据权利要求1的电路，其中第一BCH子矩阵

的列向量被表示为

j＝1，...，n，并等于Galois域GF(2^m)的元素的向量表达式，其中α是所述Galois域GF(2^m)的元素，并且第二BCH子矩阵

的列向量被表示为

并等于Galois域GF(2^m)的元素

的向量表达式，并且其中m是

和的列向量的长度。

3.根据权利要求2的电路，其中α是Galois域GF(2^m)的本原元素。

4.根据权利要求1的电路，其中所述解码器被配置为使得其根据所述错误校正子s的分量s₁、s₃、s_P来形成用于校正二进制字v’的所述相应比特v₁’，...，v_n’的n个二进制校正值e₁，...，e_n，其中s_P是代码字v’的总体奇偶性，并且其中所述校正值e₁，...，e_n是根据所述校正子分量s₁、s₃、s_P和所述二进制向量K的值来确定的，使得所述解码器Dec：

在1比特错误或者2比特错误的情况下，

当

时在其第j个输出端处输出校正值e_j＝1，j＝1，...，n，

以及当

时在其第j个输出端处输出校正值e_j＝0，

以及在3比特错误的情况下，当 $s_1^3\⊕s_3\⊕s_1^{2}K\⊕s_1{K}^2\⊕K^2{\mathrm{\α}}^{i_j}\⊕{\mathrm{K\α}}^{{2i}_j}=0$ 或者

时，在其第j个输出端处输出校正值e_j＝1，j＝1，...，n，

以及在3比特错误时情况下，当 $s_1^3\⊕s_3\⊕s_1^{2}K\⊕s_1{K}^2\⊕K^2{\mathrm{\α}}^{i_j}\⊕{\mathrm{K\α}}^{{2i}_j}\≠0$ 和

两者都适用时，在其第j个输出端处输出校正值e_j＝0，j＝1，...，n。

5.根据权利要求1的电路，其中所述解码器包括：

辅助子电路，用于基于第一错误校正子部分s₁、第二错误校正子部分s₃和所述相同的列向量K形成至少一个辅助信号；

多个解码器子电路，每个解码器子电路与所述二进制字v’的特定比特关联且被配置为用于接收所述至少一个辅助信号以及用于确定所述校正向量e的对应校正值。

6.根据权利要求5的电路，其中辅助子电路被配置为形成以下辅助信号：

·“3比特错误”，其在

且s_P＝1时等于1，否则其等于0；

·m比特宽的信号

对于(s₁，s₃)≠0其等于

并且对于(s₁，s₃)＝0其等于

以及

· $s_1^3\⊕s_3\⊕s_1{K}^2\⊕s_1^{2}K;$

其中，s_P是所述数据字v’的总体奇偶性。

7.根据权利要求6的电路，其中用于所述二进制的相应比特v_j’的第j个解码器电路被配置为：当

$s_1^3\⊕s_3\⊕s_1^2{\mathrm{\α}}^{i_j}\⊕s_1{\mathrm{\α}}^{{2i}_j}=0$ 或者

$s_1^3\⊕s_3\⊕s_1^{2}K\⊕s_1{K}^2\⊕K^2{\mathrm{\α}}^{i_j}\⊕{\mathrm{K\α}}^{2i_j}=0$ 或者

$s_1\⊕K={\mathrm{\α}}^{i_j}$

时输出校正值e_j＝1，以及当

$s_1^3\⊕s_3\⊕s_1^2{\mathrm{\α}}^{i_j}\⊕s_1{\mathrm{\α}}^{{2i}_j}\≠0$ 或者

$(s_1^3\⊕s_3\⊕s_1^{2}K\⊕s_1{K}^2\⊕K^2{\mathrm{\α}}^{i_j}\⊕K{\mathrm{\α}}^{2i_j}\≠0$ 并且 $s_1\⊕K={\mathrm{\α}}^{i_j})$

时输出校正值e_j＝0。

8.根据权利要求1的电路，其中所述可能错误的二进制字v’是由用于读取包括具有大于两种状态的存储单元的存储器的电路的辅助读取值生成器提供的辅助读取值。

9.根据权利要求1的电路，其中对于n为偶数，比特对[v₁’，v₂’]，[v₃’，v₄’]...，[v_n-1’，v_n’]中的至少一对，以及对于n为奇数，比特对[v₁’，v₂’]，[v₃’，v₄’]...，[v_n-2’，v_n-1’]中的至少一对，被存储在具有大于两种状态的存储单元中。

10.一种用于相对于代码字v＝v₁，...，v_n校正可能错误的二进制字v＝v₁’，...，v_n’中的错误的方法，该方法包括：

确定修改的BCH码的错误校正子s＝(s₁，s₃)，所述修改的BCH码具有包括第一BCH子矩阵

和第二BCH子矩阵

的H矩阵

并且具有码距d≥5，

其中子矩阵

的n’个列向量被配对作为列向量对，使得每个列向量对的两个列向量的逐分量的异或组合产生相同的列向量K，所述列向量K与BCH子矩阵的所有列向量不同，并且其中n’是偶数，且4≤n’≤n适用，

其中第二BCH子矩阵

包括针对第一BCH子矩阵

中的每个列向量的对应列向量，使得根据Galois域算法，所述对应列向量是第一BCH子矩阵中的所述列向量的三次幂，

其中通过将所述H矩阵H^mod与所述可能错误的二进制字v’相乘来确定所述错误校正子s，使得通过

给出第一错误校正子部分，以及通过

给出第二错误校正子部分；以及

生成校正向量e＝(e₁，...e_n)，如果s₁等于所述相同的列向量K与第一BCH子矩阵

的列位置l处的列向量的逐分量的异或组合，以及如果s₃等于第二BCH子矩阵

的列位置j、j+1和l处的列向量的逐分量的异或组合，则所述校正向量具有校正值e_j＝e_j+1＝e_l＝1以及针对t≠j，j+1，l的e_t＝0。

11.一种非瞬时存储介质，其上存储有具有程序代码的计算机程序，所述程序代码当在计算机上运行时用于执行用于相对于代码字v＝v₁，...，v_n校正可能错误的二进制字v’＝v₁’，...，v_n’中的错误的方法，该方法包括：

确定修改的BCH码的错误校正子s＝(s₁，s₃)，所述修改的BCH码具有包括第一BCH子矩阵和第二BCH子矩阵

的H矩阵H^mod并且具有码距d≥5，

其中子矩阵

的n’个列向量被配对作为列向量对，使得每个列向量对的两个列向量的逐分量的异或组合产生相同的列向量K，所述列向量K与BCH子矩阵

的所有列向量不同，并且其中n’是偶数，且4≤n’≤n适用，

其中第二BCH子矩阵

包括针对第一BCH子矩阵中的每个列向量的对应列向量，使得根据Galois域算法，所述对应列向量是第一BCH子矩阵中的所述列向量的三次幂，

其中通过将所述H矩阵H^mod与所述可能错误的二进制字v’相乘来确定所述错误校正子s，使得通过

给出第一错误校正子部分，以及通过给出第二错误校正子部分；以及

生成校正向量e＝(e₁，...e_n)，如果s₁等于所述相同的列向量K与第一BCH子矩阵

的列位置l处的列向量的逐分量的异或组合，以及如果s₃等于第二BCH子矩阵

的列位置j、j+1和l处的列向量的逐分量的异或组合，则所述校正向量具有校正值e_j＝e_j+1＝e_l＝1以及针对t≠j，j+1，l的e_t＝0。

12.一种用于校正可能错误的二进制字v’＝v₁’，...，v_n’中的错误的电路，所述可能错误的二进制字v’＝v₁’，...，v_n’在发生错误的情况下是从线性码的代码字v＝v₁，...，v_n由于这些错误而产生的，该线性码具有m’≥2m行和n列的H矩阵H^mod并且具有码距d≥5，以及

如果没有错误发生，则所述可能错误的二进制字v’＝v₁’，...，v_n’等于该码的所述代码字v＝v₁，...，v_n，其中1比特错误、2比特错误和包含相邻2比特错误的3比特错误可以被校正，其中n＜2^m和m≥3适用，其中该电路包括用于从所述可能错误的二进制字v’至少确定(2m)数位的错误校正子s的校正子生成器Synd，以及其中所述错误校正是由校正子生成器下游的解码器Dec根据由校正子生成器确定的所述错误校正子而执行的，其中所述校正子生成器Synd包括n个二进制输入端以及至少2m个二进制输出端并且被实现为使得当二进制字v’＝v₁’，...，v_n’在其输入端处被输入时，其在2m个二进制输出端处输出被分配给所述输入的二进制字v’的错误校正子s＝(s₁，s₃)，其中，s₁和s₃每个均是m数位的二进制向量，并且所述错误校正子s通过下式被确定

s＝H^mod·v′

并且H^mod是n个列向量h₁，...，h_n的[m’，n]矩阵，所述n个列向量每个均具有m’个分量，并且对于j＝1，...，n，所述列向量h_j包括形成向量

的m个第一分量以及列向量h_j的随后的m个分量的第二向量

使得下式适用

$h_j=\left(\begin{array}{c}{h}_j^1\\ h_j^3\end{array}\right)=\left(\begin{array}{c}{\mathrm{\α}}^{i_j}\\ {\mathrm{\α}}^{3\left(i_j\right)}\end{array}\right)$

其中，

等于Galois域GF(2^m)的元素

的向量表达式，并且

等于Galois域GF(2^m)的元素

的向量表达式，并且α是Galois域GF(2^m)的元素，并且H矩阵H的列向量h₁，...，h_n的前m个分量

被确定为使得对于n’是偶数且4≤n’≤n，下式适用

${\mathrm{\α}}^{i_1}\⊕{\mathrm{\α}}^{i_2}=h_1^1\⊕h_2^1=K$

${\mathrm{\α}}^{i_3}\⊕{\mathrm{\α}}^{i_4}=h_3^1\⊕h_4^1=K$

${\mathrm{\α}}^{i_{n^{\′}-1}}\⊕{\mathrm{\α}}^{i_{n^{\′}}}=h_{n^{\′}-1}^1\⊕h_{n^{\′}}^1=K$

其中，K是m分量二进制向量，使得没有m分量向量

等于K，并且其中s₁，s₃通过下式被确定

$s_1=H_1^{\mathrm{mod}}\·v^{\′},$

$s_3=H_3^{\mathrm{mod}}\·v^{\′},$

其中 $H_1^{\mathrm{mod}}=(h_1^1,...,h_n^1),H_3^{\mathrm{mod}}=(h_1^3,...,h_n^3)$ 适用，并且

和

的指数i_j和3i_j每个均被确定为以2^m-1为模，并且v’是具有分量v₁’，...，v_n’的n分量列向量，

并且其中解码器Dec包括被连接到所述校正子生成器Synd的输出端的至少2m个二进制输入端，所述校正子生成器Synd的输出端载有所述错误校正子s＝(s₁，s₃)的分量，并且存在解码器Dec的用于输出n个二进制校正值e₁，...e_n以用于校正所述二进制字v’的相应比特v₁’，...，v_n’的n个二进制输出端，其中，所述校正值e₁，...e_n是从所述校正子分量s₁，s₃和所述二进制向量K的值被确定的，且所述解码器Dec被配置为使得

·当错误校正子s＝0被应用到其输入端时，其在其输出端处输出校正值e＝0，

·当错误校正子s＝(s₁，s₃)，其中

$s_1={\mathrm{\α}}^{i_j},s_3={\mathrm{\α}}^{3\left(i_l\right)},$

被应用到其输入端时，其输出e_j＝1以及针对t≠j的e_t＝0，

·当错误校正子s＝(s₁，s₃)，其中

$s_1={\mathrm{\α}}^{i_j}\⊕{\mathrm{\α}}^{i_r},s_3={\mathrm{\α}}^{3\left(i_j\right)}\⊕{\mathrm{\α}}^{3\left(i_r\right)},$

被应用到其输入端时，其输出e_j＝1、e_r＝1以及针对t≠j，r的e_t＝0，

·当错误校正子s＝(s₁，s₃)，其中

$s_1={\mathrm{\α}}^{i_j}\⊕{\mathrm{\α}}^{i_{j+1}}\⊕{\mathrm{\α}}^{i_l},s_3={\mathrm{\α}}^{3\left(i_j\right)}\⊕{\mathrm{\α}}^{3\left(i_{j+1}\right)}\⊕{\mathrm{\α}}^{3\left(i_l\right)},$

被应用到其输入端时，其中

以及j+1≤n′适用，且其中K不是矩阵

的任何列，其输出校正值e_j＝1、e_j+1＝1以及e_l＝1以及针对t≠j，j+1，l的e_t＝0。

13.根据权利要求12的电路，其中所述校正子生成器Synd包括第(2m+1)个输出端，用于输出所述错误校正子的附加比特s_P，其中s_P被确定为奇偶性比特并且其中存在所述解码器Dec的附加的第(m+1)个输入端，用于输入校正子分量s_P。

14.根据权利要求12的电路，其中H矩阵H_mod的列h₁，...，h_n被确定为使得这些列的分量的子集中的1的个数为奇数。

15.根据权利要求13的电路，其中所述解码器从错误校正子的与H矩阵H^mod的包括奇数个1的列的分量相对应的那些分量通过异或组合形成奇偶性校正子s_P。

16.根据权利要求13的电路，其中所述解码器Dec被配置为使得它从错误校正子s的分量s₁，s₃，s_P形成用于校正所述二进制字v’的相应比特v₁’，...，v_n’的n个二进制校正值e₁，...e_n，其中，所述校正值e₁，...e_n是从所述校正子分量s₁，s₃，s_P和所述二进制向量K的值被确定的，使得所述解码器Dec：

在1比特错误或者2比特错误的情况下，

当

时，在其第j个输出端处输出校正值e_j＝1，j＝1，...，n，

以及当

时，在其第j个输出端处输出校正值e_j＝0，

以及在3比特错误的情况下，当 $s_1^3\⊕s_3\⊕s_1^{2}K\⊕s_1{K}^2\⊕K^2{\mathrm{\α}}^{i_j}\⊕{\mathrm{K\α}}^{{2i}_j}=0$ 或者

时，在其第j个输出端处输出校正值e_j＝1，j＝1，...，n，

以及在3比特错误的情况下，当 $s_1^3\⊕s_3\⊕s_1^{2}K\⊕s_1{K}^2\⊕K^2{\mathrm{\α}}^{i_j}\⊕{\mathrm{K\α}}^{{2i}_j}\≠0$ 以及

二者都适用时，在其第j个输出端处输出校正值e_j＝0，j＝1，...，n。

17.根据权利要求13的电路，还包括用于将所述解码器输出的校正值e₁，...e_n与数据字的分量v₁’，...，v_n’组合成校正后的数据比特

的组合电路，其中所述组合电路被配置为用以针对j＝1，...，n实现校正值e_j与所述对应数据比特v_j’的各自唯一可逆的组合。

18.根据权利要求12的电路，其中对于n为偶数，比特对[v₁’，v₂’]，[v₃’，v₄’]...，[v_n-1’，v_n’]中的至少一对，以及对于n为奇数，比特对[v₁’，v₂’]，[v₃’，v₄’]...，[v_n-2’，v_n-1’]中的至少一对，被存储在具有大于两种状态的存储单元中。

19.根据权利要求12的电路，其中H^mod是n个列向量h₁，...，h_n的[m’，n]矩阵，所述n个列向量中的每个具有m’个分量，并且对于j＝1，...，n，所述列向量h_j包括形成向量的m个第一分量、形成第二向量的m个随后的分量以及形成第三向量

的所述列向量h_j的m个随后的分量，使得

$h_j=\left\{\begin{array}{c}{h}_j^1={\mathrm{\α}}^{i_j}\\ h_j^3={\mathrm{\α}}^{3\left(i_j\right)}\\ h_j^5={\mathrm{\α}}^{5\left(i_j\right)}\end{array}\right.$

适用，其中，

等于Galois域GF(2^m)的元素

的向量表达式，并且其中

等于Galois域GF(2^m)的元素

的向量表达式，以及

等于Galois域GF(2^m)的元素

的向量表达式，

以及还存在具有n个二进制输入行并具有用于输出至少1比特宽的输出信号q的至少1比特宽的输出端的错误指示电路，所述错误指示电路的输入端被连接到异或电路的载有校正后的数据字v^cor的n数位输出端，其中所述错误指示电路被实现为使得当存在不可校正的3比特错误时其输出第一值q₁，以及使得当存在具有相邻2比特错误的可校正3比特错误时其输出不同于q₁的第二值q₂。

20.根据权利要求19的电路，其中所述错误指示电路被实现为使得其实现函数

其中

适用。

21.根据权利要求19的电路，其中所述错误指示电路被实现为使得其实现函数

其中

$({\left[s_{5_1}\right]}^{,},...,{\left[s_{5_m}\right]}^{,})=H_5^{\mathrm{mod}}\·v^{\mathrm{cor}}$

适用，并且

是的子集，且M＜m适用。

22.根据权利要求12的电路，其中，H^mod是n个列向量h₁，...，h_n的[m’，n]矩阵，所述n个列向量中的每个具有m’个分量，并且对于j＝1，...，n，列向量h_j包括形成向量的m个第一分量，以及第二向量

包括列向量h_j的随后的m个分量，以及另外m个分量的第三向量

使得

$h_j=\left\{\begin{array}{c}{h}_j^1={\mathrm{\α}}^{i_j}\\ h_j^3={\mathrm{\α}}^{3\left(i_j\right)}\\ h_j^5={\mathrm{\α}}^{5\left(i_j\right)}\end{array}\right.$

适用，

其中，

等于Galois域GF(2^m)的元素

的向量表达式，并且

等于Galois域GF(2^m)的元素

的向量表达式，并且等于Galois域GF(2^m)的元素

的向量表达式，并且进一步地，所述解码器被实现为使得其包括用于输出错误指示信号q’的输出端，其中：

当 $s_1^6\⊕s_3^2\⊕s_1^{5}K\⊕{\mathrm{Ks}}_5\⊕K^3{s}_3\⊕K^3{s}_1^3=0$ 适用时，q’呈现第一值q₁’，

当 $s_1^6\⊕s_3^2\⊕s_1^{5}K\⊕{\mathrm{Ks}}_5\⊕K^3{s}_3\⊕K^3{s}_1^3\≠0$ 适用时，q’呈现不同于第一值q₁’的第二值q₂’。

23.根据权利要求12的电路，其中α是Galois域GF(2^m)的本原元素。

24.根据权利要求12的电路，其中用于校正可能错误的二进制字中的错误的电路的子电路被部分联合地优化。

Images