Improvement of Long Binary Sequence Merit Factors using Modified Legendre Algorithms

Print
International Journal of Computer Applications
© 2015 by IJCA Journal
Volume 116 - Number 2
Year of Publication: 2015
Authors:
B. Suribabu Naick
P. Rajesh Kumar
10.5120/20308-2351

Suribabu B Naick and Rajesh P Kumar. Article: Improvement of Long Binary Sequence Merit Factors using Modified Legendre Algorithms. International Journal of Computer Applications 116(2):11-18, April 2015. Full text available. BibTeX

@article{key:article,
	author = {B. Suribabu Naick and P. Rajesh Kumar},
	title = {Article: Improvement of Long Binary Sequence Merit Factors using Modified Legendre Algorithms},
	journal = {International Journal of Computer Applications},
	year = {2015},
	volume = {116},
	number = {2},
	pages = {11-18},
	month = {April},
	note = {Full text available}
}

Abstract

Low autocorrelation binary sequence (LABS) detection is a classic problem in the literature. We use these sequences in many real-life applications. The detection of these sequences involves many problems. In the literature, various methods have been developed to approach the LABS issue. Based on the length of the sequence, an appropriate method can be selected and implemented. For short length sequences, linear search is possible and as the length increases we can implement various stochastic optimization algorithms. In our case that is for long binary sequences, we can use construction methods. Kristiansen and Parker [1] in their work have shown that Legendre sequences with periodic rotation can achieve a merit factor of 6. 34. We have applied these Legendre sequences to steepest descent and prime step algorithms with some modifications. We call these techniques as modified Legendre algorithms. Using these improved methods we were able to achieve a merit factor of 6. 4245 for long binary sequences.

References

  • R. A Kristiansen and M. G. Parker," Binary Sequences With merit factor ? 6. 3",IEEE Trans. Theory,vol. 50,no,12,pp,3385-3389,Dec. 2004.
  • M. J. E. Golay, "The merit factor of Legendre sequences,"IEEE Trans. Inf. Theory, vol. IT-29, no. 6, pp. 934–936, Nov. 1983.
  • A. Kirilusha and G. Narayanaswamy, "Construction of New Asymptotic Classes of Binary Sequences based on Existing Asymptotic Classes," Tech. Rep. Dept. Math. Comput. Sci. , Univ. of Richmond, Richmond, VA, 1999.
  • M. J. E. Golay, The merit factor of long low autocorrelation binary sequences. ,IEEE Transactions on Information Theory 28 (3) (1982) 543–549.
  • S. Mertens, Exhaustive search for low-autocorrelation binary sequences, Journal of Physics A: Mathematical and General 29 (1996) 473–481.
  • S. Mertens, H. Bauke,Ground statesof the Bernasconi model with open boundary conditions, website available at http://www-e. uni-agdeburg. de/mertens/research/labs/open. dat (accessed January2007).
  • S. Prestwich, A hybrid local search for low autocorrelation binary sequences,Technical Report TR-00-01, Department of Computer science,National University of Ireland, Cork, Ireland (2000).
  • P. Borwein, K. -K. S. Choi, and J. Jedwab, "Binary sequences with merit factor greater than 6. 34," IEEE Trans. Inf. Theory, vol. 50, no. 12, pp. 3234–3249, Dec. 2004.
  • R. N. Brace well, "The Fourier Transform and its Applications", 2nd edition. New York: McGraw-Hill, 1986.
  • J. E. Gallardo, C. Cotta, and A. J. Fernandez, "Finding low autocorrelation binary sequences with Memetic algorithms,"Appl. Soft Computer. ,vol. 9, no. 4, pp. 1252–1262, 2009
  • J. Jedwab and K. -U. Schmidt, "Appended -Sequences with Merit Factor Greater than 3. 34", 2010, submitted for publication
  • J. Jedwab, "A Survey of the Merit Factor Problem for Binary Sequences," Tech. Rep. Dept. Mathematics, Simon Fraser University, Burnaby, BC, Canada, 2004.
  • M. Golay, "A class of finite binary sequences with alternate auto-correlation values equal to zero (corresp. )," IEEE Trans. Inf. Theory, vol. IT-18, no. 3, pp. 449–450, May 1972.
  • J. M. Jensen, H. E. Jensen, and T. Høholdt, "The merit factor of binary sequences related to difference sets," IEEE Trans. Inf. Theory, vol. 37,no. 3, pp. 617–626, May 1991.
  • T. Hoholdt and H. E. Jensen, "Determination of the merit factor of Legendre sequences," IEEE Trans. Inf. Theory, vol. 34, no. 1, pp. 161–164, Jan. 1988.
  • John Michael Baden, "Efficient Optimization of the Merit Factor of Long Binary Sequences", IEEE transactions on information theory, vol. 57, no. 12, December 2011.