Dual-Step Optimization for Binary Sequences with High Merit Factors
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866918034505990144 |
|---|---|
| author | Pšeničnik, Blaž Mlinarič, Rene Brest, Janez Bošković, Borko |
| author_facet | Pšeničnik, Blaž Mlinarič, Rene Brest, Janez Bošković, Borko |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_07222 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Dual-Step Optimization for Binary Sequences with High Merit Factors Pšeničnik, Blaž Mlinarič, Rene Brest, Janez Bošković, Borko Data Structures and Algorithms 68T20 I.2.8; G.1.6 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. |
| title | Dual-Step Optimization for Binary Sequences with High Merit Factors |
| topic | Data Structures and Algorithms 68T20 I.2.8; G.1.6 |
| url | https://arxiv.org/abs/2409.07222 |