Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2001-09-12
2003-03-25
Decady, Albert (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S784000, C714S782000
Reexamination Certificate
active
06539516
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: 5970075 (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: 6119262 (2000-09-01), Chang et al.
patent: 6209115 (2001-03-01), Truong et al.
patent: 6317858 (2001-11-01), Cameron
patent: 08080129 (1997-11-01), None
patent: WO 97/27675 (1997-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 Communications, Aug. 1998, IEEE, USA, vol. 46, No. 8, pp. 973-976, XP002131805 ISSN; 0090-6778.
Fleishchmann, M.; “Modified Berlekamp-Massey Algorithm for Two Sided Shift Register Synthesis,” Electronic Letters, vol. 31, No. 8, Apr. 13, 1995.
Wicker, Stephen B.; “Error Control Systems,” Prentice-Hall, 1995.
Truong et al. (Trieu-Kien Truong; Jeng, J.H.; King-Chu Hung; Inversionless decoding of both errors and erasures of Reed-Solomon code, IEEE Transactions on Communications vol.: 46 Issue: 8 , Aug. 1998 pp.: 973-976).*
Reed et al. (Reed, I.S. and Shih, M.T.; VLSI design of inverse-free Berlekamp-Massey algorithm, IEE Proceedings E [see also Computers and Computers and DigitalTechniques, IEE Proceedings-] Digital Techniques vol.: 138 Issue: 5 , Sep. 1991 pp.: 295.*
Fleischmann (Fleischmann, M.; Modified Berlekamp-Massey algorithm for two-sided shift-register synthesis, Electronics Letters , vol.: 31 Issue: 8 , Apr. 13, 1995 pp.: 605-606).*
Youzhi (Xu Youzhi, Implementation of Berlekamp-Massey algorithm without inversion, IEE Proceedings I Speech and Vision Communications, vol.: 138 Issue: 3, Jun. 1991 pp.: 138-140).
Broadcom Corporation
Christie Parker & Hale LLP
De'cady Albert
Torres Joseph D.
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-3058866