Computational Search of Long Skew-symmetric Binary Sequences with High Merit Factors
Abstract
In this paper, we present a computational search for best-known merit factors of longer binary sequences with an odd length. Finding low autocorrelation binary sequences with optimal or suboptimal merit factors is a very difficult optimization problem. An improved version of the heuristic algorithm is presented and tackled to search for aperiodic binary sequences with good autocorrelation properties. High-performance computations with the execution of our stochastic algorithm
to search skew-symmetric binary sequences with high merit factors. After experimental work, as results, we present new binary sequences with odd lengths between 201 and 303 that are skew-symmetric and have the merit factor F greater than 8.5. Moreover, an example of a binary sequence having F > 8 has been found for all odd lengths between 201 and 303. The longest binary sequence with F > 9 found to date is of length 255.
References
Baden, J. Efficient optimization of the merit factor of long binary sequences. IEEE Transactions on Information Theory 57, 12 (Dec 2011), 8084–8094.
Beenker, G., Claasen, T., and Hermens, P. Binary sequences with a maximally flat amplitude spectrum. Philips J. Res. 40 (1985), 289–304.
Bernasconi, J. Low autocorrelation binary sequences: statistical mechanics and configuration space analysis. J. Physsique 48 (April 1987), 559–567.
Borwein, P., Choi, K.-K., and Jedwab, J. Binary sequences with merit factor greater than 6.34. IEEE Transactions on Information Theory 50, 12 (Dec 2004), 3234–3249.
Borwein, P., Ferguson, R., and Knauer, J. The merit factor problem. London Mathematical Society Lecture Note Series 352 (2008), 52.
Boskovic, B., Brglez, F., and Brest, J. Low-Autocorrelation Binary Sequences: On Improved Merit Factors and Runtime Predictions to Achieve Them. Applied Soft Computing 56 (2017), 262–285.
Brest, J., and Boskovic, B. A heuristic algorithm for a low autocorrelation binary sequence problem with odd length and high merit factor. IEEE Access 6 (2018), 4127–4134.
Brest, J., and Boskovic, B. Low autocorrelation binary sequences: Best-known peak sidelobe level values. IEEE Access 9 (2021), 67713–67723.
Chen, Y., and Lin, R. Computationally efficient long binary sequence designs with low autocorrelation sidelobes. IEEE Transactions on Aerospace and Electronic Systems (2021).
deGroot C., D., W., and H., H. K. Low autocorrelation binary sequences: exact enumeration and optimization by evolutionary strategies. Optimization 23 (1992), 369–384.
Deng, X., and Fan, P. New binary sequences with good aperiodic autocorrelations obtained by evolutionary algorithm. IEEE Communications Letters 3, 10 (1999), 288–290.
Dimitrov, M. On the aperiodic autocorrelation of rotated binary sequences. IEEE Communications Letters 25, 5 (2020), 1427–1430.
Dimitrov, M. On the skew-symmetric binary sequences and the merit factor problem. arXiv preprint arXiv:2106.03377 (2021).
Dimitrov, M., Baitcheva, T., and Nikolov, N. Efficient generation of low autocorrelation binary sequences. IEEE Signal Processing Letters 27 (2020), 341–345.
Dimitrov, M., Baitcheva, T., and Nikolov, N. On the generation of long binary sequences with record-breaking psl values. IEEE Signal Processing Letters 27 (2020), 1904–1908.
Dimitrov, M., Baitcheva, T., and Nikolov, N. Hybrid constructions of binary sequences with low autocorrelation sidelobes. arXiv preprint arXiv:2104.10477 (2021).
Farnane, K., Minaoui, K., and Aboutajdine, D. Local search algorithm for low autocorrelation binary sequences. In 2018 4th International Conference on Optimization and Applications (ICOA) (2018), IEEE, pp. 1–5.
Ferguson, R., and Knauer, J. Optimization methods for binary sequences—the merit factor problem. In MITACS 6th Annual Conference (2005).
Gallardo, J. E., Cotta, C., and Fernandez, A. J. Finding low autocorrelation binary sequences with memetic algorithms. Appl. Soft Comput. 9, 4 (Sept. 2009), 1252–1262.
Golay, M. J. E. Sieves for low autocorrelation binary sequences. IEEE Transactions on Information Theory 23 (1977), 43–51.
Golay, M. J. E. The merit factor of long low autocorrelation binary sequences. IEEE Transactions on Information Theory 28 (1982), 543–549.
Gunther, C. Flat Polynomials, Low Autocorrelation Sequences, and Difference Sets. PhD thesis, Universit¨at Paderborn, 2018.
Gunther, C., and Schmidt, K.-U. Merit factors of polynomials derived from difference sets. Journal of Combinatorial Theory, Series A 145, Supplement C (2017), 340–363.
Halim, S., Yap, R. H., and Halim, F. Engineering stochastic local search for the low autocorrelation binary sequence problem. In Proceedings of the 14th international conference on Principles and Practice of Constraint Programming (Berlin, Heidelberg, 2008), CP ’08, Springer-Verlag, pp. 640–645.
Jedwab, J., et al. A survey of the merit factor problem for binary sequences. In SETA (2004), Springer, pp. 30–55.
Jedwab, J., Katz, D. J., and Schmidt, K.-U. Advances in the merit factor problem for binary sequences. Journal of Combinatorial Theory, Series A 120, 4 (2013), 882–906.
Jedwab, J., Katz, D. J., and Schmidt, K.-U. Littlewood polynomials with small L4 norm. Advances in Mathematics 241, Supplement C (2013), 127–136.
Jedwab, J., and Yoshida, K. The peak sidelobe level of families of binary sequences. IEEE Transactions on Information Theory 52, 5 (2006), 2247–2254.
Jeon, H.-G., Lee, J.-Y., Han, Y., Joo Kim, S., and So Kweon, I. Fluttering pattern generation using modified legendre sequence for coded exposure imaging. In Proceedings of the IEEE International Conference on Computer Vision (2013), pp. 1001–1008.
Jeon, H.-G., Lee, J.-Y., Han, Y., Kim, S. J., and Kweon, I. S. Generating fluttering patterns with low autocorrelation for coded exposure imaging. International Journal of Computer Vision 123, 2 (2017), 269–286.
Katz, D. J., Lee, S., and Trunov, S. A. Crosscorrelation of Rudin–Shapiro-like polynomials. Applied and Computational Harmonic Analysis 48, 2 (2020), 513–538.
Leukhin, A., and Potekhin, E. A Bernasconi model for constructing ground-state spin systems and optimal binary sequences. Journal of Physics: Conference Series 613, 1 (2015), 012006.
Lin, R., Soltanalian, M., Tang, B., and Li, J. Efficient Design of Binary Sequences With Low Autocorrelation Sidelobes. IEEE Transactions on Signal Processing 67, 24 (2019), 6397–6410.
Mertens, S. Exhaustive search for lowautocorrelation binary sequences. Journal of Physics A: Mathematical and General 29 (1996), 473–481. https://wasd.urz.uni-magdeburg.de/mertens/research/labs/open.dat.
Militzer, B., Zamparelli, M., and Beule, D. Evolutionary search for low autocorrelated binary sequences. IEEE Transactions on Evolutionary Computation 2, 1 (April 1998), 34–39.
Packebusch, T., and Mertens, S. Low autocorrelation binary sequences. Journal of Physics A: Mathematical and Theoretical 49, 16 (2016), 165001.
Prestwich, S. D. Improved branch-and-bound for low autocorrelation binary sequences. CoRR abs/1305.6187 (2013).
Reinholz, A. Ein paralleler genetischer algorithms zur optimierung der binaren autokorrelationsfunktion, Diplom thesis, Universit¨at Bonn, 1993.
SLING. SLING – Slovenian Initiative for National Grid. http://www.sling.si/, October 2020.
Song, J., Babu, P., and Palomar, D. P. Optimization methods for designing sequences with low autocorrelation sidelobes. IEEE Transactions on Signal Processing 63, 15 (2015), 3998–4009.
Tarnu, D. On the maximal autocorrelation of Rudin-Shapiro sequences. arXiv preprint arXiv:2202.05897 (2022).
Tomassini, M. Complex networks analysis of the energy landscape of the low autocorrelation binary sequences problem. Physica A: Statistical Mechanics and its Applications 577 (2021), 126089.
Ukil, A. On asymptotic merit factor of low autocorrelation binary sequences. In IECON 2015 – 41st Annual Conference of the IEEE Industrial Electronics Society (2015), IEEE, pp. 004738–004741.
Velazquez-Gutierrez, J. M., and Vargas-Rosales, C. Sequence sets in wireless communication systems: A survey. IEEE Communications Surveys Tutorials 19, 2 (2017), 1225–1248.
Zeng, F., He, X., Zhang, Z., Xuan, G., Peng, Y., and Yan, L. Optimal and Z-optimal type-II odd-length binary Z-complementary pairs. IEEE Communications Letters 24, 6 (2020), 1163–1167.
Zhao, L., Song, J., Babu, P., and Palomar, D. P. A unified framework for low autocorrelation sequence design via majorization–minimization. IEEE Transactions on Signal Processing 65, 2 (2017), 438–453.
Zufan, P., and Bidlo, M. Advances in evolutionary optimization of quantum operators. MENDEL 27, 2 (2021), 12–22.
Zurek, D., Pietak, K., Pietron, M., and Kisiel-Dorohinicki, M. Toward hybrid platform for evolutionary computations of hard discrete problems. Procedia Computer Science 108 (2017), 877–886.
Copyright (c) 2022 MENDEL
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
MENDEL open access articles are normally published under a Creative Commons Attribution-NonCommercial-ShareAlike (CC BY-NC-SA 4.0) https://creativecommons.org/licenses/by-nc-sa/4.0/ . Under the CC BY-NC-SA 4.0 license permitted 3rd party reuse is only applicable for non-commercial purposes. Articles posted under the CC BY-NC-SA 4.0 license allow users to share, copy, and redistribute the material in any medium of format, and adapt, remix, transform, and build upon the material for any purpose. Reusing under the CC BY-NC-SA 4.0 license requires that appropriate attribution to the source of the material must be included along with a link to the license, with any changes made to the original material indicated.
