Research On Faulty Test Pattern Generation Methods For Digital Circuits

IC industry is a fast growing field for the world economy. It is essential to ensure theirreliability and quality. While IC manufacturing testing is one of important means of onlyshipping the good products. Many tasks essential for developing adequate tests, generally fallinto four categories: design for testability (DFT), test pattern generation, pattern-grading, andtest program development and debugging. The focus in this paper is on test pattern generationand pattern-grading.As the complexity of VLSI circuits and their quality requirements are increasing, theproblem of test generation is becoming more important and more difficult. Today the DFTtechnique of full scan is becoming a de facto standard for testing and diagnosis for sequentialcircuits in the electronic industry. This transforms the problem of sequential test patterngeneration into the problem of combinational generation. Therefore, test generation forcombinational circuits is getting even more important.ATPG is one of the most difficult problems for electronic design automation (EDA)because their research topics and subtopics concerned are NP hard which are intensive in boththeory and practice. It has been a popular research topic in EDA because it closes to the testingeconomy and fast evolution of semiconductor technology. Their aims were primarily to speedup test generation, and improve the quality of test pattern. This dissertation makes a intensive study of the subject of TPG in theory and practice,which include the representation of Boolean functions, formal dealing with logic circuit, faultmodeling, fault simulation and various technology and heuristics of test pattern generation forcombinational circuit. It systematically analyzed and summarized theories and literatures abouttest generation, and studied modern SAT algorithms and ROBDD algorithms shown how thesealgorithms can account for structural information in combinational circuits, and explained whatvarious learning can be added to SAT. This paper presents fault-mapping techniques in fault simulation and modeling approachbased on Boolean satisfiability to solve the problem of test pattern generation for combinationalcircuits. The main contents as follows:1. Fault modeling techniques, and fault collapsing techniques for the single stuck-at faultmodel by means of the fault relations of equivalence and dominance.2. Modern SAT algorithms and base on SAT methods of circuit modeling, presenting aformal ATPG approach which combination into the topological information about the circuitunder test.3. Transformation methods from non-clausal SAT problems to CNF formulas, and thesolution for ATPG based on SAT.4. Presenting 4-value parallel fault simulation technology based on fault-mapping thatmapping of nonstem faults to stem faults, which reduced the passes of explicit simulation in par-allel and greatly enhanced the performance of simulator.5. Exploring an effective means of having SAT methods co-operate with establishedengines such BDDs, structural ATPG methods etc. which have traditionally formed themainstay of EDA tools. Presenting the BDD learning technique based on TRL from the networkstructures.It decouples the correlation between the value assignment of local signal. In otherwords, we first exploit inexpensive reconvergent fanout analysis of circuit to gather informationon the local signal correlation by using BDDs, i.e., we explore the use of learning from BDDs,where learned clauses generated by BDD-based analysis are added to the SAT search engine, tosupplement its other learning mechanisms. We then use the above learned information to restrictand focus the overall search space of SAT-based ATPG. Our learning technique is effective andlightweight. Furthermore, we transform the heuristics from structure into CNF, which furtherprune the search tree. We use the 2-SAT algorithms to speed up the solution of ATPG.6. Presenting an additional layer that maintains circuit-related information and valuejustification relations to a generic SAT algorithm. This approach eliminates some of thedrawbacks of using CNF models and SAT algorithms in TPG—the inaccessibility to structuralinformation and overspecification of test patterns. 7. Engineering and implementing a prototype ATPG framework in the C++ programminglanguage, and the experimental results demonstrating the robustness and effectiveness of ourtechniques.