Boolean Difference Techniques for Time-Sequence and Common-Cause Analysis of Fault-Trees

Fault trees are a major model for the analysis of system reliability. In particular, Boolean difference methods applied to fault trees provide a widely used measure of subsystem criticality. This paper generalizes the fault-tree model to time-varying systems and uses timedependent Boolean differences to analyze such systems. In particular, suitable partial Boolean differences provide maximal and minimal solution sets for sensitization conditions. A method of common-cause failure analysis based on partial time-dependent Boolean differences allows the study of failures due to repeated occurrences, at different times, of the same phenomenon. Such methods generalize to systems with repair, and under certain assumptions of independence, steady-state distributions can be used for the analysis of system faults. These methods are generally useful in reliability and sensitivity analysis.     

An improved algorithm for symbolic reliability analysis

The authors describe an efficient Boolean algebraic algorithm to compute the probability of a union of nondisjoint sets as applied to symbolic reliability analysis. Coherent networks and fault-trees with statistically-independent components characterized by their minimal pathsets or cutsets are used as examples for generating the nondisjoint sets. The algorithm uses the concept of multiple variable inversion originally proposed by A. Grnarov et al. (1979). The authors illustrate improvements in the use of the multiple variable inversion technique for this problem using two examples. The algorithm is extended to compute the reliability importance of a given component (sensitivity of system reliability to the component reliability). A computer program implementing the modified algorithm is used to solve and obtain measured time complexities for a large set of network and fault tree models     

Stack filter design using selection probabilities

Selection probabilities, viz. rank and sample selection probabilities, quantify the impulse suppression, robustness, lowpass filtering ability, and detail preserving ability of stack filters. Closed-form expressions exist for computing selection probabilities from positive Boolean function describing the stack filter. We first present an analysis framework that interprets a Boolean vector to denote membership in a partition set. Using this framework a new algorithm to compute selection probabilities from positive Boolean functions is derived. Next a method to synthesize a stack filter from specified selection probabilities is presented. An underdetermined system of linear Diophantine equations is derived in the unknown elements of the C-matrix and the desired selection probabilities. This system of equations is solved to obtain the candidate solutions for the C-matrix. For each candidate C-matrix, an algorithm based on partition sets is used to derive one or more positive Boolean functions of the stack filter or show that none exists.     

Digraph Matrix Analysis

This paper describes a systematic procedure for constructing a Boolean reliability model from plant schematics, and a technique for determining all sets of single and double component failures which will cause system failure. This technique, called digraph matrix analysis, uses a fault graph instead of the more traditional fault tree. Digraph matrix analysis was recently applied to the system interaction analysis of a very large safety system (over ten thousand components) and is being used to determine security system vulnerabilities.     

A Computer Program for Approximating System Reliability

A computer program, which provides bounds for system reliability, is described. The algorithms are based on the concepts of success paths and cut sets. A listing of the elements in the system, their predecessors, and the probability of successful operation of each element are the inputs. The outputs are the success paths, the cut sets, and a series of upper and lower reliability bounds; these bounds converge to the reliability which would be calculated if all the terms in the model were evaluated. The algorithm for determining the cuts from the success paths is based on Boolean logic and is relatively simple to understand. Two examples are described, one of which is very simple and the computation can be done by hand, and a second for which there are 55 success paths and 10 cuts and thus machine computation is desirable.     

Reliability Modeling and Analysis of Computer Networks

The reliability analysis of computer communication networks is generally based on Boolean algebra and probability theory. This paper discusses various reliability problems of computer networks including terminal-pair connectivity, tree connectivity, and multi-terminal connectivity. This paper also studies the dynamic computer network reliability by deriving time-dependent expressions for reliability measures assuming Markov behavior for failures and repairs. This allows computation of task and mission related measures such as mean time to first failure and mean time between failures. A detailed analysis of the bridge network is presented.     

A unified domination approach for reliability analysis of networkswith arbitrary logic in vertices

The concept of a probabilistic graph G has been used as a universal model for network reliability. Most of the literature on this subject concentrates on computing various reliability measures (such as k-terminal reliability or all-terminal reliability) which are the probability that vertices of G can communicate with other specified vertices. Primarily, this paper provides a common theoretical framework for addressing k-terminal reliability problems. To this end, it extends the model admitting vertex functions of G to be arbitrary monotone Boolean functions: in this case G is called a monotone (S,t)-graph. In such graphs the signal passability across a node is carried out in accordance with collections of signals delivered on the node inputs from other ones, the collections are subjected to some logic principle realized by a Boolean function. Monotone (S,t)-graphs include all known classes of directed multi-terminal network reliability models. The main result of this paper is the reliability expression for computing the probability of an acyclic monotone (S,t)-graph G being operational. The expression uses the local domination parameters introduced here. That reduces the system level of consideration to the element level, providing a unifying understanding of the combinatorial nature of some results based on the domination theory and developed earlier for ordinary networks     

On Boolean Techniques for Non Touching Loops of Signal Flow Graphs

Vertex disjoint (non touching) loops have to be processed to form all combinations of disjoint loops for Mason’s graph. Similarly Coates’ graph-based method needs all spanning disjoint loop sets. This is required to obtain the transfer function/solve equations of a system represented by Mason’s/Coates’ signal flow graph. A Boolean formula is presented in this note to obtain them. A Boolean function is formed comprising product of sums of pairs of touching loops for each connected component. It is then simplified using some rules of Boolean algebra. The resulting terms are “complemented” to derive all combinations of non touching loops for a Mason’s graph. Using an additional Boolean rule, the same formula gives all spanning disjoint loop sets of a Coates’ graph. The graph need not be connected.     

Reliability optimization in generalized stochastic-flow networks

A model and an algorithm for reliability optimization in generalized stochastic-flow networks are given. This algorithm uses the relationship of the k-weak-link sets and sets of failure events to the parameters of the generalized stochastic flow networks. This facilitates a fast location of the optimal capacity expansion for a system from the information obtained by the latest iteration and alleviates the dimension calamity on computation. Consequently, this reliability optimization method is powerful for large systems. As an example, the IEEE Reliability Test System with 24 nodes and 70 components was tested, revealing the components and their capacity values which should be enhanced. The computation results show that the algorithm can be applied to practical problems     

网络系统可靠度的BDD算法

文中研究3-状态设备网络系统2-终端可靠度的计算问题。BDD是布尔函数的图形表示形式。武小悦和沙基昌提出了一个采用BDD方法求2-状态网络系统的不交化最小路集,从而直接计算网络系统可靠度的算法。通过引入简化技术,结合归约公式和BDD技术,给出了一个计算3-状态设备网络2-终端可靠度的一个新算法;算法有效地消除了冗余项,并且产生的分枝树具有结点少,可有效得到可靠度符号表达式。     

微波测试系统中开关网络的设计与实现

设计了一种适用于地面站微波测试系统中的信号传输开关网络.基于开关网络的拓扑结构设计,不仅可实现测量仪表对被测系统多测试点和多路径的接入,还可通过测试电缆分组环接测量再用方程组求解的方法,实现测试电缆方便而精确的标校.另外,开关网络可通过局域网远程控制,并能方便地集成在整个测量系统中.实际测试结果表明,该开关网络的设计具...     

An Efficient Algorithm for Deducing the Minimal Cuts and Reliability Indices of a General Network Configuration

The paper describes an efficient algorithm for evaluating the minimal cut sets of any general network. The algorithm is based on Boolean algebra and set theory, and contains many important improvements. The four most important features are 1. only one set of topological input data is required to evaluate the minimal cuts and reliability indices of every output node; 2. a mix of undirectional, bidirectional and multi ended components can be included very simply; 3. any number of input nodes may be specified; 4. a new concept of overall system reliability permits different, large, and complex systems to be compared. The computational efficiency of the algorithm is clearly indicated by the fact that the time required to analyse Example 1 on a CDC7600 was 0.7 sec. The storage required with the appropriate arrays dimensioned for a system having 100 components and up to 125 minimal cut sets per output node is 15 k-words. These times and storage include the overall system reliability analysis.     

Universal delay test sets for logic networks

It has been shown earlier that, if we are restricted to unate gate network (UGN) realizations, there exist universal test sets for Boolean functions. Such a test set only depends on the function f, and checks any UGN realization of f for all multiple stuck-at faults and all robustly testable stuck-open faults. In this paper, we prove that these universal test sets are much more powerful than implied by the above results. They also constitute complete delay fault test sets for arbitrary UGN implementations of a given function. This is even true for UGN networks which are not completely testable with respect to the gate or path delay fault model. Our ability to prove the temporal correctness of such circuit realizations comes from the fact that we do not argue the correctness of individual paths, but rather complete path systems     

OBDD-based evaluation of k-terminal network reliability

An efficient approach to determining the reliability of an undirected k-terminal network based on 2-terminal reliability functions is presented. First, a feasible set of (k-1) terminal-pairs is chosen, and the 2-terminal reliability functions of the (k-1) terminal-pairs are generated based on the edge expansion diagram using an OBDD (ordered binary decision diagram). Then the k-terminal reliability function can be efficiently constructed by combining these (k-1) reliability expressions with the Boolean and operation. Because building 2-terminal reliability functions and reducing redundant computations by merging reliability functions can be done very efficiently, the proposed approaches are much faster than those which directly expand the entire network or directly factor the k-terminal networks. The effectiveness of this approach is demonstrated by performing experiments on several large benchmark networks. An example of appreciable improvement is that the evaluation of the reliability of a source-terminal 3/spl times/10 all-terminal network took only 2.4 seconds on a SPARC 20 workstation. This is much faster than previous factoring-algorithms.     

An improved method for symbolic reliability analysis

This paper describes a method for finding the terminal-pair reliability expression of communication networks. This method incorporates bit manipulation and Boolean operations for generating a sum of disjoint products (SDP) expression in which each term has 1:1 correspondence with respective minimal path (or cut). This method is convenient and efficient. An example of the method is given.     

A New Improved Method for Symbolic Reliability Analysis

ＡＮｅｗＩｍｐｒｏｖｅｄＭｅｔｈｏｄｆｏｒＳｙｍｂｏｌｉｃＲｅｌｉａｂｉｌｉｔｙＡｎａｌｙｓｉｓＭａｎｕｓｃｒｉｐｔｒｅｃｅｉｖｅｄＡｕｇ．２２，１９９６ＳｈｅｎＹｕａｎｌｏｎｇ（ＤｅｐａｒｔｍｅｎｔｏｆＥｌｅｃｔｒｏｎｉｃＥｎｇｉｎｅｅｒｉｎｇ，Ｎ...     

自动电话系统任务可靠性建模的探讨

通过对几种任务可靠性模型的比较,基于和联系统及任务重要度的概念,利用布尔真值表法建立了自动电话系统任务可靠性模型,并列出利用几种模型计算的任务可靠性度,将其进行比较,为自动电话系统任务可靠性预计提供了合理的数据,为准确预计系统任务可靠性奠定了基础。     

触发器泛特性方程

本文定义了触发器ＣＰ链布尔表达式，建立了触发器泛特性方程，举例说明在异步时序电路分析中的应用。     

Qualitative Analysis in Reliability & Safety Studies

The qualitative evaluation of system logic models is described as it pertains to assessing the reliability and safety characteristics of nuclear systems. Qualitative analysis of system logic models, i.e., models couched in an event (Boolean) algebra, is defined, and the advantages inherent in qualitative analysis are explained. Certain qualitative procedures that were developed as a part of fault-tree analysis are presented for illustration. Five fault-tree analysis computer-programs that contain a qualitative procedure for determining minimal cut sets are surveyed. For each program (SETS, MOCUS, PREP, MICSUP, ELRAFT), the minimal cut-set algorithm and limitations on its use are described. The recently developed common-cause analysis for studying the effect of common-causes of failure on system behavior is explained. This qualitative procedure does not require altering the fault tree, but does use minimal cut sets from the fault tree as part of its input. The method is applied using two different computer programs, COMCAN and SETS.     

Neural network for the reliability analysis of simplex systems

A new approach to the reliability analysis, based on neural networks, is introduced in this paper. The reliability analysis of a simple nonredundant digital system, Simplex System, with repair is used to illustrate the neural network approach. The discrete-time Markov model of simplex systems is realized using feed-forward recursive neural network. The energy function and update equations for the weights of the neural network are estabilished such that the network converges to the desired reliability of the simplex system under design. The failure rate and repair rate, satisfying the desired reliability, are extracted from the neural weights at convergence. The obtained results are verified by the conventional approach.