ON TESTING OF SEQUENTIAL-MACHINES USING CIRCUIT DECOMPOSITION AND STOCHASTIC MODELING

The increasing complexity of today's digital devices has rendered the problem of fault detection, fault analysis and test generation extreme ly difficult. Test generation for sequential circuits has been a diffi cult task. This is due to the large search space to be considered in t est pattern generation. Different approaches have been taken in the pa st to solve the problem of fault detection and test generation in sequ ential circuits. A popular approach, called the scan design, is often used where the problem of test generation in sequential circuits is tr ansformed into that in combinational circuits. Unfortunately, this app roach is restricted to synchronous sequential circuits free of critica l races. Moreover, when a circuit is very large and complex, the test generation can be quite involved, making the ad hoc approaches ineffec tive. Therefore, alternative methods should be considered. In this pap er the detection of permanent faults in sequential circuits by random testing is analyzed utilizing the circuit partitioning approach togeth er with a continuous parameter Markov model. Given a large sequential circuit, it is partitioned into several smaller partitions using eithe r series of parallel decomposition. For each partition with certain st uck faults specified, the original state table and its error version a re derived from an analysis of the partition under fault-free and faul ty conditions, respectively. A random testing strategy that uses a thr ee-state Markov model is used for detecting permanent stuck faults. Ex perimentation on various sequential circuits has shown that a signific ant saving in testing or test generation time can be achieved if we pa rtition the circuit and then test each of its components as opposed to testing the circuit in its original form.