Information Technology Reference
In-Depth Information
the PMC and PGM approaches are similar. At the core, these methodologies
construct probabilistic models that can be derived from one another; assume that
if each gate fails independently, the scalability problem affects them equally.
10.4.4. Markov Random Fields (MRFs)
Reference [65] proposed a probabilistic approach based on Markov Random
Fields (MRFs) for analyzing nanocircuits. An MRF is defined as a finite set of
random variables, L ¼fl 1 ;
l k g . Each variable l i has a neighborhood
N i which has variables from { Ll i }. The probability distribution of a given
variable depends only on a typically small neighborhood of other variables that is
called a clique. As per the Hammersley-Clifford theorem [66],
l 2 ; ... ...;
KT c 2 C U c ðlÞ
1
1
Z e
P ðl i jfL l i gÞ ¼
:
ð 10
:
3 Þ
The conditional probability in Equation 10.3 is the Gibbs distribution. Z is
the normalizing constant and for a given node i, C is the set of cliques. U c is the
clique energy function [65] and depends only on the neighborhood of the node
whose energy state probability is being calculated.
The idea of this model of computation is to use such a Gibbs distribution-
based technique to characterize the logic functionality of each gate and maximize
probability of being in valid energy configurations at the gate outputs. The logic
functionality of each gate is represented by a logic compatibility function which is
similar to a truth table. But instead of only considering the valid logic combina-
tions, i.e., for given logic values at the inputs, the corresponding logic value at the
gate output is correct; the logic compatibility function considers the invalid logic
logic operation scenarios as well (output value is invalid for a given logic
combination at the inputs). Such a function is used to represent the logic or
clique energy for each Boolean function, and hence formulate energy-based
transformation for the Boolean function.
Due to such a formulation of the logic compatibility function, this computa-
tional scheme implicitly considers structural defects during the circuit formulation
and eliminates the need for defect mapping followed by defect avoidance. The
reliability of Boolean networks can be evaluated by representing circuits as MRF-
based formulations of logic gates, applying Belief Propagation to the output
energy distributions of each logic gate, and computing the probabilities of the
signals at the prime outputs. These output distributions are evaluated for specific
probability distributions at the primary inputs and signal noise at the intercon-
nects. Note that this model of computation encodes signals over a continuous
energy distribution, unlike conventional computational models where signals are
bimodal (logic low or high).
Let us take a specific NAND gate example to walk through the methodology
in [65]. For a two-input NAND gate, there are three nodes in the assumed MRF:
the inputs x 0 and x 1 , and the output x 2 . Figure 10.12 shows x 0 and its
 
Search WWH ::




Custom Search