List Decoding of<tex>$q$</tex>-ary Reed–Muller Codes

Abstract

The q-ary Reed-Muller (RM) codes RM/sub q/(u,m) of length n=q/sup 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/sub q/(u,m) with u<q/2 and works for up to E<n(1-/spl radic/2u/q) errors. In this correspondence, following , we show that q-ary RM codes are subfield subcodes of RS codes over F/sub q//sup m/. Then, using the list- decoding algorithm in Guruswami and Sudan (1999) for RS codes over F/sub q//sup 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-/spl radic/(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/sub q/ and O(n/sup 3/) field operations in F/sub q//sup m/ under some assumption.