Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2001-01-18
2003-11-11
Decady, Albert (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S782000
Reexamination Certificate
active
06647529
ABSTRACT:
BACKGROUND OF THE INVENTION
(1) Field of the Invention
The present invention relates to an error correcting method and, more particularly to, a technology for speedily solving an error-position polynomial for chien's searching used in error correction.
(2) Description of the Related Art
General Background of the Technology
Digital data written on a DVD-ROM and the like may produce a read-out error due to a fingerprint, other dirt, a scar, or the like if the data is read out as is. In order to cope with this, when data which is stored by use of a Reed-Solomon code is read out, an algorithm called chien's searching is used to find an error position or error numeral for correction.
This is done so, because an odd/even parity check method which only adds one bit to every original seven data bits can find error generation itself but cannot specify error data nor find the generation itself in case two errors occur simultaneously, so that by providing a large number of parity bits in a duplicate manner, i.e. both horizontally and vertically, to thereby reduce a question of “correcting an error” to a question of “solving a simultaneous equation.” The Reed-Solomon code itself is a known technology already described in, for example, “INTRODUCTION TO CODE THEORY” by Iwadare, published by Shouseidou, “PRACTICAL ERROR CORRECTION TECHNOLOGY” published by Trikeppsu, and the like. Also, arrays of data and parity bits on a DVD-ROM and the like and the ECC format are also already known. Therefore, detailed description on these issues is omitted here, and outlining only those items directly related to the present invention.
As shown in
FIG. 1
, 1 (one) ECC (error correction code) according to a DVD format comprises a rectangular-shaped data portion consisting of horizontal 172 bytes and vertical 182 bytes and additional two parity portions of a rightward 10-byte portion and a downward 16-byte portion.
With this, data read out from a DVD-ROM and the like is sent through a syndrome arithmetic unit, an Euclidean arithmetic unit and to a chien's searching apparatus (error-position and numeral calculation unit).
In this configuration, the Euclidean arithmetic unit and the chien's searching apparatus are provided for speeding, because an equation of interest cannot be solved if the number of employed parity bits is too large, such as 10 or 16.
In this configuration, the Euclidean arithmetic unit on the upstream side obtains an error-position polynomial L(X) and an error-numeral polynomial V(X) based on a syndrome polynomial S(X). In this case, a code polynomial C(X) uses d data pieces Di (i=0, 2, . . . , d−1) and p parity bits Pi (i=0, . . . , p−1) as coefficients in this order. Also, S(X) is obtained by substituting a root of a generation polynomial G(X) into a reception polynomial R(X) received. Note here that the parity bit of the code polynomial C(X) is added so that C(X) can be exactly divided by the generation polynomial G(X) having the parity bits as sequential coefficients. Also, the error-position polynomial L(X) is provided to obtain an error position Lj, while the error-numeral polynomial V(X) is provided to obtain an error numeral Ej.
With this, the error-position polynomial L(X) has X=&agr;{circumflex over ( )}−Lj(−Lj'th power of &agr;) as a solution. Further, a relation of Ej=−V(&agr;{circumflex over ( )}Lj)/Lodd(&agr;{circumflex over ( )}−Lj) holds. This mathematical expression is called an error-numeral polynomial. In this expression, the denominator Lodd is a function of only an odd-number order of the error-position polynomial L(X), while &agr; is a root of the generation function C(X).
With this, X=&agr;{circumflex over ( )}0, &agr;{circumflex over ( )}1, &agr;{circumflex over ( )}2, . . . are substituted as a solution on a Galois field GF (2{circumflex over ( )}n; n'th power of 2) into an error-position polynomial L(X) obtained by the Euclidean algorithm, to thereby obtain a solution that a total sum of each bit component becomes 0. The Galois field and arithmetic operations thereon are known from disclosures in, for example, “MODERNE ALGEBRA” by B. L. van der Waerden, published by Springer Verlag, and the like, and a Galois field multiplier is also a so-called known technology, so that description on these issues is omitted here.
Note here that this error-position polynomial L(X) is expressed as follows if it has a maximum correction power p:
L
(
x
)=
ApX{circumflex over ( )}p+ . . . +A
2
x{circumflex over ( )}
2
+A
1
X{circumflex over ( )}
1
+A
0
where A0-Ap are all coefficients of the 0'th power through the p'th power of X.
Such a circuit is called a chien's searching (apparatus) that is constituted to solve this equation on a real-time basis, i.e. corresponding to a situation that one actually appreciates music or pictures, to thereby find an error position and obtain an error numeral.
FIG. 2
shows the denominator of this chien's searching apparatus, i.e. the calculation unit of the above mentioned L(&agr;{circumflex over ( )}−Lj).
In
FIG. 2
, a reference numeral
100
indicates an error-position calculating (also referred to as an error-position arithmetic) unit, i.e. the error-position polynomial calculating unit. Reference numerals
1010
-
101
p
indicate input terminals. Reference numerals
1020
-
102
p
indicate Galois field multipliers. Reference numerals
1030
-
103
p
indicate selectors (circuits). Reference numerals
1040
-
104
p
indicate registers or overwritable memories. A reference numeral
105
indicates a full adder (aggregate batcher). A reference numeral
106
indicates a 0-decoder. A reference numeral
107
indicates an odd-number order summing (aggregate) unit. A reference numeral
108
indicates an error-location counter. A reference numeral
109
indicates an error-location output signal terminal. A reference numeral
110
indicates an arithmetic-unit output-signal terminal. A reference numeral
111
indicates an even-number order sum output signal terminal.
With this, at the first cycle, each coefficient of an error-position polynomial is input from the Euclidean arithmetic unit (not shown) on the upstream side to their corresponding input terminals
1010
-
101
p
. The selectors
1030
-
103
p
following to each input terminal for each input terminals select a coefficient input from each of the input terminal
1010
-
101
p
at the beginning of only the initial cycle or at the start of the corresponding cycle and, during the subsequent cycle, always select as an input the output value from each of the Galois field multipliers
1020
-
102
p
, which is the other input signal. With this, according to the following procedure, &agr;{circumflex over ( )}0, &agr;{circumflex over ( )}1, &agr;{circumflex over ( )}2, . . . are sequentially substituted into X in the subsequent cycles, to thereby check one by one whether L(X)=0 or not.
Values selected by each of the selectors
1030
-
103
p
are respectively stored in the following registers
1040
-
104
p
in synchronization with a system clock signal, which values are then summed by the following full adder
105
at the beginning of the next cycle. This sum value is judged whether it is 0 or not by the 0-decoder
106
. If it is judged as 0, j indicates an error position.
The reference numeral
108
indicates the error-location counter, which is reset to 0 at the first cycle and then counts up by one per every one clock cycle. That is, this error-location counter always stores a value of i+1 for every i cycles, so that its count value, when the o-decoder has judged as 0, indicates an error position.
In the cycle following the initial cycle, each value stored in each of the registers
1040
-
104
p
are respectively multiplied by &agr;{circumflex over ( )}0, &agr;{circumflex over ( )}1, . . . , &agr;{circumflex over ( )}p by the Galois field multipliers
1020
-
102
p
which branch from and follow the full adder
105
, so that thus obtained products are r
Hanaki Yoshitaka
Hirofuji Masanori
Matsushita Electric - Industrial Co., Ltd.
Parkhurst & Wendel L.L.P.
Torres Joseph D.
LandOfFree
Chien's searching 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 Chien's searching apparatus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Chien's searching apparatus will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3122014