A shift register is a finite-state sequence generator that shifts the symbols in its state and appends a new symbol. In a feedback shift
register, the appended symbol is determined by a feedback function
of the current state. For a finite alphabet 
and a state of length 
, the update is
 |
(1)
|
where 
.
Every trajectory is eventually periodic because
the state space is finite (Wolfram 2002, pp. 974 and 1088).
A binary linear feedback shift register uses the finite field GF(2) and a feedback function of the form
 |
(2)
|
where the coefficients 
belong to GF(2) and addition is modulo 2. A nonlinear feedback
shift register instead uses a nonlinear Boolean function.
The binary linear update fixes the all-zero state, so a cycle of nonzero states has length at most 
. With the left-shift convention above, its characteristic
polynomial is
 |
(3)
|
If 
is a primitive
polynomial over GF(2), then all 
nonzero states form a single cycle
(Wolfram 2002, p. 974). For example, the rule 
has characteristic
polynomial 
and produces the seven-state cycle
 |
(4)
|
Suitable nonlinear feedback can generate a binary de Bruijn sequence, whose cycle includes all 
states, in contrast to the 
nonzero states of a maximal binary linear register (Wolfram
2002, p. 1088).
