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

Margaret Rouse

Margaret 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 IT definitions have been published by Que in an encyclopedia of technology terms and cited in articles by the New York Times, Time Magazine, USA Today, ZDNet, PC Magazine, and Discovery Magazine. She joined Techopedia in 2011. Margaret's idea of a fun day is helping IT and business professionals learn to speak each other’s highly specialized languages.