A simple component-connection method for building binary decision diagrams encoding a fault tree

https://doi.org/10.1016/S0951-8320(00)00048-XGet rights and content

Abstract

A simple new method for building binary decision diagrams (BDDs) encoding a fault tree (FT) is provided in this study. We first decompose the FT into FT-components. Each of them is a single descendant (SD) gate-sequence. Following the node-connection rule, the BDD-component encoding an SD FT-component can each be found to be an SD node-sequence. By successively connecting the BDD-components one by one, the BDD for the entire FT is thus obtained. During the node-connection and component-connection, reduction rules might need to be applied. An example FT is used throughout the article to explain the procedure step by step.

Our method proposed is a hybrid one for FT analysis. Some algorithms or techniques used in the conventional FT analysis or the newer BDD approach may be applied to our case; our ideas mentioned in the article might be referred by the two methods.

Introduction

Since the early 1970s, fault tree (FT) analysis using the conventional substitution–expansion–minimization approach have been investigated a lot. Recently, there has been new interest in the use of the binary decision diagram (BDD) for the FT analysis [1], [2], [3], [4], [5], [6], [7]. This kind of diagram was first introduced by Lee [8], popularized by Akers [9], and improved by Bryant [10], [11]. The BDD provides a new method for the representation and manipulation of Boolean functions, which is different in data structure from the classical methods, such as the truth table, Karnaugh map, or canonical sum-of-products (s-o-p) form [12]. BDDs are nowadays used in many domains, such as hardware design and verification, protocol validation and automatic deduction (for a survey of BDDs and their applications, see Ref. [11]).

The BDD approach for FT analysis was initiated by Rauzy [7] for a coherent FT. The basic events in the FT must be given an ordering in advance. Then the FT is transformed into the BDD structure using the BDD operation under the specified basic-event-ordering. The cut sets (CSs) obtained from the resulting BDD structure might not be minimal even if the FT is fully modular (the modular FT is an FT in which all events and all gates are referred only once). The BDD must undergo a minimizing operation to create the minimized BDD structure that, thus, gives only the minimal cut sets (MCSs) of the FT. InRef. [2] Rauzy and Dutuit further considered truncated approximation while obtaining the BDD for a big FT.

The ordering of the basic events in FT or of the variables in other applications determines the size of the resulting BDD. Berman [13], while discussing a variable ordering and the size of the BDD for a circuit structure, presented a decomposition of the circuit into the composition of two smaller circuits. As to the FT, Bouisson [5] discussed the module for the basic event ordering investigation. For this, the FT is simplified in advance as the conventional FT analysis.

Our new method for FT analysis seems to be a hybrid one. This method is the same as the conventional FT analysis that do not set basic event ordering. The gates of the FT are traversed in the ‘depth-first left-most’ (DFLM) way. In the traversal, the BDD structure is set straightforward. This is similar to the substitution for the conventional FT analysis. In other words, we do not use the BDD operation to obtain the BDD structure; what we do is just ‘to set’ the structure. The minimization is carried out while building the BDD. This is different from the BDD approach for the FT analysis. This is also different from the conventional FT analysis. In the latter case, the Boolean formula for the FT is expressed in the s-o-p form and then some Boolean absorption is performed. In our case, the Boolean formula is expressed in the BDD data structure.

To give some background to our method, Fig. 1 shows some simple FTs and their BDDs. A basic event x of the FT, or a Boolean expression f=x, is typically represented in BDD by a node having the if-then-else (ite) structure ite (x, 1, 0), as shown in Fig. 1a. This means that if x is true, then f is true, or else f is false. For simplicity, we shall, in the latter part of this article, use a simplified form of BDD for the representation of a FT. In this kind of simplified BDD form, the logic constant 1-node and 0-node are all omitted, as shown in Fig. 1b. As our present interests are limited to the discussion of coherent FTs, in which a gate is either an AND-gate or an OR-gate, no ambiguity should arise from this kind of omission. In Fig. 1b, the 1-leg of x is written as AND-leg, and the 0-leg is written as OR-leg. They are interchangeable. If y and x are AND-related together, y is simply connected to the AND-leg of x; if y and x are OR-related together, y is simply connected to the OR-leg of x. These are shown in Fig. 1c and d where the BDDs are just representing the corresponding FTs or Boolean expressions.

Fig. 1e shows an FT bigger than the FTs corresponding to Fig. 1c and d. The corresponding BDD as shown in Fig. 1f can be drawn without difficulty from the Boolean logical argument. Four CSs are ‘seen’ from this BDD also shown in Fig. 1f. It is reminded here that the BDDs in the article are drawn for illustration. To implement our method in a computer program, the BDDs are stored in node-data-structure as shown in Fig. 2 of Ref. [7] where equivalent sub-graphs, if any, are shared while the computer memory is managed. By traversing the node-data-structure information, a computer can ‘see’ the diagram and can obtain all CSs using the algorithm as shown in Fig. 4 of Ref. [7]. If necessary, the truncation approximation may be included in the algorithm for a big FT.

The FT in Fig. 1e shows a single-descendent (SD) gate sequence, in which a mother-gate has at most one daughter-gate. For this kind of FT, the BDD is in the zigzag form as shown in Fig. 1f and this kind of BDD will be named as zigzag BDD or SD BDD. It must be reminded here that basic-event-daughters, if any, are first put under the mother-gate in the FT as shown in Fig. 1e. In other words, under the mother-gate, the daughter-basic-events are elder sisters of other daughter-gates. In Section 3, more information is given to explain how to obtain the SD BDD for a SD-gate-sequence FT using node-connection rule. If an SD-gate-sequence FT is not a modular one, while building the BDD, the reduction rules mentioned in Section 5 are applied, and the resulting SD BDD is still in the zigzag form.

The simple FT in Fig. 1g is a modular one. The BDD obtained from the BDD operation is ite (a, ite(b, 1, ite(c, ite(d, 1, 0), 0)), ite(c, ite(d, 1, 0), 0)). This is not minimal. That is, the CSs obtained from the BDD could be non-minimal even the FT is modular. The BDD has to be minimized using the algorithm as shown in Fig. 6 of Ref. [7]. However, the minimization for the case of modular FT is not needed when using the conventional FT analysis or our hybrid approach. Fig. 1h shows our resulting BDD.

The FT in Fig. 1g is not an SD-gate-sequence FT. We consider the FT as a composition of several SD-gate-sequence FT-components. The BDD for each FT-component is set as a zigzag form and the resulting zigzag BDD components are then connected stage by stage. Some reduction-rules in Section 5 are used while the node-connection and the component-connection is performed. In the following sections, details of our hybrid method are described step by step through an example FT as shown in Fig. 2.

Section snippets

The FT-components and their respective ranks

For a given FT, to build a BDD encoding it, we first decompose it into several FT-components. Each of them is an SD-gate-sequence FT structure, and, starting from some specific gate containing the top gate of the FT-component in the FT, terminates only at a certain basic-event gate of the FT. There is no intersection among them. The union of the total of them is the FT itself. For example, the FT in Fig. 2 can be decomposed into four FT-components A–B, C–D–E–F, G, and H–I–J, as shown in Fig. 3.

BDD-components and node-connection rule

In this section, we first introduce the rule to build an SD BDD for an SD FT. We then describe the one-to-one correspondence between a gate in (an SD) FT and a straight line in (its corresponding SD) BDD. The BDD-components are discussed at the end of this section.

Build a BDD encoding of an FT stage by stage

To simplify the statements, the BDD encoding of an entire FT is denoted by BDDFT, that encoding FTstage n by BDDstage n, and that encoding component FTn by component BDDn for n=1,2,…,N. In this notation, BDDstage 1=BDD1, and BDDFT=BDDstageN.

For a given set of N BDD-components, we may build a BDD encoding an FT stage by stage, in a total number of N stages. The BDDFT-building procedure is given as follows:

  • In stage 1, take BDDstage 1 to be component BDD1.

  • In stage 2, build BDDstage 2 by connecting

Reduction rules

To remove the non-minimal CS from the resulting BDD, while building BDD-components and connecting the BDD-components, we suggest five kinds of reduction-rules. For mnemonic considerations, we name four of the five as intra-AND reduction-rule, intra-OR reduction-rule, inter-AND reduction-rule, and inter-OR reduction-rule. The first part of the name is called “intra” or “inter” to stand for, respectively, “just this working CS is involved” or “some other CSs are involved, in addition to this

Discussions

As mentioned before, our method seems a hybrid one of the conventional FT analysis and the newer BDD approach. In one hand, we may borrow something from the literature of the two approaches; in other hand, we encourage the research community to think the potential it may offer.

It is known that each path from the top node of a BDD to the 1-node defines a CS of the BDD. And how to obtain all the CSs from the BDD structure was mentioned in Rauzy's paper [7]. If truncated approximation for a big FT

Conclusions

For building a BDD encoding an FT, we have provided a new method. The four key points of our method are as follows: (1) The gates in the FT are traversed from the top in the DFLM way to decompose the FT into several SD-gate-sequence FT-components. (2) The BDD-component for each FT-component could be set as a zigzag BDD form following the node-connection rule. (3) The BDD-components are then connected stage by stage following the component-connection rule. (4) During the node-connection and the

Acknowledgements

We are indebted to Dr Shyn-Jen Lee, a colleague, for providing us with the latest references about BDDs, and for the useful suggestions he gave us when we discussed the FTs with him. We are also pleased to extend our thanks to Mr Ching-Kai Yeh, another colleague, who drew the figures included in this paper; and we are grateful to Mr Ching-Hui Wu, Dr Tsu-Mu Kao, our colleagues as well, and Dr Richard A. Riemke, of the Idaho National Engineering and Environmental Laboratory, USA, for their proof

References (15)

There are more references available in the full text version of this article.

Cited by (21)

  • Methods and models in process safety and risk management: Past, present and future

    2015, Process Safety and Environmental Protection
    Citation Excerpt :

    The properties of BDD itself also can be used to estimate the minimal cut set by transforming the fault tree into a BDD (Sinnamon and Andrews, 1997). Way and Hsia (2000) discussed a simple component-connection method to build a BDD encoding fault tree. Reay and Andrews (2002) restructured the complex fault tree into smaller and simple sub-trees using a two-stage process.

  • Fault tree analysis: A survey of the state-of-the-art in modeling, analysis and tools

    2015, Computer Science Review
    Citation Excerpt :

    Fig. 5 shows how a different variable ordering affects the size of the resulting BDD. Remenyte and Andrews [43,44] have compared several different methods for constructing BDDs from FTs, and conclude that a hybrid of the if–then–else method [39] and the advanced component-connection method by Way and Hsia [54] is a good trade-off between processing time and size of the resulting BDD. Improvements to BDD.

  • A novel decision diagrams extension method

    2014, Reliability Engineering and System Safety
    Citation Excerpt :

    Based on references [4,6], Bryant investigated the full potential for efficient algorithms based on reduced ordered BDD (ROBDD) in 1986 [7], ROBDD first encodes the model in a compact data structure, and has time complexity proportional to the sizes of the graphs being operated on. As a well-known alternative to the minimal cut sets approach to assess the reliability Boolean models, BDDs has been investigated to solve large fault trees: Rauzy [3] introduced a BDD-based method for fault tree management, which supplies the efficient computation of both the minimal cut sets of a fault tree and the probability of its top event; Way and Hsia [8] developed a special method to build a BDD encoding fault tree by decomposing the fault tree into components; the size of a BDD structure depends critically on variable ordering and the determination of an appropriate variable ordering has a highly heuristic nature [9,10]; Jung, Han and Ha [11] presented a coherent BDD algorithm for coherent fault trees, the construction of the BDD structure was simplified by subsuming subset and truncating if-then-else (ITE) connectives with a probability or size limit in the intermediate BDD structure; Remenyte-Prescott and Andrews [12] conversed the fault tree to BDD by ordering the basic events and merging sub-BDDs to represent a parent gate; Ibáñez-Llano, Rauzy, Meléndez and et al. [13] reduced the BDD model through the set of the most relevant minimal cut sets. BDD has also been applied in the areas of reliability analysis of phased-mission systems (PMS): Xing and Levitin [14] used BDD in the reliability evaluation of non-repairable binary PMS with common-cause failures (CCF); Zhang, Sun and Trivedi [15] presented a new PMS-BDD algorithm, phase algebra was used to deal with the dependence across the phases, and the phase algebra was incorporated by a new BDD operation.

View all citing articles on Scopus
View full text