A Characterization of Low-Weight Words That Span Generalized Reed–Muller Codes
T. Kaufman, Dana Ron · IEEE Transactions on Information Theory · 2005
We consider the generalized Reed-Muller code R/sub Fq/(/spl rho/,m) of order /spl rho/ and length q/sup m/,m>1, over the field F/sub q/, where q=p/sup t/ for prime p and t/spl ges/1. In particular, we are interested in the case that t>1 (so that q is not prime), and the order /spl rho/ is at least q. As shown by Ding and Key, under these conditions, unless /spl rho/ is very large (i.e., /spl rho/>(m-1)(q-1)+p/sup t-1/-2), the code is not spanned by its minimum-weight words. Furthermore, there was no known characterization of words with small weight that span the code. In this correspondence, we characterize a set of words that span the code, and show that their weight is upper-bounded by q/sup /spl lceil/m(q-1)-/spl rho//q-q/p/spl rceil//, which is at most quadratic in the weight of the minimum-weight words.