Algorithms and architectures for error correcting codes (decoding, reed-solomon)
Todd Citron · 1986
Ever since Shannon demonstrated the unexpected possibility of virtually error-free communication over noisy channels, work in coding theory has been aimed towards finding practical encoding and decoding schemes. Berlekamp's fast algorithm for decoding Reed-Solomon and BCH codes was a major step in this direction; however, the intrinsic structure of this algorithm hinders its use on the high rate channels of the future. Additionally, Berlekamp's algorithm is not entirely regular, complicating its VLSI implementation (e.g. testability, modularity, design time). By re-examining the underlying structure of the problem, new algorithms and architectures are developed that overcome these limitations. A particular implementation has more than twice the throughput of Berlekamp's algorithm, and is ideally suited for VLSI implementation. The philosophy adopted here is novel in that the algorithms are designed to match the VLSI hardware constraints instead of vice versa. A matrix approach to the derivation leads to an algorithm that can be implemented on a parallel architecture with local communication between processing elements. A polynomial approach yields an algorithm that can be implemented on a serial-input, concurrent architecture with local communication. The invocation of scattering theory for this derivation both provides physical intuition and readily displays the impact of algorithmic choices on the implementation architecture. The matrix and polynomial approaches are unified to obtain the Micro-level Euclidean (MLE) Algorithm, which defines a family of VLSI-compatible implementations for decoding Reed-Solomon and BCH codes. Two particular concurrent processing architectures for implementing the MLE algorithm are detailed to determine area and time performance. It is shown that these architectures require less than half the area of other alternatives to Berlekamp's algorithm. In the process of deriving the MLE algorithm, several related results are discovered. One outcome is a better understanding of Berlekamp's algorithm, including the meaning of inner products and also a derivation from a particular form of the Euclidean algorithm. This allows us to explicitly exhibit the tradeoffs between Berlekamp's algorithm and the implementations of Euclidean algorithm presented here. Other results in partial realization theory and connections to Hankel and Toeplitz matrix inversion are also obtained.