Abstract
De Bruijn sequences are maximum-length sequences generated by feedback shift registers. The study of their feedback functions is very important and has attracted a lot of attention. Many necessary conditions are proposed so far. In this manuscript, based on the complementary and converse properties of de Bruijn sequences, and on some special cross-join pairs in de Bruijn sequences, we give several properties about the proportions of linear part and second-highest degree part of de Bruijn sequence feedback functions. We prove that at least 34 proportion de Bruijn sequence feedback functions of order n have their second-highest degree n-2. We also exhaust all possible Boolean functions and discover all feedback functions of order 6 de Bruijn sequences and feedback functions with second-highest degree 2, of order 7, 8 and 9 de Bruijn sequences. Then we statistically analyze these functions according to their linear parts, second-highest degrees and number of terms. The result shows that their distribution according to degree n-2 parts is almost uniform. But the distribution according to linear parts has significant bias, which means that certain kinds of feedback functions are more likely to generate de Bruijn sequences.
| Original language | English |
|---|---|
| Pages (from-to) | 121-138 |
| Number of pages | 18 |
| Journal | Cryptography and Communications |
| Volume | 17 |
| Issue number | 1 |
| DOIs | |
| State | Published - Jan 2025 |
Keywords
- de Bruijn sequence
- Distribution
- Feedback function
- Linear part
- Second-highest degree
Fingerprint
Dive into the research topics of 'Distribution of linear and second-highest degree parts of maximum-length feedback functions'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver