# American Institute of Mathematical Sciences

May  2014, 8(2): 209-222. doi: 10.3934/amc.2014.8.209

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

 1 Department of Electrical and Computer Engineering, Lakehead University, Thunder Bay, Ontario, Canada

Received  August 2013 Revised  January 2014 Published  May 2014

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.
Citation: Nam Yul Yu. A Fourier transform approach for improving the Levenshtein's lower bound on aperiodic correlation of binary sequences. Advances in Mathematics of Communications, 2014, 8 (2) : 209-222. doi: 10.3934/amc.2014.8.209
##### References:
 [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.

show all references

##### References:
 [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.
 [1] Gang Wang, Deng-Ming Xu, Fang-Wei Fu. Constructions of asymptotically optimal codebooks with respect to Welch bound and Levenshtein bound. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021065 [2] Xing Liu, Daiyuan Peng. Sets of frequency hopping sequences under aperiodic Hamming correlation: Upper bound and optimal constructions. Advances in Mathematics of Communications, 2014, 8 (3) : 359-373. doi: 10.3934/amc.2014.8.359 [3] Gaojun Luo, Xiwang Cao. Two classes of near-optimal codebooks with respect to the Welch bound. Advances in Mathematics of Communications, 2021, 15 (2) : 279-289. doi: 10.3934/amc.2020066 [4] Xing Liu, Daiyuan Peng. Frequency hopping sequences with optimal aperiodic Hamming correlation by interleaving techniques. Advances in Mathematics of Communications, 2017, 11 (1) : 151-159. doi: 10.3934/amc.2017009 [5] 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 [6] Yael Ben-Haim, Simon Litsyn. A new upper bound on the rate of non-binary codes. Advances in Mathematics of Communications, 2007, 1 (1) : 83-92. doi: 10.3934/amc.2007.1.83 [7] Mariusz Lemańczyk, Clemens Müllner. Automatic sequences are orthogonal to aperiodic multiplicative functions. Discrete and Continuous Dynamical Systems, 2020, 40 (12) : 6877-6918. doi: 10.3934/dcds.2020260 [8] Mohammed Mesk, Ali Moussaoui. On an upper bound for the spreading speed. Discrete and Continuous Dynamical Systems - B, 2022, 27 (7) : 3897-3912. doi: 10.3934/dcdsb.2021210 [9] Nian Li, Xiaohu Tang, Tor Helleseth. A class of quaternary sequences with low correlation. Advances in Mathematics of Communications, 2015, 9 (2) : 199-210. doi: 10.3934/amc.2015.9.199 [10] Mikko Kaasalainen. Dynamical tomography of gravitationally bound systems. Inverse Problems and Imaging, 2008, 2 (4) : 527-546. doi: 10.3934/ipi.2008.2.527 [11] 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 [12] Yu Zheng, Li Peng, Teturo Kamae. Characterization of noncorrelated pattern sequences and correlation dimensions. Discrete and Continuous Dynamical Systems, 2018, 38 (10) : 5085-5103. doi: 10.3934/dcds.2018223 [13] Z.G. Feng, K.L. Teo, Y. Zhao. Branch and bound method for sensor scheduling in discrete time. Journal of Industrial and Management Optimization, 2005, 1 (4) : 499-512. doi: 10.3934/jimo.2005.1.499 [14] Marcin Dumnicki, Łucja Farnik, Halszka Tutaj-Gasińska. Asymptotic Hilbert polynomial and a bound for Waldschmidt constants. Electronic Research Announcements, 2016, 23: 8-18. doi: 10.3934/era.2016.23.002 [15] Miklós Horváth, Márton Kiss. A bound for ratios of eigenvalues of Schrodinger operators on the real line. Conference Publications, 2005, 2005 (Special) : 403-409. doi: 10.3934/proc.2005.2005.403 [16] Roland D. Barrolleta, Emilio Suárez-Canedo, Leo Storme, Peter Vandendriessche. On primitive constant dimension codes and a geometrical sunflower bound. Advances in Mathematics of Communications, 2017, 11 (4) : 757-765. doi: 10.3934/amc.2017055 [17] John Fogarty. On Noether's bound for polynomial invariants of a finite group. Electronic Research Announcements, 2001, 7: 5-7. [18] Srimanta Bhattacharya, Sushmita Ruj, Bimal Roy. Combinatorial batch codes: A lower bound and optimal constructions. Advances in Mathematics of Communications, 2012, 6 (2) : 165-174. doi: 10.3934/amc.2012.6.165 [19] Carmen Cortázar, Marta García-Huidobro, Pilar Herreros. On the uniqueness of bound state solutions of a semilinear equation with weights. Discrete and Continuous Dynamical Systems, 2019, 39 (11) : 6761-6784. doi: 10.3934/dcds.2019294 [20] Yuntao Zang. An upper bound of the measure-theoretical entropy. Discrete and Continuous Dynamical Systems, 2022  doi: 10.3934/dcds.2022052

2020 Impact Factor: 0.935