Don't miss an insight. Subscribe to Techopedia for free.


Linear Feedback Shift Register

What Does Linear Feedback Shift Register Mean?

A linear feedback shift register (LSFR) is a shift register that takes a linear function of a previous state as an input. Most commonly, this function is a Boolean exclusive OR (XOR). The bits that affect the state in the other bits are known as taps. LSFRs are used for digital counters, cryptography and circuit testing.


Techopedia Explains Linear Feedback Shift Register

A linear feedback shift register takes a linear function, typically an exclusive OR, as an input. An LSFR, like other shift registers, is a cascade of flip-flop circuits. The bits that change state for the others in the cascade are called taps. Two of the major 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 configration, named after the French mathematician Évariste Galois, each tap is XOR’d to the output stream.

LSFRs are used in cryptography for pseudo-random number generation, pseudo-noise sequences and whitening sequences. They are also often used for digital counters because they are so fast.


Related Terms