List decoding of q-ary Reed-Muller codes

The q-ary Reed-Muller (RM) codes RMq(u,m) of length n = q(m) are a generalization of Reed-Solomon (RS) codes, which use polynomials in m variables to encode messages through functional encoding. Using an idea of reducing the multivariate case to the univariate case, randomized list-decoding algorithms for RM codes were given in [1] and [15]. The algorithm in [15] is an improvement of the algorithm in [1], it is applicable to codes RMq(u,m) with u < q/2 and works for up to E < n (1-root2u/q) errors. In this correspondence, following [6], we show that q-ary RM codes are subfield subcodes; of RS codes over F-qm. Then, using the list-decoding algorithm in [5] for RS codes over F,m, we present a list-decoding algorithm for q-ary RM codes. This algorithm is applicable to codes of any rates, and achieves an error-correction bound n(1-root(n-d)/n). The algorithm achieves a better error-correction bound than the algorithm in [15], since when u is small n (1-root/(n-d)/n) = n(1-1rootu/q) The implementation of the algorithm requires O (n) field operations in F-q and O(n(3)) field operations in F-qm under some assumption.