Discrete Mathematics Problems Arising in Sequence Design for Digital Communications
Final Report Abstract
The extent to which a sequence of finite length differs from a shifted version of itself is measured by its aperiodic autocorrelations. Mainly motivated by applications in digital communications, there is sustained interest in sequences whose aperiodic autocorrelations at all nonzero shifts are small in magnitude relative to their lengths. Of particular interest are binary sequences, whose elements are −1 or 1. Many of the problems involved can also be stated as problems of general interest in pure mathematics and are in particular related or equivalent to several old unsolved problems concerning the behaviour of polynomials on the unit circle. The merit factor of a sequence, or equivalently the L4 norm on the unit circle of the corresponding polynomial, is a measure for the collective smallness of the aperiodic autocorrelations. For the first time since 1988, a new asymptotic lower bound for the optimal merit factor of binary sequences has been obtained in this project. This disproves a conjecture that 6 is the largest asymptotic merit factor for binary sequences and proves a conjecture on the asymptotic merit factor of a class of binary sequences formed by the Legendre symbol. The proof is based on a new method to determine the asymptotic merit factor, which combines Fourier analysis, character sum estimates, and combinatorial arguments. This method was also used to prove a series of other conjectures and to give simpler unifying proofs, as well as generalisations, of most prior results on the asymptotic merit factor of families of binary sequences. The largest magnitude of the aperiodic autocorrelations at nonzero shifts is called the peak sidelobe level. This measure is of significant interest for communications engineers and gives rise to interesting mathematical problems. It has been shown in this project that the peak sidelobe level of random binary sequences is strongly concentrated, which gives a complete solution to an old problem from the 1960s. The method, which combines probabilistic and counting arguments, can also be applied to attack other important problems in this field. Moreover, a new construction for binary sequences with small peak sidelobe level has been found, which improves the previously best known result, dating back to 1984. There are indications that, for all practical lengths, this construction produces binary sequences with almost optimal peak sidelobe level. In recent years, codes over Z4 have attracted the attention of the coding community as several very good binary nonlinear codes were found to be binary images under the Gray map of linear codes over Z4. Cyclic codes over Z4 can be used to construct sets of quaternary sequences with mutually low correlation, which means that every sequence in the set can be well distinguished from nonzero shifts of itself and from all shifts of all other sequences in the set. The transition from a binary to a quaternary alphabet is important since this allows the construction of asymptotically optimal sets. In this research project, connections between Z4-valued quadratic forms and cyclic codes over Z4 have been studied. This naturally leads to extremal problems related to Z4-valued quadratic forms. The resulting theory sheds new light on known key results in this area and gives rise to new results concerning sets of quaternary sequences.
Publications
- Advances in the merit factor problem for binary sequences
K.-U. Schmidt, J. Jedwab and D. J. Katz
- Littlewood polynomials with small L4 norm
K.-U. Schmidt, J. Jedwab and D. J. Katz
- The peak sidelobe level of random binary sequences
Kai-Uwe Schmidt
- Z4 -valued quadratic forms and quaternary sequence families, IEEE Trans. Inf. Theory 55(12):5803–5810, 2009
Kai-Uwe Schmidt
- Symmetric bilinear forms over finite fields of even characteristic, J. Combin. Theory (A) 117(8):1011–1026, 2010
Kai-Uwe Schmidt
- Binary sequences with small peak sidelobe level, IEEE Trans. Inf. Theory 58(4):2512– 2515, 2012
Kai-Uwe Schmidt
