→國!四四 FIGURE 85.7 LFSR for signature ana 1∞kLs0kxsk2m FIGURE 85. 8 LCAR for signature analys however, some errors are missed due to cancellation. This is the case when an error in one output at time t is canceled 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 2l-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), also possess better aliasing characteristics Data Compaction with Linear Cellular Automata Registers LCARs are one-dimensional arrays composed of two types of cells: rule 150 and rule 90 cells [Cattell et al, 996. Each cell is composed of a flip-flop that 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 Fig. 85.8, all connections in an LCAR are near-neighbor connections, thus saving routing area and delays(common for long LFSRs 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 LCARs instead of LFSRs: first, the localization of all connections, and second, and most importantly, it has been shown that LCARs are much better" pseudo-random pattern generators when used in autonomous mode, as they do not show the corre lation of bits due to the shifting of the LFSRs. Finally, the better pattern distribution provided by lCars input stimuli has been shown to provide better detection for delay faults and open faults, normally very difficult to test As for LFSRs, L CARs 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 LCARs is in the area verhead 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. Accessibility to internal dense circuitry is becoming a greater problem, and thus it is essential that a designer consider how the IC will be tested and incorporate structures in the design. Formal DFT techniques are e 2000 by CRC Press LLC© 2000 by CRC Press LLC however, some errors are missed due to cancellation. This is the case when an error in one output at time t is canceled 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 21–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), also possess better aliasing characteristics. Data Compaction with Linear Cellular Automata Registers LCARs are one-dimensional arrays composed of two types of cells: rule 150 and rule 90 cells [Cattell et al., 1996]. Each cell is composed of a flip-flop that 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 Fig. 85.8, all connections in an LCAR are near-neighbor connections, thus saving routing area and delays (common for long LFSRs). 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 LCARs instead of LFSRs: first, the localization of all connections, and second, and most importantly, it has been shown that LCARs are much “better” pseudo-random pattern generators when used in autonomous mode, as they do not show the corre￾lation of bits due to the shifting of the LFSRs. Finally, the better pattern distribution provided by LCARs as input stimuli has been shown to provide better detection for delay faults and open faults, normally very difficult to test. As for LFSRs, LCARs 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 LCARs is 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 Accessibility to internal dense circuitry is becoming a greater problem, and thus it is essential that a designer consider how the IC will be tested and incorporate structures in the design. Formal DFT techniques are FIGURE 85.7 LFSR for signature analysis. FIGURE 85.8 LCAR for signature analysis