American Institute of Mathematical Sciences

Advanced
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

Nam Yul Yu 1,

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.
Keywords: Levenshtein bound, Welch bound., binary sequences, Aperiodic correlation.
Mathematics Subject Classification: Primary: 94A55, 94A05; Secondary: 94B6.
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.  Google Scholar

[2]

R. M. Gray, Toeplitz and Circulant Matrices: A Review, Now Publishers Inc., 2006. Google Scholar

[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.  Google Scholar

[4]

S. Litsyn, Peak Power Control in Multicarrier Commmunications, Cambridge Univ. Press, 2007. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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. Google Scholar

[10]

L. R. Welch, Lower bounds on the maximum cross correlation of signals, IEEE Trans. Inform. Theory, IT-20 (1974), 397-399. Google Scholar

show all references

References:
[1]

E. Chu, Discrete and Continuous Fourier Transforms: Analysis, Applications and Fast Algorithms, Chapman & Hall/CRC, 2008.  Google Scholar

[2]

R. M. Gray, Toeplitz and Circulant Matrices: A Review, Now Publishers Inc., 2006. Google Scholar

[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.  Google Scholar

[4]

S. Litsyn, Peak Power Control in Multicarrier Commmunications, Cambridge Univ. Press, 2007. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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. Google Scholar

[10]

L. R. Welch, Lower bounds on the maximum cross correlation of signals, IEEE Trans. Inform. Theory, IT-20 (1974), 397-399. Google Scholar

[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]

Mohammed Mesk, Ali Moussaoui. On an upper bound for the spreading speed. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021210
[8]

Mariusz Lemańczyk, Clemens Müllner. Automatic sequences are orthogonal to aperiodic multiplicative functions. Discrete & Continuous Dynamical Systems, 2020, 40 (12) : 6877-6918. doi: 10.3934/dcds.2020260
[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 & 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 & 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 & 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 & Continuous Dynamical Systems, 2019, 39 (11) : 6761-6784. doi: 10.3934/dcds.2019294
[20]

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

2020 Impact Factor: 0.935

Tools

Metrics

  • PDF downloads (93)
  • HTML views (0)
  • Cited by (1)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy