Efficient generation of odd order de Bruijn sequence with the same complement and reverse sequences
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866929449329491968 |
|---|---|
| author | Chang, Zuling Wang, Qiang |
| author_facet | Chang, Zuling Wang, Qiang |
| contents | Experimental results show that, when the order $n$ is odd, there are de Bruijn sequences such that the corresponding complement sequence and the reverse sequence are the same. In this paper, we propose one efficient method to generate such de Bruijn sequences. This solves an open problem asked by Fredricksen forty years ago for showing the existence of such de Bruijn sequences when the odd order $n >1$. Moreover, we refine a characterization of de Bruijn sequences with the same complement and reverse sequences and study the number of these de Bruijn sequences, as well as the distribution of de Bruijn sequences of the maximum linear complexity. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_01794 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Efficient generation of odd order de Bruijn sequence with the same complement and reverse sequences Chang, Zuling Wang, Qiang Information Theory Combinatorics 94A55 Experimental results show that, when the order $n$ is odd, there are de Bruijn sequences such that the corresponding complement sequence and the reverse sequence are the same. In this paper, we propose one efficient method to generate such de Bruijn sequences. This solves an open problem asked by Fredricksen forty years ago for showing the existence of such de Bruijn sequences when the odd order $n >1$. Moreover, we refine a characterization of de Bruijn sequences with the same complement and reverse sequences and study the number of these de Bruijn sequences, as well as the distribution of de Bruijn sequences of the maximum linear complexity. |
| title | Efficient generation of odd order de Bruijn sequence with the same complement and reverse sequences |
| topic | Information Theory Combinatorics 94A55 |
| url | https://arxiv.org/abs/2408.01794 |