Built In Test for VLSI: Pseudorandom Techniques

3

Pseudorandom Sequence Generators

A string of binary digits (1's and 0's) is called a pseudorandom binary sequence when the bits appear to be random in the local sense, but they are in some way repeatable, hence only pseudorandom. These sequences have been studied extensively because they find use in communications systems, en-cipherment, privacy encoding, error-correcting coding, and others. These sequences are of interest here because they form an important class of stimuli for the testing of digital circuits.

While a formal definition of pseudorandomness will be given later in this chapter, the reader can see that if the next output of a sequence generator is equally likely to be a 1 as a 0, independent of what the previous output was, the sequence would appear random on a local scale. However, if it is possible to reset the sequence generator so that exactly the same sequence is produced at another time, the sequence is not random; in fact, it is repeatable. This repeatability gives rise to the pseudorandom nature of the sequences of interest in this chapter.

3.1 SHIFT-REGISTER IMPLEMENTATION OF A PSEUDORANDOM SEQUENCE

Feedback shift registers have been used by many workers to generate pseudorandom sequences. A shift register is a collection of storage elements (for example, ...