On binary de Bruijn sequences from LFSRs with arbitrary characteristic polynomials

DOI10.1007/S10623-018-0509-YMaRDI QIDQ2414937zbMATH OpenOpenAlexWikidataFDO

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

Publication date 17 May 2019

Published in Designs, Codes and Cryptography (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1611.10088

zbMATH Keywords

de Bruijn sequencecycle structureLFSRadjacency graphcyclotomic numberbinary periodic sequence

Mathematics Subject Classification ID

Cryptography (94A60) Shift register sequences and sequences over finite alphabets in information and communication theory (94A55) Sequences (mod (m)) (11B50)

Abstract: We propose a construction of de Bruijn sequences by the cycle joining method from linear feedback shift registers (LFSRs) with arbitrary characteristic polynomial $f(x)$. We study in detail the cycle structure of the set $Omega(f(x))$ that contains all sequences produced by a specific LFSR on distinct inputs and provide a fast way to find a state of each cycle. This leads to an efficient algorithm to find all conjugate pairs between any two cycles, yielding the adjacency graph. The approach is practical to generate a large class of de Bruijn sequences up to order $napprox20$. Many previously proposed constructions of de Bruijn sequences are shown to be special cases of our construction.

Recommendations

• Construction of de Bruijn sequences from product of two irreducible polynomials
• An efficiently generated family of binary de Bruijn sequences
• Constructions of de Bruijn sequences from a full-length shift register and an irreducible LFSR
• The adjacency graphs of FSRs with a class of affine characteristic functions
• An interleaved method for constructing de Bruijn sequences

Cites work

• scientific article; zbMATH DE number 1099195 (Why is no real title available?)
• scientific article; zbMATH DE number 1122449 (Why is no real title available?)
• scientific article; zbMATH DE number 6900646 (Why is no real title available?)
• scientific article; zbMATH DE number 954401 (Why is no real title available?)
• scientific article; zbMATH DE number 967590 (Why is no real title available?)
• scientific article; zbMATH DE number 2238187 (Why is no real title available?)
• scientific article; zbMATH DE number 3068971 (Why is no real title available?)
• scientific article; zbMATH DE number 3095523 (Why is no real title available?)
• A Class of de Bruijn Sequences
• A Survey of Full Length Nonlinear Shift Register Cycle Algorithms
• A class of nonlinear de Bruijn cycles
• A proof of Golomb's conjecture for the de Bruijn graph
• A relationship between linear complexity and k-error linear complexity
• Adjacencies Between the Cycles of a Shift Register with Characteristic Polynomial (1 + x)ⁿ
• Algorithms for the generation of full-length shift- register sequences
• Construction of de Bruijn Sequences From LFSRs With Reducible Characteristic Polynomials
• Construction of de Bruijn sequences from product of two irreducible polynomials
• De Bruijn Sequences-A Model Example of the Interaction of Discrete Mathematics and Computer Science
• De Bruijn sequences, irreducible codes and cyclotomy
• On the classification of deBruijn sequences
• Shift Register Sequences – A Retrospective Account
• Simple and Robust Binary Self-Location Patterns
• The Adjacency Graphs of LFSRs With Primitive-Like Characteristic Polynomials
• The Properties of a Class of Linear FSRs and Their Applications to the Construction of Nonlinear FSRs
• The adjacency graphs of some feedback shift registers
• The art of computer programming. Volume 4A. Combinatorial algorithms. Part 1.
• The cycle structure of LFSR with arbitrary characteristic polynomial over finite fields

Cited in

(16)

• A recursive construction of nonbinary de Bruijn sequences
• The minimal polynomials of modified de Bruijn sequences revisited
• Constructions of de Bruijn sequences from a full-length shift register and an irreducible LFSR
• On greedy algorithms for binary de Bruijn sequences
• An efficiently generated family of binary de Bruijn sequences
• The adjacency matrix of some class of irreducible polynomials
• The adjacency graphs of FSRs with a class of affine characteristic functions
• On cross joining de Bruijn sequences
• Methods for constructing de Bruijn sequences
• Proof of a conjecture and a bound on the imbalance properties of LFSR subsequences
• Constructing de Bruijn sequences based on a new necessary condition
• Generalized cycle joining method and its application to the construction of long-period Galois NFSRs
• The adjacency graphs of some feedback shift registers
• Decoding a perturbed sequence generated by an LFSR
• Construction of de Bruijn sequences from product of two irreducible polynomials
• An interleaved method for constructing de Bruijn sequences

This page was built for publication: On binary de Bruijn sequences from LFSRs with arbitrary characteristic polynomials

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2414937)