Hardware Reference
In-Depth Information
N
edge
_max
D
M
2
!
D
M
.M
1/
2
Finally, we derive the lower bound in the number of control pins for the outlined
rectangular layout. 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
.
Based on Theorem
6.2
, we have following corollary:
Corollary 6.2.
For large values of
m
and
n
, th
e lowe
r bound on the number of
control pins
ca
n be approximated as
M
min
2
p
m
C
n
, and if
m
D
n
D
t
,weget
M
min
2
p
2t
. In other words
, w
hen the total number of electrodes in the array is
N
, the number of pins is
˝.
p
N/
.
For an electrode array that has other shapes, the number of control pins can be
lower-bounded in a similar manner.
Let us now return to the pseudocode shown in Fig.
6.3
. In the first phase,
we determine the lower bound N
L
on the number of pins, and then initialize
the set of available pins (which is written as
PinAvailable
in Fig.
6.3
)as{Pin
1, Pin 2, :::,PinN
L
}. In the second phase, we set an index number for each
electrode on the layout by numbering the electrodes one by one, from the electrode
on the upper-right corner to the lower-left corner. An electrode E
R
is randomly
selected as the “seed” of the pin-assignment process, and Pin 1 is assigned to
E
R
. The set of electrodes whose control pins have been determined is written as
“ElectrodesAlreadyAssigned” (as shown in Fig.
6.3
). The graph corresponding to
the pin-assignment configuration of ElectrodesAlreadyAssigned is written as G
EAA
.
Then electrode E
R
is the first element that is added into the set Electrode-
sAlreadyAssigned. The pin-assignment configuration for the layout is constructed
electrode-by-electrode around the seed E
R
. In each step, we first locate all the
neighboring electrodes of ElectrodesAlreadyAssigned. Then these electrodes are
sorted out to identify the one that has the minimum index number. The electrode
with the minimum index number is written as E
neighbor
as shown in Fig.
6.3
. Then,
starting from Pin 1 and proceeding through Pin N
L
, we search for the control pin
that can be assigned to E
neighbor
to obtain a feasible pin-assignment solution. Here
are the detailed steps of the searching process.
Each time we virtually assign a control pin to E
neighbor
, and update G
EAA
by doing the union of the original G
EAA
with the graph that corresponds to
the new electrode. Then we determine whether the updated G
EAA
is a simple
graph. Based on Lemma
6.2
,ifG
EAA
is a simple graph, then we have expanded
the feasible local solution successfully and E
neighbor
will be added into the set
ElectrodesAlreadyAssigned, as shown in Fig.
6.3
. Otherwise, the pin that is assigned
to E
neighbor
will be changed.
If none of the pins in set
PinAvailable
can be assigned to E
neighbor
,anew
pin is added into
PinAvailable
, and this newly added pin is assigned to E
neighbor
.
By repeating the above procedure, the set ElectrodesAlreadyAssigned can be
expanded step-by-step until it covers the whole layout. When we assign pins to the
