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 second installment of a three-part mini-series, we consider one-to-many implementations, modifying an LFSR to sequence 2ⁿ values, accessing an LFSR's previous value, and FIFO applications.

Just to remind ourselves where we've come from and where we're heading... in Part 1 we introduced LFSRs in general, including XOR-based and XNOR-based many-to-one implementations. In this installment we are going to 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.

One-to-Many Implementations
Consider the case of an 8-bit LFSR, for which the minimum number of taps that will generate a maximal-length sequence is four. In the real world, XOR gates only have two inputs, so a four-input XOR function has to be created using three XOR gates arranged as two levels of logic. Even in those cases where an LFSR does support a minimum of two taps, for one reason or another you may actually wish to use a greater number of taps such as eight (which would result in three levels of XOR logic).

The problem is that increasing the levels of logic in the combinational feedback path can negatively impact the maximum clocking frequency of the function. One solution is to transpose the many-to-one implementations discussed in Part 1 and shown in Figure 2-1(a) into their one-to-many counterparts as illustrated in Figure 2-1(b).

Figure 2-1. Many-to-one versus one-to-many LFSR implementations.

The traditional many-to-one implementation for the eight-bit LFSR has taps at [7,3,2,1]. To convert this into its one-to-many counterpart, the most-significant tap (which is always the most significant bit) is fed back directly into the least significant bit, and is also individually XORed with the other original taps (bits [3,2,1] in this example).

It's important to note that, although both styles result in maximal-length LFSRs, the actual sequences of values will differ between the two implementations. But the main point is that using the one-to-many style means that there is never more than one level of combinational logic in the feedback path, irrespective of the number of taps being employed.

Seeding an LFSR
An interesting "quirk" with an XOR-based LFSR is that, if it happens to find itself in the all 0s value, it will happily continue to shift all 0s indefinitely (similarly for an XNOR-based LFSR and the all 1s value). This is of particular concern when power is first applied to the circuit. Each register bit can randomly initialize containing either a logic 0 or a logic 1, and the LFSR can therefore "wake up" containing its "forbidden" value. For this reason, it is necessary to initialize an LFSR with a seed value.

One method for loading a seed value is to use registers with reset and/or set inputs. A single control signal can be connected to the reset inputs on some of the registers and the set inputs on others. When this control signal is placed in its active state, the LFSR will load with a hard-wired seed value. In certain applications, however, it is desirable to be able to vary the seed value. One technique for achieving this is to include a multiplexer at the input to the LFSR (Figure 2-2).

Figure 2-2. Circuit for loading different seed values.

When the multiplexer's data input is selected, the device functions as a standard shift register and any desired seed value may be loaded. After loading the seed value, the feedback path is selected and the device returns to its LFSR mode of operation.

FIFO Applications
The fact that an LFSR generates an unusual sequence of values is irrelevant in many applications. Consider a 4-bit x 16-word First-In First-Out (FIFO) memory as illustrated in Figure 2-3.

Figure 2-3. First-In First-Out (FIFO) memory.

A brief summary of the FIFO's operation is as follows. The write and read pointers are essentially 4-bit registers whose outputs are processed by 4:16 decoders to select one of the sixteen words in the memory array. The reset input is used to initialize the device, primarily by clearing the write and read pointers such that they both point to the same memory word.

The initialization also causes the empty output to be placed in its active state and the full output to be placed in its inactive state. More-sophisticated versions may have additional signals, such as nearly-full and nearly-empty.

The write and read pointers chase each other around the memory array in an endless loop. An active edge on the write input causes any data on the data-in[3:0] bus to be written into the word pointed to by the write pointer; the empty output is placed in its inactive state (because the device is no longer empty) and the write pointer is incremented to point to the next empty word.

Data can be written into the FIFO until all the words in the array contain values. When the write pointer catches up to the read pointer, the full output is placed in its active state (indicating that the device is full) and no more data can be written into the device.

An active edge on the read input causes the data in the word pointed to by the read pointer to be copied into the output register, from whence it appears on the data-out[3:0] signals; the full output is placed in its inactive state and the read pointer is incremented to point to the next word containing data. (Note that these discussions assume the use of write-and-increment and read-and-increment techniques; however, some FIFOs employ an increment-and-write and increment-and-read approach.)

Data can be read out of the FIFO until the array is empty. When the read pointer catches up to the write pointer, the empty output is placed in its active state, and no more data can be read out of the device.

The write and read pointers for a 16-word FIFO are often implemented using 4-bit binary counters. However, a moment's reflection reveals that there is no intrinsic advantage to a binary sequence for this particular application, and the sequence generated by a 4-bit LFSR would serve equally well. In fact, the two functions operate in a very similar manner as is illustrated by their block diagrams (Figure 2-4).

Figure 2-4. Block diagrams of a binary counter and an LFSR.

However, the combinational logic for the 4-bit LFSR consists of a single, two-input XOR gate, while the combinational logic for the 4-bit binary counter requires a number of AND and OR gates. This means that the LFSR requires fewer tracks (wires) and is more efficient in terms of silicon real estate. Additionally, the LFSR's feedback only passes through a single level of logic, while the binary counter's feedback passes through multiple levels of logic. This means that the new data value is available sooner for the LFSR, which can therefore be clocked at a higher frequency. These differentiations become even more pronounced for FIFOs with more words requiring pointers with more bits. Thus, LFSR's may be a very attractive choice for the discerning designer of FIFOs.

Modifying LFSRs to Sequence 2ⁿ Values
One downside to the 4-bit LFSRs in the FIFO scenario above is that they will sequence through only 15 values (2⁴ – 1), as compared to the binary counter's sequence of 16 values (2⁴). Designers may not regard this to be a problem, especially in the case of larger FIFOs. However, if it is required for an LFSR to sequence through every possible value, there is a simple solution (Figure 2-5).

Figure 2-5. LFSR modified to sequence through 2ⁿ values.

For the value where all of the bits are logic 0 to appear, the preceding value must have comprised a logic 1 in the Most-Significant Bit (MSB) and logic 0s in the remaining bit positions. (As is often the case with any form of shift register, the MSB in these examples is taken to be on the right-hand side of the register, while the LSB is taken to be on the left-hand side; this is, of course, opposite to the way we usually do things.)

In an unmodified LFSR, the next clock would result in a logic 1 in the Least-Significant Bit (LSB) and logic 0s in the remaining bit positions. In the modified LFSR, however, the output from the NOR is a logic 0 for every case but two: the value preceding the one where all the bits are 0 and the value where all the bits are 0. These two values force the NOR's output to a logic 1, which inverts the usual output from the XOR. This in turn causes the sequence to first enter the all-0s value and then resume its normal course. (In the case of LFSRs with XNOR feedback paths, the NOR can be replaced with an AND, which causes the sequence to cycle through the value where all of the bits are logic 1.)

Accessing an LFSR's Previous Value
In some applications, it is required to make use of a register's previous value. In certain FIFO implementations, for example, the "full" condition is detected when the write pointer is pointing to the location preceding the location pointed to by the read pointer (try saying that quickly!). This implies that a comparator must be used to compare the current value in the write pointer with the previous value in the read pointer.

Similarly, the "empty" condition may be detected when the read pointer is pointing to the location preceding the location pointed to by the write pointer. This implies that a second comparator must be used to compare the current value in the read pointer with the previous value in the write pointer.

In the case of binary counters, there are two techniques by which the previous value in the sequence may be accessed. The first requires the provision of an additional set of so-called shadow registers. Every time the counter is incremented, its current contents are first copied into the shadow registers. Alternatively, a block of combinational logic can be used to decode the previous value from the current value. Unfortunately, both of these techniques involve a substantial overhead in terms of additional logic.

By comparison, LFSRs inherently remember their previous value. All that is required is the addition of a single register bit appended to the MSB as illustrated in Figure 2-6.

Figure 2-6. Accessing an LFSR's previous value.

OK, now let's bounce over to Part 3 where 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.

Author's Note: The material presented in this article was abstracted from my book Bebop to the Boolean Boogie (An Unconventional Guide to Electronics) 3rd Edition, with the kind permission of my publisher, Newnes (an imprint of Elsevier).