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

[10]

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

[10]

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

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

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

[6]

Mikko Kaasalainen. Dynamical tomography of gravitationally bound systems. Inverse Problems & Imaging, 2008, 2 (4) : 527-546. doi: 10.3934/ipi.2008.2.527

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

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

[9]

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

[10]

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

[11]

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

[12]

John Fogarty. On Noether's bound for polynomial invariants of a finite group. Electronic Research Announcements, 2001, 7: 5-7.

[13]

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

[14]

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

[15]

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 - A, 2019, 39 (11) : 6761-6784. doi: 10.3934/dcds.2019294

[16]

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

[17]

Wei-Wen Hu. Integer-valued Alexis sequences with large zero correlation zone. Advances in Mathematics of Communications, 2017, 11 (3) : 445-452. doi: 10.3934/amc.2017037

[18]

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

[19]

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

[20]

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

2018 Impact Factor: 0.879

Metrics

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

Other articles
by authors

[Back to Top]