De Bruijn Sequence and Universal Cycle Constructions

Linear Feedback Shift Registers Output
Order $n$
LFSR   (max 6)
LFSRs based on primitive polynomials

A well-known method for constructing DB sequences is by applying a linear feedback shift register for a specific $n$ based on a primitive polynomial of degree $n$. Let $\alpha = a_1a_2\cdots a_n$ be a binary string. 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$ binary strings to $\{0,1\}$. If $f$ is linear, than an FSR is said to be a linear feedback shift register (LFSR). As discussed by Golumb [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.

Example LFSR
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 25, the sequence is: $$1, 1, 2, 2, 6, 6, 18, 16, 48, 60, 176, 144, 630, 756, 1800, 2048, 7710, 7776, 27594, 24000, 84672, 120032, 356960, 276480, 1296000$$ An algorithm to exhaustively list all primitive polynomials of degree $n$ based on the work in [CRS+00] is available for download.

Download source code

» Primitive polynomial C program

References

  • [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.