Title:
ERROR CORRECTION FOR ALGEBRAIC BLOCK CODES
Document Type and Number:
WIPO Patent Application WO1985001625
Kind Code:
A1
Abstract:
Error correction for polynomial block codes is achieved without prior evaluation of power sum symmetric functions. The received word R (z) is reduced mod G (z), where G (z) is the generator of the code and a function F (z) is defined from error locator polynomial W (z), errata values Yi and code dependent function of the error positions Xi given by$(5,)$such that F (z) is decomposable into a rational polynomial function N (z)/ W (z) for which deg (N (z)) < deg (W (z)) < number of correctable errors. W (z) is the error locator polynomial, the roots of which are the errata locations and values Xi and Yi, the correction to the received character is obtained from N (z)/ f(z) W (z) evaluated at error location Xi using non-erased check symbols of R (z). Correction is carried out in a crossbar switch structure (26) which recalls a stored copy of R (z) and corrects bits as specified by (Xi, Yi). Another embodiment interposes a matrix transformer to transform the symbols of the received word so as to treat a variable set of symbols (selected by the error history of corresponding symbols of previous codewords) as erased checks and to present error location corrections directly to the crossbar (26). Only when changes occur in the pattern of errata is the error corrector apparatus required to operate and to revise the transform executed on incoming data R (z).
Inventors:
BERLEKAMP ELWYN R (US)
WLECH LLOYD R (US)
WLECH LLOYD R (US)
Application Number:
PCT/US1984/001557
Publication Date:
April 11, 1985
Filing Date:
September 26, 1984
Export Citation:
Assignee:
CYCLOTOMICS INC (US)
International Classes:
H03M13/15; H03M13/00; (IPC1-7): H03M13/00; G06F11/10
Other References:
IEEE-Transactions on Communications, Vol. COM-24, No. 4, April 1976 (New York, US) PO HSIIN CHEN: "Multisequence Linear Shift Register Synthesis and its Application to BCH-Decoding", pages 438-440, see the entire article
IEEE-Transactions on Information Theory, Vol. IT-22, No. 2, March 1976 (New York, US) J. JUSTESEN: "On the Complexity of Decoding Reed-Solomon Codes", pages 237-238, see the entire article
IBM Technical Disclosure Bulletin, Vol. 22, No. 11, April 1980 (New York, US) F.J. AICHELMANN et al.: "High Data Integrity Scheme for Memory Reliability", pages 4933-4934
IEEE-Transactions on Information Theory, Vol. IT-17, No. 6, November 1971 (New York, US) D. MANDELBAUM: "On Decoding of Reed-Solomon Codes", pages 707-712
IEEE-Transactions on Information Theory, Vol. IT-22, No. 2, March 1976 (New York, US) YASUO SUGIYAMA et al.: "An Erasures- and Errors Decoding Algorithm for Goppa Codes", pages 238-241
IEEE-Transactions on Information Theory, Vol. IT-18, No. 3, May 1972 (New York, US) C.R.P. HARTMANN: "Decoding Beyond the BCH-Bound", pages 441-444
IEEE-Transactions on Information Theory, Vol. IT-22, No. 2, March 1976 (New York, US) J. JUSTESEN: "On the Complexity of Decoding Reed-Solomon Codes", pages 237-238, see the entire article
IBM Technical Disclosure Bulletin, Vol. 22, No. 11, April 1980 (New York, US) F.J. AICHELMANN et al.: "High Data Integrity Scheme for Memory Reliability", pages 4933-4934
IEEE-Transactions on Information Theory, Vol. IT-17, No. 6, November 1971 (New York, US) D. MANDELBAUM: "On Decoding of Reed-Solomon Codes", pages 707-712
IEEE-Transactions on Information Theory, Vol. IT-22, No. 2, March 1976 (New York, US) YASUO SUGIYAMA et al.: "An Erasures- and Errors Decoding Algorithm for Goppa Codes", pages 238-241
IEEE-Transactions on Information Theory, Vol. IT-18, No. 3, May 1972 (New York, US) C.R.P. HARTMANN: "Decoding Beyond the BCH-Bound", pages 441-444
Download PDF: