Research On Variable Ordering Methods Of Binary Decision Diagram

With the development of technology, people have great demands for the safety and reliability of a system. Fault Tree Analysi(sFTA) has been widely used for quantitatively and qualitatively analysis on the reliability of a system. An efficient way to analyze a fault tree is Binary Decision Diagram (BDD) method, which can take advantage of computer technology to automatically deal with a large scale fault tree. However, in order to use this method, the fault tree has to be converted into a BDD format first. During the conversion process, the variable ordering problem is a key issue for a good BDD’s generation. Although there are several ordering methods available, no one method has been found suitable to all kinds of the fault trees. In this paper, a novel ordering method, named as Progressive Neighbor First, is proposed. Based on existing methods, this new method emphasizes the logical relationship of the basic event variables. And during the process of the BDD conversion, it will choose the basic event variables that have been fixed statically in a dynamical way, allowing different ordering on each path of the diagram. After detailing the principle and steps of this method, it has been programmed with C language for widely use. Compared with the existing best BDD ordering heuristics, the proposed scheme can achieve performance improvement on 75% of test cases. This thesis also introduces the concept of modules. The proposed new method and modules are combined as Modular Progressive Neighbor First ordering method, which improves the possibility of converting large scale fault tree into BDD.