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 third and final installment of a three-part mini-series, we will ponder a variety of LFSR applications, from encryption and decryption to pseudo-random number generation.

Just to remind ourselves where we've come from... in Part 1 we introduced LFSRs in general, including XOR-based and XNOR-based many-to-one implementations. In Part 2 we considered one-to-many implementations, modifying an LFSR to sequence 2ⁿ values, accessing an LFSR's previous value, and FIFO applications. And in this (the final) installment of our mini-series, 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.

Encryption and Decryption Applications
The unusual sequence of values generated by an LFSR can be gainfully employed in the encryption (scrambling) and decryption (unscrambling) of data. For example, a stream of data bits can be encrypted by XOR-ing them with the output from an LFSR as illustrated in Figure 3-1).

Figure 3-1. Data encryption using an LFSR.

The stream of encrypted data bits seen by a receiver can be decrypted by XOR-ing them with the output of an identical LFSR. (The rudimentary example presented here is obviously a very trivial form of encryption that's not very secure, but it's "cheap-and-cheerful" and may be useful in certain applications.)

Cyclic Redundancy Check (CRC) Applications
A traditional application for LFSRs is in Cyclic Redundancy Check (CRC) calculations, which can be used to detect errors in data communications. In this case, the stream of data bits being transmitted is used to modify the values fed back into an LFSR (Figure 3-2).

Figure 3-2. Cyclic Redundancy Check (CRC) calculation.

The final CRC value stored in the LFSR is known as a checksum, and is dependent on every bit in the data stream. After all of the data bits have been transmitted, the transmitter sends its checksum value to the receiver. The receiver contains an identical CRC calculator and generates its own checksum value from the incoming data.

Once all of the data bits have arrived, the receiver compares its internally generated checksum value with the checksum sent by the transmitter to determine whether any corruption occurred during the course of the transmission. This form of error detection is very efficient in terms of the small number of bits that have to be transmitted in addition to the data.

In the real world, a 4-bit CRC calculator would not be considered to provide sufficient confidence in the integrity of the transmitted data. This is due to the fact that a 4-bit LFSR can only represent 16 unique values, which means that there is a significant probability that multiple errors in the data stream could result in the two checksum values being identical. As the number of bits in a CRC calculator increases, however, the probability that multiple errors will cause identical checksum values approaches zero. For this reason, CRC calculators typically use a minimum of 16-bits providing 65,536 unique values.

There are a variety of standard communications protocols, each of which specifies the number of bits employed in their CRC calculations and the taps to be used. The taps are selected such that an error in a single data bit will cause the maximum possible disruption to the resulting checksum value. Thus, in addition to being referred to as maximal-length, these LFSRs may also be qualified as maximal-displacement.

Data Compression Applications
The CRC calculators discussed in the previous topic can also be used in a data compression role. One such application is found in the circuit board test strategy known as functional test. In this case, the board is plugged into a functional tester by means of its edge connector.

The tester applies a pattern of signals to the board's inputs, allows sufficient time for any effects to propagate around the board, and then compares the actual values seen on the outputs with a set of expected values stored in the system. This process is repeated for a series of input patterns, which may number in the tens or hundreds of thousands (Figure 3-3).

Figure 3-3. Simplified representation of a functional board test scenario.

The illustration above is simplified for reasons of clarity. In practice, the edge connector may contain hundreds of pins while the board may contain thousands of components and tracks (wires). If the board fails the preliminary tests, a more sophisticated form of analysis known as guided probe may be employed to identify the cause of the failure (Figure 3-4).

Figure 3-4. Guided probe analysis.

The idea here is that the functional tester instructs the operator to place the probe at a particular location on the board, and then the entire sequence of test patterns is rerun. The tester compares the actual sequence of values seen by the probe with a sequence of expected values that are stored in the system. This process (placing the probe and running the tests) is repeated until the tester has isolated the faulty component or track.

A major consideration when supporting a guided probe strategy is the amount of expected data that must be stored. Consider a test sequence comprising 10,000 patterns driving a board containing 10,000 tracks. If the data were not compressed, the system would have to store 10,000 bits of expected data per track, which amounts to 100,000,000 bits of data for the board. Additionally, for each application of the guided probe, the tester would have to compare the 10,000 data bits observed by the probe with the 10,000 bits of expected data stored in the system. Thus, using data in an uncompressed form is an expensive option in terms of storage and processing requirements.

One solution to these problems is to employ LFSR-based CRC calculators. The sequence of expected values for each track can be passed through a 16-bit CRC calculator implemented in software. Similarly, the sequence of actual values seen by the guided probe can be passed through an identical CRC calculator implemented in hardware. In this case, the calculated checksum values are also known as signatures, and a guided probe process based on this technique is known as signature analysis.

Irrespective of the number of test patterns used, the system has to store only two bytes of data for each track. Additionally, for each application of the guided probe, the tester has to compare only the two bytes of data gathered by the probe with two bytes of expected data stored in the system. The end result is that compressing the data results in storage requirements that are orders of magnitude smaller – and comparison times that are orders of magnitude faster – than the uncompressed data approach.

Built-In Self-Test (BIST) Applications
One test strategy which may be employed in complex integrated circuits is that of Built-In Self-Test (BIST). [There are several specialized versions of BIST; for example, Logic Built-In Self-Test (LBIST) and Memory Built-In Self-Test (MBIST); we're focusing on LBIST in these discussions.] Devices using BIST contain special test generation and result gathering circuits as illustrated in Figure 3-5.

Figure 3-5. Built-In Self-Test (BIST).

A multiplexer is used to select between the standard inputs and those from a "test generator." A second multiplexer selects between the standard outputs and those from a "results gatherer." The point is that both the test generator and results gatherer can be implemented using LFSRs as illustrated in Figure 3-6. (Note that the standard inputs and outputs – along with their multiplexers – have been omitted from Figure 3-6 in order to keep things simple.)

Figure 3-6. BIST implemented using LFSRs.

The LFSR forming the test generator is used to create a sequence of test patterns, while the LFSR forming the results gatherer is used to capture the results. The results-gathering LFSR features modifications that allow it to accept parallel data. (Note that the two LFSRs are not obliged to contain the same number of bits, because the number of inputs to the logic being tested may be different to the number of outputs from the logic.)

Once the self-test has been run, the contents of the results gathering LFSR can be compared to a known-good value to determine if the core logic is functioning as expected.

Pseudo-Random Number Applications
Many computer programs rely on an element of randomness. Computer games such as "Space Invaders" employ random events to increase the player's enjoyment. Graphics programs may exploit random numbers to generate intricate patterns.

Similarly, all forms of computer simulation may utilize random numbers to more accurately represent the real world. For example, digital simulations (see note below) may benefit from the portrayal of random stimulus such as external interrupts. Random stimulus can result in more realistic design verification, which can uncover problems that may not be revealed by more structured tests.

Note: Digital simulation is based on a program called a logic simulator, which is used to build a virtual representation of an electronic design in the computer's memory. The simulator then applies stimulus to the design's virtual inputs, simulates the effect of these signals as they propagate through the design, and checks the responses at the design's virtual outputs.

Random number generators can be constructed in both hardware and software. The majority of these generators are not truly random, but they give the appearance of being random and are therefore said to be pseudo-random. In fact, pseudo-random numbers have an advantage over truly random numbers, because the majority of computer applications typically require repeatability. For example, a designer repeating a digital simulation would expect to receive identical answers to those from the previous run. However, designers also need the ability to modify the seed value of the pseudo-random number generator so as to spawn different sequences of values as required.

There are a variety of methods available for generating pseudo-random numbers. A popular cheap-and-cheerful technique uses the remainder from a division operation as the next value in a pseudo-random sequence. For example, a C function which returns a pseudo-random number in the range 0 to 32767 could be written as illustrated below (this example came from The C Programming Language, Second Edition, by Brian W. Kernighan and Dennis M. Ritchie.):

In this case, the variable next would be declared as global and initialized with some seed value. Also, an additional function would be provided to allow the programmer to load next with a new seed value if required. Every time this function is accessed it returns a new pseudo-random value.

Unfortunately, pseudo-random implementations based on division do not always produce a "white spectrum". The series of generated values may be composed of a collection of sub-series, in which case the results will not be of maximal length. By comparison, the sequence of values generated by a software implementation of a maximal-length LFSR provides a reasonably good pseudo-random source, but is somewhat more expensive in terms of processing requirements.

Last But Not Least
LFSRs are simple to construct and are useful for a wide variety of applications, but be warned that choosing the optimal polynomial (which ultimately boils down to selecting the optimal tap points) for a particular application is a task that is usually reserved for a master of the mystic arts; the math behind this can be hairy enough to make a grown man break down and cry, and don't even get me started on the subject of cyclotomic polynomials, which are key to the tap-selection process (the real reason I don’t want you to ask me about cyclotomic polynomials is because I don't have the faintest clue as to what a cyclotomic polynomial is).