List Decoding of-ary Reed–Muller Codes

Abstract—The q-ary Reed–Muller (RM) codes RM (u;m) of length n = q are a generalization of Reed–Solomon (RS) codes, which use poly-nomials in m variables to encode messages through functional encoding. Using an idea of reducing the multivariate case to the univariate case, ran-domized 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 appli-cable to codesRM (u;m) with u < q=2 and works for up to E < n(1 2u=q) errors. In this correspondence, following [6], we show that q-ary RM codes are subfield subcodes of RS codes over. Then, using the list-decoding algorithm in [5] for RS codes over, we present a list-de-coding 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 [15], since when u is small 1 ( ) = 1 The implementation of the algorithm requires O(n) field operations in and O(n) field operations in under some assumption. Index Terms—Guruswami–Sudan algorithm, list decoding, order domain, q-ary Reed–Muller (RM) codes, subfield subcodes