On binary de Bruijn sequences from LFSRs with arbitrary characteristic polynomials

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 Ω ( f ( x ) ) that contains all sequences produced by a specific LFSR on disti...

Full description

Saved in:
Bibliographic Details
Published in:Designs, codes, and cryptography codes, and cryptography, 2019-05, Vol.87 (5), p.1137-1160
Main Authors: Chang, Zuling, Ezerman, Martianus Frederic, Ling, San, Wang, Huaxiong
Format: Article
Language:English
Subjects:
Algorithms
Circuits
Coding and Information Theory
Computer Science
Cryptology
Data Structures and Information Theory
Discrete Mathematics in Computer Science
Information and Communication
Linear feedback shift registers
Polynomials
Sequences
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 Ω ( 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 n ≈ 20 . Many previously proposed constructions of de Bruijn sequences are shown to be special cases of our construction.
ISSN:0925-1022
1573-7586
DOI:10.1007/s10623-018-0509-y