Abstract
The build-in test pattern generators such as linear feedback shift registers (LFSR’s) and cellular automata are used to generate pseudo-random patterns for circuit-under-test. They are both lowcost and realize the at-speed testing for the circuit, especially for testing delay faults in the circuit which requires that the test vectors be applied to the circuit at its intended operating speed. However, different configurations or different initial states of LFSR’s may yield significantly different fault coverages when used as a test pattern generator for a given circuit. In this thesis, we develop a Simulated Annealing (SA) algorithm to select an effective LFSR for testing the transition faults and path delay faults of a circuit. In our SA algorithm, we have to simulate a large amount of LFSR’s. Therefore, we develop a faster algorithm use to estimate the fault coverage. If the SA algorithm is used to search a better LFSR for transition fault, we propose a statistic method to estimate the transition fault coverage of the chosen LFSR. On the other hand, if the SA algorithm is used to search a better LFSR for a given path set, we also develop a logic simulator which can be used to estimate the path delay fault coverage. Experimental results shows the search result of SA algorithm and the comparison between statistic method and fault simulation.