Linear-feedback shift register

A four-bit Fibonacci-type LFSR

A linear-feedback shift register is a shift register which will produce a sequence of numbers. The next value of the sequence depends on the current value. The first value is usually called seed. Usually, the function XOR is used to link two consecutive values. Commonly, the function XOR is used on a bit-level. With n bits, it is possible to represent 2ⁿ numbers, so after 2ⁿ-1 values the sequence will repeat. In computing, linear-feedback shift registers are commonly used to compute pseudorandom numbers. There are two common types:

1. Fibonacci LFSR (after Fibonacci)
2. Galois LFST (after Evariste Galois)

Both are equivalent, but they produce different sequences

Fibonacci LFSR

Galois LFSR