A surprisingly simple de Bruijn sequence construction

Joe Sawada; Aaron Williams; Dennis Wong

doi:10.1016/j.disc.2015.08.002

A surprisingly simple de Bruijn sequence construction

Joe Sawada
, Aaron Williams
, Dennis Wong

Research output: Contribution to journal › Article › peer-review

47 Citations (Scopus)

Abstract

Pick any length n binary string ^b1^b2⋯^bn and remove the first bit ^b1. If ^b2^b3⋯^bn1 is a necklace, then append the complement of ^b1 to the end of the remaining string; otherwise append ^b1. By repeating this process, eventually all 2ⁿ binary strings will be visited cyclically. This shift rule leads to a new de Bruijn sequence construction that can be generated in O(1)-amortized time per bit.

Original language	English
Pages (from-to)	127-131
Number of pages	5
Journal	Discrete Mathematics
Volume	339
Issue number	1
DOIs	https://doi.org/10.1016/j.disc.2015.08.002
Publication status	Published - 6 Jan 2016
Externally published	Yes

Keywords

CAT algorithm
De Bruijn sequence
Generate
Necklaces
Shift Gray code
Shift rule
Successor rule
Universal cycle

Access to Document

10.1016/j.disc.2015.08.002

Cite this

@article{2121d227cb5141648442cf06dc818404,

title = "A surprisingly simple de Bruijn sequence construction",

abstract = "Pick any length n binary string b1b2⋯bn and remove the first bit b1. If b2b3⋯bn1 is a necklace, then append the complement of b1 to the end of the remaining string; otherwise append b1. By repeating this process, eventually all 2n binary strings will be visited cyclically. This shift rule leads to a new de Bruijn sequence construction that can be generated in O(1)-amortized time per bit.",

keywords = "CAT algorithm, De Bruijn sequence, Generate, Necklaces, Shift Gray code, Shift rule, Successor rule, Universal cycle",

author = "Joe Sawada and Aaron Williams and Dennis Wong",

year = "2016",

month = jan,

day = "6",

doi = "10.1016/j.disc.2015.08.002",

language = "English",

volume = "339",

pages = "127--131",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier BV",

number = "1",

}

TY - JOUR

T1 - A surprisingly simple de Bruijn sequence construction

AU - Sawada, Joe

AU - Williams, Aaron

AU - Wong, Dennis

PY - 2016/1/6

Y1 - 2016/1/6

N2 - Pick any length n binary string b1b2⋯bn and remove the first bit b1. If b2b3⋯bn1 is a necklace, then append the complement of b1 to the end of the remaining string; otherwise append b1. By repeating this process, eventually all 2n binary strings will be visited cyclically. This shift rule leads to a new de Bruijn sequence construction that can be generated in O(1)-amortized time per bit.

AB - Pick any length n binary string b1b2⋯bn and remove the first bit b1. If b2b3⋯bn1 is a necklace, then append the complement of b1 to the end of the remaining string; otherwise append b1. By repeating this process, eventually all 2n binary strings will be visited cyclically. This shift rule leads to a new de Bruijn sequence construction that can be generated in O(1)-amortized time per bit.

KW - CAT algorithm

KW - De Bruijn sequence

KW - Generate

KW - Necklaces

KW - Shift Gray code

KW - Shift rule

KW - Successor rule

KW - Universal cycle

UR - https://www.scopus.com/pages/publications/84940399452

U2 - 10.1016/j.disc.2015.08.002

DO - 10.1016/j.disc.2015.08.002

M3 - Article

AN - SCOPUS:84940399452

SN - 0012-365X

VL - 339

SP - 127

EP - 131

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 1

ER -

A surprisingly simple de Bruijn sequence construction

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this