A recursive construction of nonbinary de Bruijn sequences

DOI10.1007/S10623-010-9423-7MaRDI QIDQ543426zbMATH OpenOpenAlexFDO

Authors Abbas M. Alhakim, Mufutau Akinwande

Publication date 17 June 2011

Published in Designs, Codes and Cryptography (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0812.4012

zbMATH Keywords

de Bruijn sequencegraph homomorphismLempel's \(D\)-morphismrecursive construction

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38) General topics of discrete mathematics in relation to computer science (68R01) Graph theory (including graph drawing) in computer science (68R10) Shift register sequences and sequences over finite alphabets in information and communication theory (94A55)

Abstract: This paper presents a method to find new De Bruijn cycles 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 connecting these cycles into one full cycle. We characterize homomorphisms between De Bruijn digraphs of different orders that allow this construction. These maps generalize the well-known D-morphism of Lempel between De Bruijn digraphs of consecutive orders. Also, an efficient recursive algorithm that yields an exponential number of nonbinary De Bruijn cycles is implemented.

Recommendations

• Stretching de Bruijn sequences
• A generalized recursive construction for de Bruijn sequences
• An interleaved method for constructing de Bruijn sequences
• On binary de Bruijn sequences from LFSRs with arbitrary characteristic polynomials
• A de Bruijn sequence construction by concatenating cycles of the complemented cycling register

Cites work

• An efficient implementation of the D-homomorphism for generation of de Bruijn sequences
• Construction of de Bruijn sequences of minimal complexity
• Feedback shift registers
• On a Homomorphism of the de Bruijn Graph and its Applications to the Design of Feedback Shift Registers
• On the complexities of de-Bruijn sequences
• Regular Sequences and Frequency Distributions

Cited in

(19)

• De Bruijn sequences and suffix arrays: analysis and constructions
• The adjacency graphs of FSRs with a class of affine characteristic functions
• A de Bruijn sequence construction by concatenating cycles of the complemented cycling register
• Preliminary results on the minimal polynomial of modified de Bruijn sequences
• On ideal t-tuple distribution of filtering de Bruijn sequence generators
• An interleaved method for constructing de Bruijn sequences
• A framework for constructing de Bruijn sequences via simple successor rules
• De Bruijn sequences with efficient decoding algorithms
• Construction for de Bruijn sequences with large stage
• Stretching de Bruijn sequences
• A generalized recursive construction for de Bruijn sequences
• Methods for constructing de Bruijn sequences
• De Bruijn Sequences and Perfect Factors
• scientific article; zbMATH DE number 1024022 (Why is no real title available?)
• Efficient design of compact unstructured RNA libraries covering all k-mers
• New orientable sequences
• De Bruijn sequences: from games to shift-rules to a proof of the Fredricksen-Kessler-Maiorana theorem
• Orientable and negative orientable sequences
• Orientable sequences over non-binary alphabets

This page was built for publication: A recursive construction of nonbinary de Bruijn sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q543426)