Scalable Interpolation Architecture for Soft-decision Reed-Solomon Decoding

Reed-Solomon (RS) codes can be found in many communication and digital storage applications. Among various decoding algorithms, algebraic soft-decision decoding (ASD) of RS codes can achieve very good performance with polynomial complexity. Interpolation is a major step of ASD algorithms. It has been shown that the architectures for interpolation with small multiplicities can achieve higher efficiency by using the newly developed Lee-O'Sullivan (LO) algorithm. The LO algorithm consists of generator construction and basis conversion steps and the achievable throughput is decided by the number of coefficients updated simultaneously in the basis conversion. This algorithm is scalable. In this paper, architectures with different numbers of coefficients updated in parallel in the basis conversion are discussed. For each case, optimized computation units and scheduling schemes are developed. Our results can serve as guidelines for picking proper interpolation architectures to satisfy given application requirements.