Method and means for computationally efficient on-the-fly error correction in linear cyclic codes using ultra-fast error location

摘要

A computationally efficient, machine-implementable method and means for detecting and correcting errors in received codewords on-the-fly within the capacity of a linear cyclic code using ultra-fast error location processing. Each error locator polynomial of degree t over a finite Galois field derived from a codeword syndrome is mapped into a matrix representative of a system of linear simultaneous equations related to the polynomial coefficients. Roots indicative of error locations within the codeword are extracted from the matrix by a modified Gaussian Elimination process for all the roots where t≦5 and at least one root plus a subset of candidate roots from the finite field for iterative substitution where t5. Corrected values are separately determined and correction is secured by logically combining the corrected values with the codeword values in error at the error locations represented by the roots.