# 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. 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. [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. [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. 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. [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. [10] L. R. Welch, Lower bounds on the maximum cross correlation of signals,, IEEE Trans. Inform. Theory, IT-20 (1974), 397.

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. 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. [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. [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. 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. [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. [10] L. R. Welch, Lower bounds on the maximum cross correlation of signals,, IEEE Trans. Inform. Theory, IT-20 (1974), 397.
 [1] 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 [2] 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 [3] 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 [4] 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 [5] Mikko Kaasalainen. Dynamical tomography of gravitationally bound systems. Inverse Problems & Imaging, 2008, 2 (4) : 527-546. doi: 10.3934/ipi.2008.2.527 [6] 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 [7] 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 [8] Z.G. Feng, K.L. Teo, Y. Zhao. Branch and bound method for sensor scheduling in discrete time. Journal of Industrial & Management Optimization, 2005, 1 (4) : 499-512. doi: 10.3934/jimo.2005.1.499 [9] 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 [10] 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 [11] John Fogarty. On Noether's bound for polynomial invariants of a finite group. Electronic Research Announcements, 2001, 7: 5-7. [12] 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 [13] 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 [14] Yu Zheng, Li Peng, Teturo Kamae. Characterization of noncorrelated pattern sequences and correlation dimensions. Discrete & Continuous Dynamical Systems - A, 2018, 38 (10) : 5085-5103. doi: 10.3934/dcds.2018223 [15] Xiaoni Du, Chenhuang Wu, Wanyin Wei. An extension of binary threshold sequences from Fermat quotients. Advances in Mathematics of Communications, 2016, 10 (4) : 743-752. doi: 10.3934/amc.2016038 [16] Nguyen Van Thoai. Decomposition branch and bound algorithm for optimization problems over efficient sets. Journal of Industrial & Management Optimization, 2008, 4 (4) : 647-660. doi: 10.3934/jimo.2008.4.647 [17] J. De Beule, K. Metsch, L. Storme. Characterization results on weighted minihypers and on linear codes meeting the Griesmer bound. Advances in Mathematics of Communications, 2008, 2 (3) : 261-272. doi: 10.3934/amc.2008.2.261 [18] Florent Foucaud, Tero Laihonen, Aline Parreau. An improved lower bound for $(1,\leq 2)$-identifying codes in the king grid. Advances in Mathematics of Communications, 2014, 8 (1) : 35-52. doi: 10.3934/amc.2014.8.35 [19] Carlos Munuera, Fernando Torres. A note on the order bound on the minimum distance of AG codes and acute semigroups. Advances in Mathematics of Communications, 2008, 2 (2) : 175-181. doi: 10.3934/amc.2008.2.175 [20] Xu Zhang, Shiwang Ma, Qilin Xie. Bound state solutions of Schrödinger-Poisson system with critical exponent. Discrete & Continuous Dynamical Systems - A, 2017, 37 (1) : 605-625. doi: 10.3934/dcds.2017025

2018 Impact Factor: 0.879

## Metrics

• HTML views (0)
• Cited by (1)

## Other articlesby authors

• on AIMS
• on Google Scholar