Research On Variable Ordering Methods Of Binary Decision Diagram Base On Common Events

Binary Decision Diagram (BDD) has been widely used in many areas including digital system design and system reliability analysis due to its efficient structure for representing and manipulating Boolean functions. BDD technology has shown its advantage of low computational complexity and efficiency when used to solve large fault trees in the system reliability domain. Fault tree analysis(FTA), an important branch in systems reliability engineering, is a common practical technique used in evaluating reliability and safety for large-complex systems presently. Fault Tree Analysis has been widely used to assess the system risk in many domains. The analysis of the fault tree involves obtaining the various combinations of events which cause the system failure; it’s also called minimal cut sets. The probability of the system failure could be calculated by quantitative analysis of these minimal cut sets if the basic events’failure probability is given. However, when a fault tree is large and contains repeated events, the traditional approach to obtain the minimal cut sets becomes difficult and sometimes even unsolvable.To solve this problem the Binary Decision Diagram (BDD) methodology has been applied into system reliability domain. Utilizing this technique involves converting the fault tree into an alternative logic representation. The most important step of this converting is the ordering of the basic events. But, the analysis process only is efficient if the BDD can be generated and the size is acceptable. The key problem of the conversion is the ordering of basic events. A good variable ordering can result in a very efficient analysis and a poor ordering even couldn’t generate a BDD. Bryant put restrictions on the ordering of decision variables in the vertices which leads to a canonical form for Boolean function representation. Many BDD variable ordering approach in fault tree area are based on this ordering restriction, which means that during the conversion from a fault tree into a BDD form, the decision variable ordering maintain fixed. Although the fixed ordering methods can keep a unique BDD form for a fault tree, it may not produce a minimal size BDD. This thesis applies the progressive ordering method to generate BDD and introduces a new ordering scheme base on common events.