# Linear feedback shift register

Generating pseudorandom signals with shift register and XNOR gate.
Linear feedback shift register (LSFR) is a ring counter that computes the new value for the lowest digit from the current values, combining them with XOR gate[1]. This device is still a counter: every value ever emitted appears only once through the whole loop of the changing values. Depending on the circuits, it can be a maximum-length counter (passing through the most of possible combinations, apart the stall states) or only go through some more limited set of possible values. The LSFR counter is very fast as only minimal logics is involved[2]

LSFR can also be used as a random number generator. The generated signal that can be picked at any digit of the register, is not fully random (pseudorandom), still reasonably chaotic. The number of possible states (hence the randomness of the signal) would likely increase when increasing the number of bits in the register.

## XOR versus XNOR

The "theoretically correct" LSFR should use XOR gate, however such device may stall the generator in "all zeros" state. Using XNOR (XOR with inverted output) makes the opposite "all ones" state illegal (stall state), however it is often easier to reset the register to the "all zeros" state on startup. While XNOR-based device is not strictly a LSFR, in practice it behaves largely the same way as a XOR based device.

## Rules of construction

Register bits from where the signal is picked for the generating the next value for the lowest bit are called taps. The pictured diagram has two taps, the bit 3 and the highest bit 4 (the device may also work with different taps).

The LFSR is only a maximum-length if the number of taps is even. Just 2 or 4 taps can suffice even for very long sequences. To produce a maximum length counter, the set of taps — taken all together, not pairwise (i.e. as pairs of elements) — must be relatively prime (there must be no common divisor to all taps). There can several ways of connecting taps to produce a maximum-length LSFR.

Device that only modifies the currently lowest bit (computing it from the tap outputs) is also called a Fibonacci LFSR. If some logic is also inserted to compute values for the intermediate bits (rather than inheriting these values from the lower bit as in usual shift operation), the device is a Galois LFSR.

## References

1. 1 homepage.mac.com Linear Feedback Shift Registers
2. 2 www.yikes.com Linear Feedback Shift Registers