On the complexities of de-Bruijn sequences

DOI10.1016/0097-3165(82)90038-3zbMath0506.05005OpenAlexW2018332397MaRDI QIDQ1836666

Agnes Hui Chan, Richard A. Games, Edwin L. Key

Publication date: 1982

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0097-3165(82)90038-3

zbMATH Keywords

binary de- Bruijn sequencedistribution of the complexitiesshortest linear recursion

Mathematics Subject Classification ID

Enumerative combinatorics (05A99) Sequences and sets (11B99)

Related Items (28)

On evaluating the linear complexity of a sequence of least period \(2^ n\) ⋮ Roulette games and depths of words over finite commutative rings ⋮ Perfect factors in the de Bruijn graph ⋮ Cryptographically Strong de Bruijn Sequences with Large Periods ⋮ Further results on correlation functions of de Bruijn sequences ⋮ On ideal \(t\)-tuple distribution of orthogonal functions in filtering de Bruijn generators ⋮ The combinatorics of binary arrays ⋮ Characterising the linear complexity of span 1 de Bruijn sequences over finite fields. ⋮ A new upper bound on the order of affine sub-families of NFSRs ⋮ A generalization of de Bruijn graphs and classification of endomorphisms of Cuntz algebras by graph invariants ⋮ Graphs with the unique path property: Structure, cycles, factors, and constructions ⋮ Construction of de Bruijn sequences from product of two irreducible polynomials ⋮ Preliminary results on the minimal polynomial of modified de Bruijn sequences ⋮ Spans of preference functions for de Bruijn sequences ⋮ On ideal \(t\)-tuple distribution of filtering de Bruijn sequence generators ⋮ Minimal polynomials of the modified de Bruijn sequences ⋮ Asymptotically-tight bounds on the number of cycles in generalized de Bruijn-Good graphs ⋮ A recursive construction of nonbinary de Bruijn sequences ⋮ Randomness and Representation of Span n Sequences ⋮ Characterizations of generators for modified de Bruijn sequences ⋮ On the \(k\)-error linear complexities of De Bruijn sequences ⋮ Clues to the hidden nature of de Bruijn sequences ⋮ On the minimum linear complexity of de Bruijn sequences over non-prime finite fields ⋮ Longest subsequences shared by two de Bruijn sequences ⋮ There are no de Bruijn sequences of span \(n\) with complexity \(2^{n- 1}+n+1\) ⋮ Minimal Polynomials of the Modified de Bruijn Sequences ⋮ On the distribution of de Bruijn sequences of low complexity ⋮ Weight class distributions of de Bruijn sequences

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Generation of some de Bruijn sequences
• On the cycle structure of some nonlinear shift register sequences
• On the Complexity of Finite Sequences
• An analysis of the structure and complexity of nonlinear binary sequence generators
• Shift-register synthesis and BCH decoding
• On a Homomorphism of the de Bruijn Graph and its Applications to the Design of Feedback Shift Registers
• The definition of random sequences
• Normal Recurring Decimals

This page was built for publication: On the complexities of de-Bruijn sequences