A New Theorem About the Mattson-Solomon Polynomial and Some Applications

Let F = GF(2), and FG = F[x]/(xⁿ + 1). FG is the residue class ring of polynomials mod xⁿ + 1. An element of FG is represented by a polynomial of degree at most n − 1 c(x) = c_o + c₁x + … + c_n−1x_n−1 with coefficients in F. It may also be represented by a polynomial [formula omitted] with coefficients in GF(2^m), where m is the least integer such that n divides 2^m − 1, and α is a primitive nth root of unity. Mattson and Solomon [1] introduced this representation in 1961. The new theorem states that [formula omitted] A typical application of this result is as follows. Let n = 2^m − 1, where m ≡ 1 mod 2. Let A_l be the cyclic code of dimension 2m defined by the property that its check polynomial has zeros α^−j, where j = 1,2,⋯, 2^m−1 and j = 1,2l,⋯,2^m−1 l, l = 2ⁱ + 1. If (i,m) = 1 this code has just three nonzero weights, namely, 2^m−1 ± 2^(m−1)/2 and 2^m−1. The weight distribution can then be obtained from the MacWilliams identities. These conditions are satisfied for n = 31, l = 3,5; n = 127, l = 3,5,9; n = 511, l= 3,5,17; etc. Thus for n = 127, for example, the three codes A₃, A₅, A₉ have the same weight distribution, although they are probably not equivalent in the usual sense.