Hardware Reference
In-Depth Information
Fig. 6.7
An m
n outlined
rectangle
Based on Theorem
6.1
, we have following corollary:
Corollary 6.1.
For large values of
m
and
n
, the
low
er bound on the number of
control pins
c
an be approximated as
M
min
2
p
3mn
, and if
m
D
n
D
t
,weget
M
min
2
p
3t
. In other words
, w
hen the total number of electrodes in the array is
N
, the number of pins is
˝.
p
N/
(Fig.
6.7
).
Next we calculate the lower bound for the number of control pins required by an
m
n outlined rectangular layout. The layout is shown in Fig.
6.7
, and the outlined
rectangular array is used extensively in commercial biochips [
1
,
2
]. For the outlined
rectangular array, we have the following theorem:
Theorem 6.2.
A lower bound on the number of control pins in the
m
n
outlined
rectangle is given by following inequality:
M
2
!
4m
C
4n
8:
Proof.
For this layout, there are (2.m
C
n/
4) CEGs in total and each CEG has
three electrodes. When we map the layout to the graph model, we get (2.m
C
n/
4)
complete graphs, and each graph has three nodes and three edges. Some edges are
contained in more than one sub-graph. The number of edges that are contained in
two graphs is (2
.n
1/+2
.m
1/). Therefore, according to the principle of
inclusion/exclusion, we get the total number of edges in the graph G
layout
as:
N
edge
D
3
.2.m
C
n/
4/
.2
.n
1/
C
2
.m
1//
D
4m
C
4n
8
t
According to Lemma
6.2
, if the pin-assignment configuration satisfies
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 N
edge
_max
in the
simple graph G
layout
, which has M nodes, is given by:
