The Application And Research Of BDD To Combinational Circuits Test

With the development of the integrated circuits, the probability of emerging faults is higher and higher, and the fault detection becomes more and more important. The process of circuit design can be speeded up and the enormous benefit of economy can also be brought when the faults are fast and correctly detected. Binary decision diagram (BDD) is an effective data structure for representing Boolean functions. It is widely used in the fields of computer science and digital circuit and system. The main work of this paper is the applications of BDD in combinational circuits.First, the principle of BDD is introduced in this paper. The importance of variable ordering to a BDD is also illuminated. A heuristic variable ordering algorithm is presented, which can generate good variable ordering in a short time.Second, the operations of BDD are introduced in this paper. Apply algorithm and reduce algorithm can be used to construct the BDD of Boolean functions. Its example is given in this paper. Compared with the ITE algorithm, it is less effective. Two suggestions are made to the ITE algorithm.Third, the application of BDD to the test generation for combinational circuits is studied. The test generation methods of BDD avoid enormous backtracking process. They speed up the test generation and save the cost of test. However, their complexity is very high. An improved method named EBDDT is presented in this paper. It combines BDD and the path sensitized method and reduces the complexity. The experimental results demonstrate the efficiency of this method.Finally, the application of BDD to the test suppression is studied. BDD is used to suppress the test sets in this paper. A suppressed test set is generated, which reduces the test patterns and the cost of design.