Efficient reliability assessment of redundant systems subject to imperfect fault coverage using binary decision diagrams

Systems requiring very high levels of reliability, such as aircraft controls or spacecraft, often use redundancy to achieve their requirements. This paper provides highly efficient techniques for computing the reliability of redundant systems involving simple k-out-of-n arrangements, and those involving complex structures which may include imbedded k-out-of-n structures. Techniques for modeling systems subject to imperfect fault coverage must be appropriate to the redundancy management architecture utilized by the system. Systems for which coverage can be associated with each of the redundant components, perhaps taking advantage of the component's built-in test capability, are modeled with what we term Element Level Coverage (ELC); while systems which utilize majority voting for the selection from among redundant components are modeled with Fault Level Coverage (FLC). In FIX, systems coverage is a function of the fault sequence, i.e., coverage will be greater for the initial faults which can utilize voting for redundant component selection, but will have a lower coverage value when the system must select from among the last two operational components. Occasionally, FLC systems can be adequately modeled using a simplified version of FLC in which it can be assumed that the initial fault coverage values are unity. This model is called one-on-level coverage (OLC). The FLC algorithms provided in this paper are of particular importance for the correct modeling of systems which utilize voting to select from among their redundant elements. While combinatorial, and recursive techniques for modeling ELC, FLC, and OLC have been previously reported, this paper presents new table-based algorithms, and binary decision diagram-based algorithms for these models which have superior computational complexity. The algorithms presented here provide the ability to analyse large, and complex systems very efficiently, in fact with a computational complexity comparable to the best available techniques for systems with perfect fault coverage.