Complexity of computations
Shmuel Winograd
ACM Annual Conference 1978
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. © 1995 IEEE
Shmuel Winograd
ACM Annual Conference 1978
Ephraim Feig, Shmuel Winograd
IEEE Trans. Inf. Theory
Khaled A. S. Abdel-Ghaffar, Martin Hassner
IEEE Trans. Inf. Theory
Don Coppersmith, Shmuel Winograd
Journal of Symbolic Computation