Linear Feedback Shift Registers  Output  

A wellknown 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_{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 number of primitive polynomials of degree $n$ is given by sequence A011260 in the OnLine 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.