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

In a system having a source of data words, means for mapping each data word into a codeword selected according a predetermined linear cyclic code, and means for writing said codewords either to a transmission or recording medium, and means responsive to reception of each codeword from a transmission medium or read back from a storage medium for detecting and correcting codewords corrupted by errors, said code having up to a maximum number of consecutive zero or null values occurring in said code definition, wherein said error detection and correction means comprise:

• (a) means responsive to the codewords for deriving a set of syndromes {S.sub.j };
• (b) a Berlekamp-Massey-type key equation solver for deriving coefficients of an error locator polynomial f(z) from the set of syndromes;
• (c) a root solver coupling the key equation solver for locating any valid roots to the relation f(z)=0for a predetermined number of iterations and including:
• (1) means for mapping f(z) into a canonical form as an augmented matrix M of a system of linear simultaneous equations in a finite Galois field GF(2.sup.n);
• (2) means for extracting the t roots of the error locator polynomial as an algebraic polynomial expression of degree t, where t>5, by executing a Gaussian Elimination process over matrix M using square and square roots as linear operators to obtain at least one root and a subset of the Galois field values as candidates and determining the remaining roots by iteratively substituting the candidate values in the system of equations until said equations are satisfied, and where t.ltoreq.5, executing a modified Gaussian Elimination process obtaining t.ltoreq.5 roots analytically;
• and
• (d) means responsive to the extracted roots error locations for determining error values and for logically combining the error values at the error locations in the received codeword to form a corrected codeword.