Search

The problem of finding aperiodic low auto-correlation binary sequences (LABS) presents a significant computational challenge, particularly as the sequence length increases. Such sequences have important applications in communication engineering, physics, chemistry, and cryptography. This paper introduces a novel dual-step algorithm for long binary sequences with high merit factors. The first step employs a parallel algorithm utilizing skew-symmetry and restriction classes to generate sequence candidates with merit factors above a predefined threshold. The second step uses a priority queue algorithm to refine these candidates further, searching the entire search space unrestrictedly. By combining GPU-based parallel computing and dual-step optimization, our approach has successfully identified new best-known binary sequences for all lengths ranging from 450 to 527, with the exception of length 518, where the previous best-known value was matched with a different sequence. This hybrid method significantly outperforms traditional exhaustive and stochastic search methods, offering an efficient solution for finding long sequences with good merit factors., Comment: 14 pages, 6 figures, 2 tables

A low-autocorrelation binary sequences problem with a high figure of merit factor represents a formidable computational challenge. An efficient parallel computing algorithm is required to reach the new best-known solutions for this problem. Therefore, we developed the $\mathit{sokol}_{\mathit{skew}}$ solver for the skew-symmetric search space. The developed solver takes the advantage of parallel computing on graphics processing units. The solver organized the search process as a sequence of parallel and contiguous self-avoiding walks and achieved a speedup factor of 387 compared with $\mathit{lssOrel}$, its predecessor. The $\mathit{sokol}_{\mathit{skew}}$ solver belongs to stochastic solvers and can not guarantee the optimality of solutions. To mitigate this problem, we established the predictive model of stopping conditions according to the small instances for which the optimal skew-symmetric solutions are known. With its help and 99% probability, the $\mathit{sokol}_{\mathit{skew}}$ solver found all the known and seven new best-known skew-symmetric sequences for odd instances from $L=121$ to $L=223$. For larger instances, the solver can not reach 99% probability within our limitations, but it still found several new best-known binary sequences. We also analyzed the trend of the best merit factor values, and it shows that as sequence size increases, the value of the merit factor also increases, and this trend is flatter for larger instances., Comment: 17 pages, 5 figures

The search for binary sequences with low peak sidelobe level value represents a formidable computational problem. To locate better sequences for this problem, we designed a stochastic algorithm that uses two fitness functions. In these fitness functions, the value of the autocorrelation function has a different impact on the final fitness value. It is defined with the value of the exponent over the autocorrelation function values. Each function is used in the corresponding optimization phase, and the optimization process switches between these two phases until the stopping condition is satisfied. The proposed algorithm was implemented using the compute unified device architecture and therefore allowed us to exploit the computational power of graphics processing units. This algorithm was tested on sequences with lengths $L = 2^m - 1$, for $14 \le m \le 20$. From the obtained results it is evident that the usage of two fitness functions improved the efficiency of the algorithm significantly, new-best known solutions were achieved, and the achieved PSL values were significantly less than $\sqrt{L}$., Comment: 8 pages, 4 figures, 5 tables

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., Comment: 8 pages, 2 figures, 1 algorithm, 1 table

The search for binary sequences with a high figure of merit, known as the low autocorrelation binary sequence ($labs$}) problem, represents a formidable computational challenge. To mitigate the computational constraints of the problem, we consider solvers that accept odd values of sequence length $L$ and return solutions for skew-symmetric binary sequences only -- with the consequence that not all best solutions under this constraint will be optimal for each $L$. In order to improve both, the search for best merit factor $and$ the asymptotic runtime performance, we instrumented three stochastic solvers, the first two are state-of-the-art solvers that rely on variants of memetic and tabu search ($lssMAts$ and $lssRRts$), the third solver ($lssOrel$) organizes the search as a sequence of independent contiguous self-avoiding walk segments. By adapting a rigorous statistical methodology to performance testing of all three combinatorial solvers, experiments show that the solver with the best asymptotic average-case performance, $lssOrel\_8 = 0.000032*1.1504^L$, has the best chance of finding solutions that improve, as $L$ increases, figures of merit reported to date. The same methodology can be applied to engineering new $labs$ solvers that may return merit factors even closer to the conjectured asymptotic value of 12.3248.