Computation of k-out-of-n System Reliability via Reduced Ordered Binary Decision Diagrams
Ali Muhammad Ali Rushdi
King Abdulaziz University, PO.Box 80204, Jeddah 21589, Saudi Arabia.
Alaa Mohammad Alturki *
King Abdulaziz University, PO.Box 80204, Jeddah 21589, Saudi Arabia.
*Author to whom correspondence should be addressed.
Abstract
A prominent reliability model is that of the partially-redundant (k-out-of-n) system. We use algebraic as well as signal-flow-graph methods to explore and expose the AR algorithm for computing k-out-of-n reliability. We demonstrate that the AR algorithm is, in fact, both a recursive and an iterative implementation of the strategy of Reduced Ordered Binary Decision Diagrams (ROBDDs). The underlying ROBDD for the AR recursive algorithm is represented by a compact Signal Flow Graph (SFG) that is used to deduce AR iterative algorithms of quadratic temporal complexity and linear spatial complexity. Extensions of the AR algorithm for (single or scalar) threshold, double-threshold, vector-threshold, and k-to-l-out-of-n systems have similar ROBDD interpretations.
Keywords: AR algorithm, k-out-of-n system, reduced ordered binary decision diagram, reliability, signal flow graph