Built In Test for VLSI: Pseudorandom Techniques

5

Shift Register Polynomial Division

Polynomial division with a linear feedback shift register uses the remainder left in the register after completion of the test as the retained statistic for comparison with the known good remainder. It is an extension of the well known CRC code and is the most popular data compression technique because it is sensitive to the sequence of ones and zeros in the output bit stream and because it is easily modified for use with multiple-output circuits. The remainder is usually called a signature, and the technique is called signature analysis, a name coined by Hewlett-Packard and first used in Frohwerk (1977). This chapter addresses the techniques of signature analysis for single- and multiple-output circuits, the error masking probabilities of the method, and some suggested techniques for improving its efficiency.

In the first parts of this chapter, attention will be directed towards singleoutput combinational circuits, postponing a discussion of multiple-output circuits and sequential circuits to later portions.

5.1 POLYNOMIAL REPRESENTATION OF BINARY DATA

Coding theory treats binary streams as polynomials in a dummy variable, usually represented by x. Let

be any m-bit binary sequence. Using the dummy variable x, the sequence can be converted into ...