An efficiently generated family of binary de Bruijn sequences

An efficiently generated family of binary de Bruijn sequences

We study how to generate binary de Bruijn sequences efficiently from the class of simple linear feedback shift registers with feedback function f (x0,x1, ...xn-1) = x0 +x1 +xn-1 for n >_ 3, using the cycle joining method. Based on the properties of this class of LFSRs, we propose two new generic...

Full description

Saved in:
Bibliographic Details
Main Authors: Zhu, Yunlong, Chang, Zuling, Ezerman, Martianus Frederic, Wang, Qiang
Other Authors: School of Physical and Mathematical Sciences
Format: Article
Language:English
Published: 2021
Subjects:
Science::Mathematics
Binary Periodic Sequence
de Bruijn Sequence
Online Access:https://hdl.handle.net/10356/146961
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Nanyang Technological University
Language: English
Description
Summary:We study how to generate binary de Bruijn sequences efficiently from the class of simple linear feedback shift registers with feedback function f (x0,x1, ...xn-1) = x0 +x1 +xn-1 for n >_ 3, using the cycle joining method. Based on the properties of this class of LFSRs, we propose two new generic successor rules, each of which produces at least 2n-3 de Bruijn sequences. These two classes build upon a framework proposed by Gabric, Sawada,Williams andWong in Discrete Mathematics vol. 341, no. 11, pp. 2977–2987, November 2018. Here we introduce new useful choices for the uniquely determined state in each cycle to devise valid successor rules. In each class, the next bit costs O(n) time and O(n) space for a fixed n.

Similar Items