Pipelined Berlekamp-Massey error locator polynomial generating apparatus and method

In a computer system, a method for generating an error locator polynomial from a plurality of partial syndromes, which are generated from a data sector that is read sequentially from a storage medium, the method comprising the operations of:

• a) receiving the plurality of partial syndromes;
• b) initializing Berlekamp-Massey algorithm variables k, L, T(z), and .LAMBDA..sup.(0) (z) to 0, 0, z, and 1, respectively;
• c) incrementing the index k by 1 and determining a discrepancy .DELTA..sup.(k) of the Berlekamp-Massey algorithm;
• d) determining a connection polynomial .LAMBDA..sup.(k) (z) and a correction polynomial T(z) of the Berlekamp-Massey algorithm based on the discrepancy .DELTA..sup.(k) and the connection polynomial .LAMBDA..sup.(k-1) (z);
• e) while the connection polynomial .LAMBDA..sup.(k) (z) and the correction polynomial T(z) are being determined, incrementing k by 1 and determining the discrepancy .DELTA..sup.(k) by delaying the evaluation of discrepancy .DELTA..sup.(k) until .LAMBDA..sup.(k-1) (z) becomes available from the operation d);
• and
• f) incrementing the degree of the error correction polynomial T(z) and repeating the operations d) and e) in accordance with the Berlekamp-Massey algorithm to generate an error locator polynomial.

An apparatus for generating an error locator polynomial from a plurality of partial syndromes, which are generated from a data sector read sequentially from a storage medium, the apparatus comprising:

• a discrepancy determining means configured to receive the plurality of partial syndromes for determining a discrepancy;
• a connection and correction polynomial determining means configured to receive the discrepancy for determining a connection polynomial and a correction polynomial;
• and
• a control means for providing sequencing and control signals to the discrepancy determining means, the connection and correction polynomial determining means, wherein the connection and correction polynomial determining means outputs the connection polynomial as an error locator polynomial, wherein the connection polynomial determining means, the correction polynomial determining means, and the discrepancy determining means determine the connection polynomial .LAMBDA..sup.(k) (z), the correction polynomial T(z), and a next discrepancy .DELTA..sup.(k+1), respectively, in parallel and substantially at the same time.