The Research Of Test Generation Method For Combinational Circuits Based On Binary Decision Diagrams

Digital-system's performance is higher than before, and its integration degree also increases rapidly. All these developments are for the improvement of IC (Integrated Circuit) design and manufacturing technology. Especially as the appearance of SoC (System-on-a-Chip), IC industry request more advanced products with shorter design and developing cycle, smaller volume and higher performance. This trend makes a big challenge for circuit test, and to develop efficient methods for test generation is the key point of improving test quality and speed.Theory system of BDD (Binary Decision Diagrams) matures in recent years. More and more applications based on BDD in IC design and test field have been developed. These applications include design verification, logic synthesize and test generation.The main works of the thesis are showed as follow:This thesis described the principle and types of testing, fault models, fault collapsing and some evaluation measures. It introduced some main ATPG (Automatic Test Pattern Generation) algorithms in IC testing part. Later it discussed BDD's fundament and basic operation algorithms.The first scheme made a primary research in BDD minimization. The method improved traditional exact BDD minimization with adjacency symmetric variables in Boolean expression based on studying of original algorithm. It reduced redundant operations in original algorithm. Experimental results showed that improved algorithm has the excellence of mathematics strictness and optimal result as original algorithm, moreover it could efficiently decrease operation time cost.The second scheme developed a new test generation method for single stuck-at faults in CUT (Circuits Under Test). The method improved idea of Boolean difference with BDD's structural properties based on studying of BDD and Boolean difference. For test generation of a complete circuit, the method divided a whole circuit into parts of several sub-circuits based on dependence of PIs (Primary Input) and POs (Primary Output). Fault simulation was inserted at the end part of every sub-circuit's test generation to make fault-dropping, and this operation could reduce target faults and time cost. Experimental results on ISCAS-85 benchmark circuits showed that the method could effectively generate test vectors for combinational circuits. Besides, this method could also identify redundant structure of circuits and its relative complete result offered a potential for test set collapsing.