Information Technology Reference
In-Depth Information
two vertices can be assigned to at most
(
k
−
n/
(
k
−
n/
(
k
−
−
≤
2
n
2
/
(
k
−
1
)(
1
)
)(
1
)
1
)
1
)
pairs because the first can be assigned to
(
k
−
1
)
sets each containing at most
n/
(
k
−
1
)
elements and the second must be assigned to one of the remaining elements in that set.
The number of ways to choose variables in
t
i
sothatithasvalue0isthenumberof
ways to choose a variable of each kind multiplied by the number of ways to assign values to
it. Let
α
be the number of variables of
t
i
for which one vertex has previously been assigned
apairandlet
β
be the number of variables for which neither vertex has been assigned a
pair. (
β
≤
p
(
p
−
1
)
/
2
−
α
since
t
i
has at most
p
(
p
−
1
)
/
2 variables.) Thus, a variable
of the first kind can be assigned in at most
αn/
(
k
1
)
ways and the number of ways of
assigning the two vertices in variables of the second kind is at most
β
2
n
2
/
(
k
−
1
)
.Since
each vertex associated in such pairs can b
e assigned in th
e same number of ways,
γ
, it follows
that
γ
2
−
≤
β
2
n
2
/
(
k
1
)
.
Summarizing, the variables in
t
i
can be assigned in at most the following number of
ways so that
t
i
has value 0:
≤
β
2
n
2
/
(
k
−
1
)
.Thus,
γ
−
1
)+
(
p
(
p
αn/
(
k
−
−
1
)
/
2
−
α
)
2
n
2
/
(
k
−
1
)
(
k
This quantity is largest when
α
=
0 and is at most
n/
2since
p
=
−
1
)
/
2
,whichis
the desired conclusion.
We now derive an upper bound on the number of errors that can be made by
AND
gates
on
k
-positive inputs.
LEMMA
9.6.8
Let an
AND
gate
∧
and its approximation
∧
each be given as inputs the functions
f
l
and
f
r
whose POSE contains sum terms of endpoint size
q
or less. Then the number of
k
-positive
test inputs for which
and
∧
has value
1
but
∧
∧
∧
produce different outputs (
has value
0
)isat
most
e
AND
:
e
AND
=
(
n/
2
)
p
+
1
(
n
−
p
−
1
)!
k
)!
Proof
The proof is similar to that of Lemma
9.6.7
.Let
f
correct
=
f
l
∧
k
!(
n
−
f
r
and
f
approx
=
f
l
∧
f
r
.Let
c
1
,
...
,
c
l
be the sum terms in the POSE for
f
correct
. Since by induction the
endpoint size of all terms in the POSE of
f
l
and
f
r
is at most
q
,eachtermin
f
correct
is the
sum of at most
q
(
q
1
)
/
2 variables.
In this case we count the number of
k
-positive test graphs (they contain one
k
-clique)
that cause
f
correct
(
x
)=
1 but
f
approx
(
x
)=
0. Since a
k
-positive test graph contains just
those edges between a specified set of
k
vertices, we define each such graph by a one-to-one
mapping from the vertices (endpoints) in
V
to the integers
(
n
)=
−
{
1, 2,
...
,
n
}
,where
we adopt the rule that vertices mapped to the first
k
integers are those in the clique associated
with a particular test graph. It follows that each
k
-positive test graph corresponds to exactly
k
!(
n
k
)!
of these 1-1 mappings. Then,
e
AND
is the number of such 1-1 mappings for
which
f
correct
(
x
)=
1 but
f
approx
(
x
)=
0 divided by
k
!(
n
−
k
)!
.
We show that any mapping that results in
f
correct
(
x
)=
1 assigns each endpoint to at
most
n/
2 values from
(
n
)
.But
f
approx
(
x
)=
0 for positive test inputs only if more than
p
endpoints are assigned values, because
f
approx
is obtained from
f
correct
by discarding
product terms in its SOPE that contain more than
p
endpoints. It follows that at most
(
n/
2
)
p
+
1
(
n
−
1
)!
of the positive test inputs result in an error by the approximate
AND
gate. Dividing by
k
!(
n
−
p
−
−
k
)!
, we have the desired upper bound on
e
AND
.
Search WWH ::
Custom Search