TY - JOUR

T1 - Typical peak sidelobe level of binary sequences

AU - Alon, Noga

AU - Litsyn, Simon

AU - Shpunt, Alexander

N1 - Funding Information:
Manuscript received August 22, 2008; revised February 04, 2009. Current version published December 23, 2009. This work was supported in part by a USA-Israeli BSF grant, by a grant from the Israel Science Foundation, and by an ERC advanced grant. The work of S. Litsyn was supported in part by ISF under Grant 1177/06. The work of A. Shpunt was supported in part by the Di Capua MIT Graduate Fellowship.

PY - 2010/1

Y1 - 2010/1

N2 - For a binary sequence Sn = {si : i = 1, 2,...,n} ∈ {±1}n, n > 1, the peak sidelobe level (PSL) is defined as M(Sn) = maxk=1,2,n-1 |Σ i=1n-k sisi+k|. It is shown that the distribution of M (Sn) is strongly concentrated, and asymptotically almost surely γ(Sn) = M(Sn)/√n In n ∈ [1 - o(1),√2]. Explicit bounds for the number of sequences outside this range are provided. This improves on the best earlier known result due to Moon and Moser that the typical γ(Sn) ∈ [o(1/√In n), 2], and settles to the affirmative the conjecture of Dmitriev and Jedwab on the growth rate of the typical peak sidelobe. Finally, it is shown that modulo some natural conjecture, the typical γ(Sn) equals √2.

AB - For a binary sequence Sn = {si : i = 1, 2,...,n} ∈ {±1}n, n > 1, the peak sidelobe level (PSL) is defined as M(Sn) = maxk=1,2,n-1 |Σ i=1n-k sisi+k|. It is shown that the distribution of M (Sn) is strongly concentrated, and asymptotically almost surely γ(Sn) = M(Sn)/√n In n ∈ [1 - o(1),√2]. Explicit bounds for the number of sequences outside this range are provided. This improves on the best earlier known result due to Moon and Moser that the typical γ(Sn) ∈ [o(1/√In n), 2], and settles to the affirmative the conjecture of Dmitriev and Jedwab on the growth rate of the typical peak sidelobe. Finally, it is shown that modulo some natural conjecture, the typical γ(Sn) equals √2.

KW - Aperiodic autocorrelation

KW - Concentration

KW - Peak sidelobe level (PSL)

KW - Random binary sequences autocorrelation

KW - Second moment method

UR - http://www.scopus.com/inward/record.url?scp=73849124156&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=73849124156&partnerID=8YFLogxK

U2 - 10.1109/TIT.2009.2034803

DO - 10.1109/TIT.2009.2034803

M3 - Article

AN - SCOPUS:73849124156

VL - 56

SP - 545

EP - 554

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

SN - 0018-9448

IS - 1

M1 - 5361502

ER -