CN1055586C

CN1055586C - 纠错译码器和纠错译码方法

Info

Publication number: CN1055586C
Application number: CN94113457A
Authority: CN
Inventors: 中村隆彦
Original assignee: Mitsubishi Electric Corp
Current assignee: Mitsubishi Electric Corp
Priority date: 1993-12-28
Filing date: 1994-12-28
Publication date: 2000-08-16
Anticipated expiration: 2014-12-28
Also published as: US5684810A; JPH07202717A; CN1122025A; FR2714498B1; FR2714498A1; JP3154607B2; NL9402204A

Abstract

在对一组数据已进行一个方向的错误检测和错误校正之后，可将在其它方向的错误校正选为删除和错误校正或只是错误校正。当在行错误校正期间已检测到成组错误指示时、或者当在行错误校正之内的最大错误校正的数目较小时、或者当在行错误校正之内的不可校正错误较少时，就选择利用在第一方向上的错误校正的结果的删除和错误校正。否则，就选择错误校正。

Description

纠错译码器和纠错译码方法

本发明涉及校正在存储装置中的编码的、未校正的数据中的错误的方法和设备，特别涉及在音频和视频数字信号处理中使用的纠错译码方法和纠错译码器。

1987年6月29日出版的日本第一流的双周刊之一的《NikkeiElectronics》的一篇文章中记载了将乘积码用于数字音频磁带的纠错译码方法。图21所示的流程图体现了这一常规的纠错译码方法的原理，图22说明了乘积码的块结构，在这一块结构中，32、28和5个里德-所罗门(RS)码用作每一行的C1码，32、26和7个RS码用作每一列的C2码。

根据对于接收字数据获得的校正子计算在C1码中的接收字的错误个数。当错误个数为1时，就对错误进行单个错误的校正。当错误个数为2时，就进行两个错误的校正并在存储器中确定两个删除标记，以便指出这两个错误的位置。如果错误个数为3或更多个时，就不进行纠错而是在存储器中着手表示未校正的错误的位置的删除标记。

当沿行的方向重复上述操作32遍时，就译码了C1码信号。

一旦结束了对C1码信号的译码，就根据译码的C1数据计算接收字的错误个数。

当错误个数为1时，就对错误进行单个错误的校正。当错误个数为2时，就进行两个错误的校正。当出现三个错误时，校正错误的方法就依赖于在C1译码期间确定的删除标记的个数：当有两个删除标记时，就进行两次删除和单个错误的校正，当有三个删除标记时，就进行三次删除校正。同样地，如果错误个数是四个，当有三个删除标记时就进行三次删除和单个错误的校正，当有四个删除标记时就进行四次删除校正。如果确认在C2码中存在五个错误时，就进行五次删除校正。在有六个错误的场合中，当有六个删除标记时就进行六次删除校正。

如果删除标记的个数大于六时，对C2译码就进行错误检测而不进行错误校正。当沿图22所示列的方向对于信息部分重复28遍或对于在乘积码块中的所有代码重复32遍上述操作时就结束了C2译码。

在现有技术中存在这样的明显不足，即例如，如果在C1码中出现了与对其进行了两次错误校正的两个随机错误相结合的长的成组错误，就只对错误进行了检测而没有进行校正。这是因为删除标记的个数与错误的个数成比例地增加，超出C2码的译码能力的删除标记将只导致错误检测。

此外，总是有错误地校正了所接收的字的可能性。错误地校正的接收字加上大量的随机错误的删除标记将不可避免地以C2码的许多错误译码的符号来结束。

因此，本发明的主要目的是提供即使当同时出现长的成组错误和随机错误时仍能校正错误的译码器和译码方法。

本发明的另一目的是提供能够使在C2译码中的错误删除校正减到最小的译码器和译码方法。

本发明的目的是获得确保有效的和省时的纠错译码方法的纠错译码器，该纠错译码方法能够将错误的出现减至最少并且还可根据被检测错误的类型、例如成组或随机错误、或者也许成组和随机错误兼而有之来进行最佳的译码。

利用一纠错译码器来实现这一目的，该纠错译码器利用“钱氏搜索”对由包括纠错码的n2行×n1列的符号组成的代码信号进行译码以便进行错误校正或删除及纠错，并且根据纠错码校正在代码信号中的接收字的错误，该纠错译码器具有以下部件：

—第一译码器，校正作为接收字的每行的可校正错误和检测不可校正错误，

—标记存储器，如果接收字的连续检测的不可校正错误的个数超过第一预定值就设置成组错误标记，

—位置存储器，存储具有第一译码器检测的不可校正错误的行的位置，

—计数器，计数具有第一译码器检测的不可校正错误的行的数目，以及

—第二译码器，对作为接收字的每列的错误进行n1次校正。当计数器的数值在第二和第三预定值之间以及存在成组错误标记时，第二译码器利用在位置存储器中的位置、根据删除及纠错对接收字进行译码。当计数器的数值在第二和第三预定值之间而不存在成组错误标记时，第二译码器根据错误校正对接收字进行译码。

还可利用一纠错译码器来实现这一目的，该纠错译码器对由包括纠错码的n2行×n1列的符号组成的代码信号进行译码以便进行错误校正或删除及纠错。该译码器根据纠错码校正在代码信号中的接收字的错误。该译码器由以下部件组成：

—第一计数器，计数具有第一译码器检测的不可校正错误的行的数目，

—第二计数器，在每行中的符号的被检测错误的个数等于最大可校正错误值的情况下，计数在每行中设置的最大错误校正标记的个数，以及

—第二译码器，对作为接收字的每列的错误进行n1次校正，并且当第一计数器的数值在第二和第三预定值之间以及第一计数器的数值和第二计数器的数值之和小于第一预定值时，利用在位置存储器中的位置、根据删除及纠错对接收字进行译码。当第一计数器的数值在第二和第三预定值之间以及第一计数器的数值和第二计数器的数值之和大于第一预定值时，第二译码器根据错误校正对接收字进行译码。

还可利用一纠错译码器来实现这一目的，该纠错译码器对由包括纠错码的n2行×n1列的符号组成的代码信号进行译码以便进行错误校正或删除及纠错，并且根据纠错码校正在代码信号中的接收字的错误，该纠错译码器具有以下部件：

—第一译码器，对作为接收字的每行的可校正错误进行n2次校正并对该接收字的不可校正错误进行n2次检测，

—计数器，计数具有由第一译码器检测的不可校正错误的行的数目，

—“钱氏(Chien)搜索”电路，计算欧几里德算法的错误位置和错误大小(magnitude)。该电路设置一些错误位置，在这些错误位置中，不可校正错误行的数目一开始为零。

—第二译码器，对作为接收字的每列的错误进行n1次校正，并且在计数器的数值小于第一预定值以及起初在“钱氏搜索”电路中的错误位置的数目大于第二预定值的情况下，利用在位置存储器中的位置、根据删除及纠错对接收字进行译码，第二译码器还在计数器的数值大于第一预定值以及起初在“钱氏搜索”电路中的错误位置的数目大于第二预定值的情况下，根据错误校正对接收字进行译码。

利用对由包括纠错码的n2行×n1列的符号组成的代码信号进行译码和校正接收字的错误的译码方法来实现这一目的，该方法包括以下步骤：

—根据接收字的校正子产生定位多项式，

—根据定位多项式分析每行中的接收字的错误位置的错误大小，

—在出现错误和错误位置的个数小于每行中的第一预定值的情况下，利用纠错码校正每行中的接收字，

—在错误位置的个数大于每行中的第一预定值的情况下，在有限域中将行的元素作为不可校正错误元素来存储，

—在接收字的连续检测的不可校正错误的个数超过第二预定值的情况下，设置成组错误标记，

—根据定位多项式分析每列中的接收字的错误位置和错误大小，

—在错误出现于每一列中、不可校正错误元素的个数小于第三预定值以及存在成组错误标记的情况下，根据删除及纠错对每列中的接收字进行校正，以及

—在错误出现于每一列中、不可校正错误元素的个数小于第三预定值以及不存在成组错误标记的情况下，根据错误校正对每列中的接收字进行校正。

还可利用对由包括纠错码的n2行×n1列的符号组成的代码信号进行译码和校正接收字的错误的译码方法来实现这一目的，该方法包括以下步骤：

—根据接收字的校正子产生定位多项式，

—根据定位多项式分析在每行中的接收字的错误位置和错误大小，

—在出现错误以及错误位置的个数小于每行中的第一预定值的情况下，根据错误校正对每行中的接收字进行校正，

—在每行中的符号的被检测错误的个数等于最大可校正错误值的情况下，设置最大错误校正标记，

—根据定位多项式分析在每列中的接收字的错误位置和错误大小，

—在出现错误、不可校正错误元素的个数小于第二预定值以及最大错误校正标记的个数小于第三预定值的情况下，根据删除及纠错对每列中的接收字进行校正，以及

—在出现错误、不可校正错误元素的个数小于第二预定值以及最大错误校正标记的个数大于第三预定值的情况下，根据错误校正对每列中的接收字进行校正。

通过给译码方法增加利用在列中的校正步骤在行的不可校正错误元素中填充接收字的步骤和在填充步骤的基础上再次校正接收字的步骤可有效地实现本目的。

图1表示常规的通信系统配置；

图2表示记录系统配置的一般说明；

图3表示专用H/W配置；

图4表示在通用H/W上的S/W；

图5表示本发明的纠错译码器的配置；

图6表示本发明实施例1的纠错译码器的删除计算机的细节；

图7表示本发明实施例1的纠错译码器的操作流程；

图8是本发明实施例2的纠错译码方法的操作流程图；

图9是本发明实施例2的纠错译码方法的操作流程图；

图10表示本发明实施例3的纠错译码器的错误检测器和删除计算机的细节；

图11表示本发明实施例3的纠错译码器的操作流程；

图12是本发明实施例5的纠错译码方法的操作流程图；

图13是本发明实施例5的纠错译码方法的操作流程图；

图14表示本发明实施例6的纠错译码器的错误检测器和删除计算机的细节；

图15是本发明实施例6的纠错译码器的操作流程图；

图16是本发明实施例8的纠错译码方法的操作流程图；

图17是本发明实施例8的纠错译码方法的操作流程图；

图18是本发明实施例9的纠错译码方法的操作流程图；

图19是本发明实施例9的纠错译码方法的操作流程图；

图20是本发明实施例9的纠错译码方法的操作流程图；

图21表示常规的纠错译码方法；

图22表示乘积码的结构。

实施例0

图1是设置了本发明的译码器的系统配置的一般说明，图中描述的通信系统由两个主要部分组成：发射机100和接收机110，它们都与传输线路105连接。转换器102接收从源101发出的信息并将其转换为电信号。该信号然后被传送给编码器103和调制器104。现在已被编码和调制的发送信息输出到传输线路105。编码信号，不管其是通过有线还是无线传输，总是对外界噪声敏感的。因此到达接收机110的编码信号受到外界噪声的影响，必须首先在解调器(接收接口)106处被恢复为其原来的波形。然后被传送给译码器(纠错译码器)107并被其译码。波形在到达用户109之前在接收电路108处被转换为接收信号。

图2表示主要由记录设备120和再现设备130组成的记录系统的系统配置。输入信息源121通过麦克风或转换器122被转换为电信号。该信号然后被编码器123编码、被调制器124调制、然后在记录系统125、例如磁带上被记录。在记录和再现期间，记录系统对外界噪声敏感。再现设备130从磁带获取信号。记录信号被解调器(再现接口)126解调、被译码器(纠错译码器)127译码、然后在从喇叭作为声音到达用户129之前通过再现电路128被恢复为原来的电信号。

利用硬件或利用软件来专门构成图1和图2所示的译码器107和127。在表示硬件配置的图3中，接收字序列被CPU131经由数据总线124从解调器106或126一次地存储到存储器132。输入的接收字序列然后根据地址产生电路133的指令通过由纠错译码电路135消除产生的噪声而被译码。

对于通用处理器的软件配置，译码器是利用CPU 141和存有软件的存储器142来构成的。输入信息通过数据总线143来传送，译码结果在输出到数据总线143之前被暂存在存储器142中。CPU 141执行实现译码的软件。

图5表示专门的硬件配置的纠错译码电路135的细节。

实施例1

在行和列方向上的具有纠错码的一组数据中，在行中连续出现大于预定值的接收字的不可校正错误强烈地表示了成组错误的出现。在这种情况下，对C2列译码，必须进行删除和错误校正。相反地，当成组错误不大可能出现时，如果在设置了许多删除标记时根据删除进行译码，就会错误地校正错误。因此，在这种情况下，应忽略删除以使有效的错误校正成为可能。虽然在说明书中对于行和列进行说明，本领域的技术人员知道这一原理对于列和行或者诸如时间这样的任何其它量纲也同样有效。

以下参看图5详细说明基于这一原理的纠错译码器的实例，在图5中，输入端1接收接收字序列，校正子产生器2根据接收字计算校正子，欧几里德算法运算器3根据校正子和删除位置计算错误定位多项式和错误大小多项式，次数计算器4计算错误定位多项式的次数，“钱氏搜索”电路5根据错误定位多项式和错误大小多项式计算错误位置、错误大小和错误个数。如果接收字中的错误大于预定值，错误检测器6就根据由“钱氏搜索”电路计算的错误定位多项式的次数和错误个数输出不可校正错误标记信号，以便进行错误检测而不是进行错误校正。删除计算机7根据在C1译码中的不可校正错误标记的输信号输出用于C2译码的删除个数。在C1译码期间输出了不可校正错误标记信号的接收字的删除位置存储在删除位置存储器8中。从输出端9输出错误位置，从输出端10输出错误大小，表示不可校正错误的不可校正错误标记信号通过输出端11进行输出。

在图6的方框图中详细描述删除计算机，在该图中，计数器12计算具有输出的不可校正错误标记信号的接收字的个数，当对于预定值的连续接收字输出了不可校正错误标记信号时，由计数器和比较器组成的连续错误检测器13就输出成组错误信号。成组错误信号存储在存储器14中，比较器15和16将在C1译码结束时从计数器12输出的值与预定值Z₃和Z₄比较。与门17将比较器16的结果与存储器14合并。或门18将比较器15的输出与与门17的输出合并。选择器19根据或门的输出用于C2译码的删除个数。

图7是迄今已描述的纠错译码器的操作流程图。Z₁、Z₂、C₃和Z₄都是预定值。

以下参看图7所示的流程图描述译码器的操作。在C1译码时，从存储器读出的接收字序列通过输入端1输入到校正子产生器2，利用校正子产生器2计算校正子。接收字在此指被包括在沿C1方向的一行或沿C2方向的一列中的信号。术语“码字”代替术语“接收字”可被广泛地接受。但是，因为译码器接收码字所以在该说明书中全部用接收字来代替码字。校正子产生器2计算的校正子然后输入到欧几里德算法运算器3，欧几里德算法运算器3产生定位多项式。然后计算错误定位多项式和错误大小多项式的系数。欧几里德算法运算器3计算的错误定位多项式的系数输入到次数计算机4，以便计算和输出次数。错误定位多项式和错误大小多项式的系数输入到“钱氏搜索”电路5。计算的错误位置通过输出端9输出而错误大小通过输出端10输出。错误个数K1输出到错误检测器6。如果错误定位多项式的次数和从“钱氏搜索”电路输出的错误个数不一致、或者如果错误个数K1超过了Z₁(图7中的步骤3)，就从输出端11输出不可校正错误标记信号(S4)。

小于Z₁的错误个数K1(S1)表示接收字能被译码。因此，当没有从输出端11输出不可校正错误标记信号时(图7中的步骤1)，存储了相应于从输出端9输出错误位置的接收符号的存储器的内容就与通过输出端10输出的错误大小相加并且进行错误校正(S2)。在删除计算机7中的连续错误检测器13的计数器被清零。

另一方面，当从输出端11输出了不可校正错误标记信号时(S3)，存储了接收字的存储器的内容就不管错误位置或错误大小而保持原封不动。

计数器12对输入到删除计算机7的不可校正错误标记信号进行计数。不进行错误校正地对接收字的不可校正错误的个数进行计数。也对连续错误检测器13的内容进行计数。当可校正错误标记信号输入到删除位置存储器8时，C1码的位置、例如这一例子中的行的位置就被作为C2译码的删除位置来存储。

当已经对一组乘积码重复了上述操作时，例如在C1方向有n行的情况下在行中重复n次时，就结束了C1译码。

当连续错误检测器13的计数器的值在C1译码期间变成大于Z₂时，成组错误标记(连续错误标记)就被输出(S5)并在存储器14中被保持。

当C1译码结束时，接收字不可校正错误的个数L被存储在删除计算机7的计数器12中(S6)，这些错误不能在C1译码期间被校正。当计数器12输出的值L小于Z₃(S7)，或者如果值L小于在比较器16和与门17处的Z₄(S8)以及存在连续错误标记(S8)，则将进行删除和错误校正。或门18选择将从选择器19输出的删除符号的个数作为计数器12的内容，否则，就输出零，以便防止在C2译码中进行删除和错误校正。

对于C2译码，从存储了被逐行地译码的接收字的存储器中读出的序列将从输入端1输入到校正子产生器2，以便计算校正子。

校正子产生器2计算的校正子输入到欧几里德算法运算器3。利用删除计算机7输出的值作为删除个数和利用删除位置存储器8输出的值作为删除位置，就获得了错误定位多项式和错误大小多项式的系数。

欧几里德算法运算器3计算的错误定位多项式的系数输入到次数计算机4，计算并输出错误定位多项式的次数(degree)。欧几里德算法运算器3计算的错误定位多项式和错误大小多项式的系数输入到“钱氏搜索”电路5。在该电路中计算错误位置和错误大小，并分别从输出端9和10输出它们。“钱氏搜索”电路还计算错误个数并输出计算结果。

如果次数计算机4输出的错误定位多项式的次数与“钱氏搜索”电路5输出的错误个数不一致，就从输出端11输出不可校正错误标记信号。当这两个值一致时，从输出端10输出的错误大小就与存储了在C1方向上被译码的相应于从输出端9输出的错误位置的接收字的存储器中的内容相加，以便进行错误校正。

这样一来，当错误校正的可能性很大时(S8)，就根据是不考虑删除而进行错误校正还是进行删除和错误校正的决断来仔细地检查连续错误标记(成组错误)。

本发明的纠错译码器检查每行的超过第一预定值的连续的不可校正错误。在被第一译码器检测的接收字的不可校正错误的个数在第二和第三预定值之间的条件下，如果在C1方向上存在连续检测的不可校正错误，译码器就着手在列的方向上进行删除和错误校正，如果没有检测到连续的不可校正错误，就只进行错误校正。

本发明的纠错译码器和纠错译码方法具有以下优点：纠错译码器实现了进行有效的错误校正、将错误的校正减至最少的目的。通过逐行地检查接收字不可校正错误的个数，就能够确定删除的范围。当接收字的连续的不可校正错误、即成组错误看起来很可能出现时，就在C2译码中进行删除和错误校正。当判断检测的错误为随机错误时，如果存在许多删除，就只进行错误校正，这是因为这样不大可能导致错误的校正。

实施例2

实施例1描述了使用专用装置的纠错译码的实例。实施例2说明使用图4所示的通用处理器和存储器进行纠错译码的方法。

这一实施例的配置如图4所示，操作流程图如图8和图9所示。

在整个实施例中假定在C1码、即在行中的接收字个数为n2，在C2码、即在列中的接收字个数为n1。接收字首先沿C1方向、即在行中被译码。

在图8中的步骤11开始C1码的行1的译码，在步骤13用欧几里德算法进行错误检测。“钱氏搜索”电路计算定位多项式、获得错误位置和错误大小。通过计算错误位置的个数获得错误个数K1。如果在步骤15获得的值在可纠错范围之内，就在步骤16进行错误校正，译码在步骤17移向下一行。

在步骤12重复错误检测和错误校正直至涉及了全部n2行。在步骤14和步骤15检测被判断为不可校正的错误，在步骤18将这些错误的位置记作相应于在有限域中的i的元素。

在步骤19合计接收字的不可校正错误的个数。在步骤20判断是否出现了成组错误。当接收字的不可校正错误的个数大于Z₂时，就在步骤21设置连续错误标记。

在步骤17开始译码新的行。在沿行的方向对C1码进行n2次译码之后，就如图9所示，沿列的方向对C2码进行n1次译码。

在步骤22开始列1的C2译码，在步骤24，如果值L小于Z₃，欧几里德算法运算器就在步骤28进行计算以便进行删除和错误校正。就是说，对于C2方向获得了错误位置和错误大小。

如果在步骤25中，C1译码中的值L大于Z₄，在步骤26就只进行错误校正计算，认为没有删除。

如果值L在Z₃和Z₄之间，则在步骤27中检测连续错误标记的存在。在步骤26或在步骤28进行错误校正计算。在这一例子中，错误定位多项式的次数和被存储的错误的个数在步骤29中进行计算。如果这些值在步骤30中一致，就在步骤31进行错误校正。

然后在步骤32对下一列进行译码，在C2方向上重复n1次上述操作。

本发明的纠错译码方法就在于在第一方向C1上对代码信号译码II2次。在C2译码之前，检查超过第一预定值的连续不可校正错误的存在，并且比较接收字的不可校正错误的个数以便确定其是否在第二和第三预定值之间。当沿C1方向检测的不可校正错误的个数确实在第二和第三预定值之间、并且存在超过第一预定值的连续不可校正错误时，就进行删除和错误校正，如果连续不可校正错误的个数小于第一预定值，就忽略删除只进行错误校正。

通过在C1译码中检查接收字的不可校正错误的个数来确定删除的范围，通过检查接收字的连续不可校正错误的存在来存储成组错吴的可能出现。当看来似乎已出现成组错误时，就根据存储的值进行删除和错误校正。当很可能已出现了随机错误并且存在接收字的许多不可校正错误时，就只进行错误校正，以便使接收字不被错误地校正。

实施例3

以下说明实施例3的纠错译码器的原理。按照由每个字的长度与每个字的纠错码的长度之比确定的最大可校正错误值对其进行了彻底的纠错的大量的接收字一定与大量的错误的校正相关。在这种情况下，因为删除和错误校正将很可能产生对于C2译码的更多的错误的校正，所以就进行错误校正，不考虑删除。同样地，当对其进行了彻底的纠错的接收字的数目较小时，就认为存在较少的错误的校正。因此，由于错误的校正的可能性较低，所以对于C2译码就选择删除和错误校正。

图10是表示图5所示错误检测器6b和删除计算机7b的细节的方框图。错误检测器6b由三个基本部件组成：两个比较器20和21以及或非门22。比较器20将错误定位多项式的次数与“钱氏搜索”电路计算的错误个数比较。另一比较器21将错误定位多项式的次数与在C1译码中已进行了最大错误校正的错误个数比较。计数器23计算对其使用了最大可校正错误值的接收字的数目。加法器24求计数器12和计数器23的最后输出的和、例如在C1译码中检测的接收字的不可校正错误的个数与对其进行了最大错误校正的接收字的个数之和。比较器25将加法器24的输出与预定值Z₂比较。

图11表示在实施例3中说明的纠错译码器所进行的错误校正。在这一流程图中，值Z₁、Z₂、Z₃和Z₄为预定的。

在此只说明错误检测器6b和删除计算机7b的操作，这是因为这一实施例的所有其它操作功能与在实施例1中描述的相同。

次数计算机4计算的错误定位多项式的次数和“钱氏搜索”电路5计算的错误个数K输入到错误检测器6b。比较器20将次数与值K进行比较，如果这两个值不相等，就输出不可校正错误标记信号(S47)。比较器21将次数与最大可校正错误值Z₁比较，如果这两个值不相等就输出信号。当这两个值相等时(S43)，就从或非门22输出最大错误校正标记信号而不是不可校正错误标记信号(S48)。

当不可校正错误标记信号输入到计数器12时，就合计了在C1译码中接收字的不可校正错误的个数。对每一译码行输入最大错误校正标记信号并在计数器23中对其进行计数。当已重复了n2次针对行的译码时，即当C1译码已结束，计数器23就计算了对其进行了最大错误校正的接收字的个数M(S49)。

当C1译码已结束，加法器24就将计数器12输出的值L与计数器23输出的值M相加。然后，如果加法器24输出的值小于Z₂(S53)，比较器25就输出信号。当比较器15发现计数器12输出的值小于Z₃(S50)、或者如果比较器16和与门17发现该值小于Z₄(S51)，并且当比较器25已输出了信号(S53)，错误的校正的可能性就认为较小，计数器12输出的值L经由或门18被作为删除符号个数传送给选择器19，并对C2译码进行删除和错误校正。

在其它情况下，当错误的校正的可能性较大时，就输出零作为删除符号的个数，在C2译码中假定没有删除，只进行错误校正。

此外，对具有相同的最大可校正错误值的接收字的错误个数进行检查，然后对接收字的不可校正错误的个数进行检查。如果在C1译码中检测的接收字的不可校正的个数在第二和第三预定值之间时，就将每行中设置的最大错误校正标记或者每行中设置的最大错误校正标记和在C1译码中检测的接收字的不可校正错误的个数之和与第四预定值比较。当比较的值小于第四预定值时，就进行删除和错误校正，如果该值大于第四预定值，就只进行错误校正。

通过检查超过最大可校正错误值的接收字的个数来计算删除的范围。如果具有超过最大可校正错误值的错误的接收字个数较大，对C2译码就只进行错误校正，以便使接收字不被错误地校正。如果具有超过最大可校正错误值的错误的接收字个数较小，就选择删除和错误校正。

实施例4

在实施例3中，虽然在输入到比较器25之前，加法器24将计数器12输出的值与计数器23输出的值相加，但通过改变预定值Z₃，将计数器23输出的值输入到比较器25同样有效。

此外，对在行中检测的接收字的不可校正错误的个数进行了计算，然后还检查了具有相同的由基于译码结果的设计距离确定的最大可校正错误值的接收字的个数。如果接收字的不可校正错误的个数在第二和第三预定值之间，则每行中设置的最大错误校正标记或者每行中设置的最大错误校正标记和在行中的接收字的不可校正错误的个数之和就与第四预定值比较。当该值小于第四预定值，就进行删除和错误校正。如果该值大于第四预定值，就进行错误校正，不考虑删除。

确定在C1方向上具有超过最大可校正错误值的错误的接收字的个数。当检测到许多具有超过最大可校正错误值的错误的接收字时，就只进行错误校正，以便使接收字不被错误地校正，而当具有超过最大可校正错误值的错误的接收字的个数可忽略时，就进行删除和错误校正。

实施例5

实施例5利用图12和图13所示的操作流程图来描述用图4所示的通用处理器和存储器实现的纠错译码方法。

在步骤61，开始对行1译码。在步骤63，用欧几里德算法进行错误检测：输入错误定位多项式的系数以便获得错误位置和错误大小。

在步骤65，如果它被证明在可进行译码的范围之内，就在步骤66开始错误校正，然后在步骤67移向下一行。

在步骤62重复错误检测和错误校正直至译码了全部n2行。在步骤64和65检测被确定为不可校正的接收字，它们的位置在步骤70被记作相应于在有限域中的i的元素。

在步骤69将最大可校正错误值作为最大错误校正标记来计数，在步骤71合计接收字的不可校正错误的个数。

译码在步骤67移向下一行。当在行的方向上对C1码译码n2次时，如图13所示，就将在列在方向上对C2码进行n1次译码。

在图13的步骤72中从列1开始C2译码。如果接收字不可校正错误的个数L小于Z₃(S74)，就通过欧几里德算法运算器进行删除错误校正计算(S81)。

如果C1译码中的值L大于Z₄(S75)并且如果L和M之和小于或等于Z₂(S80)，则在步骤76中只进行错误校正、不考虑删除。

如果值L在Z₃和Z₄之间，则根据在步骤76或步骤81进行哪一种错误校正计算来确定值L和最大错误校正标记之和或者最大错误校正标记是否小于预定值。

当错误定位多项式的次数(S77)与“钱氏搜索”电路计算的错误个数一致时(S78)，就在步骤82中进行错误校正。

译码在步骤79移向下一列，在列的方向上对于C2码重复上述操作n1次(S73)。

此外，对在行中的接收字的不可校正错误的个数进行检查。然后在C2译码中假定没有删除，产生错误定位多项式。如果多项式的次数小于第一预定值，就进行错误校正。如果次数大于第一预定值，就将在行中的接收字的不可校正错误的个数与第二预定值比较。如果该个数小于第二预定值，就利用在位置存储器中的错误位置来进行重新计算，以便在C2方向进行删除和错误校正。如果该值大于第二预定值，就在C2方向不考虑删除地进行错误校正。

此外，对于C2码，假定没有删除，进行错误校正。根据结果，错误定位多项式的次数大于某一值，利用删除位置来再次进行错误校正。校正了随机错误，将可能的错误的校正减至最少，但当已出现成组错误时，就进行删除和错误校正。

实施例6

实施例6基于以下原理：当已出现随机错误时，在C1译码中检测的大多数删除不是实际的错误。如果在C1译码中已进行了错误的校正，如果对C2译码进行删除校正，则错误的校正的可能性就变大。倒不如不考虑删除，可利用错误校正来译码接收字。另一方面，当已出现成组错误时，在C1译码中的删除实际上是不正确的。因此，是删除和错误校正而不是错误校正使C2译码成为可能。根据这一原理，不管成组还是随机错误，首先进行错误校正，不考虑删除。然后，被证明为大于预定值的错误定位多项式的次数被作为成组错误的出现。因此，这一实施例的纠错译码器通过利用删除位置进行错误校正就显著地改善了错误校正的能力。

除错误检测器和删除计算机外，这一实施例的配置与实施例1的配置相同。图14是表示错误检测器6c和删除计算机7c的细节的方框图。在图14中，6c表示错误检测器而7c表示删除计算机。比较器26将错误定位多项式的次数与预定值比较，如果次数大于该值，就输出欧几里德再启动信号。欧几里德再启动信号存储在存储器27中，选择器28根据欧几里德再启动信号的存在来选择删除个数。这一欧几里德再启动信号还输入到欧几里德算法运算器3。

图15所示流程图描述了实施例6的纠错译码方法的实例。在图15中，值Z₁、Z₂和Z₃是预先确定的。如在实施例3中那样，由于这一实施例的所有其它操作功能与实施例1中描述的相同，所以只描述错误检测器6c和删除计算机7c的操作。

次数计算机4计算的错误定位多项式的次数和“钱氏搜索”电路5计算的错误个数输入到错误检测器6c。如果值K大于Z₁(S93)，就象在错误个数大于Z₁的情形那样，比较器20输出不可校正错误标记信号(S94)。如果K＝＜Z₁(S91)，就进行通常的错误校正(S92)。当不可校正错误标记信号输入到计数器12时，删除计算机7c就对在C1译码中的接收字的不可校正错误个数进行计数。当这一操作被重复n2次时，C1译码就结束了，在计数器12中合计接收字的全部不可校正错误。

当C1译码已经结束时，接收字不可校正错误的个数L就存储在删除计算机7c的计数器12中。如果计数器12输出的值小于Z₃，比较器15就选择将要从选择器19输出的删除符号个数。

当从选择器28输出零时(S95)，就对C2译码开始错误校正。换句话说，不考虑在C1译码中检测的删除，进行错误校正。次数计算机4根据欧几里德算法运算器计算的错误定位多项式计算错误定位多项式的次数(S96)。当比较器26发现次数大于Z₂时，就输出欧几里德再启动信号(S97)。

输出的欧几里德再启动信号存储在存储器27中。选择器28转接选择器19输出的值作为删除个数。校正子产生器2计算的校正子重新装入欧几里德算法运算器3。在删除计算机7c输出的删除个数的基础上(S97)，欧几里德算法运算器3从删除位置存储器8读出删除位置，以便进行删除和错误校正。

这样一来，就先进行错误校正，不考虑删除。如果由于进行错误校正而增大了错误定位多项式的次数，就用错误位置来再进行错误校正。

此外，对在行中检测的接收字的不可校正错误个数进行检查。假定对于C2译码没有删除，产生错误定位多项式，以便将错误定位多项式的次数与第一预定值比较。如果次数大于第一预定值，则在行中的接收字的不可校正错误的个数与第二预定值比较。如果该个数小于第二预定值，就利用在位置存储器中的位置进行重新计算，并进行删除和错误校正。如果该值大于第二预定值，就进行错误校正，不考虑删除。

此外，假定没有删除，对C2译码进行错误校正。在校正结果的基础上，如果错误定位多项式的次数大于某一值，就利用删除位置再次进行错误校正。因此就校正了随机错误，将可能的错误的校正减至最少，而当已出现成组错误，就进行删除和错误校正。

实施例7

在上述实施例中，比较器15确定从选择器19是输出接收字的不可校正错误的个数还是输出零。如已在实施例1和实施例3中描述的那样，还可以通过选择器19从更大的输出值范围选择输出来实现同样的信号传输作用等，该更大的输出值范围包括连续错误检测器和最大错误校正标记信号。

在C1译码的基础上，在C2方向上译码接收字。根据在C2译码中被校正的接收字重新计算在C1译码中尚未被校正的错误。在C2译码中不能被校正的接收字很可能就是在C1译码中不能被校正的接收字。因为只对在C1译码中不能被校正的接收字利用在C2译码中获得的接收字来再次进行错误校正，所以能够以省时的方式、以很少的错误的校正有效地进行纠错译码。

实施例8

实施例8利用图4所示的通用处理器和存储器对实施例6描述的纠错译码方法的实例进行详细的说明。

图16和17是操作流程图。在步骤101，沿C1方向从行1开始对接收字译码，在步骤103基于欧几里德算法进行错误检测。如果检测的错误在可被译码的范围内，就在步骤106进行错误校正，译码然后移向下一行(S107)。

重复错误检测和错误校正直至对所有行，例如n2行进行了译码。在步骤104和步骤105检测被判断为不可校正的接收字，并在步骤108将它们的位置写入存储器。在步骤109合计值L。

在步骤107，译码移向下一行。当沿X方向已对C1码译码n2次时，就如图17所示，沿Y方向对C2码进行n1次译码。

在步骤110，从列1开始对C2码译码。在步骤112，假定在C1译码中没有出现删除，计算错误定位多项式。在步骤113的操作是非常重要的。如果通过忽略删除计算的错误定位多项式次数小于Z₂，就在步骤116将次数与错误个数比较，在步骤119进行错误校正。

另一方面，如果错误定位多项式的次数大于Z₂，则在步骤114将错误检测标记的个数与Z₃比较。如果错误检测标记的个数较小，就认为错误的校正的可能性较小。然后复位错误检测的个数并在步骤115再次计算错误定位多项式。

如果次数大于Z₃，则在步骤119不考虑删除，只进行错误校正。

译码将在步骤118移向下一列，在列的方向上对C2码重复上述操作n1次。

实施例9

在进行了C1和C2译码之后错误仍未被校正是可能的。这些错误很可能就是在C1译码中不能被校正的接收字。基于这一原理，这一实施例描述通过只对在C1译码中不能被校正的接收字的错误再次进行译码实现了有效和省时的错误校正目的的译码方法的实例。

在已对乘积码译码之后，根据错误位置信息读出其中已存储了被译码的C1和C2信息的存储器地址，以便对在C1译码中被检测但未被校正的接收字再进行错误校正。

这一实施例的操作流程图如图18、19和20所示。

在步骤120，首先从行1开始对C1码译码。在步骤122，利用欧几里德算法进行错误检测。如果检测的错误在可译码范围之内，就在步骤124进行错误校正，译码在步骤125移向下一行。

重复错误检测和错误校正直至所有n2行被译码(步骤121)。在步骤123中被检测为不可校正的接收字的位置在步骤126中被写入到存储器，在步骤127合计接收字的不可校正错误的个数L。

译码在步骤125将移向下一行。当沿X方向已对C1码译码n2次时，就如图19所示，沿Y方向对C2码进行n1次译码。

在步骤128，从C2码的列1开始译码。如果接收字的不可校正错误的个数大于Z₁，就在步骤131中假定没有删除，计算错误定位多项式和错误大小多项式。当其小于Z₁时，就在步骤136根据接收字的不可校正错误的个数计算错误定位和错误大小多项式。然后在步骤135根据上述计算进行错误校正。

一旦对所有n1列完成了计算，就从步骤137开始再一次检查接收字。然后对其错误在C1译码中不能被校正的接收字计算错误定位和错误大小多项式。

这样一来，在由于C2译码而获得的值的基础上，在步骤143进行错误校正，获得了被认为是正确的代码。

在步骤142重复这一操作L次，就是说，在C1译码中不能被校正的接收字的错误个数。

于是已描述了本发明的几个特定实施例，对本领域的技术人员而言，各种改变、修改和改进是显而易见的。这样的改变、修改和改进被认为是所公开内容的一部分并在本发明的精神和范围之内。因此，以上描述只是作为示范而已，不作为一种限制。本发明只受权利要求及其等同物的限制。

Claims

1.纠错译码器，利用“钱氏搜索”电路对由包括纠错码的n2行×n1列的符号组成的编码信号进行译码，以便进行错误校正或删除及错误校正，以及根据纠错码校正在编码信号中的接收字的错误，该纠错译码器的特征在于包括：

(A)第一译码器，校正作为接收字的每行的错误，以及对接收字的不可校正错误进行n2次检测；

(B)标记存储器，与第一译码器连接，在接收字的连续检测的不可校正错误的个数超过第一预定值时设置成组错误标记；

(C)位置存储器，与第一译码器连接，存储具有第一译码器检测的不可校正错误的行的位置；

(D)计数器，与第一译码器连接，计算具有第一译码器检测的不可校正错误的行的数目；

(E)第二译码器，与第一译码器连接，对作为接收字的每列的错误进行n1次校正，在存在成组错误标记和计数器的数值在第二和第三预定值的情况下，利用在位置存储器中的位置、根据删除和错误校正对接收字进行译码，在计数器的数值在第二和第三预定值之间和不存在成组错误标记的情况下，根据错误校正对接收字进行译码。

2.根据权利要求1的纠错译码器，进一步包括

(F)第一计数器，与第一译码器连接，计算具有第一译码器检测的不可校正错误的行的数目；

(G)第二计数器，与第一译码器连接，在每行中的符号的被检测错误的个数等于最大可校正错误值时计算在每行中设置的最大错误校正标记的个数；以及其中，

第二译码器，对作为接收字的每列的错误进行n1次校正，在第一计数器的数值在第二和第三预定值之间以及第一计数器的数值和第二计数器的数值之和小于第一预定值的情况下，利用在位置存储器中的位置、根据删除和错误校正对接收字进行译码，以及在第一计数器的数值在第二和第三预定值之间以及第一计数器的数值和第二计数器的数值之和大于第一预定值的情况下，根据错误校正对接收字进行译码。

3.权利要求2所述的纠错译码器，其特征在于：第二译码器在第一计数器的数值在第二和第三预定值之间以及第二计数器的数值不与第一预定值比较而是小于第四预定值的情况下，利用在位置存储器中的位置、根据删除和错误校正对接收字进行译码，在第一计数器的数值在第二和第三预定值之间以及第二计数器的数值不与第一预定值比较而是小于第四预定值的情况下，根据错误校正对接收字进行译码。

4.根据权利要求1或2的纠错译码器，其特征在于还包括用于计算欧几里德算法的次数的次数计算器，当在次数计算器中的次数与由“钱氏搜索”电路在每行中检测的错误位置的个数不相同时，次数计算器就将行设定为不可校正错误行。

5.权利要求1所述的纠错译码器，其特征在于第一译码器在第二译码器校正了在每列中的接收字的错误之后只校正在每行中的接收字的不可校正错误。

6.对由包括纠错码的n2行×n1列的符号组成的编码信号进行译码和校正接收字的错误的译码方法，其特征在于包括以下步骤：

(A)根据接收字的校正子产生定位多项式；

(B)根据定位多项式分析每行中的接收字的错误位置和错误大小；

(C)在出现错误和错误位置的个数小于每行中的第一预定值的情况下，利用纠错码校正每行中的接收字；

(D)在错误位置的个数大于每行中的第一预定值时，在有限域中将行的元素作为不可校正错误元素来存储；

(E)在接收字的连续检测的不可校正错误的个数超过第二预定值时，设置成组错误标记；

(F)根据定位多项式分析每列中的接收字的错误位置和错误大小；

(G)在错误出现于每一列中、不可校正错误元素的个数小于第三预定值以及存在成组错误标记时，根据删除和错误校正校正每列中的接收字；以及

(H)在错误出现于每一列中、不可校正错误元素的个数小于第三预定值以及不存在成组错误标记时，根据错误校正校正每列中的接收字。

7.权利要求6所述的译码方法，其特征在于还包括以下步骤：将定位多项式次数的值与错误位置的个数比较，在定位多项式的次数与错误位置的个数不相同时，将元素设定为不可校正错误元素。

8.权利要求6所述的译码方法，其特征在于在步骤(F)和(G)之间还包括以下步骤：将定位多项式次数的值与每列中错误位置的个数比较，当该列的定位多项式的次数与错误位置的个数不相同时，就让错误原样不变。

9.权利要求6所述的译码方法，其特征在于在最后的步聚之后还包括以下步骤：利用列中的校正步骤在行的不可校正错误元素中填充接收字，并在填充步骤的基础上再次校正接收字。