Abstract
The k-out-of-n system model is the most prominent model of coherent system reliability. with a variety of important special cases, generalizations, and extensions thereof. In particular, the k-out-of-n reliabilities (1 <= k <= n) constitute a basis for expressing the reliability of an n-order coherent system in terms of its signature (destruction spectrum). A notable algorithm for computing the reliability of a k-out-of-n system is the Improved Disjoint Products (IMDP) algorithm. This paper has four goals, namely, (a) to present a detailed and novel exposition of the IMDP algorithm; (b) to demonstrate that the IMDP algorithm is derivable from the BH-2 algorithm, which is an enhancement of the BH-1 algorithm that is used for evaluating the probability of exactly k successes among n Bernoulli trials and, hence, for computing the probability mass function (pmf) of the generalized binomial distribution; (c) to demonstrate that the IMDP algorithm can be derived from the AR algorithm, which is the Reduced-Ordered-Binary-Decision-Diagram (ROBDD) algorithm for evaluating the k-out-of-n reliability and also for computing the Cumulative Distribution Function (CDF) of the generalized binomial distribution; and (d) to show that the IMDP algorithm is a collective orthogonalization (disjointness) algorithm for a shellable sum-of-products formula (DNF) for k-out-of-n success. The paper plays a unifying role for a variety of concepts and algorithms and tries to emphasize similarities and interrelations among them, while pinpointing any subtle differences among them. A common denominator in explaining the various algorithms is the use of signal flow graphs that are compact, regular, and acyclic. For these loopless graphs. the gain formula requires only simple path enumeration, as well as a calculation of the transmittances of the paths.