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