A Heuristic Algorithm for a Low Autocorrelation Binary Sequence Problem With Odd Length and High Merit Factor

IEEE Access

Borko Boskovic¹  Janez Brest¹ 

[1] Faculty of Electrical Engineering and Computer Science, Institute of Computer Science, University of Maribor, Maribor, Slovenia;

关键词: Algorithm design and analysis;    combinatorial optimization;    heuristic algorithms;    aperiodic autocorrelation;    merit factor;    skew-symmetric sequences;   

DOI  :  10.1109/ACCESS.2018.2789916

来源: DOAJ

【 摘 要 】

A low autocorrelation binary sequence (LABS) problem is a hard combinatorial problem and its solutions are important in many practical applications. Till now, the largest best-known skew-symmetric sequence with merit factor greater than 9 had a length of 189. In this paper, a new heuristic algorithm is presented for the LABS problem. The proposed algorithm stores promising solutions and this mechanism enables the algorithm to perform local searches on these solutions in a systematic way. Our algorithm was tested on skew-symmetric sequences and the obtained results are compared with results of the state-of-the-art algorithms. The proposed algorithm was able to find some new best-known skew-symmetric solutions with merit factor greater than 9 in sequence lengths over 200. The obtained results improve the suggestion from 1985 (Beenker et al.) and 1987 (Bernasconi) greatly, where the merit factor is approximately equal to 6 for long skew-symmetric sequences with length up to 199. Now, the largest best-known skew-symmetric sequence with merit factor greater than 9 has the length 225. Additionally, now all merit factors are greater than 8.5 on the interval from 159 up to 225 for odd lengths.

【 授权许可】

Unknown