CN1264032B - 数据错误纠正装置 - Google Patents

Abstract

在用多个错误纠正码的装置中，通过有效使用纠正能力大的编码的并发位计算电路，增大纠正能力小的编码的并发位计算并行处理编码字数，实现纠错高速化。由伽罗瓦域的加法器、触发电路和伽罗瓦域的元的第1常数乘法器，构成16个并发位计算电路，计算8重错误纠正里德索洛蒙(RS)码的1编码字的并发位。部分并发位计算电路上附有伽罗瓦域的元的第2常数乘法器，及选择第1和第2常数乘法器的选择电路，构成能8并行处理1重错误纠正RS码的并发位计算电路。

Description

数据错误纠正装置

技术领域

本发明涉及一种使用多个错误纠正码，纠正数据错误的数据错误纠正装置。

背景技术

作为数据处理系统的高可靠性手段，应用各种机器里纠正数据错误的错误纠正码。特别是，包含里德索洛蒙码的BCH(Bose-Chaundhuri-Hocqenghen)码由于码的效率高成为重要的编码之一。里德索洛蒙码就是在设定原始多项式为W(z)，W(z)＝0的根为α时，将该根α作为原始元的伽罗瓦域(Galois field)上的编码，是数据块出错纠正码之一。

图3表示刊载于特开平5-55926号公报上的的错误纠正装置的结构。该错误纠正装置具有存储输入数据的数据存储器72，计算附加到输入数据上的多重错误纠正码的并发位的并发位计算电路76、78，存储用该并发位计算电路76、78算出的并发位的并发位存储器80，读出存储于并发位存储器80的并发位并改写数据存储器72上的错误数据的错误检出纠正处理电路86。并且，OR电路82求出已计算出的并发位的全部二进制数的逻辑和(即，“或”)，由其结果作为表示数据出错存在的信息，存入标记存储器84里。并且，定时控制电路88控制该错误纠正装置的动作定时。并发位计算电路76、78由加法器20、22、24、36、38、40，延迟器26、28、30、42、44、46、52、54、56，及伽罗瓦域元的常数乘法器32、34、48、50构成，设若输入数据Wi，生成多项式的根为αm，则按照以下的式(1)、(2)和(3)，计算并发位S0、S1和S3。

(数1)

$S0=\underset{i=1}{\overset{n}{\mathrm{\Σ}}}\mathrm{Wi}---\left(1\right)$

$S1=\underset{i=1}{\overset{n}{\mathrm{\Σ}}}\mathrm{Wi}{\mathrm{\α}}^{n-i}---\left(2\right)$

$S2=\underset{i=1}{\overset{n}{\mathrm{\Σ}}}\mathrm{Wi}{\left({\mathrm{\α}}^2\right)}^{n-i}---\left(3\right)$

而且，错误检出纠正处理电路86由并发位存储器80读出并发位S0、S1、S2，在至少一个并发位不是“0”的情况下，由S0～S2算出出错的位置和大小，根据其结果，改写数据存储器72上的输入数据中出错的数据。

这样，倘采用上述错误纠正装置，与由输入端子70输入的数据被写入数据存储器72的同时，在并发位计算电路76、78中，计算附加于该数据的错误纠正码的并发位，根据该并发位的结果，纠正数据的错误，纠正后的数据变成由输出端子74输出的结果。

一般，在进行t(t是1以上的整数)重错误纠正BCH编码的错误纠正处理的时候，对2t个的并发位进行计算。例如，在数字音频磁带录音机(DAT)中，为了纠正数据的错误，附加了3重错误纠正里德索洛蒙码或2重错误纠正里德索洛蒙码，这时，对于1编码字，以3重错误纠正里德索洛蒙码计算6个并发位，以2重错误纠正里德索洛蒙码计算4个并发位。

图2中，示出了用于数据错误纠正装置的现有并发位计算电路的构成图。并发位计算电路，如图2所示，是由6个并发位计算电路300～305构成，这些并发位计算电路300～305，分别具有输入数据的输入端子320～325，伽罗瓦域的加法器340～345，作为延迟器的触发电路360～365，和对伽罗瓦域的元α的0次方(以下，表记为“α^0”)～α^5进行相乘的常数乘法器380～385。而且，在这些并发位计算电路300～305中，每当从编码字的开头数据起按顺序，向各输入端子320～325输入数据，就在常数乘法器380～385中，对触发电路360～365中的保持数据进行常数相乘，在加法器340～345中，将该常数相乘后的数据与上述输入数据进行相加，再用该加法器340～345输出的数据，更新上述触发电路360～365中的保持数据，由此，计算出错误纠正码的并发位。例如，为了计算3重错误纠正里德索洛蒙码的6个并发位，在使用上述并发位计算电路300～305计算3重错误纠正里德索洛蒙码的并发位的情况下，就使用全部6个并发位计算电路。另一方面，为了计算2重错误纠正里德索洛蒙码的4个并发位，在使用上述并发位计算电路300～305计算2重错误纠正里德索洛蒙码的并发位的情况下，就只使用上述并发位计算电路300～305之中，纠正能力小的一方的4个并发位计算电路300～303，而不用其余两个并发位计算电路304和305的计算结果。

这样，在上述的并发位计算电路，以通用的硬件，实现象3重错误纠正里德索洛蒙码和2重错误纠正里德索洛蒙码这样的纠正能力不同的编码的并发位计算。

然而，在上述现有的例子中，虽然以通用的硬件实现纠正能力不同的并发位计算，但由于象3重错误纠正里德索洛蒙码和2重错误纠正里德索洛蒙码这样的纠正能力相差小，因而不可能得到使3重错误纠正里德索洛蒙码的并发位计算的处理编码字数与2重错误纠正里德索洛蒙码的并发位计算的处理编码字数不相等。就是说，进行3重错误纠正里德索洛蒙码的并发位计算，或进行纠正能力小的2重错误纠正里德索洛蒙码的并发位计算时，无论哪一次处理中，也不可能是1编码字处理。特别是，在编码长度大时或编码字上没有错误时，为了按照并发位计算，决定错误纠正装置的纠正速度，为了使错误纠正的高速化，希望并发位计算效率高。

尽管，在例如，DVD-ROM用错误纠正装置中，不仅对DVD-ROM，而且对CD-ROM和CD-R等的数据都必须进行处理。为了在DVD-ROM上，附加8重错误纠正里德索洛蒙码和5重错误纠正里德索洛蒙码，在CD-ROM上附加1重错误纠正里德索洛蒙码，就需要纠正能力大小不同的错误纠正码的并发位计算。这时，在示于图2的上述并发位计算电路中，象DVD-ROM那样纠正能力大的编码，例如按8重错误纠正里德索洛蒙码，要计算16个并发位计算，这时，用于进行并发位计算，就需要16个并发位计算电路。因此，在已具有这种并发位计算电路的数据错误纠正装置中，进行象上述DVD-ROM那样的纠正能力大的编码的并发位计算要用16个并发位计算电路，而在象上述CD-ROM那样的纠正能力小的编码，例如1重错误纠正里德索洛蒙码中由于计算2个并发位，所以在进行并发位计算时，只使用上述16个并发位计算电路之中的2个，其余的14个并发位计算电路不用。特别是，以共同的并发位计算电路处理纠正能力不同的编码的情况下，在低能力编码的并发位计算的时候，由于存在很多未使用的并发位计算电路，因此并发位计算的效率恶化，结果是，存在难以提高数据错误纠正处理速度的问题。

发明内容

本发明就是鉴于上述问题而作出发明的，就是在数据错误纠正装置中，在处理纠正能力不同的编码的共同并发位计算电路里，通过构成可以并行处理纠正能力小的编码的并发位计算，实现错误纠正处理的高速化。

根据本发明的一种数据错误纠正装置，用于对附加了n重错误纠正BCH码的数据和附加了t重错误纠正BCH码的数据进行错误纠正处理，其中t、n为具有n≥2t关系的正整数，其特征在于包括：2n个以上的并发位计算电路，分别具有：利用伽罗瓦域的元，计算n重错误纠正BCH码的并发位的第1常数乘法器；把在该第1常数乘法器求得的数据与从输入端子来的输入数据相加的加法器；和将保持的数据更新为来自上述加法器的数据的延迟器，在上述2n个并发位计算电路中，除规定的2t个以外的任意2t个以上的并发位计算电路还具有：利用伽罗瓦域的元，计算上述t重错误纠正BCH码的并发位的第2常数乘法器，以及在输入附加了n重错误纠正BCH码的数据时选择上述第1常数乘法器，在输入附加了t重错误纠正BCH码的数据时选择上述第2乘法器的选择器。

附图说明

图1为本发明一个实施例的并发位计算电路的结构图。

图2为现有的并发位计算电路的结构图。

图3为现有的数据错误纠正装置的结构图。

具体实施方式

在图1中，示出本发明实施例的数据错误纠正装置中使用的并发位计算电路的结构图。

在本实施例中，对于DVD-ROM的8重错误纠正里德索洛蒙码的1个编码字，具有16个并发位计算电路的情况下，示出了并行处理CD-ROM的1重错误纠正里德索洛蒙码的8个编码字的例子。就是，本实施例中的并发位计算电路，如图1所示，由对于DVD-ROM的8重错误纠正里德索洛蒙码的16个并发位计算电路100～115构成，这些并发位计算电路100～115，分别具有输入数据的输入端子120～135，伽罗瓦域的加法器140～155，作为延迟器的触发电路160～175，和将伽罗瓦域的元α的0次方(以下，表记为“α^0”)～α^15进行相乘的常数乘法器180～185。

并且，本实施例中的并发位计算电路具有，可用于并行处理CD-ROM的1重错误纠正里德索洛蒙码，除上述16个并发位计算电路100～115之中纠正能力小的一方的2个(100和101)以外的其余并发位计算电路102～115，分别使用于计算上述CD-ROM的1重错误纠正里德索洛蒙码，求出伽罗瓦域的元α^0和α^1的第2常数乘法器200～213；及将与上述加法器142～155的连接，从上述第1常数乘法器182～195转换到该第2常数乘法器200～213上的选择电路222～235。就是，把新的相乘α^0的第2常数乘法器200～206和相乘α^1的第2常数乘法器207～213，及选择上述第1常数乘法器和该第2常数乘法器的选择电路222～235，附加到各个并发位计算电路102～115上，由此，构成8组1重错误纠正里德索洛蒙码的错误纠正里德索洛蒙码的并发位计算电路100和101、102和103、104和105、106和107、108和109、110和111、112和113、114和115。

接着，说明上述并发位计算电路的动作。

在DVD-ROM的8重错误纠正里德索洛蒙码的并发位计算时，对1个编码字计算16个并发位。这时，对伽罗瓦域的元α^0～α^15为止进行相乘，因而在示于图1的并发位计算电路102～115中的选择电路222～235都与第1常数乘法器182～195连接。而且，关于DVD-ROM的8重错误纠正里德索洛蒙码的1个编码字，从其开头起按顺序，向并发位计算电路100～115的各个输入端子120～135输入数据。每当数据被输入到各个输入端子120～135，就在第1常数乘法器180～195中，对触发电路160～175的保持数据进行常数相乘，在加法器140～155中，将该常数相乘后的数据与上述输入数据进行相加，再用该加法器140～155输出的数据，更新上述触发电路160～175的保持数据，由此，计算出8重错误纠正码的并发位。另外，并发位S的计算，按现有技术中说过的计算公式(1)～(3)进行类似计算，在这里，其详细说明从略。

一方面，在1重错误纠正里德索洛蒙码的并发位计算时，对1个编码字计算2个并发位。这时，对伽罗瓦域的元α^0与α^1进行相乘，因而在图1示出的并发位计算电路102～115中的选择器222～235都与第2常数乘法器200～213连接。而且，CD-ROM的1重错误纠正里德索洛蒙码的第1编码字在并发位计算电路100和101，第2编码字在并发位计算电路102和103，第3编码字在并发位计算电路104和105，第4编码字在并发位计算电路106和107，第5编码字在并发位计算电路108和109，第6编码字在并发位计算电路110和111，第7编码字在并发位计算电路112和113，第8编码字在并发位计算电路114和115中，分别进行计算。关于这些第1～第8的编码字，都从其开头起按顺序，向并发位计算电路100～115的各输入端子120～135输入数据。每当输入数据被输入到各输入端子120～135后，就在第1常数乘法器180、181和第2常数乘法器200～213中对触发电路160～175的保持数据进行常数相乘，再在加法器140～155中把该常数相乘后的数据相加起来，并用来自该加法器140～155的输出数据，更新上述触发电路160～175的保持数据，由此，算出1重错误纠正里德索洛蒙码的并发位。

这样，在1次并发位计算处理中，在8重错误纠正里德索洛蒙码中不可能只有1个编码字，而在计算1重错误纠正里德索洛蒙码的并发位时，变成并行处理8个编码字。因此，在计算1重错误纠正里德索洛蒙码的并发位时，就可以全部有效地使用在8重错误纠正里德索洛蒙码的并发位计算中所使用的并发位计算电路100～115，8个并行处理1重错误纠正里德索洛蒙码的并发位计算，结果是，具有可使错误纠正处理高速化的这种效果。

另外，上述并发位计算电路100～115，可以组装到图3示出的数据错误纠正装置中进行使用。

并且，在上述实施例中，作为常数乘法器的组合，虽然在伽罗瓦域的元α^15和α^1(并发位计算电路115)、α^14和α^0(并发位计算电路114)、α^13和α^1(并发位计算电路113)、α^12和α^0(并发位计算电路112)、α^11和α^1(并发位计算电路111)、α^10和α^0(并发位计算电路110)、α^9和α^1(并发位计算电路109)、α^8和α^0(并发位计算电路108)、α^7和α^1(并发位计算电路107)、α^6和α^0(并发位计算电路106)、α^5和α^1(并发位计算电路105)、α^4和α^0(并发位计算电路104)、α^3和α^1(并发位计算电路103)、以及α^2和α^0(并发位计算电路102)中示出了选择其中哪个常数乘法器的例子，但是本发明并不限于上述例子的组合，而是也可以任意组合。

并且，在上述实施例中，虽然示出了在并发位计算电路100、101上没有第2常数乘法器和选择电路的例子，但是本发明并不限于上述例子，而是也可以作为在并发位计算电路100、101上具有第2常数乘法器和选择电路的结构。

并且，在上述实施例中，至于纠正能力小的编码的并行处理编码字数，虽然示出了全部使用纠正能力大的编码的并发位计算例子，但是本发明如以2个并行以上处理纠正能力小的编码的并发位计算，也能达到所述的错误纠正处理高速化的目的，因而在纠正能力小的编码的并发位计算中，并没有全部使用纠正能力大的编码的并发位计算电路，而且也可以作成按2并行、3并行或4并行等进行并行处理。

并且，在上述实施例中，虽然示出了对于8重错误纠正码与1重错误纠正码之间的2种类型能力不同的错误纠正码的例子，但是本发明也可以作成，对于例如，8重错误纠正码、2重错误纠正码与1重错误纠正码之类3种类型或其以上的能力不同的错误纠正码，并具有多个伽罗瓦域的元的常数乘法器及选择这些多个常数乘法器的选择器。

另外，在上述实施例中，虽然示出了对于8重错误纠正码与1重错误纠正码的例子，但是本发明也可以构成应用于8重错误纠正码与2重错误纠正码、8重错误纠正码与3重错误纠正码、5重错误纠正码与1重错误纠正码之类任意2种或其以上能力不同的错误纠正码。

如上所述，根据本发明的错误纠正装置，在进行附加了t(t为1以上的整数)重错误纠正BCH编码的数据错误纠正处理时，该t重错误纠正BCH编码的并发位计算并行处理编码字数，象变成上述2t重以上的n(n为1以上的整数)重错误纠正BCH编码的并发位计算处理编码字数的2倍以上一样，把除上述2n个并发位计算电路中纠正能力小的2t个以外的任意2t个以上的并发位计算电路具有，使用于计算上述t重错误纠正BCH编码的并发位的，求出伽罗瓦域的元的第2常数乘法器，及从上述第1常数乘法器转换到上述第2常数乘法器与上述加法器之间连接的选择器。因此，由于有效地使用了纠正能力大的2t重以上的n重错误纠正BCH编码并发位计算电路，使纠正能力小的2t重以上的n重错误纠正BCH编码并发位计算高速化，结果是，具有实现错误纠正处理高速化的效果。

Claims (1)

1.一种数据错误纠正装置，用于对附加了n重错误纠正BCH码的数据和附加了t重错误纠正BCH码的数据进行错误纠正处理，其中t、n为具有n≥2t关系的正整数，其特征在于包括：2n个以上的并发位计算电路，分别具有：利用伽罗瓦域的元，计算n重错误纠正BCH码的并发位的第1常数乘法器；把在该第1常数乘法器求得的数据与从输入端子来的输入数据相加的加法器；和将保持的数据更新为来自上述加法器的数据的延迟器，

在上述2n个并发位计算电路中，除规定的2t个以外的任意2t个以上的并发位计算电路还具有：

利用伽罗瓦域的元，计算上述t重错误纠正BCH码的并发位的第2常数乘法器，以及

在输入附加了n重错误纠正BCH码的数据时选择上述第1常数乘法器，在输入附加了t重错误纠正BCH码的数据时选择上述第2乘法器的选择器。