Information Technology Reference
In-Depth Information
0:0
0:1
0:9
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:1
0:9
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:1
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:9
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0.01
0:0
0:0
0:0
1:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0.99
0:0
0:0
0:0
0:0
1:0
0:0
0:0
0:0
0:0
0:0
0:0
0:0
0.0
0:01
0:0
0:0
0:0
0:0
1:0
0:0
0:0
0:0
0:0
0:0
0:0
0.0
0:99
0:0
0:0
0:0
0:0
0:0
1:0
0:0
0:0
0:0
0:0
0:0
0.0
0:0
0:01
0:0
0:0
0:0
0:0
0:0
1:0
0:0
0:0
0:0
0:0
0.0
0:0
0:99
0:0
0:0
0:0
0:0
0:0
0:0
1:0
0:0
0:0
0:0
0.0
0:0
0:0
0:99
0:0
0:0
0:0
0:0
0:0
0:0
1:0
0:0
0:0
0.0
0:0
0:0
0:01
0:0
0:0
0:0
0:0
0:0
0:0
0:0
1:0
Figure 10.10. Transition probability matrix for NAND DTMC.
[42] shows how to represent probability matrices as MTBDDs. Consider a
square 2 m
2 m matrix A (non-square matrices can be padded) with elements from
M.
Its
elements
a ij may
be
viewed
as
values
of
a
function
2 m
2 m
f A : f 1
; ;
gf 1
; ;
g! M, where f A ð i
;
j Þ¼ a ij . Using the Boolean en-
m
2 m
coding c
: f 0
;
1 g
!f 1
; ;
g , f A may be interpreted as a Boolean function
1 g 2 m
f
: f 0
;
! M, where
f ð x
;
y Þ¼ f A ð c ð x Þ;
c ð y ÞÞ
for x ¼ð x 1 ; ;
x m Þ
and
y ¼ð y 1 ; ;
y m Þ . The variables for the rows and columns are interleaved, implying
that the MTBDD interpreted from the function f ð x 1 ;
y m Þ can be used
to represent the matrix A. This interleaving imposes a recursive structure from
which efficient recursive algorithms for all matrix operations are derived [42].
For instance, the transition probability matrix of Figure 10.10 can be
represented as a MTBDD with Boolean row variables s 0 ;
y 1 ; ;
x m ;
s 1 ;
A 0 ;
B 0 ;
out and
column variables s 0 0 ;
s 0 1 ;
A 0 0 ;
B 0 0 ;
out 0 . Note that since s 2f 0
;
1
;
2
;
3 g , it is encoded
2
out 0 Þ is the interleaved
function from which the MTBDD is interpreted in this case. Figure 10.9 indicates
that only 52 MTBDD nodes are required to represent the 15 15 probability
matrix. Thus, the PMC-based methodology entails modeling circuits as DTMCs
and the PRISM tool uses compact MTBDDs to represent and analyze the
DTMCs.
s 0 0 ;
s 0 1 ;
A 0 0 ;
B 0 0 ;
as
f 0
;
1 g
!f 0
;
1
;
2
;
3 g . f ð s 0 ;
s 1 ;
A 0 ;
B 0 ;
out
;
10.4.1.1. Evaluating Multiplexing Architectures. The effect of noisy
communication on computing systems has been theoretically analyzed in terms
of information theoretic entropy, and bounds have been established on the noise
levels that can be tolerated during transmission [44]. Error-correcting codes have
been used extensively to abate transient faults at interconnections [45, 46]. The
theory to treat the effect of noise on gates was first developed by von Neumann
[47], and later extended in [3, 48-54].
In his seminal work [47], von Neumann proposed a gate-level fault tolerance
technique called multiplexing (MUX) for both the majority (MAJ) and NAND
 
Previous Page
Next Page
Bio-Inspired and Nanoscale Integrated Computing
Search WWH ::




Custom Search
Home