Biomedical Engineering Reference
In-Depth Information
sequences can be generated from a single signal source. Therefore, the cor-
responding electrodes E
1
and E
4
can be connected to a single control pin.
3.3.2 Optimization based on Clique Partitioning in graphs
In this subsection, we focus on reducing the number of control pins by con-
necting together electrodes with mutually compatible activation sequences,
and addressing them using a single control pin. Therefore, the resulting
electrode-access method is referred to as a
broadcast addressing
. We first parti-
tion the electrodes into groups. For all the electrodes in any group, the cor-
responding activation sequences must be pairwise compatible. Our goal is
to find an optimal partition that leads to the minimum number of groups,
which in turn yields the minimum number of control pins.
The problem of finding the minimum number of groups can be easily mapped
to the clique-partitioning problem from graph theory [56]. We use the example
in Figure 3.32 to illustrate this mapping. Based on the activation-sequence table,
an undirected graph, referred to as electrode-activation graph, is constructed
(see Figure 3.33)
. Each node in the graph represents an activation sequence for
an electrode. An edge in the graph between a pair of nodes indicates that their
corresponding activation sequences are compatible. For example, nodes 1 and
4, which represent the activation sequences for electrode E1 and E4, respec-
tively, are connected by an edge because the activation sequences can be con-
verted to a single sequence “01000010” by replacing the don't-care terms.
As mentioned in Subsection 3.2.2, a
clique
in a graph is defined as a com-
plete subgraph; that is, any two nodes in this subgraph are connected by an
edge [56].
Clique partitioning
refers to the problem of dividing the set of nodes
into nonoverlapping subsets such that the subgraph induced by each subset
of nodes is a clique. A
minimal clique partition
is one that covers the nodes in
the graph with a minimum number of nonoverlapping cliques. The group-
ing of droplets as discussed earlier is equivalent to the clique-partitioning
problem. A minimal clique partition here for this example is given by {1,4},
{5,8}, {2,6}, and {3,7}. Even though the general clique-partitioning problem is
known to be NP-hard [57], a number of heuristics are available in the litera-
ture to solve it in an efficient manner.
2
3
1
8
4
7
5
6
Figure 3.33
Mapping of the activation sequences of Figure 3.32 to an undirected graph.
