Towards a VLSI architecture for interpolation-based soft-decision Reed-Solomon decoders

The Koetter-Vardy algorithm is an algebraic soft-decision decoder for Reed-Solomon codes which is based on the Guruswami-Sudan list decoder. There are three main steps: (1) multiplicity calculation, (2) interpolation and (3) root finding. The Koetter-Vardy algorithm seems challenging to implement due to the high cost of interpolation. Motivated by a VLSI implementation viewpoint we propose an improvement to the interpolation algorithm that uses a transformation of the received word to reduce the number of iterations. We show how to reduce the memory requirements and give an efficient VLSI implementation for the Hasse derivative.