De Bruijn Sequence and Universal Cycle Constructions
| Linear Feedback Shift Registers | Output | ||||||
|
Let $\alpha = a_1a_2\cdots a_n$ denote a length $n$ string over the alphabet $\Sigma$. A feedback shift register (FSR) is a function $F(\alpha) = a_2\cdots a_n f(\alpha),$ where $f$ is a feedback function that maps length $n$ strings to $\Sigma$. When $\Sigma = \{0,1\}$, the following are among the simplest feedback functions where $\oplus$ denotes addition mod 2:
- Pure Cycling Register (PCR): $f(\alpha) = a_1$
- Complementing Cycling Register (CCR): $f(\alpha) = a_1 \oplus 1 = \overline{a_1}$
- Pure Summing Register (PSR): $f(\alpha) = a_1 \oplus a_2 \oplus \cdots \oplus a_n$
- Complementing Summing Register (CSR): $f(\alpha) = a_1 \oplus a_2 \oplus \cdots \oplus a_n \oplus 1 $
- Pure Run-length Register (PRR): $f(\alpha) = a_1 \oplus a_2 \oplus a_n$
The above feedback functions can be applied to derive a number of simple binary shift-rules to construct DB sequences. The PCR generalizes naturally to larger alphabets and can be applied to derive a number of simple $k$-ary shift rules to construct DB sequences along with a universal cycle for weak orders.
Permutations and fixed-weight binary strings are special cases of strings with fixed-content, or multiset permutations: For permutations the content is $\{1,2,\ldots, n\}$, and for binary strings with fixed-weight the content consists of $w$ 1s and $n-w$ 0s. If $\alpha z$ is a multiset permutation where $z$ is an element of the multiset, then $\alpha$ is said to be a shorthand multiset permutation with $z$ as the missing (redundant) symbol. The following feedback function generalizes the PSR/CSR for (shorthand) fixed-weight strings:
- Missing Symbol Register (MSR): $f(\alpha) = z$
The above feedback function can be applied to derive a universal cycle for shorthand multiset permutations based on cool-lex order.
LFSRs based on primitive polynomials
A well-known method for constructing DB sequences is to apply a linear feedback shift register for a specific $n$ based on a primitive polynomial of degree $n$. As discussed by Golomb [Gol17], a primitive polynomial of the form $$g(x) = c_0 + c_1x + c_2x^2 + \cdots + c_nx^n$$ over GF(2) corresponds to a linear feedback function of the form $$f(\alpha) = c_na_1 \oplus c_{n-1}a_2 \oplus \cdots \oplus c_1a_n$$ where the operator $\oplus$ denotes addition mod 2. LFSRs based on primitive polynomials generate maximal length sequences (m-sequences) having length $2^n-1$ that miss only the all 0 string.
The primitive polynomial $1 + x^2 + x^5$ over GF(2) corresponds to the feedback function $f(a_1a_2a_3a_4a_5) = a_1 + a_4$. If $a_1a_2a_3a_4a_5$ is initialized to $00001$, then the LFSR with this feedback function produces the m-sequence $$0000101011101100011111001101001$$ of length $2^5-1=31$ when outputting the value $a_1$ before each application of the LFSR. By prepending a 0 to the beginning of this m-sequence we obtain a DB sequence.
The number of primitive polynomials of degree $n$ is given by sequence A011260 in the On-Line Encyclopedia of Integer Sequences. For $n=1$ to $20$, the sequence is: $$1, 1, 2, 2, 6, 6, 18, 16, 48, 60, 176, 144, 630, 756, 1800, 2048,7710,7776, 27594, 24000$$ An algorithm to exhaustively list all primitive polynomials of degree $n$ based on the work in [CRS+00] is available for download.
- [CRS+00] K. Cattell, F. Ruskey, J. Sawada, M. Serra, and C. Miers. Fast algorithms to generate necklaces, unlabeled necklaces, and irreducible polynomials over GF(2). Journal of Algorithms, 37(2):267–282, 2000.
- [Gol17] S. W. Golomb. Shift Register Sequences (Third Edition). World Scientific, Singapore, 2017.