An ROBDD Algorithm for the Reliability of Double-Threshold Systems

Abstract

A double-threshold system (DTS) is a system that is successful if and only if the weighted arithmetic sum of its successes/failures equals or exceeds a certain threshold T1 and is smaller than or equal to a certain threshold T2. Generally a DTS is neither symmetric nor coherent. The DTS reduces for positive weights to a weighted k-to-l-out-of-n:G system, whose symmetric special case is the k-to-l-out-of-n:G system. Another important special case of the DTS is the threshold system (TS), commonly known for positive weights as the weighted k-out-of-n system. The paper presents the fundamental properties of the DTS. Recursive relations covering a DTS are given together with various possible sets of boundary conditions. Based on these, a novel recursive algorithm for computing the reliability of a DTS is described, and then demonstrated via an illustrative example using the signal ow graph technique together with probability map interpretation. The DTS recursive algorithm developed herein is an extension of earlier algorithms for (single-) threshold systems and for k-out-of-n systems. The current algorithm as well as these former algorithms are shown to be equivalent to implementation of the Reduced Ordered Binary Decision Diagram (ROBDD).