Construction of de Bruijn sequences from product of two irreducible polynomials

Zuling Chang, Martianus Frederic Ezerman, San Ling, Huaxiong Wang

TL;DR

This paper introduces a novel method for constructing de Bruijn sequences by combining two distinct irreducible polynomials. This approach generalizes existing methods and leads to a significantly larger number of unique de Bruijn sequences, with potential applications in areas like coding theory and cryptography.

What Problem Does This Paper Address?

De Bruijn sequences are fascinating binary sequences where every possible n-bit subsequence appears exactly once within a single period. They have numerous applications due to their desirable properties like long periods and high linear complexity. While various construction methods exist, they often rely on specific types of polynomials (e.g., primitive polynomials) or yield a limited number of sequences. This paper aims to broaden the scope of construction by using the product of two distinct irreducible polynomials as the characteristic polynomial for Linear Feedback Shift Registers (LFSRs), thereby generating a more diverse and abundant set of de Bruijn sequences.

Methods

The core of this work lies in understanding the cycle structure and adjacency graph of LFSRs whose characteristic polynomials are products of two distinct irreducible polynomials, $f(x) = p(x)q(x)$. The authors leverage the "cycle joining" (CJ) method, a standard technique for constructing de Bruijn sequences from FSRs.

Key methodological contributions include:

  • Cycle Structure Analysis: Detailed analysis of the cycle structure of $\Omega(f(x))$, which is the set of all sequences generated by an LFSR with characteristic polynomial $f(x)$.
  • Adjacency Graph Construction: Defining and analyzing the adjacency graph of these cycles, where vertices represent cycles and edges represent shared conjugate pairs.
  • Conjugate Pair Determination: Developing algorithms to find conjugate pairs between cycles, which is crucial for the CJ method. This involves intricate calculations related to cyclotomic numbers.
  • Generalization of CJ Method: Adapting the CJ method to the more complex cycle structures arising from the product of two irreducible polynomials.

The paper also introduces a matrix-based approach for representing states and finding conjugate pairs, which simplifies the computational process.

Datasets

Not discussed in the paper. The paper focuses on theoretical constructions and algorithmic development rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Power of Irreducible Polynomials: Using the product of two distinct irreducible polynomials as the characteristic polynomial opens up a much larger space for constructing de Bruijn sequences compared to methods relying solely on primitive polynomials.
  • Cyclotomic Numbers as Key: The paper highlights the critical role of cyclotomic numbers in characterizing the relationships between cycles and determining the number of conjugate pairs, which directly impacts the number of constructible de Bruijn sequences.
  • Algorithmic Elegance: The development of algorithms for finding conjugate pairs and constructing the adjacency graph provides a systematic way to navigate the complex cycle structures.
  • Generalizability: The methods presented are shown to be extendable to characteristic polynomials that are products of more than two irreducible polynomials, suggesting a broad applicability.

Key Results

  • Construction of New de Bruijn Sequences: The paper successfully constructs a new class of de Bruijn sequences based on the product of two distinct irreducible polynomials.
  • Quantitative Estimates: The authors provide estimates for the number of de Bruijn sequences that can be constructed, and in some special cases, they determine this number exactly. For instance, in one example, their method constructs approximately $2^{60.797}$ de Bruijn sequences.
  • Algorithmic Efficiency: The proposed algorithms for finding conjugate pairs are more efficient than exhaustive search methods, reducing the computational complexity.
  • Theoretical Framework: The paper establishes a solid theoretical framework for understanding the cycle structure and adjacency graph of LFSRs with such characteristic polynomials.

Limitations and Future Work

  • Computational Complexity: While more efficient than brute-force, the algorithms for finding conjugate pairs can still be computationally intensive for very large degrees of polynomials.
  • Generalization to More Factors: The paper mentions that the methods can be extended to products of s > 2 irreducible polynomials, but this is not fully explored in detail.
  • Applications: The paper suggests potential applications in spread spectrum and DNA analysis, but these are not deeply investigated. Future work could focus on exploring these applications and analyzing the correlation properties of the constructed sequences.
  • Exact Counting: While estimates are provided, finding exact counts for all cases remains a challenge, especially for more complex polynomial combinations.

Summary updated

BibTeX
@article{chang2018construction,
  author = {Zuling Chang and Martianus Frederic Ezerman and San Ling and Huaxiong Wang},
  title = {{Construction of de Bruijn sequences from product of two irreducible polynomials}},
  journal = {Cryptogr. Commun},
  year = {2018},
  doi = {10.1007/s12095-017-0219-8},
}
Figure