An LFSR is a shift register whose output 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. In this, the first installment of a three-part mini-series, we introduce general LFSR concepts.

Just so we know where we're going... in this installment we are going to introduce LFSRs in general, including XOR-based and XNOR-based many-to-one implementations. In Part 2 we will consider one-to-many implementations, modifying an LFSR to sequence 2ⁿ values, accessing an LFSR's previous value, and FIFO applications. And in Part 3 we will ponder a variety of LFSR applications, including encryption and decryption, data compression, cyclic redundancy check (CRC) generation, built-in self-test (BIST) structures, and pseudo-random number generation (phew!).

The Ouroboros of the Digital Consciousness
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 (not to be confused with the Amphisbaena, a serpent in classical mythology having a head at each end and capable of moving in either direction).

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. (In conversation, LFSR is spelled out as "L-F-S-R".)

Many-to-One Implementations
LFSRs are simple to construct and are useful for a wide variety of applications (we will consider some of these applications in detail later in this mini-series). 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 (Figure 1-1).

Figure 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 (Figure 1-2).

 .
Figure 1-2. Comparison of alternative tap selections

Both LFSRs start with the same initial value but, due to the different tap selections, 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 Figure 1-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ⁿ unique values, but a maximal-length LFSR with n register bits will only sequence through (2ⁿ – 1) values. This is because LFSRs with XOR feedback paths will not sequence through the value where all the bits are logic 0, while their XNOR equivalents will not sequence through the value where all the bits are logic 1 (Figure 1-3).

Figure 1-3. Comparison of XOR versus XNOR feedback paths.

More Taps Than You Know What to Do With
Each LFSR supports a number of tap combinations that will generate maximal-length sequences. The problem is weeding out the ones that do from the ones that don't, because badly chosen taps can result in the register entering a loop comprising only a limited number of states.

Way back in the mists of time, I discovered that many of the tap combinations I was seeing in the text books I owned were incorrect. Thus, I created a simple C program to determine the taps for maximal-length LFSRs with 2 to 32 bits. These values are presented for your delectation and delight in Figure 1-4 (the * annotations indicate sequences whose length is a prime number).

Figure 1-4. Example taps for maximal length LFSRs with 2 to 32 bits.

The taps are identical for both XOR-based and XNOR-based LFSRs, although the resulting sequence will, of course, differ. As was previously noted, alternative tap combinations may also yield maximum-length LFSRs, although the resulting sequences will vary. For example, in the case of a 10-bit LFSR, there are two 2-tap combinations that result in a maximal-length sequence: [2,9] and [6,9]. There are also twenty 4-tap combinations, twenty-eight 6-tap combinations, and ten 8-tap combinations that satisfy the maximal-length criteria.

Now, on to Part 2 in which we will consider one-to-many implementations, modifying an LFSR to sequence 2ⁿ values, accessing an LFSR's previous value, and LFSR-based FIFO applications.