| Reed-Solomon codes are powerful error-correcting codes that can be found in a wide variety of digital communications systems, from digital media to wireless communications and deep-space probes. The ubiquitous nature of these codes continues to fuel research into decoding algorithms some forty years after their introduction.; Using the recently-introduced Guruswami-Sudan list decoding algorithm as a starting point, Koetter and Vardy introduced an algebraic soft-decision decoding algorithm that uses “soft” reliability information from the channel to provide improved error correction capability.; In this thesis, we study the problem of the implementation of the Koetter-Vardy algorithm at the systems, algorithmic, and architectural levels.; A systems level architecture is proposed that reduces the average complexity of soft-decision decoding. We introduce an error-detection method for the output of the Koetter-Vardy algorithm that can determine which decoded frames are unreliable and need extra processing. We show that the extra memory required to implement this scheme is low and can be integrated into on-chip SRAM.; Fast algorithmic optimizations for the components of the Koetter-Vardy algorithm, interpolation and factoring, are introduced for high-rate codes that result in a speedup factor of O((n/( n − k))2) and a memory reduction factor of O(n/n − k), where n is the code length and k is the code dimension. A software implementation on a P4 at 2.4 GHz was demonstrated to decode at 1 Mbps.; A parallel architecture for polynomial interpolation is described that could be used to implement CMOS ASIC decoders in the 10–100 of Mbps range. We have demonstrated a prototype on an FPGA system that runs at 23 MHz with a throughput of at least 10 Mbps. |
