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

Nam Yul Yu

doi:10.3934/amc.2014.8.209

Article Contents

2014, Volume 8, Issue 2: 209-222. Doi: 10.3934/amc.2014.8.209

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

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

Received: July 31, 2013

Revised: December 31, 2013

Published: April 2014

Abstract Related Papers Cited by

Abstract

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:

Mathematics Subject Classification: Primary: 94A55, 94A05; Secondary: 94B65.

Citation:

Related Papers

Cited by

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.