Top-down Algorithm for Obtaining Prime Implicant Sets of Non-Coherent Fault Trees

An algorithm for finding all the prime implicant sets is given for non-coherent fault trees involving gates other than simple AND and OR, e.g., EOR and NOT. The sets are a generalization of min cut sets and can be used in quantitative and/or qualitative system reliability analysis. The algorithm is a top-down analysis and avoids sum of product expressions of top event, which usually involve a large number of terms. Each step of the algorithm is clearly defined and it is proven that all prime implicant sets can be obtained. The algorithm is efficient, and rather complicated trees can be handled manually.     

Optimal design of switching networks A topological approach†

The given functions specifications are represented as a reduced n-cell graph, and its incidence matrix is constructed. The prime implicant table for the given functions is then obtained by a systematic search of the matrix for sub-graphs satisfying certain properties. This table is represented as a linear graph, and the trees of this graph are tagged with a cost depending on the prime implicants in them. The tree with the minimum cost generates the desired optimal network.     

Classification of fault trees and algorithms of fault tree analysis

A new classification of fault trees is proposed, and the relationship between the new and old classifications is discussed. The new classification is illustrated with an example, and the limitation of the well-known simple prime implicant algorithm, which can work on fault trees, is shown. Thus a general unified algorithm for computer-aided fault tree analysis is presented.     

On the s-Importance of Elements and Prime Implicants of Non-Coherent Systems

This paper extends methods for evaluating the s-importance of elements and cut-sets of s-coherent systems to elements and prime implicants of non-coherent systems. Existing measures of s-importance are redefined to provide general expressions for the system elements and prime implicants when non-coherent systems are encountered. The redefined measures utilize the methodology of I&H and the absolute value of the influence of event i (or prime implicant j) on the top-event occurrence probability (or unavailability). An example illustrates the evaluation of the extended Birnbaum and critically measures of s-importance for a non-coherent system. Further research is required to implement the extended measures in procedures for determining optimum restoration sequences (assuming such sequences exist and are meaningful).     

An Algorithm for Obtaining Simplified Prime Implicant Sets in Fault-Tree and Event-Tree Analysis

Some fault trees or event trees use NOT logic in expressing an accident sequence. The number of prime implicant sets (PIS), a generalization of a minimal cut set and includes logical NOT as well as AND and OR, is apt to exceed general computer capacity. In order to deal with this problem, this paper assumes that component failure probability is far smaller than component success probability. Three steps are developed to delete certain sets of basic events from the fault tree of an accident sequence so as to obtain upper side approximate probability calculations and this with the number of PISs enumerated reduced to a practical level in most cases. Asymptotic convergence is proved and numerical examples are provided.     

Generation Methodology for Good-Enough Approximate Modules of ATMR

Approximate triple modular redundancy (ATMR) is sought for logic masking of soft errors while effectuating lower area overhead than conventional TMR through the introduction of approximate modules. However, the use of approximate modules instigates reduced fault coverage in ATMR. In this work, we target better design tradeoffs in ATMR by proposing a heuristic method that effectively utilizes a threshold for unprotected input vectors to generate good enough combinations of approximate modules for ATMR, which accomplishes higher fault coverage and reduced area overhead compared with previously proposed approaches. The key concept is to employ logic optimization techniques of prime implicant (PI) expansion and reduction for successively obtaining approximate modules such that the combination of three approximate modules appropriately functions as an ATMR. For an ATMR to function appropriately, blocking is used to ensure that at each input vector, through the prime implicant (PI) expansion and reduction technique, only one approximate module differ from the original circuit. For large circuits, clustering is utilized and comparative analysis indicates that higher fault coverage is attained through the proposed ATMR scheme while preserving the characteristic feature of reduced area overhead. With a small percentage of unprotected input vectors, we achieved substantial decrease in transistor count and greater fault detection, i.e., an improvement of up to 26.1% and 42.1%, respectively.     

化简开关函数的图论方法

本文引入了n变量开关函数F(x1,,xn)的伴随图G和伴随超图H的概念,导出了下列方法和算法:(1)求F的所有本原蕴含项的图论方法和分支定界算法BBAPI;(2)应用超图理论求F的最小和表达式的算法AMSHT。这些方法简单、直观;既便于手算,也便于用计算机实现;计算效率高于常用的卡诺图法和Q-M列表法。     

Mathematical foundations of minimal cutsets

Since their introduction in the reliability field, binary decision diagrams have proved to be the most efficient tool to assess Boolean models such as fault trees. Their success increases the need of sound mathematical foundations for the notions that are involved in reliability and dependability studies. This paper clarifies the mathematical status of the notion of minimal cutsets which have a central role in fault-tree assessment. Algorithmic issues are discussed. Minimal cutsets are distinct from prime implicants and they have a great interest from both a computation complexity and practical viewpoint. Implementation of BDD algorithms is explained. All of these algorithms are implemented in the Aralia software, which is widely used. These algorithms and their mathematical foundations were designed to assess efficiently a very large noncoherent fault tree that models the emergency shutdown system of a nuclear reactor     

Application of fuzzy logic to reliability engineering

The analysis of system reliability often requires the use of subjective-judgments, uncertain data, and approximate system models. By allowing imprecision and approximate analysis fuzzy logic provides an effective tool for characterizing system reliability in these circumstances; it does not force precision where it is not possible. Here we apply the main concepts of fuzzy logic, fuzzy arithmetic and linguistic variables to the analysis of system structures, fault trees, event trees, the reliability of degradable systems, and the assessment of system criticality based on the severity of a failure and its probability of occurrence     

一种新的基于最小项逻辑优化的软件设计与实现

文章提出了一个新的产生本源蕴涵项的算法，并形成了相应的组合逻辑电路逻辑综合优化软件，测试表明，它在运算速度和存储性能上都是高效的。     

Concerning the maximum number of essential prime implicants in a Boolean function

It is proved that the maximum number of essential prime implicants in a Boolean function with n variables is 2n?1, or the number of its canonic terms T if T is less than 2n?1.     

逻辑函数化简语义树

提出了一种逻辑函数化简语义树算法，其特点是在求全部本源蕴涵项和从本源蕴函项集合中选取最小覆盖两步中都采用同一算法，因此，算法程序的编写可较为简单，最后，从解题质量和解题速度等方面对该算法进行了评价。     

On the Walsh-Hadamard Transform and Prime Implicant Extraction

The Walsh-Hadamard transform (WHT) provides a one-to-one mapping of n-variable Boolean functions onto an n-dimensional transform space. As such, it enables synthesis procedures to be carried out in the transform domain. This short paper discusses the role of the WHT in extracting prime implicants, which is pertinent to the overall minimization problem. First, a procedure to identify all the prime implicants of a 1-vertexl located at the origin is developed by inspecting the elements of a single inverse transform. Second, a theorem is proved to show how the signs of the transform coefficients can be changed, to obtain all the prime implicants of an arbitrazy 1-vertex via the same inverse transforn operation.     

ESPRESSO-SIGNATURE: a new exact minimizer for logic functions

An algorithm for exact two-level logic optimization that radically improves the Quine-McCluskey (QM) procedure is presented. The new algorithm derives the covering problem directly and implicitly without generating the set of all prime implicants. It then generates only those prime implicants involved in the covering problem. A set of primes is represented by the cube of their intersection. Therefore, the unique set of sets of primes that forms the covering problem can be implicitly represented by a set of cubes that forms a minimum canonical cover. The minimum canonical cover starting from any initial cover is obtained and then the covering problem is derived. The method is effective; it improves on the runtime and memory usage of ESPRESSO-EXACT by average factors of 1.78 and 1.19, respectively, on the 114 of 134 benchmark examples that could be completed by ESPRESSO-EXACT. Of the remaining 20 hard problems, 14 are solved exactly. For three of the remaining six, the covering problem is derived but it can not be solved exactly     

Modeling reflex-healing autonomy for large-scale embedded systems

High-energy physics experiments require an extraordinary amount of real-time computation, and the computers implementing the online data processing must be very reliable because of the large cost associated with operating the facilities and the potential for loss of irreplaceable data. Conventional redundancy-based fault tolerance and adaptive approaches are not appropriate because of the tremendous system cost (fault tolerance is limited to a maximum of 10% overhead). In this work, we developed a framework for building robust embedded systems, which utilizes an autonomic reflex-healing approach to achieve fault tolerance. Components of the framework implement user-defined failure adaptation strategies within the context of a large-scale embedded environment. The tools embrace a model-based approach combining design specification and code-generation for both simulation and system implementation. In this paper we present the concepts and entities of the reflex and healing framework.     

Advanced hand calculations for fault tree analysis and synthesis

In many areas of engineering, hand calculations are mainly used for (1) small exercises, (2) checking new algorithms and (3) rough approximations. In all of these areas, especially in a modern extension of the second one, namely the testing of (software) tools, there is an ever increasing interest in better hand calculations. This paper presents a variety of concepts and tricks for advanced hand calculations in the field of fault trees, covering both analysis and synthesis. Only refined graph reductions are precluded.     

Modularizing, Minimizing, and Interpreting the K&H Fault-Tree

The verification by Worrell & Stack (W&S) of results previously obtained by Kumamoto & Henley (K&H) for a fault tree of an s-noncoherent system and its inverse and their correction of the three errors in the tree makes it possible to simplify the analysis by forming modules; this facilitates Boolean algebraic operations, so that both sets are described economically in their minimal forms, a subset of the prime implicants (p.i.'s). Quine's consensus operation is used to minimize and to find the p.i.'s. Corresponding to the MOCUS output for the inverse reported by K&H, which is neither minimal nor the set of p.i.'s, instead of 32 terms, there are 15 in the modularized set. Instead of the 42 p.i.'s obtained by both K&H and W&S, we have 17; 13 of these are a unique minimal form. Instead of 352 p.i.'s for the tree per both K&H and W&S, we have a 15-term minimal form, identical to the list of p.i.'s. The results are further analyzed as a contribution to the continuing discussion of the utility of minimal forms vis-a-vis the p.i.'s and of the consensus method.     

Evaluating fault trees (AND and OR gates only) with repeated events

It is pointed out that a common practice in the evaluation of large fault trees is to truncate the computation by neglecting high-order or low-probability cutsets. A major disadvantage of most simple truncation methods, however, is that their accuracy is indeterminate because they do not establish rigorous bounds on the combined probability of the neglected cutsets. A truncated with residuals algorithm is presented. It uses probability-based truncation and determines a rigorous upper bound on each event-probability by propagating the effect of all the truncated cutsets in the form of numeric residuals. The method applies only to fault trees constructed entirely of AND and OR gates and allows unrestricted use of repeated events