A proof of the Welch and Niho conjectures on cross-correlations of binary \(m\)-sequences (Q5941619)
From MaRDI portal
scientific article; zbMATH DE number 1635867
Language | Label | Description | Also known as |
---|---|---|---|
English | A proof of the Welch and Niho conjectures on cross-correlations of binary \(m\)-sequences |
scientific article; zbMATH DE number 1635867 |
Statements
A proof of the Welch and Niho conjectures on cross-correlations of binary \(m\)-sequences (English)
0 references
20 August 2001
0 references
The authors study the number of values attained by the cross-correlation of a binary \(m\)-sequence and its decimation by a factor of \(t\). This number equals the number of nonzero weights in the dual of \(C_{1,t}\), the binary cyclic code of length \(2^m-1\) with defining zeros \(\alpha\) and \(\alpha^t\), where \(\alpha\) is primitive in \(\mathrm{GF}(2^m)\). A unified method is presented for proving that \(C^\perp_{1,t}\) has three weight for the following pairs \((m,t)\): (a) \(t= 2^r+1\) if \((r,m)= 1\) (proved by Gold in 1968), (b) \(t= 2^{2r}- 2^r+ 1\) if \((r,m)= 1\) (proved by Welch (1969) and Kasami (1971)), (c) \(m= 2r+ 1\), \(t= 2^r+ 3\) (conjectured by Welch in 1972), (d) \(m\) is odd, \(4r\equiv-1\pmod m\), \(t= 2^{2r}+ 2^r- 1\) (conjectured by Niho, 1972). The method uses the Pless power moment identities, a deep theorem of McEliece on the divisibility of nonzero weights in cyclic codes by powers of two, and an ingenious counting method. In the application of the Pless power moment identities, Dobbertin's breakthrough result [\textit{H. Dobbertin}, IEEE Trans. Inf. Theory 45, 1271--1275 (1999; Zbl 0957.94021); Inf. Comput. 151, 57--72 (1999; Zbl 1072.94513)] is used, which states that in cases (c) and (d), \(C_{1,t}\) has minimum distance 5.
0 references
cyclic codes
0 references
cross-correlation
0 references
Pless power moment identities
0 references