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

Latest Computer Science Terms

Related Reading

Margaret Rouse

Margaret Rouse is an award-winning technical writer and teacher known for her ability to explain complex technical subjects to a non-technical, business audience. Over the past twenty years her explanations have appeared on TechTarget websites and she's been cited as an authority in articles by the New York Times, Time Magazine, USA Today, ZDNet, PC Magazine and Discovery Magazine.Margaret's idea of a fun day is helping IT and business professionals learn to speak each other’s highly specialized languages. If you have a suggestion for a new definition or how to improve a technical explanation, please email Margaret or contact her…