A surprisingly simple de Bruijn sequence construction

Joe Sawada, Aaron Williams, Dennis Wong

Research output: Contribution to journalArticlepeer-review

36 Citations (Scopus)

Abstract

Pick any length n binary string b1b2bn and remove the first bit b1. If b2b3bn1 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.

Original languageEnglish
Pages (from-to)127-131
Number of pages5
JournalDiscrete Mathematics
Volume339
Issue number1
DOIs
Publication statusPublished - 6 Jan 2016
Externally publishedYes

Keywords

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

Fingerprint

Dive into the research topics of 'A surprisingly simple de Bruijn sequence construction'. Together they form a unique fingerprint.

Cite this