Reduced complexity interpolation architecture for soft-decision Reed-Solomon decoding

Reed-Solomon (RS) codes are one of the most widely utilized block error-correcting codes in modern communication and computer systems. Compared to hard-decision decoding, soft-decision decoding offers considerably higher error-correcting capability. The Koetter-Vardy (KV) soft-decision decoding algorithm can achieve substantial coding gain, while maintaining a complexity polynomial with respect to the code word length. In the KV algorithm, the interpolation step dominates the decoding complexity. A reduced complexity interpolation architecture is proposed in this paper by eliminating the polynomial updating corresponding to zero discrepancy coefficients in this step. Using this architecture, an area reduction of 27% can be achieved over prior efforts for the interpolation step of a typical (255, 239) RS code, while the interpolation latency remains the same.