Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1999-11-09
2001-11-13
Decady, Albert (Department: 2784)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S784000, C714S782000
Reexamination Certificate
active
06317858
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to an apparatus for correcting errors present in stored or transmitted data; and, more particularly, to an apparatus for evaluating an error evaluator polynomial, an error locator polynomial and a differential polynomial which are used in correcting errors in the data encoded by using an algebraic code, such as a Reed-Solomon code.
2. Description of Related Art
Noise occurring during a process of transmitting, storing or retrieving data can in turn cause errors in the transmitted, stored or retrieved data. Accordingly, various encoding techniques, having the capability of rectifying such errors, for encoding the data to be transmitted or stored have been developed.
In such encoding techniques, a set of check bits is appended to a group of message or information bits to form a codeword. The check bits, which are determined by an encoder, are used to detect and correct the errors. In this regard, the encoder essentially treats the bits comprising the message bits as coefficients of a binary message polynomial and derives the check bits by multiplying the message polynomial R(x) with a code generator polynomial G(x) or dividing R(x) by G(x), to thereby provide a codeword polynomial C(x). The code generator polynomial is selected to impart desired properties to a codeword upon which it operates so that the codeword will belong to a particular class of error-correcting binary group codes (see, e.g., S. Lin et al., “Error Control Coding: Fundamentals and Applications”, Prentice-Hall, 1983).
One class of error correcting codes is the well-known BCH (Bose-Chaudhuri-Hocquenghen) codes, which include the Reed-Solomon (“RS”) code. The mathematical basis of the RS code is explained in, e.g., the aforementioned reference by Lin et al. and also in Berlekamp, “Algebraic Coding Theory”, McGraw-Hill, 1968, which is further referred to in U.S. Pat. No. 4,162,480 issued to Berlekamp. The aforementioned references are hereby incorporated by reference in pertinent part.
SUMMARY OF THE INVENTION
The invention herein provides a method and apparatus for decoding an algebraic-coded message. The method can include the steps of determining a discrepancy indicator, with the discrepancy being between a calculated and a predicted value; determining an error locator polynomial using a selected class of error correction algorithms, such as, for example, a Berlekamp-Massey algorithm; and detecting an uncorrectable message using the selected error correction algorithm. The apparatus is composed of storage devices which can include recirculating storage devices; arithmetic components attached to the storage devices, the components operating over a Galois Field on selected contents of the storage devices; and an uncorrectable message detector, connected with the storage devices and the arithmetic components.
REFERENCES:
patent: 5099482 (1992-03-01), Cameron
patent: 5170399 (1992-12-01), Cameron et al.
patent: 5592404 (1997-01-01), Zook
patent: 5640286 (1997-06-01), Acosta et al.
patent: 5689452 (1997-11-01), Cameron
patent: 5727003 (1998-03-01), Zook
patent: 5844919 (1998-12-01), Glover et al.
patent: 5964826 (1999-10-01), Wei
patent: 5970975 (1999-10-01), Wasada
patent: 5971607 (1999-10-01), Im
patent: 5974582 (1999-10-01), Ly
patent: 5974583 (1999-10-01), Joo
patent: 5978950 (1999-11-01), Im
patent: 5978956 (1999-11-01), Weng et al.
patent: 6092233 (2000-07-01), Yang
patent: 0 808 0129 A2 (1997-11-01), None
patent: WO 97/27675 (1999-07-01), None
Blahut, E.R.: “theory and practice of error control codes”, 1984 Addison-Wesley Publishing Company, London, XP002131806, pp. 176-178, pp. 191-193.
Trieu-Kien Truong et al.: “Inversionless decoding of both errors and erasures of Reed-Solomon code”, IEEE Transactions on Communcations, Aug. 1998, IEEE, USA, vol. 46, No. 8, pp. 973-976, XP002131805 ISSN: 0090-6778.
Stephen b. Wicker, ‘Error Control Systems’, Prentice-Hall, 1995.*
Trieu-Kien Truong, J.H. Jeng and King-Chu Hung, ‘Inversionless Decoding of Both Errors and Erasures of Reed-Solomon Code’, IEEE Transactions on Communcations, vol. 46, No. 8, Aug. 1998.*
M. Fleishmann, “Modified Berlekamp-Massey Algorithm for Two Sided Shift Register Synthesis”, Electronics Letters, vol. 31, No. 8, Apr. 13, 1995.
Broadcom Corporation
Christie Parker & Hale LLP
De'cady Albert
Torres Joseph
LandOfFree
Forward error corrector 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 corrector, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Forward error corrector will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2605475