Biomedical Engineering Reference
In-Depth Information
1
1
2
3
512345
234512
451234
123451
345123
512345
1
2
3
1
2
1
1
2
3
1
1
123
3
1
3
12
1
1
2
3
Figure 3.8
Covering a partition by shifting a Bagua repetition along rows.
Five copies of Bagua repetitions are sufficient to cover a partition of any
size. This is because of the following property of a Bagua repetition: vertices
connected to the same (shared) pin appear after exactly five cells in the same
row or column of the partition. The partition can be covered with Bagua rep-
etitions by simply taking a Bagua repetition and shifting it one cell along an
arbitrary direction, for example, upward, then assigning it to another control
pin and repeating this step four times, as shown in Figure 3.8. Note that,
although the shifting direction is arbitrarily selected at the start of the tiling
process, once chosen it must be consistent over the four shifting steps.
As shown in Figure 3.8, the pin assignment that results from the shifting of
Bagua repetition satisfies a cyclic property, that is, each row is a cyclic repeti-
tion of an ordered sequence, and it is also a shifted copy (shift by two cells)
of the previous row. This cyclic property provides an easy way to implement
the Connect-5 algorithm.
To start, the first row of a partition is selected. Pins are assigned in a fixed
cyclic order until the boundary of the partition is reached. Then, in the next
row, the same order is used but with a 2-cell-shift to the left/right. The pro-
cedure continues until all cells in the partition have been assigned pins.
Recall that the shifting direction, once chosen, must remain fixed during the
assignment procedure for a given partition.
Next, we show that control pins assigned to the electrodes in a partition
using this method allows free movement of a single droplet; that is, the cross
constraint is met. To demonstrate this, we consider the cell that is hatched
in Figure 3.9. If the cell is assigned Pin 1, we cannot assign the same pin to
the unit cells that are shaded. Otherwise, we will violate the cross constraint
in some cases. It can be found that all the unit cells in the Bagua tile and its
repetitions stay out of the forbidden area. Thus, for each pin assigned to cells
in a Bagua repetition, the cross constraint is not violated. Since this is true for
any Bagua repetitions and any partition can be tiled by five copies of Bagua
repetitions, the cross constraint is automatically met for every cell in our
pin-assignment method.
Compared to the graph-coloring approach, the Connect-5 algorithm offers
the important advantage that it allows wiring to be done easily on a 3-layer
Search WWH ::




Custom Search