Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2000-03-15
2003-12-09
Chung, Phung M. (Department: 2784)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S785000, C714S781000
Reexamination Certificate
active
06662336
ABSTRACT:
BACKGROUND
1. Field of the Invention
The present invention pertains to error correction of digital data, and particularly to error correction using the Berlekamp-Massey algorithm.
2. Related Art and Other Considerations
Error correction coding techniques are typically employed for digital data that is transmitted on a channel or stored/retrieved with respect to a storage device (such as, for example, an optical disk drive or magnetic media drive). With error correction coding, the data to be transmitted or stored is processed to obtain additional data symbols (called check symbols or redundancy symbols). The data and check symbols together comprise a codeword. After transmission or retrieval, the codeword is mathematically processed to obtain error syndromes which contain information about locations and values of errors. Certain principles regarding error correction coding are provided in Glover et al.,
Practical Error Correction Design For Engineers
, 2
nd
Edition, Cirrus Logic (1991).
The Reed-Solomon codes are a class of multiple-error correcting codes. One of the most popular methods of decoding is to generate an error location polynomial &sgr;(x);
generate an error evaluator polynomial &ohgr;(x) from the error location polynomial;
perform a root search for the error locator polynomial to detect error locations; and then evaluate the error evaluator polynomial at the error location polynomial root to calculate an error value. Most logic circuits for error detection and correction implement the Berkekamp-Massey algorithm.
Examples of error correction coding, including utilization of Reed-Solomon codes, are provided by the following (all of which are incorporated herein by reference): U.S. Pat. No. 5,446,743; U.S. Pat. No. 5,724,368; U.S. Pat. No. 5,671,237; U.S. Pat. No. 5,629,949; U.S. Pat. No. 5,602,857; U.S. Pat. No. 5,600,662; U.S. Pat. No. 5,592,404; and, U.S. Pat. No. 5,555,516.
U.S. Pat. No. 5,446,743, entitled “Coefficient Updating Method And Apparatus For Reed-Solomon Decoder”, incorporated herein by reference in its entirety, discloses a Reed-Solomon decoder which forms coefficients of an error locator polynomial &sgr;(x) in a bank of error locator registers and coefficients of an error evaluator polynomial &ohgr;(x) in a bank of intermediate registers (&tgr;registers). The decoder of U.S. Pat. No. 5,446,743 comprises a plurality of “slices”, each slice having one syndrome register, one of the error location registers, one of the intermediate registers, is and a modified syndrome register.
For each codeword input to the decoder of U.S. Pat. No. 5,446,743 there are two iterations: a first iteration for obtaining the coefficients of the error location polynomial and a second iteration for obtaining the coefficients of the error evaluator polynomial. Each error location iteration has two phases: a first phase (phase A) and a second phase (phase B). During phase A of each error locator iteration, a current discrepancy d
n
is generated and the coefficient values in the intermediate registers (&tgr; registers) are updated. The current discrepancy d
n
is generated by a discrepancy determination circuit which adds multiplicative products from the slices. During phase B of each error locator.iteration, the coefficients values in the error location registers (&sgr; registers) are updated. At the end of phase B, the inverse of the discrepancy, i.e., d
n
−1
, is outputted from a discrepancy inversion circuit. The inverse of the discrepancy becomes known as the inverse of the prior discrepancy or d
n−1
−1
during the next error location iteration, and is used for updating the coefficient values in the intermediate registers. The discrepancy determination circuit does not use a ROM-stored lookup table, but instead serially receives the discrepancy in a second basis representation (e.g., dual or &bgr; basis representation) and produces the inverse thereof in a first basis representation (&agr; basis representation).
Assuming its codewords to comprise m-bit symbols, the decoder of U.S. Pat. No. 5,446,743 thus takes m clock cycles to accomplish each phase of an iteration. Therefore, when m=8, sixteen clock cycles per iteration are required to determine the coefficients of the error location polynomial and another sixteen clock cycles are required to determine the coefficients of the error evaluator polynomial. Moreover, as noted above, such decoder requires four sets of registers per slice.
What is needed, and an object of the present invention, is an error correction technique which can perform error correction operations even more expeditiously.
BRIEF SUMMARY OF THE INVENTION
Using a Berlekamp-Massey process operating with unique recursion rules, a fast correction subsystem performs, for each codeword having m-bit symbols, a series of error locator iterations, followed by a series of error evaluator iterations, followed by a series of correction iterations to generate, and then use, an error pattern for correcting a codeword. The fast correction subsystem includes three sets of registers and three sets of multipliers distributed over v+1 component slices where v is the maximum number of symbol errors that can be corrected. In accordance with the recursion rules, a first set of registers (“&sgr; registers”) ultimately contains quantities including coefficients of an error locator polynomial &sgr;(x) for the codeword. A second set of registers (“&tgr; registers”) are utilized, e.g., to update the &sgr; registers. A third set of registers (“R registers”) ultimately contains quantities including coefficients of an error evaluator polynomial &ohgr;(x) for the codeword.
For each codeword, each error location iteration is performed in two phases. In the first phase [Phase A], the fast correction subsystem generates a quantity including a current discrepancy d
n
in an accumulator. Also during Phase A the fast correction subsystem of the present invention updates the contents of the &tgr; registers according to the following general recursion rule:
&tgr;
(n)
(
x
)=
x
*(&tgr;
(n−1)
(
x
)+(&agr;
d
d
n−1
)
−1
&sgr;
(n)
(
x
)CHANGE_L)
for d not equal to zero. For one illustrated example embodiment, the general recursion rule for Phase A takes the following form:
τ
(
n
)
(
x
)
=
x
*
(
τ
(
n
-
1
)
(
x
)
+
α
-
3
(
(
(
α
-
4
(
α
-
3
d
n
-
1
)
)
-
1
CHANGE_L
)
σ
(
n
)
(
x
)
)
)
=
x
*
(
τ
(
n
-
1
)
(
x
)
+
(
α
-
4
d
n
-
1
)
-
1
σ
(
n
)
(
x
)
CHANGE_L
(
d
=
-
4
)
In the second phase [Phase B] of an error locator iteration, the fast correction subsystem obtains a quantity including the inverse of the current discrepancy. The quantity including the inverse of the current discrepancy is used in Phase A of a next iteration as a quantity including the inverse of the prior discrepancy. Also, in Phase B of an error locator iteration, the fast correction subsystem updates the contents of the &sgr; registers according the following general recursion rule:
&sgr;
(n+1)
(
x
)=&agr;
d
(&sgr;
(n)
−d
n
&tgr;
(n)
)=&agr;
d
&sgr;
(n)
(
x
)−&agr;
d
d
n
&tgr;
(n)
(x)
for d not equal to zero (d being the same as for the &tgr; recursion rule). For the illustrated example embodiment, the general recursion rule for Phase B takes the following form:
σ
(
n
+
1
)
(
x
)
=
(
α
-
4
σ
(
n
)
(
x
)
)
-
(
α
-
3
d
n
)
(
τ
(
n
)
(
x
)
)
α
-
1
=
(
α
-
4
σ
(
n
)
(
x
)
)
-
(
α
-
3
(
(
α
-
3
d
n
)
α
2
)
(
τ
(
n
)
&
Chung Phung M.
Cirrus Logic Inc.
Nixon & Vanderhye P.C.
LandOfFree
Error correction method and 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 Error correction method and apparatus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Error correction method and apparatus will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3099043