Hardware Reference
In-Depth Information
We next assume that Constraint
2
in Lemma
6.1
is violated. Thus two
non-overlapping CEGs E
group
1
and E
group
2
exist, and their corresponding CPGs
share more than one common pin. Assume the graph derived from E
group
1
and
E
group
2
are G
1
and G
2
, respectively. Suppose E
x
1
2
E
group
1
and E
x
2
2
E
group
2
are
both connected to pin X, and E
y
1
2
E
group
1
and E
y
2
2
E
group
2
are both connected
to pin Y. Electrode pair {E
x
1
, E
y
1
} is mapped to an edge between the nodes
that represent pin X and pin Y according to the definition of the one-to-one
mapping from the set of electrode pairs to edges in the graph. The label of this
edge is
Link
.E
x
1
;E
y
1
/
(or
Link
.E
y
1
;E
x
1
/
). Electrode pair {E
x
2
, E
y
2
} is mapped to an
edge between the nodes that represent pin X and pin Y. The label of this edge is
Link
.E
x
2
;E
y
2
/
(or
Link
.E
y
2
;E
x
2
/
). Based on the definition of the
union
of two graphs,
when G
1
and G
2
are merged to G
1
[
G
2
, there will be two edges with different labels
between the nodes that represent pin X and pin Y. Thus G
1
[
G
2
is a multigraph. As
G
1
[
G
2
is a subgraph of G
layout
, we can conclude that G
layout
also is a multigraph.
According to the definition of G
layout
, it is easy see that if it is a simple graph,
then the pin-assignment configuration satisfies Constraint
1
and Constraint
2
.
For any given layout, according to its shape, we can estimate a lower bound on
the number of control pins needed to avoid pin-actuation conflicts for any target
application.
Here we show two examples for the calculation of the lower bound of the number
of control pins.
Theorem 6.1.
Consider an
m
n
digital microfluidic array. Then suppose a
pin-assignment configuration with
M
pins exists, such that Constraint
1
and
Constraint
2
in Sect.
6.1
are satisfied. A lower bound on
M
is given by:
M
2
!
6mn
5m
5n
C
2:
For a m
n electrode array, and for any electrode E
.i;j /
in this array, since its
corresponding graph G
.i;j /
is a complete graph, the number of edges can be derived
from the number of elements in the CPG. For different positions of the electrodes,
the numbers of elements in CPG are different. Thus we count the number of edges
G
layout
by classifying electrode into three categories according to their positions, as
shown in Fig.
6.6
a.
The first category includes the electrodes located at the corner of the array. The
corresponding graph is shown in Fig.
6.6
a. For each graph, there are three nodes and
the number of edges is
2
D
3. Since the number of such electrodes in the m
n
array is 4, we get 4 graphs with 3 edges. The second category includes the electrodes
located at four sides but not the corners of the array, and the corresponding graph is
shown in Fig.
6.6
b. For each graph, there are four nodes and the number of edges
is
2
=6. As the number for such electrodes is 2(m+n-4), we have 2(m+n-4) graphs
with 6 edges. The third category includes the electrodes located within the array
and the corresponding graph is shown in Fig.
6.6
c. For each graph, there are five
