Construction of de Bruijn Sequences from Product of Two Irreducible Polynomials
This work addresses a specific problem in combinatorics and coding theory for researchers, offering incremental improvements in sequence construction methods.
The paper tackles constructing de Bruijn sequences by analyzing LFSRs with characteristic polynomials as products of two irreducible polynomials, deriving properties like cycle structure and adjacency graphs, and providing algorithms to efficiently generate a new class of sequences with estimated or exact counts.
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 $\F_2[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.