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 Runlength 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 shiftrules 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 fixedweight binary strings are special cases of strings with fixedcontent, or multiset permutations: For permutations the content is $\{1,2,\ldots, n\}$, and for binary strings with fixedweight the content consists of $w$ 1s and $nw$ 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) fixedweight 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 coollex order.
LFSRs based on primitive polynomials
A wellknown 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_{n1}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 (msequences) having length $2^n1$ 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 msequence $$0000101011101100011111001101001$$ of length $2^51=31$ when outputting the value $a_1$ before each application of the LFSR. By prepending a 0 to the beginning of this msequence we obtain a DB sequence.
The number of primitive polynomials of degree $n$ is given by sequence A011260 in the OnLine 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.