Cultural Algorithm for Minimization of Binary Decision Diagram and Its Application in Crosstalk Fault Detection

The binary decision diagrams （BDDs） can give canonical representation to Boolean functions; they have wide applications in the design and verification of digital systems. A new method based on cultural algorithms for minimizing the size of BDDs is presented in this paper. First of all, the coding of an individual representing a BDDs is given, and the fitness of an individual is defined. The population is built by a set of the individuals. Second, the implementations based on cultural algorithms for the minimization of BDDs, i.e., the designs of belief space and population space, and the designs of acceptance function and influence function, are given in detail. Third, the fault detection approaches using BDDs for digital circuits are studied. A new method for the detection of crosstalk faults by using BDDs is presented. Experimental results on a number of digital circuits show that the BDDs with small number of nodes can be obtained by the method proposed in this paper, and all test vectors of a fault in digital circuits can also be produced.

A New Method for the Detections of Multiple Faults Using Binary Decision Diagrams

With the complexity of integrated circuits is continually increasing, a local defect in circuits may cause multiple faults. The behavior of a digital circuit with a multiple fault may significantly differ from that of a single fault. A new method for the detection of multiple faults in digital circuits is presented in this paper, the method is based on binary decision diagram （BDD）. First of all, the BDDs for the normal circuit and faulty circuit are built respectively. Secondly, a test BDD is obtained by the XOR operation of the BDDs corresponds to normal circuit and faulty circuit. In the test BDD, each input assignment that leads to the leaf node labeled 1 is a test vector of multiple faults. Therefore, the test set of multiple faults is generated by searching for the type of input assignments in the test BDD. Experimental results on some digital circuits show the feasibility of the approach presented in this paper.

Fault Tree Analysis of a Launching with Binary Decision Diagram Method and Fuzzy Theory

Fault tree analysis(FTA),as a structurally simple,visualized and scientific method,is widely used in various fields.To complete the FTA of the launching device,the binary decision diagram(BDD)method is used to obtain the non-intersect cut sets,the minimum cut sets and the probability importance of components.Then,the expert evaluation method is applied to solving fuzzy probability rate of bottom event with zero failure data.In this paper,the BDD and expert evaluation method are applied into FTA to analyze a launch device.

Reliability Analysis of Electrical System of CNC Machine Tool Based on Dynamic Fault Tree Analysis Method

The electrical system of CNC machine tool is very complex which involves many uncertain factors and dynamic stochastic characteristics when failure occurs.Therefore,the traditional system reliability analysis method,fault tree analysis(FTA)method,based on static logic and static failure mechanism is no longer applicable for dynamic systems reliability analysis.Dynamic fault tree(DFT)analysis method can solve this problem effectively.In this method,DFT first should be pretreated to get a simplified fault tree(FT);then the FT was modularized to get the independent static subtrees and dynamic subtrees.Binary decision diagram(BDD)analysis method was used to analyze static subtrees,while an approximation algorithm was used to deal with dynamic subtrees.When the scale of each subtree is smaller than the system scale,the analysis efficiency can be improved significantly.At last,the usefulness of this DFT analysis method was proved by applying it to analyzing the reliability of electrical system.

Analysis of Phased-Mission System Reliability and Importance with Imperfect Coverage

Accounting for static phased-mission systems (PMS) and imperfect coverage (IPC), generalized and integrated algorithm (GPMS-CPR) implemented a synthesis of several approaches into a single methodology whose advantages were in the low computational complexity, broad applicability, and easy implementation. The approach is extended into analysis of each phase in the whole mission. Based on Fussell-Vesely importance measure, a simple and efficient importance measure is presented to analyze component’s importance of phased-mission systems considering imperfect coverage.

System reliability evaluation method considering physical dependency with FMT and BDD analytical algorithm

Recently, the physics-of-failure(PoF) method has been more and more popular in engineering to understand the failure mechanisms(FMs) of products.However, due to the lack of system modeling methods and problem-solving algorithms,the information of FMs cannot be used to evaluate system reliability.This paper presents a system reliability evaluation method with failure mechanism tree(FMT) considering physical dependency(PDEP) such as competition, trigger, acceleration, inhibition, damage accumulation, and parameter combination.And the binary decision diagram(BDD) analytical algorithm is developed to establish a system reliability model.The operation rules of ite operators for generating BDD are discussed.The flow chart of system reliability evaluation method based on FMT and BDD is proposed.The proposed method is applied in the case of an electronic controller drive unit.Results show that the method is effective to evaluate system reliability from the perspective of FM.

Fault Tree Analysis of CNC Machine Tool Based on BDD Technology

CNC machine tool is a large complex system which contains both mechanical and electrical components.As one of these components,the spindle is crucial for the performance of CNC machine tool.To improve the quality of CNC machine,the reliability of spindle was evaluated in this paper using a fault tree analysis(FTA)method.The FTA method is a set of calculation methods based on Boolean algebra.However,it is difficult to analyze a large and complex fault tree with inaccurate results and low efficiency as well as the complexity of time and space.Both of them will result in the so-called "combinatorial explosion".To overcome this problem,the analysis method based on binary decision diagram(BDD)was introduced in our works,and a sorting method about bottom events was also recommended which can reduce the size of the BDD effectively.

A new approach to fuzzy dynamic fault tree analysis using the weakest n-dimensional t-norm arithmetic

Dynamic fault tree analysis is widely used for the reliability analysis of the complex system with dynamic failure characteristics. In many circumstances, the exact value of system reliability is difficult to obtain due to absent or insufficient data for failure probabilities or failure rates of components. The traditional fuzzy operation arithmetic based on extension principle or interval theory may lead to fuzzy accumulations. Moreover, the existing fuzzy dynamic fault tree analysis methods are restricted to the case that all system components follow exponential time-to-failure distributions. To overcome these problems, a new fuzzy dynamic fault tree analysis approach based on the weakest n-dimensional t-norm arithmetic and developed sequential binary decision diagrams method is proposed to evaluate system fuzzy reliability. Compared with the existing approach,the proposed method can effectively reduce fuzzy cumulative and be applicable to any time-tofailure distribution type for system components. Finally, a case study is presented to illustrate the application and advantages of the proposed approach.

Reliability evaluation of wireless sensor networks using an enhanced OBDD algorithm

An enhanced ordered binary decision diagram （EOBDD） algorithm is proposed to evaluate the reliability of wireless sensor networks （WSNs）, based on the considerations of the common cause failure （CCF） and a large number of nodes in WSNs. The EOBDD algorithm analyzes the common cause event （CCE） and the network structure when CCE takes place according to the stochastic graph and the CCF model of WSNs. After constructing the ordered binary decision diagram （OBDD） of the original network with node expansion, it uses a set of OBDD variables （SOV） to guide reliability computations along this OBDD. The two steps about OBDD can decrease the cost of OBDD constructions and storage. Furthermore, the efficient OBDD structure and Hash tables can greatly decrease redundant computations of isomorphs. The experiment results show that the EOBDD can be used to evaluate the reliability of WSN efficiently.

Reliability evaluation of avionics system with imperfect fault coverage and propagated failure mechanisms

Fault tolerance designs are essential techniques for systems that require high levels of reliability,such as aircraft or spacecraft control system.Imperfect Fault Coverage(IFC)may lead to the failure of a system or subsystem even with adequate redundancy.Previous studies of IFC mostly concentrated on evaluating Coverage Factor(CF),whereas the system failure behaviors with IFC have rarely been involved.Failures that occur in low-layer may be covered by highlayer.However,if the coverage is imperfect,uncovered failure will have functional and physical impact on the system behavior.In this thesis,the failure behavior and reliability of IFC of multi-layer systems are studied and a Binary Decision Diagram(BDD)-based modeling and simulation method are proposed to evaluate system reliability.As a case,the failure behavior of an aero engine electronic controller with IFC is studied.The results show that the IFC may impact system behavior without taking the IFC into account,the system maintenance intervals may reduce,and thus the maintenance costs will increase.

Reliability Analysis of Aircraft Condition Monitoring Network Using an Enhanced BDD Algorithm

The aircraft condition monitoring network is responsible for collecting the status of each component in aircraft. The reliability of this network has a significant effect on safety of the aircraft. The aircraft condition monitoring network works in a real-time manner that all the data should be transmitted within the deadline to ensure that the control center makes proper decision in time. Only the connectedness between the source node and destination cannot guarantee the data to be transmitted in time. In this paper, we take the time deadline into account and build the task-based reliability model. The binary decision diagram （BDD）, which has the merit of efficiency in computing and storage space, is introduced when calculating the reliability of the network and addressing the essential variable. A case is analyzed using the algorithm proposed in this paper. The experimental results show that our method is efficient and proper for the reliability analysis of the real-time network.

Short-Time Scaling of Variable Orderingof OBDDs

A short-time scaling criterion of variable ordering of OBDDs is proposed. By this criterion it is easy and fast to determine which one is better when several. variable orders are given, especially when they differ 10% or more in resulted BDD size from each other. An adaptive variable order selection method, based on the short-time scaling criterion, is also presented. The experimental results show that this method is efficient and it makes the heuristic variable ordering methods more practical.

Efficient Heuristic Variable Ordering of OBDDs

An efficient heuristic algorithm for variable ordering of OBDDs, the WDHA (Weight and Distance based Heuristic Algorithm), is presented. The algorithm is based on the heuristics implied in the circuit structure graph. To scale the heuristics, pi -weight , node -weight , average -weight and pi -distance in the circuit structure graph are defined. As any of the heuristics is not a panacea for all circuits, several sub algorithms are proposed to cope with various cases. One is a direct method that uses pi -weight and pi -distance . The others are based on the depth first search (DFS) traversal of the circuit structure graph, with each focusing on one of the heuristics. An adaptive order selection strategy is adopted in WDHA. Experimental results show that WDHA is efficient in terms of BDD size and run time, and the dynamic OBDD variable ordering is more attractive if combined with WDHA.