Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2000-02-18
2002-10-22
Decady, Albert (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
Reexamination Certificate
active
06470471
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a data error correction apparatus for correcting data errors by using a plurality of error correcting codes.
BACKGROUND OF THE INVENTION
As a technique for improving the reliability of a data processing system, error correcting codes (ECC) for correcting errors in data have been applied to various kinds of equipment. Especially BCH (Bose-Chaundhuri-Hocqenghen) codes including Reed-Solomon codes are regarded as important because of the high efficiency. Assuming that a primitive polynomial is W(z) and a root of W(z)=0 is &agr;, a Reed-Solomon code is a code on a Galois field having this root a as a primitive element, and it is a kind of a block error correcting code.
FIG. 3
is a block diagram illustrating the structure of an error correction apparatus disclosed in Japanese Published Patent Application No. Hei.5-55926. This error correction apparatus comprises a data memory
72
for storing input data, syndrome calculation circuits
76
and
78
for calculating syndromes of multiple error correcting codes added to the input data, a syndrome memory for storing the syndromes calculated by the syndrome calculation circuits
76
and
78
, and an error detection and correction circuit
86
for reading the syndromes stored in the syndrome memory
80
and correcting the error data in the data memory
72
. Further, an OR circuit
82
ORs all bits of the calculated syndromes, and the result is stored in a flag memory
84
as flag data indicating data errors. Further, a timing control circuit
88
controls the operation timing of the error correction apparatus. The syndrome calculation circuit
76
comprises adders
20
,
22
, and
24
, delay units
26
,
28
, and
30
, and constant multipliers
32
and
34
for the element of the Galois field, while the syndrome calculation circuit
78
comprises adders
36
,
38
, and
40
, delay units
42
,
44
,
46
,
52
,
54
, and
56
, and constant multipliers
48
and
50
. Assuming that input data is Wi and the root of the generating polynomial is am, syndromes S
0
, S
1
, and S
2
are calculated according to the following formulae (1), (2), and (3).
S0
=
∑
i
=
1
n
Wi
(
1
)
S1
=
∑
i
=
1
n
Wi
α
n
-
i
(
2
)
S2
=
∑
i
=
1
n
Wi
(
α
2
)
n
-
i
(
3
)
Then, the error detection and correction circuit
86
reads the syndromes S
0
, S
1
, and S
2
from the syndrome memory
80
. When at least one of these syndromes is not “0”, the position and size of error are calculated according to S
0
-S
2
, and the error data in the input data stored in the data memory
72
are corrected according to the result.
In this error correction apparatus, simultaneously with writing the input data applied to the input terminal
70
into the data memory
72
, the syndrome calculators
76
and
78
calculate syndromes of the error correcting codes added to the input data, and data errors are corrected on the basis of the syndromes. The corrected data are output from the output terminal
74
.
Generally, when performing error correction by using a t-fold (t=integer, t≧1) error correcting BCH code, 2t syndromes are calculated. For example, in a digital audio tape recorder (DAT), a triple error correcting Reed-Solomon code and a double error correcting Reed-Solomon code are added to correct data errors. In this case, for one code word, six syndromes are calculated for the triple error correcting Reed-Solomon code, and four syndromes are calculated for the double error correcting Reed-Solomon code.
FIG. 2
shows the structure of a conventional syndrome calculation circuit used in a data error correction apparatus. The syndrome calculation circuit comprises six syndrome calculators
300
~
305
, and these calculators
300
~
305
are provided with data input terminals
320
~
325
, Galois field adders
340
~
345
, flip-flops
360
~
365
as delay units, and constant multipliers
380
~
385
for calculating the 0th to 5th powers of an element &agr; of Galois field (hereinafter referred to as &agr;{circumflex over ( )}
0
~&agr;{circumflex over ( )}
5
). In these syndrome calculators
300
~
305
, every time data of a code word are input to the input terminals
320
~
325
, starting from the head data, the data held in the flip-flops
360
~
365
are subjected to constant multiplication in the constant multipliers
380
~
385
, and the constant-multiplied data and the input data are added in the adders
340
~
345
, respectively. Then, the data held by the flip-flops
360
~
365
are updated with the data output from the adders
340
~
345
, whereby syndromes of the error correcting code are calculated. For example, since six syndromes are calculated for the triple error correcting Reed-Solomon code, when calculating the syndromes of the triple error correction Reed-Solomon code by using the syndrome calculators, all of the six syndrome calculators
300
~
305
are used. On the other hand, since four syndromes are calculated for the double error correcting Reed-Solomon code, when the syndromes of the double error correcting Reed-Solomon code are calculated by using the syndrome calculators, only four syndrome calculators
300
~
303
of relatively low correction abilities are used, and the results from the remaining two syndrome calculators
304
and
305
are not used.
As described above, in the conventional syndrome calculation circuit, syndrome calculations for error correcting codes of different correction abilities, such as the triple error correcting Reed-Solomon code and the double error correcting Reed-Solomon code, are realized by using common hardware. In this case, however, since a difference in error-correcting abilities between the triple error correcting Reed-Solomon code and the double error correcting Reed-Solomon is small, the number of code words to be processed in the syndrome calculation for the triple error correcting Reed-Solomon code should be equal to the number of code words to be processed in the syndrome calculation for the double error correcting Reed-Solomon code. That is, only one code word is processed at one time in both of these syndrome calculations. Especially when the code length is large or the code word has no error, since the error correcting speed of the error correction apparatus is regulated by the syndrome calculation, the efficiency of syndrome calculation should be increased to increase the error correcting speed.
By the way, in a data error correction apparatus for a DVD-ROM, not only data in a DVD-ROM but also data in a CD-ROM or a CD-R should be processed. Since an octuple error correcting Reed-Solomon code and a quintuple error correcting Reed-Solomon code are added to the DVD-ROM while a single error correcting Reed-Solomon code is added to the CD-ROM, syndrome calculations for error correcting codes having greatly different error-correcting abilities are required. In this case, in the syndrome calculation circuit shown in
FIG. 2
, since sixteen syndromes are calculated for the high error-correcting ability code applied to the DVD-ROM, such as the octuple error correcting Reed-Solomon code, sixteen units of syndrome calculators are required for this calculation. Accordingly, in a data error correction apparatus having such syndrome calculation circuit, by using the sixteen syndrome calculators performing syndrome calculation for a high error-correcting ability code, two syndromes are calculated for a low error-correcting ability code such as the single error correcting Reed-Solomon code. Therefore, when calculating the two syndromes, only two syndrome calculators amongst the sixteen syndrome calculators are used while the remaining fourteen syndrome calculators are not used. Especially when processing plural codes of different error correcting abilities by using a common syndrome calculation circuit, a lot of unused syndrome calculators exist when calculating syndromes of a lower error-correcting ability code, whereby the efficiency of the syndrome calculation is degraded, resulting in difficulty in increasing the dat
Noguchi Nobuaki
Watanabe Takahiro
Chase Shelly A
De'cady Albert
LandOfFree
Data error correction apparatus does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Data error correction apparatus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data error correction apparatus will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2958508