Combinatorial methods for the evaluation of yield and operational reliability of fault-tolerant systems-on-chip

In this paper we develop combinatorial methods for the evaluation of yield and operational reliability of fault-tolerant systems-on-chip. The methods assume that defects are produced according to a model in which defects are lethal and affect given components of the system following a distribution common to all defects; the method for the evaluation of operational reliability also assumes that the fault-tree function of the system is increasing. The distribution of the number of defects is arbitrary. The methods are based on the formulation of, respectively, the yield loss and the operational unreliability as the probability that a given Boolean function with multiple-valued variables has value 1. That probability is computed by analyzing a ROMDD (reduced ordered multiple-value decision diagram) representation of the function. For efficiency reasons, a coded ROBDD (reduced ordered binary decision diagram) representation of the function is built first and, then, that coded ROBDD is transformed into the ROMDD required by the methods. We present numerical experiments showing that the methods are able to cope with quite large systems in moderate CPU times.