Typical peak sidelobe level of binary sequences

Noga Alon; Simon Litsyn; Alexander Shpunt

doi:10.1109/TIT.2009.2034803

Typical peak sidelobe level of binary sequences

Noga Alon
, Simon Litsyn
, Alexander Shpunt

Research output: Contribution to journal › Article › peer-review

11 Scopus citations

Abstract

For a binary sequence S_n = {s_i : i = 1, 2,...,n} ∈ {±1}ⁿ, n > 1, the peak sidelobe level (PSL) is defined as M(S_n) = max_k=1,2,n-1 |Σ _i=1^n-k s_is_i+k|. It is shown that the distribution of M (S_n) is strongly concentrated, and asymptotically almost surely γ(S_n) = M(S_n)/√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 γ(S_n) ∈ [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 γ(S_n) equals √2.

Original language	English (US)
Article number	5361502
Pages (from-to)	545-554
Number of pages	10
Journal	IEEE Transactions on Information Theory
Volume	56
Issue number	1
DOIs	https://doi.org/10.1109/TIT.2009.2034803
State	Published - Jan 2010
Externally published	Yes

All Science Journal Classification (ASJC) codes

Information Systems
Computer Science Applications
Library and Information Sciences

Keywords

Aperiodic autocorrelation
Concentration
Peak sidelobe level (PSL)
Random binary sequences autocorrelation
Second moment method

Access to Document

10.1109/TIT.2009.2034803

Cite this

@article{c81fb15eb0bc44cb88826236313f6622,

title = "Typical peak sidelobe level of binary sequences",

abstract = "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.",

keywords = "Aperiodic autocorrelation, Concentration, Peak sidelobe level (PSL), Random binary sequences autocorrelation, Second moment method",

author = "Noga Alon and Simon Litsyn and Alexander Shpunt",

note = "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.",

year = "2010",

month = jan,

doi = "10.1109/TIT.2009.2034803",

language = "English (US)",

volume = "56",

pages = "545--554",

journal = "IEEE Transactions on Information Theory",

issn = "0018-9448",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "1",

}

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 - https://www.scopus.com/pages/publications/73849124156

UR - https://www.scopus.com/pages/publications/73849124156#tab=citedBy

U2 - 10.1109/TIT.2009.2034803

DO - 10.1109/TIT.2009.2034803

M3 - Article

AN - SCOPUS:73849124156

SN - 0018-9448

VL - 56

SP - 545

EP - 554

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

IS - 1

M1 - 5361502

ER -

Typical peak sidelobe level of binary sequences

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this