Research On BDD And Its Applications To Circuits Test Generation And Reliability

BDD( Binary Decision Diagram)is the state-of-the-art data structure in logic function. It is widely used in the fields of computer science and digital circuit and system. First, this paper introduces the principle and correlative conclusions of HDD, and illuminates the important of variable ordering to a BDD. A simple and easy using variable ordering algorithm is presented, which doesn't involve in the knowledge of other fields.Second, this paper also discusses the construction of BDD. According to the popular ITE (IF-THEN-ELSE) algorithm, we construct the BDD by C++ program. It can give BDD presentation of Boolean function or arbitrary combination logic circuits which are presented by CDL, and can realize different operation of Boolean function by the operation to BDD.Finally, We study two applications of BDD. The first one is the fault detect of combinational logic circuits. The test vector set of the circuit can be obtained through constructing a test BDD. Compared with the traditional algorithms, this method avoids enormous backtracking process. The second application is the network reliability based on BDD. Reliability is an important parameter in evaluating the performance of a communication network. Anew algorithm of computing networks reliability by using binary decision diagrams (BDD) is presented in this paper. The algorithm can get a much simpler BDD diagram than the other algorithms, and can reduce the complexity of the computation efficiently.