A, B, C, D, E, F, G, H, I, J, L, M, N, O, P, Q, R, S, T, U, V, W
Landing Pad: Contact metal pads on a wafer usually associated with test probes and existing for test only. (SM*)
The evaluation of the reliability and quality of a digital IC is commonly called "testing", yet it is comprised of distinct phases which are mostly kept separate both in the research community and in industrial practice [Pradhan, 1986]. (SE)
The density of circuitry continues to increase, while the number of I/O pins remains small. This causes a serious escalation of complexity and testing is becoming one of the major costs to industry (estimated up to 30%). Integrated circuits should be tested before and after packaging, after mounting on a board, and periodically during operation. Different methods may be necessary for each case. Thus by testing we imply the means by which some qualities or attributes are determined to be fault-free or faulty. The main purpose of testing is the detection of malfunctions (Go/NoGo Test), and only subsequently one may be interested in the actual location of the malfunction; this is called fault diagnosis or fault location.
(5.1) LFSRs as Pseudo-Random Pattern Generators
An autonomous LFSR is a clocked synchronous shift registers augmented with appropriate feedback taps and receiving no external input [Bardell, 1987; Abramovici, 1990]. It is an example of a general linear finite state machine, where the memory cells are simple D-flip flops and the next state operations are implemented by EXOR gates only. Figure 6 shows an example of an autonomous LFSR of length k=3. An LFSR of length k can be described by a polynomial with binary coefficients of degree k, where the non zero coefficients of the polynomial denote the positions of the respective feedback taps. In figure 6, the high order coefficient for x3 is 1 and thus there is a feedback tap from the rightmost cell s2; the coefficient for x2 is 0 and thus no feedback tap exist after cell s1; however taps are present from cell s0 and to the leftmost stage since x and x0 have non zero coefficients. Since this is an autonomous LFSR, there is no external input to the leftmost cell. The state of the LFSR is denoted by the binary state of its cells. In Figure 6, the next state of each cell is determined by the implementation given by its polynomial and can be summarized as follows: s0+ = s2, s1+ = s0 [[circleplus]] s2, s2+ = s1, where the si+ denotes the next state of cell si at each clock cycle. If the LFSR is initialized in a non zero state, it cycles through a sequence of states and eventually comes back to the initial state, following the functionality of the next state rules implemented by its polynomial description. An LFSR that goes through all possible 2k -1 non zero states is said to be described by a primitive polynomial (see theory of Galois fields for the definition of primitive), and such polynomials can be found from tables [Bardell, 1987].
By connecting the output of each cell to an input of a circuit under test, the LFSR implements an ideal input generator, as it is inexpensive in its implementation and it provides the stimuli in pseudo-random order for either exhaustive or pseudo-exhaustive testing.
(5.2) LFSRs as Signature Analyzer
If the leftmost cell of an LFSR is connected to an external input, as shown in Figure 7, the LFSR can be used as a compactor [Bardell, 1987; Abramovici, 1990]. In general, the underlying operation of the LFSR is to compute polynomial division over GF(2) and the theoretical analysis of the effectiveness of signature analysis is based on this functionality. The polynomial describing the LFSR implementation is seen to be the divisor polynomial. The binary input stream can be seen to represent the coefficients (high order first) of a dividend polynomial. For example, if the input stream is 1001011 (bits are input left to right in time), the dividend polynomial is x6+x3+x+1. After 7 clock cycles for all the input bits to have entered the LFSR, the binary output stream exiting from the right denotes the quotient polynomial, while the last state of the cells in the LFSR denotes the remainder polynomial.
In the process of computing a signature for testing the circuit, the input stream to the LFSR used as compactor is the output stream from the circuit under test. At the end of the testing cycles, only the last state of the LFSR is examined and considered to be the compacted signature of the circuit. In most real cases, circuits have many outputs, and the LFSR is converted into a multiple input shift register, MISR. A MISR is constructed by adding EXOR gates to the input of some or all the flip-flop cells; the outputs of the circuit are then fed through these gates into the compactor. The probability of aliasing for a MISR is the same as that of an LFSR, however some errors are missed due to cancellation. This is the case when an error in one output at time t is cancelled by the EXOR operation with the error in another output at time t+1. Given an equally likely probability of errors occurring, the probability of error cancellation has been shown to be 2 1-m-N, where m is the number of outputs compacted and N is the length of the output streams.
Given that the normal length of signatures used varies between k=16 and k=32, the probability of aliasing is minimal and considered acceptable in practice. In MISR, the length of the compactor also depends on the number of outputs tested. If the number of outputs is greater than the length of the MISR, algorithms or heuristics exist for combining outputs with EXOR trees before feeding them to the compactor. If the number of outputs is much smaller, various choices can be evaluated. The amount of aliasing that actually occurs in a particular circuit can be computed by full fault simulation, that is, by injecting each possible fault into a simulated circuit and computing the resulting signature. Changes in aliasing can be achieved by changing the polynomial used to define the compactor. It has been shown that primitive polynomials, essential for the generation of exhaustive input generators (see above) possess also better aliasing characteristics.
(5.3) Data Compaction with Linear Cellular Automata Registers
LCAR's are one dimensional arrays composed of 2 types of cells: rules 150 and rule 90 cells [Serra, 1990]. Each cell is composed of a flip-flop which saves the current state of the cell, and an EXOR gate used to compute the next state of the cell. A rule 150 cell computes its next state as the EXOR of its present state and of the states of its two (left and right) neighbors. A rule 90 cell computes its next state as the EXOR of the states of its two neighbors only. As can be seen in Figure 8, all connections in an LCAR are near-neighbor connection, thus saving routing area and delays (common for long LFSR's).
Up to two inputs can be trivially connected to an LCAR, or it can be easily converted to accept multiple inputs fed through the cell rules. There are some advantages of using LCAR's instead of LFSR's: firstly the localization of all connections, and secondly and most importantly it has been shown that LCAR's are much "better" pseudo-random pattern generators when used in autonomous mode, as they do not show the correlation of bits due to the shifting of the LFSR's. Finally, the better pattern distribution provided by LCAR's as input stimuli has been shown to provide better detection for delay faults and open faults, normally very difficult to test.
As for LFSR's, LCAR are fully described by a characteristic polynomial and through it any linear finite state machine can be built either as an LFSR or as an LCAR. It is however more difficult, given a polynomial, to derive the corresponding LCAR, and tables are now used. The main disadvantage of LCAR's are in the area overhead incurred by the extra EXOR gates necessary for the implementation of the cell rules. This is offset by their better performance. The corresponding multiple output compactor is called a MICA. Summary Accessability to internal dense circuitry is becoming a greater problem and thus it is essential that a designer considers how the IC will be tested and incorporates structures in the design. Formal DFT techniques are concerned with providing access points for testing (see controllability and observability). As test pattern generation becomes even more prohibitive, probabilistic solutions based on compaction and using fault simulation are more widespread, especially if they are supported by DFT techniques and they can avoid the major expense of dedicated external testers. References:
The book by Abramovici et al is the most comprehensive view of testing methods and design for testability.
Information on deterministic pattern generation can be also found in the book edited by D.K. Pradhan
New approaches to random testing - see the book by Bardell et al.
Good comprehensive guide - Landreau.
 SEMATECH, Inc. SEMATECH Official Dictionary. SEMATECH Technology Transfer # 91010441A-STD. Austin:SEMATECH, 1991.
 Semiconductor Equipment and Materials International. 1990 SEMI International Standards, Vol. 1-5. Mountain View:SEMI, 1990\1994.
 The Institute of Electrical and Electronics Engineers, Inc.. IEEE Standards Dictionary of Electrical and Electronics Terms, Fourth ed. New York:IEEE, 1988.
 American Society for Testing and Materials, Compilation of ASTM Standard Definitions, Sixth ed. Baltimore:ASTM, 1986.
 Griggs, B., A. Miller, P. Van Zant. Semiconductor Technology Graphic Glossary of Terms. Redwood City:Semiconductor Services, 1989.
 Electronic Industries Association. "Standards Proposal SP-2133." Washington D.C.:EIA, 1988.
(TI*) - Texas Instruments military test Glossary
(SM*) - Sematech Glossary
(SR*) Micaela Serra, Testing Tutorial, DIGITAL IC TESTING: AN INTRODUCTION, University of Victoria, Victoria, B.C., Canada, EE Handbook, CRC Press.
[Abramovici] M. Abramovici, M. A. Breuer and A.D. Friedman. Digital Systems Testing and Testable Design. Computer Science press, 1990.
P.H. Bardell, W.H. McAnney, and J. Savir. Built-In Test for VLSI: Pseudorandom Techniques. John Wiley and Sons, New York, 1987.
M. Jacomino, J.L. Rainard, and R. David. Fault Detection in CMOS Circuits by Consumption Measurement. IEEE Trans. Instrumentation and Measurement, 38(3), pp. 773-778, June 1989.
E.J. McCluskey. Logic Design Principles. Prentice Hall, 1986.
D.K. Pradhan,ed. "Fault Tolerant Computing", Prentice Hall, 1986.
M. Serra, T. Slater, J.C. Muzio, and D.M. Miller. The Analysis of One-Dimensional Linear cellular Automata and Their Aliasing Properties. IEEE Trans. Computer Aided Design, 9(7), pp.767-778, 1990.
T.W. Williams, ed. VLSI Testing. North Holland, 1986.