What is linear feedback shift register?
A linear feedback shift register (LSFR) is a shift register that takes as an input a linear function of a previous state. Most often this function is a Boolean exclusive OR (XOR). The bits that affect the state in the other bits are called taps. LSFRs are used for digital counters, cryptography, and circuit testing.
A linear feedback shift register takes a linear function, typically an exclusive OR, as an input. Like other shift registers, an LSFR is a cascade of flip-flop circuits. The bits that change status for the others in the cascade are called taps. Two of the main schemes for connecting taps are Fibonacci and Galois. In the Fibonacci configuration, the taps are cascaded and fed into the leftmost bit. In a Galois configuration named after the French mathematician Évariste Galois, each tap is XORed to form the output stream.
LSFRs are used in cryptography to generate pseudo-random numbers, pseudo-noise sequences and highlighting sequences. They are also often used for digital counters because they are so fast.