Article Contents
Article Contents

# A Fourier transform approach for improving the Levenshtein's lower bound on aperiodic correlation of binary sequences

• A binary sequence family ${\mathcal S}$ of length $n$ and size $M$ can be characterized by the maximum magnitude of its nontrivial aperiodic correlation, denoted as $\theta_{\max} ({\mathcal S})$. The lower bound on $\theta_{\max} ({\mathcal S})$ was originally presented by Welch, and improved later by Levenshtein. In this paper, a Fourier transform approach is introduced in an attempt to improve the Levenshtein's lower bound. Through the approach, a new expression of the Levenshtein bound is developed. Along with numerical supports, it is found that $\theta_{\max} ^2 ({\mathcal S}) > 0.3584 n-0.0810$ for $M=3$ and $n \ge 4$, and $\theta_{\max} ^2 ({\mathcal S}) > 0.4401 n-0.1053$ for $M=4$ and $n \ge 4$, respectively, which are tighter than the original Welch and Levenshtein bounds.
Mathematics Subject Classification: Primary: 94A55, 94A05; Secondary: 94B65.

 Citation:

•  [1] E. Chu, Discrete and Continuous Fourier Transforms: Analysis, Applications and Fast Algorithms, Chapman & Hall/CRC, 2008. [2] R. M. Gray, Toeplitz and Circulant Matrices: A Review, Now Publishers Inc., 2006. [3] V. I. Levenshtein, New lower bounds on aperiodic crosscorrelation of binary codes, IEEE Trans. Inform. Theory, 45 (1999), 284-288.doi: 10.1109/18.746818. [4] S. Litsyn, Peak Power Control in Multicarrier Commmunications, Cambridge Univ. Press, 2007. [5] Z. Liu, Y. L. Guan, S. Boztas and U. Parampalli, Quadratic weight vector for tighter aperiodic Levenshtein bound, in IEEE International Symposium on Information Theory, 2013, 3130-3134. [6] Z. Liu, Y. L. Guan and W. H. Mow, Improved lower bound for quasi-complementary sequence set, in IEEE International Symposium on Information Theory, 2011, 489-493. [7] Z. Liu, U. Parampalli, Y. L. Guan and S. Boztas, A new weight vector for a tighter Levenshtein bound on aperiodic correlation, IEEE Trans. Inform. Theory, 60 (2014), 1356-1366.doi: 10.1109/TIT.2013.2293493. [8] D. Y. Peng and P. Z. Fan, Generalised Sarwate bounds on the aperiodic correlation of sequences over complex roots of unity, IEE Proceedings - Communications, 151 (2004), 375-382. [9] M. B. Pursley, Performance evaluation for phase-coded spread-spectrum multiple-accesss communication - Part I: system analysis, IEEE Trans. Commun., COM-15 (1977), 795-799. [10] L. R. Welch, Lower bounds on the maximum cross correlation of signals, IEEE Trans. Inform. Theory, IT-20 (1974), 397-399.