Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1998-10-21
2003-10-21
Decady, Albert (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C708S507000
Reexamination Certificate
active
06637002
ABSTRACT:
BACKGROUND
This invention relates to error correcting code techniques.
Error correcting code techniques are used in digital systems to correct and detect errors in digital data. Such techniques are particularly employed with magnetic disks which typically have relatively high rates of error due to manufacturing defects and so forth. Several types of error correcting techniques are known. One type of error correcting technique uses so-called “block codes.” Two examples of block codes are the so called “Reed Solomon” (RS) code and “Bose-Chaudhuri-Hocquenghem” (BCH) code.
Block codes such as “Reed Solomon” and “Bose-Chaudhuri-Hocquenghem”, operate on data symbols. Data symbols are vectors of binary bits of data. Symbols are generated by grouping bits at a particular bit position for a group of words into a vector. When block codes are used in a disk drive, before a string of data symbols are recorded on a disk, the string is mathematically encoded producing error correcting code symbols that are appended to the data symbols to form code words. These code words i.e., data symbols and error correcting code symbols are stored on the disk. When the stored data is retrieved from the disk, the code words are mathematically decoded to form decoded code words.
In order to correct errors, the locations and magnitudes or values of the errors are needed. A conventional approach for determining the location of such errors uses a decoder including a syndrome generator to form error syndromes. The error syndromes are used to generate an error location polynomial and the error location polynomial is used to determine an error location. The conventional approach uses a single Chien search circuit to search for roots of the error location polynomial. The Chien search circuit evaluates the error location polynomial for all possible error locators by iteratively evaluating the error location polynomial “n” times, where n is the code length. This is a time consuming process when n is large and the code rate is high.
The roots of the error location polynomial (i.e., when the error location polynomial is zero) correspond to the location of the errors in the code word. An error evaluation polynomial is evaluated to determine error values based on the determined error locations. Once the error locations and the corresponding error values are known, the data can be corrected.
SUMMARY
According to an aspect of the invention, a decoder for decoding block error correction codes includes a first search circuit to find roots of an error location polynomial corresponding to an error location and a second search circuit to find roots of an error location polynomial corresponding to an error location. A multiplexer is fed by the first search circuit and the second search circuit to produce an error location from the error location polynomial.
According to a further aspect of the invention, a decoder for decoding block codes includes a parallel error location polynomial search circuit. The parallel error location search circuit includes a first search circuit that finds roots of an error location polynomial that correspond to an error location. The circuit includes a first modulo adder circuit that adds odd terms of the error location polynomial to produce a derivative of the error location polynomial. The circuit also includes a second search circuit that finds roots of an error location polynomial that correspond to an error location. A second modulo adder circuit adds odd terms of the error location polynomial to produce a derivative of the error location polynomial. The circuit also includes a first multiplexer fed by error location outputs from the first search circuit and the second search circuit, a second multiplexer fed by derivatives of error location outputs from the first and the second modulo adders. The circuit also includes an error evaluation circuit that produces the error evaluator polynomial and a logic circuit including a divider circuit to divide the error evaluator polynomial by the output from the second multiplexer.
According to a still further aspect of the invention, a method of decoding an error correcting block code includes evaluating an error location polynomial produced from an error location polynomial generation circuit by applying the error location polynomial to a parallel root search circuit that searches for roots of the error location polynomial in a parallel manner.
One or more advantages are provided by the above aspects. The two-way parallel root search circuit searches for roots of the error location polynomial in a parallel manner. This saves substantial computation time to facilitate real time decoding of high rate Reed Solomon and BCH codes. For example, a two-way parallel root search circuit can use two duplicate root search circuits to reduce the search time to determine the roots of an error-locator polynomial by half. An additional advantage of the arrangement is that the parallel root search circuit can be modified to provide a term that can be used with an error evaluator without the need to compute a derivative of the error location polynomial.
REFERENCES:
patent: 4833678 (1989-05-01), Cohen
patent: 4866716 (1989-09-01), Weng
patent: 5309449 (1994-05-01), Gandini et al.
patent: 5321704 (1994-06-01), Erickson et al.
patent: 5666369 (1997-09-01), Nakamura
patent: 5771244 (1998-06-01), Reed et al.
patent: 5974582 (1999-10-01), Ly
patent: 5983389 (1999-11-01), Shimizu
patent: 6031875 (2000-02-01), Im
patent: 6061826 (2000-05-01), Thirumoorthy et al.
patent: 6192497 (2001-02-01), Yang et al.
patent: 6279137 (2001-08-01), Poeppelman et al.
patent: 403121627 (1991-05-01), None
Ganapathy et al. << Designing a scalable processor array for recurrent computations; IEEE Transactions on Parallel and Distributed Systems, , vol. 8, Issue: 8, p. 840-856, Aug. 1997.*
Richard E. Blahut “A Theory and Practice of Error Control Codes”, Addison-Wesley Publishing Company, Reading MA, table of contents, chapter 4 pp. 65-92, chapter 5, pp. 93-129, and chapter 8 pp. 207-247, 1983.
Peterson et al., “A Error-Correcting Codes, Second Edition”, MIT Press, Cambridge, MA, London, England, table of contents, chapter 4 76-115, chapter 6 pp. 144-169, chapter 7 pp. 170-205, and chapter 8 pp. 206-265, 1972.
Chang Chung
Mo Shih
Shen Ba-Zhong
Weng Lih-Jyh
Daly, Crowley & Mofford LLP
De'cady Albert
Lamarre Guy
Maxtor Corporation
LandOfFree
Decoder for error correcting block codes does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Decoder for error correcting block codes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Decoder for error correcting block codes will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3149241