Efficient multiplicity calculation for algebraic soft-decision decoding of Reed-Solomon codes

摘要

Soft-decision decoding of Reed-Solomon (RS) codes consists of three key steps: multiplicity calculation, bivariate interpolation, and factorization. In this work, we investigate the first step, with the aim of reducing the complexity of multiplicity calculation. It is observed that the objective value of multiplicity calculation in Koetter and Vardy's (KV) algorithm can be expressed as an increasing function of independent parameter. Based on this fact, we propose to use bisection or golden section methods in multiplicity calculation. Simulation study demonstrates that our proposed approach can significantly reduce the computational complexity of RS codes decoding.