Method and apparatus for computing the error locator polynomial in a decoder of a forward error correction (fec) system

Abstract

A method and apparatus for performing quickly and efficiently generating the error correction polynomial. In accordance with the present invention, multiple coefficients of the syndrome vector are processed in parallel by a Berlekamp algorithm logic block of the present invention. The Berlekamp algorithm's iterations can be performed in less than 60 clock cycles for a large order error correction polynomial, thereby enabling the polynomial to be generated very rapidly. In order to perform the Berlekamp algorithm at such a high rate of speed, Galois field multiplier logic is utilized in performing the algorithm. Furthermore, because of the large number of logical multiplication and addition operations that are performed in parallel, the Galois filed multiplier logic in accordance with the preferred embodiment of the present invention is configured in such a way that redundancy in processing polynomial coefficients is greatly reduced, which enables the number of logic gates needed to implement the Galois field multiplier logic to be vastly reduced. This reduction in the number of gates used for this purpose reduces area and power consumption requirements.