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

Anthony M. Kerdock, F. Jessie MacWilliams, Andrew M. Odlyzko

Research output: Contribution to journalArticlepeer-review

6 Scopus citations


Let F = GF(2), and FG = F[x]/(xn + 1). FG is the residue class ring of polynomials mod xn + 1. An element of FG is represented by a polynomial of degree at most n − 1 c(x) = co + c1x + … + cn−1xn−1 with coefficients in F. It may also be represented by a polynomial [formula omitted] with coefficients in GF(2m), where m is the least integer such that n divides 2m − 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 = 2m − 1, where m ≡ 1 mod 2. Let Al be the cyclic code of dimension 2m defined by the property that its check polynomial has zeros α−j, where j = 1,2,⋯, 2m−1 and j = 1,2l,⋯,2m−1 l, l = 2i + 1. If (i,m) = 1 this code has just three nonzero weights, namely, 2m−1 ± 2(m−1)/2 and 2m−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 A3, A5, A9 have the same weight distribution, although they are probably not equivalent in the usual sense.

Original languageEnglish (US)
Pages (from-to)85-89
Number of pages5
JournalIEEE Transactions on Information Theory
Issue number1
StatePublished - Jan 1974


Dive into the research topics of 'A New Theorem About the Mattson-Solomon Polynomial and Some Applications'. Together they form a unique fingerprint.

Cite this