Research On Algorithms Of Test Pattern Generation For Digital Integrated Circuits

With the rapid improvement of modern science and technology, digital integrated circuits have been applied in various fields broadly, and at the same time, the test generation (TG) problem of digital integrated circuits was considered more and more important by people. Digital integrated circuits can not depart from test in design, production, and application essential stages. Designers test them to confirm their correctness, producers test them to guarantee product eligibility, and users test them to carry out their right function. So researches on TG method of digital integrated circuits are significant in science and technology rapid development today.Although domestic and foreign scholars have presented many different TG methods constantly, test spending still took up a large proportion in the circuit production process. From existent researches on TG, we can know that the difficulty of TG lies in testing difficult-detected faults, the size of test set being large and the sequential circuits having to be initialized in advance. So this paper studied on simulation-based test pattern generation (STPG) for digital integrated circuits, applied new intelligent optimization algorithms to TG,test set compaction and initialization for sequential circuits, which reduced test complexity, moreover decreased required storage space, and improved test efficiency.Firstly, in view of the actuality of TG methods, new TG methods based on particle swarm optimization (PSO), chaotic particle swarm optimization (CHPSO) and cultural particle swarm optimization (CUPSO) for combinational circuits were proposed. The whole algorithm was mainly constructed of two parts: multiple faults test pattern generation regarding easy-detected faults as goal and single fault test pattern generation regarding a difficult-detected fault as goal, and a new fitness function was defined. Besides, several speedup methods were put forward that the initial population was produced half-randomly, introduced inverse test vector fault simulation, and adopted logical correlative fault grouping and ordering. TG for ISCAS'85 combinational circuits based on PSO, CHPSO and CUPSO algorithms when adopting these speedup methods and not adopting these speedup methods have been implemented. The experimental results indicated that these three algorithms attained the same fault coverage as the best results in references and the speedup methods improved test efficiency greatly, and CUPSO with speedup methods attained the best result.Secondly, in view of sequential circuits having to be initialized before TG to set flip-flops to certain states, the logical initialization methods based on PSO, CHPSO and CUPSO were presented. On the base of initialization, TG for sequential circuits was carried out, and new fitness function was defined. Considering ISCAS'89 sequential circuits as object, the experimental results indicated that these three algorithms generated minimal-length initialization sequence and higher fault coverage, and CHPSO attained the highest fault coverage.Thirdly, in view of test set from usual TG methods being larger, minimizing test set statically based on PSO, CHPSO and CUPSO was brought forward. Pretreated test set, and if the test set included redundant test vectors, we optimized the test set to attain minimal complete one. Test-vector-coding or fault-coding can be adopted, and two kinds of fitness function definitions can be adopted accordingly. And initializing population with chaotic optimization, and inversing test vectors in test set to simulate have been put forward. Three experiments have been done to different circuits with PSO, CHPSO and CUPSO. The experimental results indicated that they shortened size of complete test set to different extent, and CUPSO with fault-coding attained the minimal size complete test set.Finally, in view of design for testability (DFT) of circuits needing extra components, combinational circuits DFT based on high-order syndrome was studied who implemented test generation depending on logical function, not needing to put extra components. That the method is not applicable in the circuit whose logical function is symmetrical to its all primitive inputs have been pointed out. Identifying redundant faults for sequential circuits by fault-value logical simulating forward was proposed. They have been proved feasible by examples.In conclusion, on the base of intelligent optimization algorithm, this paper have researched on test pattern generation, test set optimization, and DFT for digital integrated circuits. PSO, CHPSO and CUPSO have been applied, at the same time several speedup methods have been applied too. Experimental results indicated that the adopted intelligent optimization algorithms and the proposed speedup methods could attain good results.