Main content

Constructing de Bruijn sequences by concatenating cycles of feedback shift registers

Show full item record

Title: Constructing de Bruijn sequences by concatenating cycles of feedback shift registers
Author: Gabric, Daniel
Department: School of Computer Science
Program: Computer Science
Advisor: Sawada, Joseph
Abstract: A universal cycle for a set $\mathbf{S}$ of strings is a circular sequence of length $|\mathbf{S}|$ that contains every element of $\mathbf{S}$ as a substring exactly once. In this thesis we introduce sufficient conditions for when an ordering of universal cycles for disjoint sets can be concatenated to obtain a universal cycle for the union of those sets. A $k$-ary de Bruijn sequence of order $n$ is a universal cycle where $\mathbf{S}$ is the set of all $k$-ary strings of length $n$. De Bruijn sequences can be constructed a variety of different ways, but we will focus on constructing de Bruijn sequences by concatenating universal cycles. We use our conditions to prove the validity of three new de Bruijn sequences, two of which are based on concatenating co-necklaces, and one is based on concatenating necklaces. Then we introduce a class of new $k$-ary de Bruijn sequence that are based on concatenating cycles of feedback shift registers. Finally, we show that a brute force algorithm can generate the class of de Bruijn sequences in $O(k^2n^2)$-amortized time per universal cycle.
URI: http://hdl.handle.net/10214/14185
Date: 2018-08
Terms of Use: All items in the Atrium are protected by copyright with all rights reserved unless otherwise indicated.


Files in this item

Files Size Format View
Gabric_Daniel_201809_Msc.pdf 199.4Kb PDF View/Open

This item appears in the following Collection(s)

Show full item record