A root-finding algorithm for list decoding of Reed-Muller codes

Abstract

Let Fq[X1,...,Xm⌉ denote the set of polynomials over Fq in m variables, and Fq[X1,...,Xm⌉≤u denote the subset that consists of the polynomials of total degree at most u. Let H(T) be a nontrivial polynomial in T with coefficients in Fq[X1,...,Xm⌉. A crucial step in interpolation-based list decoding of q-ary Reed-Muller (RM) codes is finding the roots of H(T) in Fq[X1,...,Xm⌉ ≤u. In this correspondence, we present an efficient root-finding algorithm, which finds all the roots of H(T) in Fq[X1,...,Xm⌉≤. The algorithm can be used to speed up the list decoding of RM codes. © 2005 IEEE.