FAULT- AND DEFECT-TOLERANT ARCHITECTURES FOR NANOCOMPUTING - Bio-Inspired and Nanoscale Integrated Computing - page 284

and its output probability is given by p 0 p 1 ½ PTM NAND . The

PTM representation encompasses all the input combinations of the NAND gate
and hence is very similar to logic compatibility functions (Section 4.4) or DTMC
models (Section 4.1) for NAND logic.
A PTM for a specific circuit is formulated by composition of the gate PTMs,
the composition being dependent on the logic dependency of the circuit. The
authors propose a framework in [31] based on PTMs that can be used for
computing the output probabilities for combinational circuits. This involves the
composition of gate PTMs in terms of the logic dependency of a circuit. This
composition technique takes into account signal dependencies between gates by
considering the underlying joint probabilities;

½ ¼ p 00 p 01 p 10 p 11

it also considers the effects of

logical masking.
The authors in [31] use algebraic decision diagrams (ADDs) to alleviate a
potential memory bottleneck for PTMs representing large circuits. The ADD
representations result in elimination of identical information and compression of
the PTMs. PTM operations such as probability value extraction are performed on
the ADDs.
There are a number of similarities between the PMC and PTM approaches.
First, instead of specifying the initial probabilities as a tuple ( p 00 p 01 p 10 p 11

½ ), if
PTM NAND is modified to encode them, the modified PTM becomes the transition
probability matrix shown in Figure 10.10. Second, both the PMC and PTM
approaches require a matrix of the order of O(2 m+n ) entries to evaluate a circuit
with m inputs and n outputs. Therefore, the PMC and PTM methodologies use
compact MTBDD and ADD (another name for MTBDDs [63, 64]) matrix
representations, respectively. Third, even the usage of these compression techni-
ques does not help these two reliability evaluation methodologies to scale for large
circuits.

10.4.3. Probabilistic Gate Models (PGMs)
The PGM-based methodology [32] entails the formulation of a PGM for each
logic gate type. For instance, the PGM for the NAND gate in Figure 10.9 with a
failure probability of e is

1 e
e

p ð out Þ¼ 1 p ð A0 Þ p ð B0 Þ ½ p ð A0 Þ p ð B0 Þ ; ð 10 : 2 Þ

where p(A0) and p(B0) are the probabilities of inputs A0andB0 being stimulated.
Hence, p(out) is the probability of the faulty NAND output being logic high. This
formulation can be applied iteratively to compute circuit reliability. This shows
that the PGM approach requires computation of the output distribution, given the
input probability distributions and logic function (truth table) performed by the
gate. The DTMC model of a gate in the PMC methodology can be interpreted as a
representation of the input probability distribution and the logic function; hence,