Ali Muhammad RUSHDI, Alaa Mohammad ALTURKI

Novel representations for a coherent threshold reliability system: a tale of eight signal ow graphs

A threshold system is a reliability system whose success/failure is a threshold switching function in the successes/failures of its components. A coherent system (CS) is one that is causal, monotone, and with relevant components. The coherent threshold system (CTS), typically called the weighted k-out-of-n system, is consequently described by strictly positive weights and threshold. This paper presents recursive relations as well as boundary conditions for eight entities pertaining to a CTS. These are (a) expressions of monoform literals as well as disjoint or probability- ready expressions for either system success or failure, and (b) all-additive formulas as well as inclusion-exclusion ones for either system reliability or unreliability. These entities are obtained according to the best policy of implementing the Boole{Shannon expansion with respect to a higher-weight component before it is made with respect to a lower-weight one. With this best policy, the success and failure expressions with monoform literals are both minimal and shellable. Each of the eight entities considered is represented by an acyclic (loopless) signal ow graph (SFG). The SFG for system success or failure is isomorphic to a reduced ordered binary decision diagram, which is the optimal data structure for a Boolean function. The interrelations between the SFGs demonstrate optimal procedures for implementing (a) the probability (real) transform of a Boolean function, (b) inversion or complementation of a Boolean function, and (c) disjointing or orthogonalization of a sum-of-products expression of a Boolean function. The SFGs discussed herein for a CT can be extended to a general coherent system. They reduce to elegant symmetric regular graphs for the special case of a partially redundant system (k-out-of-n system).

PDF

___

[1] Ball M, Provan J. Disjoint products and efficient computation of reliability. Oper Res 1988; 36: 703-715.
[2] Rushdi A. Threshold systems and their reliability. Microelectron Reliab 1990; 30: 299-312.
[3] Rushdi A, Alturki A. Reliability of coherent threshold systems. J Appl Sci 2015; 15: 431-443.
[4] Eryilmaz S. Capacity loss and residual capacity in weighted k-out-of-n: G systems. Reliab Eng Syst Safe 2015; 136: 140-144.
[5] Rushdi A. Partially-redundant systems: examples, reliability, and life expectancy. International Magazine on Advances in Computer Science and Telecommunications 2010; 1: 1-13.
[6] Rushdi A, Ghaleb F. The Walsh spectrum and the real transform of a switching function: a review with a Karnaugh- map perspective. Journal of Engineering and Computer Sciences, Qassim University 2014; 7: 73-112.
[7] Rushdi A, Goda A. Symbolic reliability analysis via Shannon's expansion and statistical independence. Microelectron Reliab 1985; 25: 1041-1053.
[8] Rushdi A, Rushdi MA. Switching-algebraic analysis of system reliability. In: Ram M, Davim P, editors. Advances in Reliability and System Engineering. Management and Industrial Engineering Series. Cham, Switzerland: Springer International Publishing, 2016. pp. 139-161.
[9] Crama Y, Hammer P. Boolean Functions: Theory, Algorithms, and Applications. Cambridge, UK: Cambridge University Press, 2011.
[10] Rushdi A, Ghaleb F. A tutorial exposition of semi-tensor products of matrices with a stress on their representation of Boolean functions Journal of King Saud University - Computer and Information Sciences 2016; 5: 3-30.
[11] Sasao T, Butler J. The eigenfunction of the Reed-Muller transformation. In: Proceedings of the Workshop on Applications of the Reed Muller Expansion in Circuit Design, and Representation and Methodology of Future Computing Technology; 16 May 2007; Oslo, Norway.
[12] Muroga S. Logic Design and Switching Theory. New York, NY, USA: Wiley, 1979.
[13] Rushdi A. Karnaugh map. In: Hazewinkel M, editors. Encyclopaedia of Mathematics, Supplement Volume I. Boston, MA, USA: Kluwer Academic Publishers, 1997. pp. 327-328.
[14] Rushdi A. Map derivation of the minimal sum of a switching function from that of its complement. Microelectron Reliab 1985; 25: 1055-1065.
[15] Rushdi A, Al-Khateeb D. A review of methods for system reliability analysis: a Karnaugh-map perspective. In: Proceedings of the First Saudi Engineering Conference; 1983; Jeddah, Saudi Arabia. pp. 57-95.
[16] Golnaraghi F, Kuo B. Automatic Control Systems. 9th ed. New York, NY, USA: Wiley, 2009.
[17] Brown F. Boolean Reasoning: The Logic of Boolean Equations. Boston, MA, USA: Kluwer Academic Publishers, 1990.
[18] Bryant R. Graph-based algorithms for Boolean function manipulation. IEEE T Comput 1986; 35: 677-691.
[19] Akers S. Binary decision diagrams. IEEE T Comput 1960; C-27: 509-516.
[20] Rauzy A. Binary decision diagrams for reliability studies. In: Misra KB, editor. Handbook of Performability Engineering. London, UK: Springer, 2008.
[21] Mo Y, Xing L, Amari S, Dugan J. Efficient analysis of multi-state k-out-of-n system. Reliab Eng Syst Safe 2015; 133: 95-105.