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

Previous Article
A reduction point algorithm for cocompact Fuchsian groups and applications
AMC Home
This Issue
Next Article
Partitions of Frobenius rings induced by the homogeneous weight

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

Abstract
Related Papers

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

Tools

Metrics

Other articles
by authors

on AIMS
Nam Yul Yu
on Google Scholar
Nam Yul Yu

[Back to Top]