Call for Paper - November 2023 Edition
IJCA solicits original research papers for the November 2023 Edition. Last date of manuscript submission is October 20, 2023. Read More

Improvement of Long Binary Sequence Merit Factors using Modified Legendre Algorithms

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

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

	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}


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.


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