Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2003-02-04
2004-04-20
Chung, Phung M. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
Reexamination Certificate
active
06725416
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates to apparatus and methods of forward error correction.
Forward error correction techniques typically are used in digital communication systems (e.g., a system for reading information from a storage medium, such as an optical disk) to increase the rate at which reliable information may be transferred and to reduce the rate at which errors occur. Various errors may occur as data is being read from a storage medium, including data errors and erasures. Many forward error correction techniques use an error correction code to encode the information and to pad the information with redundancy (or check) symbols. Encoded information read from a storage medium may be processed to correct errors and erasures.
Reed-Solomon (RS) encoding is a common error correction coding technique used to encode digital information which is stored on storage media A RS (n, k) code is a cyclic symbol error correcting code with k symbols of original data that have been encoded. An (n-k)-symbol redundancy block is appended to the data. The RS code represents a block sequence of a Galois field GF(2
m
) of 2
m
binary symbols, where m is the number of bits in each symbol. Constructing the Galois field GF(2
m
) requires a primitive polynomial p(x) of degree m and a primitive element &bgr;, which is a root of p(x). The powers of &bgr; generate all non-zero elements of GF(2
m
). There also is a generator polynomial g(x) which defines the particular method of encoding. A RS decoder performs Galois arithmetic to decode the encoded data. In general, RS decoding involves generating syndrome symbols, computing (e.g., using a Berlakamp computation process) the coefficients &sgr;
i
of an error location polynomial &sgr;(x), using a Chien search process to determine the error locations based upon the roots of &sgr;(x), and determining the value of the errors and erasures. After the error locations have been identified and the values of the errors and erasures have been determined, the original data that was read from the storage medium may be corrected, and the corrected information may be transmitted for use by an application (e.g., a video display or an audio transducer).
SUMMARY OF THE INVENTION
In one aspect, the invention features a method of correcting errors and erasures, comprising: (a) computing syndromes values; (b) computing an erasure location polynomial based upon one or more erasure locations; (c) computing modified syndromes based upon the computed erasure location polynomial and the computed syndrome values; (d) computing coefficients of an error location polynomial based upon the computed modified syndromes; (e) computing a composite error location polynomial based upon the computed coefficients of the error location polynomial; (f) computing a Chien polynomial based upon the computed composite error location polynomial; (g) performing a redundant Chien search on the computed composite error location polynomial to obtain error location values; and (h) evaluating the computed Chien polynomial based upon the error location values to obtain error and erasure values.
In another aspect, the invention features a system of correcting errors and erasures, comprising: first and second simultaneously accessible memory locations; first, second and third register banks; and a micro-sequencer configured to choreograph a method of correcting errors and erasures by coordinating the flow of data into the first and second memory locations and the first, second and third register banks.
Embodiments may include one or more of the following features.
The coefficients of the error location polynomial preferably are computed based upon a Berlakamp error correction algorithm.
In one embodiment, the computed syndrome values are stored in RAM memory. The computed erasure location polynomial is stored in a first register bank. The modified syndromes are stored in RAM memory. The computed coefficients of the error location polynomial are stored in a second register bank. The computed composite error location polynomial is stored in the first register bank. The computed Chien polynomial is stored in a third register bank. The computed error location values are stored in RAM memory.
Among the advantages of the invention are the following.
The invention provides a scheme in which rate at which signals are decoded may be increased by storing the results of the above-described algorithms in registers rather than in memory. In one implementation, only sixteen registers are needed for performing the Chien search, and only eighteen registers are needed to implement Berlakamp's error correction algorithm. The invention provides hardware support that significantly increases the rate at which error and erasure polynomials may be computed using a relatively small number of hardware components. The invention therefore enables forward error correction techniques to be implemented in a high speed digital signal processing chip. The invention provides a relatively simple micro-sequencer-based forward error corrector design that may be implemented with a relatively small number of circuit components, and provides improved programming functionality.
REFERENCES:
patent: 4845713 (1989-07-01), Zook
patent: 4870608 (1989-09-01), Kametani
patent: 4982402 (1991-01-01), Beaven et al.
patent: 5373511 (1994-12-01), Veksler
patent: 5715262 (1998-02-01), Gupta
patent: 5978954 (1999-11-01), Ou et al.
patent: 6061826 (2000-05-01), Thirumoorthy et al.
patent: 6131178 (2000-10-01), Fujita et al.
patent: 6345376 (2002-02-01), Cox et al.
patent: 6543026 (2003-04-01), Dadurian
Chung Phung M.
LSI Logic Corporation
Maiorana P.C. Christopher P.
LandOfFree
Forward error correction apparatus and methods does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Forward error correction apparatus and methods, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Forward error correction apparatus and methods will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3237927