On Algebraic Decoding of q-ary Reed-Muller and Product Reed-Solomon Codes
Nandakishore Santhi · 2007
We consider a list decoding algorithm recently proposed by Pellikaan-Wu [8] for q-ary Reed-Muller codes R M q(l, m, n) of length n les qmwhen I les q. A simple and easily accessible correctness proof is given which shows that this algorithm achieves a relative error-correction radius of taules (1 - radiclqm-1/n). This is an improvement over the proof using one-point Algebraic-Geometric codes given in [8]. The described algorithm can be adapted to decode Product-Reed- Solomon codes. We then propose a new low complexity recursive algebraic decoding algorithm for Reed-Muller and product-Reed-Solomon codes. Our algorithm achieves a relative error correction radius of taui=1m(1 - radicki/q). This technique is then proved to outperform the Pellikaan-Wu method in both complexity and error correction radius over a wide range of code rates.