Systolic interpolation architectures for soft-decoding Reed-Solomon codes

We present a systolic algorithm for performing interpolation, a computationally intensive kernel found in algebraic soft-decoding of Reed-Solomon codes. We reformulate the interpolation algorithm, resulting in the systolic interpolation algorithm, which can compute a reduced number of candidate polynomial coefficients. Using the dependence graph of the algorithm, we realize a low-latency interpolation architecture and a high-throughput interpolation architecture. These architectures are compared against previously proposed architectures for a RS soft-decoder. We derive expressions for the latency of the systolic implementations and show that, for a reasonable hardware constraint, the low-latency systolic implementation reduces latency by 34% for a [255, 239] RS code. For the same code and hardware constraints, the high-throughput implementation with a block pipelining depth of 5, increases throughput by 68%. In addition, the critical path of both the low-latency and the high-throughput implementation is smaller than that of previously proposed architectures.