List decoding of q-ary Reed-Muller codes

The q-ary Reed-Muller (RM) codes RM_q(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 and . The algorithm in Sudan et al. (1999) is an improvement of the algorithm in , it is applicable to codes RM_q(u,m) with uq^m. Then, using the list- decoding algorithm in Guruswami and Sudan (1999) for RS codes over F_q^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-√(n-d)/n). The algorithm achieves a better error-correction bound than the algorithm in , since when u is small. The implementation of the algorithm requires O(n) field operations in F_q and O(n³) field operations in F_q^m under some assumption.