On Algebraic Decoding of q-ary Reed-Muller and Product Reed-Solomon Codes

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 q^m when 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 - radiclq^m-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 tau < Pi_i=1 ^m(1 - radick_i/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.