Construction of de Bruijn sequences from product of two irreducible polynomials
We study a class of Linear Feedback Shift Registers (LFSRs) with characteristic polynomial f(x) = p(x)q(x) where p(x) and q(x) are distinct irreducible polynomials in F2[x]. Important properties of the LFSRs, such as the cycle structure and the adjacency graph, are derived. A method to determine a s...
Saved in:
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
2017
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/83380 http://hdl.handle.net/10220/43538 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Nanyang Technological University |
| Language: | English |
| Summary: | We study a class of Linear Feedback Shift Registers (LFSRs) with characteristic polynomial f(x) = p(x)q(x) where p(x) and q(x) are distinct irreducible polynomials in F2[x]. Important properties of the LFSRs, such as the cycle structure and the adjacency graph, are derived. A method to determine a state belonging to each cycle and a generic algorithm to find all conjugate pairs shared by any pair of cycles are given. The process explicitly determines the edges and their labels in the adjacency graph. The results are then combined with the cycle joining method to efficiently construct a new class of de Bruijn sequences. An estimate of the number of resulting sequences is given. In some cases, using cyclotomic numbers, we can determine the number exactly. |
|---|