Error correction for algebraic block codes

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), the generator of the code and a function F (z) of error locator polynomial W(z), errata values Y and code dependent functions f(x.sub.i) of the error positions x.sub.i given by ##EQU1## is decomposed 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 X and Y, the correction to the received character is obtained from ##EQU2## evaluated at X.sub.i using non-erased check symbols of R (z). Correction is carried out in a crossbar switch structure which recalls a stored copy of R (z) and corrects bits as specified by (X.sub.i, Y.sub.i). Another embodiment interposes a matrix transform to transform the symbols of the received word so as to treat a selected set of symbols as erased checks and to present error location corrections directly to the crossbar. Only when changes occur in the pattern of errata is this error corrector apparatus required to operate and to redetermine the transform executed on incoming data R (z).