November  2007, 1(4): 461-475. doi: 10.3934/amc.2007.1.461

Bounds on the growth rate of the peak sidelobe level of binary sequences

1. 

The D. E. Shaw Group, 39th Floor, Tower 45, 120 West Forty-Fifth Street, New York, NY 10036, United States

2. 

Department of Mathematics, Simon Fraser University, 8888 University Drive, Burnaby, BC, Canada V5A 1S6, Canada

Received  May 2007 Revised  October 2007 Published  October 2007

The peak sidelobe level (PSL) of a binary sequence is the largest absolute value of all its nontrivial aperiodic autocorrelations. A classical problem of digital sequence design is to determine how slowly the PSL of a length $n$ binary sequence can grow, as $n$ becomes large. Moon and Moser showed in 1968 that the growth rate of the PSL of almost all length $n$ binary sequences lies between order $\sqrt{n\log n}$ and $\sqrt{n}$, but since then no theoretical improvement to these bounds has been found.
   We present the first numerical evidence on the tightness of these bounds, showing that the PSL of almost all binary sequences of length $n$ appears to grow exactly like order $\sqrt{n\log n}$, and that the PSL of almost all $m$-sequences of length $n$ appears to grow exactly like order $\sqrt{n}$. In the case of $m$-sequences, a key algorithmic insight reveals behaviour that was previously well beyond the range of computation.
Citation: Denis Dmitriev, Jonathan Jedwab. Bounds on the growth rate of the peak sidelobe level of binary sequences. Advances in Mathematics of Communications, 2007, 1 (4) : 461-475. doi: 10.3934/amc.2007.1.461
[1]

Alexander Zeh, Antonia Wachter. Fast multi-sequence shift-register synthesis with the Euclidean algorithm. Advances in Mathematics of Communications, 2011, 5 (4) : 667-680. doi: 10.3934/amc.2011.5.667

[2]

Richard Hofer, Arne Winterhof. On the arithmetic autocorrelation of the Legendre sequence. Advances in Mathematics of Communications, 2017, 11 (1) : 237-244. doi: 10.3934/amc.2017015

[3]

Xiaohui Liu, Jinhua Wang, Dianhua Wu. Two new classes of binary sequence pairs with three-level cross-correlation. Advances in Mathematics of Communications, 2015, 9 (1) : 117-128. doi: 10.3934/amc.2015.9.117

[4]

Kai-Uwe Schmidt, Jonathan Jedwab, Matthew G. Parker. Two binary sequence families with large merit factor. Advances in Mathematics of Communications, 2009, 3 (2) : 135-156. doi: 10.3934/amc.2009.3.135

[5]

Ji-Woong Jang, Young-Sik Kim, Sang-Hyo Kim. New design of quaternary LCZ and ZCZ sequence set from binary LCZ and ZCZ sequence set. Advances in Mathematics of Communications, 2009, 3 (2) : 115-124. doi: 10.3934/amc.2009.3.115

[6]

Wenbing Chen, Jinquan Luo, Yuansheng Tang, Quanquan Liu. Some new results on cross correlation of $p$-ary $m$-sequence and its decimated sequence. Advances in Mathematics of Communications, 2015, 9 (3) : 375-390. doi: 10.3934/amc.2015.9.375

[7]

Zilong Wang, Guang Gong. Correlation of binary sequence families derived from the multiplicative characters of finite fields. Advances in Mathematics of Communications, 2013, 7 (4) : 475-484. doi: 10.3934/amc.2013.7.475

[8]

Hua Liang, Jinquan Luo, Yuansheng Tang. On cross-correlation of a binary $m$-sequence of period $2^{2k}-1$ and its decimated sequences by $(2^{lk}+1)/(2^l+1)$. Advances in Mathematics of Communications, 2017, 11 (4) : 693-703. doi: 10.3934/amc.2017050

[9]

Longye Wang, Gaoyuan Zhang, Hong Wen, Xiaoli Zeng. An asymmetric ZCZ sequence set with inter-subset uncorrelated property and flexible ZCZ length. Advances in Mathematics of Communications, 2018, 12 (3) : 541-552. doi: 10.3934/amc.2018032

[10]

Yixiao Qiao, Xiaoyao Zhou. Zero sequence entropy and entropy dimension. Discrete & Continuous Dynamical Systems - A, 2017, 37 (1) : 435-448. doi: 10.3934/dcds.2017018

[11]

Walter Briec, Bernardin Solonandrasana. Some remarks on a successive projection sequence. Journal of Industrial & Management Optimization, 2006, 2 (4) : 451-466. doi: 10.3934/jimo.2006.2.451

[12]

Yuhua Sun, Zilong Wang, Hui Li, Tongjiang Yan. The cross-correlation distribution of a $p$-ary $m$-sequence of period $p^{2k}-1$ and its decimated sequence by $\frac{(p^{k}+1)^{2}}{2(p^{e}+1)}$. Advances in Mathematics of Communications, 2013, 7 (4) : 409-424. doi: 10.3934/amc.2013.7.409

[13]

Matthew Macauley, Henning S. Mortveit. Update sequence stability in graph dynamical systems. Discrete & Continuous Dynamical Systems - S, 2011, 4 (6) : 1533-1541. doi: 10.3934/dcdss.2011.4.1533

[14]

Wenjun Xia, Jinzhi Lei. Formulation of the protein synthesis rate with sequence information. Mathematical Biosciences & Engineering, 2018, 15 (2) : 507-522. doi: 10.3934/mbe.2018023

[15]

José S. Cánovas. Topological sequence entropy of $\omega$–limit sets of interval maps. Discrete & Continuous Dynamical Systems - A, 2001, 7 (4) : 781-786. doi: 10.3934/dcds.2001.7.781

[16]

Ji-Woong Jang, Young-Sik Kim, Sang-Hyo Kim, Dae-Woon Lim. New construction methods of quaternary periodic complementary sequence sets. Advances in Mathematics of Communications, 2010, 4 (1) : 61-68. doi: 10.3934/amc.2010.4.61

[17]

Aixian Zhang, Zhengchun Zhou, Keqin Feng. A lower bound on the average Hamming correlation of frequency-hopping sequence sets. Advances in Mathematics of Communications, 2015, 9 (1) : 55-62. doi: 10.3934/amc.2015.9.55

[18]

Jingjun Bao. New families of strictly optimal frequency hopping sequence sets. Advances in Mathematics of Communications, 2018, 12 (2) : 387-413. doi: 10.3934/amc.2018024

[19]

Markus Dick, Martin Gugat, Günter Leugering. Classical solutions and feedback stabilization for the gas flow in a sequence of pipes. Networks & Heterogeneous Media, 2010, 5 (4) : 691-709. doi: 10.3934/nhm.2010.5.691

[20]

Eric Benoît. Bifurcation delay - the case of the sequence: Stable focus - unstable focus - unstable node. Discrete & Continuous Dynamical Systems - S, 2009, 2 (4) : 911-929. doi: 10.3934/dcdss.2009.2.911

2018 Impact Factor: 0.879

Metrics

  • PDF downloads (5)
  • HTML views (0)
  • Cited by (8)

Other articles
by authors

[Back to Top]