Editors Note: The first in a three-part introduction to Linear Feedback Shift Registers (LFSRs), this article is abstracted from the book Bebop to the Boolean Boogie (An Unconventional Guide to Electronics) with the kind permission of the publisher. (See also Part 2 and Part 3.)
The Ouroboros – a symbol of a serpent or dragon devouring its own tail and thereby forming a circle – has been employed by a variety of ancient cultures around the world to depict eternity or renewal (this should not be confused with the Amphisbaena, a serpent in classical mythology having a head at each end and capable of moving in either direction – much like some managers I have known).
The equivalent to the Ouroboros in the world of electronics would be the Linear Feedback Shift Register (LFSR), in which the output from a standard shift register is cunningly manipulated and fed back into its input in such a way as to cause the function to endlessly cycle through a sequence of patterns.
LFSRs are simple to construct and are useful for a wide variety of applications, but are often sadly neglected by designers. One of the more common forms of LFSR is formed from a simple shift register with feedback from two or more points, or taps, in the register chain (Fig 1).
1. LFSR with XOR feedback path.
The taps in this example are at bit 0 and bit 2, and can be referenced as [0,2]. All of the register elements share a common clock input, which is omitted from the symbol for reasons of clarity. The data input to the LFSR is generated by XOR-ing or XNOR-ing the tap bits; the remaining bits function as a standard shift register. The sequence of values generated by an LFSR is determined by its feedback function (XOR versus XNOR) and tap selection. For example, consider two 3-bit XOR based LFSRs with different tap selections (Fig 2).
2. Comparison of alternative tap selections.
Both LFSRs start with the same initial value but, due to the different taps, their sequences rapidly diverge as clock pulses are applied. In some cases an LFSR will end up cycling round a loop comprising a limited number of values. However, both of the LFSRs shown in Fig 2 are said to be of maximal length because they sequence through every possible value (excluding all of the bits being 0) before returning to their initial values.
A binary field with 'n' bits can assume 2^n unique values, but a maximal-length LFSR with 'n' register bits will only sequence through (2^n – 1) values. This is because LFSRs with XOR feedback paths will not sequence through the value where all the bits are 0, while their XNOR equivalents will not sequence through the value where all the bits are 1 (Fig 3).
3. Comparison of XOR versus XNOR feedback paths.