x3+x+1 FIGURE 85.6 Autonomous LfSR The most important issue is in the choice of a compactor. Although no "perfect"compactor can be found, several have been shown to be very effective. Several compaction techniques have been researched: counting chniques, as in one's count, syndrome testing, transition count, and Walsh spectra coefficients; and signature analysis techniques based on linear feedback shift registers(LFSRs)or linear cellular automata registers(LCARs) Only these latter ones are discussed here. LFSRs and LCARs are also the preferred implementation for the input pattern generators. L FSRs as Pseudo Random Pattern generators An autonomous LFSR is a clocked synchronous shift register augmented with appropriate feedback taps and receiving no external input [Bardell et al, 1987; Abramovici, 1992]. 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 EXOR gates only Figure 85.6 shows an example of an autonomous LFSR of length k=3. An LFSR of length k an be described by a polynomial with binary coefficients of degree k, where the nonzero coefficients of the polynomial denote the positions of the respective feedback taps. In Fig. 85.6, the high-order coefficient for x' 1, and thus there is a feedback tap from the rightmost cell s; the coefficient for x' is 0, and thus no feedback tap exists after cell s; however, taps are present from cell s and to the leftmost stage since x and x have nonzero 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 Fig. 85.6, the next state of each cell is determined by the implementation given by its polynomial and can be summarized as follows: $* =52, st so E s,*=S, where the s, denotes the next state of cell s, at each clock cycle. If the LFSR is initialized in a nonzero 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 througl all possible 2- 1 nonzero 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 et al., 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 LFSRs as Signature analyzer If the leftmost cell of an LFSR is connected to an external input, as shown in Fig. 85.7, the LFSR can be used a compactor[ Bardell et al, 1987; Abramovici, 1992]. In general, the underlying operation of the LFSR is to mute polynomial division over a finite field, 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+x+x+ 1. After seven 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 a 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; e 2000 by CRC Press LLC© 2000 by CRC Press LLC The most important issue is in the choice of a compactor. Although no “perfect” compactor can be found, several have been shown to be very effective. Several compaction techniques have been researched: counting techniques, as in one’s count, syndrome testing, transition count, and Walsh spectra coefficients; and signature analysis techniques based on linear feedback shift registers (LFSRs) or linear cellular automata registers (LCARs). Only these latter ones are discussed here. LFSRs and LCARs are also the preferred implementation for the input pattern generators. LFSRs as Pseudo-Random Pattern Generators An autonomous LFSR is a clocked synchronous shift register augmented with appropriate feedback taps and receiving no external input [Bardell et al., 1987; Abramovici, 1992]. 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 85.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 nonzero coefficients of the polynomial denote the positions of the respective feedback taps. In Fig. 85.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 exists after cell s1 ; however, taps are present from cell s0 and to the leftmost stage since x and x0 have nonzero 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 Fig. 85.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 % s2 , s2 + = s1, where the si + denotes the next state of cell si at each clock cycle. If the LFSR is initialized in a nonzero 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 nonzero 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 et al., 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. LFSRs as Signature Analyzer If the leftmost cell of an LFSR is connected to an external input, as shown in Fig. 85.7, the LFSR can be used as a compactor [Bardell et al., 1987; Abramovici, 1992]. In general, the underlying operation of the LFSR is to compute polynomial division over a finite field, 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 seven 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 a 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; FIGURE 85.6 Autonomous LFSR