Advances in the merit factor problem for binary sequences

DOI10.1016/J.JCTA.2013.01.010MaRDI QIDQ1946741zbMATH OpenOpenAlexFDO

Authors Daniel J. Katz, Kai-Uwe Schmidt, Jonathan Jedwab

Publication date 15 April 2013

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1205.0626

zbMATH Keywords

asymptoticbinary sequencecharacter sumFourier analysislattice pointmerit factorskew-symmetric

Mathematics Subject Classification ID

Special sequences and polynomials (11B83) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Shift register sequences and sequences over finite alphabets in information and communication theory (94A55)

Abstract: The identification of binary sequences with large merit factor (small mean-squared aperiodic autocorrelation) is an old problem of complex analysis and combinatorial optimization, with practical importance in digital communications engineering and condensed matter physics. We establish the asymptotic merit factor of several families of binary sequences and thereby prove various conjectures, explain numerical evidence presented by other authors, and bring together within a single framework results previously appearing in scattered form. We exhibit, for the first time, families of skew-symmetric sequences whose asymptotic merit factor is as large as the best known value (an algebraic number greater than 6.34) for all binary sequences; this is interesting in light of Golay's conjecture that the subclass of skew-symmetric sequences has asymptotically optimal merit factor. Our methods combine Fourier analysis, estimation of character sums, and estimation of the number of lattice points in polyhedra.

Review text

For a binary sequence \(A = (a_0,a_1,\ldots,a_{t-1})\), \(a_j\in\{-1,1\}\), of length \(t\) the aperiodic autocorrelation at shift \(u\), \(0\leq u\leq t-1\), is defined as \(c_u = \sum_{j=0}^{t-u-1}a_ja_{j+u}\) and the merit factor of \(A\) is defined as \(F(A) = t^2/(2\sum_{u=1}^{t-1}c_u^2)\). In [``Littlewood polynomials with small \(L^4\) norm, Adv. Math. 241, 127--136 (2013; Zbl 1291.30027)] the authors showed that a certain family of binary sequences attains an asymptotic merit factor of \(6.342061\ldots\) disproving a conjecture that 6 is asymptotically the largest possible merit factor for binary sequences. In this article the authors further develop their methods to deal with other classes of sequence families like \(m\)-sequences, Legendre and Jacobi sequences, and sequences obtained from them with the periodic and negaperiodic constructions in [\textit{M. G. Parker}, Applied algebra, algebraic algorithms and error-correcting codes -- AAECC-14, Lect. Notes Comput. Sci. 2227, 200--209 (2001; Zbl 1057.94510)]. With this, several previous numerical results are explained and a series of conjectures from previous works are proved. The paper contains comprehensive information on currently known results on the asymptotic merit factor. As one of the interesting results it is shown that the largest known asymptotic merit factor for a family of binary sequences can be achieved by families of skew-symmetric binary sequences, i.e., sequences \((a_0,a_1,\ldots,a_{2s})\) of odd length \(2s+1\) satisfying \(a_{s+j} = (-1)^ja_{s-j}\), \(1\leq j\leq s\). This supports a conjecture of \textit{M. J. E. Golay} [IEEE Trans. Inf. Theory 23, 43--51 (1977; Zbl 0359.94019)].

Recommendations

• A Survey of the Merit Factor Problem for Binary Sequences
• Applied Algebra, Algebraic Algorithms and Error-Correcting Codes
• scientific article; zbMATH DE number 1390146
• scientific article; zbMATH DE number 4106767
• Two binary sequence families with large merit factor

Cited in

(21)

• Merit factors and Morse sequences
• Improved lower bound for the Mahler measure of the Fekete polynomials
• Optimizing the aperiodic merit factor of binary arrays
• Two binary sequence families with large merit factor
• The merit factor of binary sequence families constructed from m-sequences
• The merit factor problem
• Recent progress in the study of polynomials with constrained coefficients
• Binary Sequences With Merit Factor Greater Than<tex>$6.34$</tex>
• Binary Sequences With Merit Factor<tex>$≫ 6.3$</tex>
• Appended m-sequences with merit factor greater than 3.34
• Construction of Even Length Binary Sequences With Asymptotic Merit Factor 6
• Determination of the merit factor of Legendre sequences
• Low autocorrelation binary sequences: exact enumeration and optimization by evolutionary strategies
• scientific article; zbMATH DE number 1390146 (Why is no real title available?)
• Merit factors of polynomials derived from difference sets
• On pseudorandomness of families of binary sequences
• Efficient Optimization of the Merit Factor of Long Binary Sequences
• A Survey of the Merit Factor Problem for Binary Sequences
• Applied Algebra, Algebraic Algorithms and Error-Correcting Codes
• The merit factor of binary arrays derived from the quadratic character
• Sequences with small correlation

This page was built for publication: Advances in the merit factor problem for binary sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1946741)