Information Technology Reference
In-Depth Information
are outputs of
OR
gates (and vice versa). Furthermore, by the approximation rules, if
f
l
and
f
r
are inputs to an
AND
(
OR
) gate, every sum (product) in their POSE (SOPE) has an endpoint
set size of at most
q
(
p
). We now show that each replacement of a gate by its approximator
introduces a relatively small number of errors. We begin by establishing this fact for
OR
gates.
LEMMA
9.6.7
Let an
OR
gate
∨
and its approximation
∨
each be given as inputs the functions
f
l
and
f
r
whose SOPE contains product terms of endpoint size
p
or less. Then the number of
k
-negative test inputs for which
∨
∨
∨
and
produce different outputs (
∨
has value
0
but
has value
1
)isatmost
e
OR
where
w
=
n
mod (
k
−
1
)
:
(
n/
2
)
q
+
1
(
n
−
q
−
1
)!
e
OR
=
(
n/
(
k
−
1
)
!)
w
(
n/
(
k
−
1
)
!)
k−
1
−w
w
!(
k
−
1
−
w
)!
f
r
and
f
approx
=
f
l
∨
Proof
Let
f
correct
=
f
l
∨
f
r
.Let
t
1
,
...
,
t
l
be the product terms
in the SOPE for
f
correct
. Since the endpoint size of all terms in the SOPE of
f
correct
is at
most
p
,eachtermistheproductofatmost
p
(
p
−
1
)
/
2 variables.
1
)
-balanced partitions and pairs of indices given
in the proof of Lemma
9.6.5
,wecount
N
, the number of one-to-one mappings from
V
to
Using the association between
(
k
−
for which
f
correct
(
x
)=
0 but
f
approx
(
x
)=
1, after which we divide by
D
,the
number of mappings corresponding to a single partition of the variables, to compute
e
OR
=
N/D
. From the proof of Lemma
9.6.5
we have that
D
=(
P
!)
w
(
n/
(
k
−
1
)
n/
(
k
−
!)
k−
1
−w
w
!(
k
1
)
w
)!
.
To derive an upper bound to
N
,observethat
f
approx
(
x
)
is obtained by converting the
SOPE of
f
correct
to a POSE and deleting all sums in this POSE whose endpoint set size
exceeds
q
.Thus,
N
is at most the number of ways to assign vertices to pairs in
−
1
−
that
causes a deleted sum to be 0 because the new POSE may now become 1. But this can
happen only if the endpoint set size of the deleted product is at least
q
+
1. Thus, only if at
least
q
+
1 vertices in a sum are assigned values is it possible to have
f
correct
(
x
)=
0and
f
approx
(
x
)=
1.
Below we show that each vertex can be assigned at most
n/
2 different pairs in
P
P
.It
follows there are at most
(
n/
2
)
q
+
1
(
n
1
)!
ways to assign pairs to
q
+
1ormore
vertices because the first
q
+
1 can be assigned in at most
(
n/
2
)
q
+
1
ways and the remaining
(
n
−
q
−
−
q
−
1
)
vertices can be assigned in at most
(
n
−
q
−
1
)!
ways. This is the desired upper
bound on
N
.
Wenowshowthateverymappingfrom
V
to
P
that corresponds to a negative test input
x
assigns each vertex to at most
n/
2pairsin
P
.
Let
t
1
,
...
,
t
l
be product terms in the SOPE of
f
correct
. We examine these terms in
sequence. Consider a partial mapping from
V
to
P
that assigns values to variables so that
at least one variable in each of the products
t
1
,
...
,
t
i−
1
is 0, thereby insuring that each
product is 0. Consider now the
i
th product,
t
i
. If the partial mapping assigns value 0 to at
least one of its variables, we move on to consider
t
i
+
1
. (It cannot set all variables in
t
i
to 1
because we are considering mappings causing all terms to be 0.)
Suppose that the partial mapping has not assigned value 0 to any of the variables of
t
i
.
There are two cases to consider. For some variable
x
a
,
b
of
t
i
either a) one or b) both of the
vertices
v
a
,
v
b
∈
. In the first case, assign the second
vertex to the set containing the first, thereby setting
x
a
,
b
=
0.Thiscanbedoneinatmost
V
has not been assigned a pair in
P
elements and at
least one of them has been chosen previously, namely the first vertex. In the second case the
n/
(
k
−
1
)
−
1
≤
n/
(
k
−
1
)
ways since the set contains at most
n/
(
k
−
1
)
Search WWH ::
Custom Search