A recursive construction of nonbinary de Bruijn sequences

作者：Alhakim Abbas^*; Akinwande Mufutau

来源：Designs, Codes and Cryptography, 2011, 60(2): 155-169.

DOI：10.1007/s10623-010-9423-7

• De Bruijn sequence
• Recursive construction
• Graph homomorphism
• Lempel's D-morphism

This paper presents a method to find new de Bruijn sequences based on ones of lesser order. This is done by mapping a de Bruijn cycle to several vertex disjoint cycles in a de Bruijn digraph of higher order and then connecting these cycles into one full cycle. We present precise formulae for the locations where those cycles can be rejoined into one full cycle. We obtain an exponentially large class of distinct de Bruijn cycles. This method generalizes the Lempel construction of binary de Bruijn sequences as well as its efficient implementation by Annextein.

• 出版日期2011-8