Hardware Reference
In-Depth Information
Fig. 6.6
(
a
) Three categories of electrodes and the graphs correspond to electrodes of (b) the first
category (
c
) the second category (
c
) the third category
nodes and the number of edges is
2
=10. Since the number of such electrodes is
.m
2/
.n
2/, we will get .m
2/
.n
2/ complete graphs with 10 edges.
On the other hand, the number of edges that are contained in two graphs is .m
1/
n
C
.n
1/
m+2
.m
1/
.n
1/. Using the principle of inclusion/exclusion,
we set the total number of edge in the graph G
layout
to be:
N
edge
D
4
3
C
12.m
C
n
4/
C
10.mn
2m
2n
C
4/
Œ.m
1/n
C
.n
1/m
2
.m
1/
.n
1/
D
6mn
5m
5n
C
2
According to Lemma
6.2
, if the pin-assignment configuration satisfies both
Constraint
1
and Constraint
2
, then graph G
layout
is a simple graph. Assume that
there are M control pins in the pin-assignment configuration. The number of nodes
in graph G
layout
is equal to M . The maximum number of edges in the simple graph
G
layout
that has M nodes is given by:
N
edge
_max
D
M
2
!
D
M
.M
1/
2
Finally, we derive the desired lower bound in the number of control pins. Since
N
edge
_max
is an upper limit on the number of edges in a graph, we have the inequality
N
edge
_max
N
edge
.