On-the-fly error correction in data storage channels

A sequential key equation solver algorithm for Reed-Solomon codes is presented. This work is motivated by the need for Error Correction Coding (ECC) On-the-Fly (OTF) in high data rate storage devices. In these applications the ECC encoder/decoder circuitry is integrated into the device controller and the actual correction is performed in the sector buffer without any microprocessor intervention thus avoiding loss of performance due to error correction. The algorithm described computes both error locator and evaluator at the same time and bears strong resemblance to the algorithm first described by Berlekamp. Due to a modified computational structure, the algorithm presented lends itself to a more efficient parallel implementation than previously described. The result is a t-symbol error correcting implementation that requires 2t multipliers and 6t symbol storage units and has a latency of 4t cycles. The structure determined by the algorithm schedule is presented, Furthermore, we have identified a modular correction unit that can be duplicated and a control unit that generates the control signals for this correction unit. We present the circuits for this modular design which lends itself to an efficient VLSI implementation.<>