7 Literal Selection in Switching Lattice Design
163
of constant inputs is allowed and only the top-to-bottom paths are used to implement
the function f but not its dual.
7.3 The Problem of Literal Selection
In this work we only consider lattices obtained by the Altun–Riedel method, and
study how to exploit the degree of freedom arising from the multiple choices
associated with some of the switches.
Consider the N × M lattice as a non-directed graph G = (V , E) whose vertices
correspond to the switches (then |V | = NM) and whose edges correspond to the
horizontal and vertical connections between adjacent switches (then E = 2NM −
N − M). We shall refer indifferently to the lattice or to the graph, to switches (or
cells) or to vertices, and to connections or to edges. Occasionally a vertex will be
indicated with a pair of integers (i, j ) denoting the row and the column of the lattice
where the vertex lays, with 1 ≤ i ≤ N and 1 ≤ j ≤ M, or with v h , with 1 ≤
h ≤ NM. Observe that h = j + (i − 1)M, that is, h spans the lattice row by
row. Obviously the vertices have degree two or three if they lay on the corners or
on the borders of the lattice, and have degree four if they are internal to the lattice.
Finally, let L be the set of literals occurring in the Boolean function. Each vertex
v i is associated with a non-void subset L i of L, from which one literal has to be
eventually assigned to v i .
Consider, for instance, the 3 × 3 lattice in Fig. 7.2a taken from [4] which presents
multiple choices on the diagonal cells. The set of literals occurring in the lattice is
L = {x 1 , x 2 , x 3 }. The vertices v 1 , v 5 , v 9 corresponding to the three diagonal cells
are associated with the three subsets L 1 = {x 1 , x 2 }, L 5 = {x 1 , x 3 }, and L 9 =
{x 2 , x 3 }, respectively, while all other vertices are associated with one literal.
Once a single literal has been assigned to each vertex of the lattice, we can define
the notions of degree and area:
Definition 7.1 The degree of a literal l in a lattice is the number of switches
controlled by l. The degree of the lattice is the maximum degree of its literals, i.e.,
the maximum number of lattice cells assigned to the same literal.
Definition 7.2 An area denotes a maximal connected subgraph of G (or connected
portion of the lattice) where all vertices have the same literal assigned, called the
literal of the area.
Note that two areas A 1 , A 2 with the same literal must be disjoint and no two vertices
a 1 ∈ A 1 , a 2 ∈ A 2 may be adjacent in G.
Both notions play an important role in the physical implementation of switching
lattices. The degree is related to the current supply needed for the literals in the
lattice, while the areas are related to the number of layers needed for connecting
163
of constant inputs is allowed and only the top-to-bottom paths are used to implement
the function f but not its dual.
7.3 The Problem of Literal Selection
In this work we only consider lattices obtained by the Altun–Riedel method, and
study how to exploit the degree of freedom arising from the multiple choices
associated with some of the switches.
Consider the N × M lattice as a non-directed graph G = (V , E) whose vertices
correspond to the switches (then |V | = NM) and whose edges correspond to the
horizontal and vertical connections between adjacent switches (then E = 2NM −
N − M). We shall refer indifferently to the lattice or to the graph, to switches (or
cells) or to vertices, and to connections or to edges. Occasionally a vertex will be
indicated with a pair of integers (i, j ) denoting the row and the column of the lattice
where the vertex lays, with 1 ≤ i ≤ N and 1 ≤ j ≤ M, or with v h , with 1 ≤
h ≤ NM. Observe that h = j + (i − 1)M, that is, h spans the lattice row by
row. Obviously the vertices have degree two or three if they lay on the corners or
on the borders of the lattice, and have degree four if they are internal to the lattice.
Finally, let L be the set of literals occurring in the Boolean function. Each vertex
v i is associated with a non-void subset L i of L, from which one literal has to be
eventually assigned to v i .
Consider, for instance, the 3 × 3 lattice in Fig. 7.2a taken from [4] which presents
multiple choices on the diagonal cells. The set of literals occurring in the lattice is
L = {x 1 , x 2 , x 3 }. The vertices v 1 , v 5 , v 9 corresponding to the three diagonal cells
are associated with the three subsets L 1 = {x 1 , x 2 }, L 5 = {x 1 , x 3 }, and L 9 =
{x 2 , x 3 }, respectively, while all other vertices are associated with one literal.
Once a single literal has been assigned to each vertex of the lattice, we can define
the notions of degree and area:
Definition 7.1 The degree of a literal l in a lattice is the number of switches
controlled by l. The degree of the lattice is the maximum degree of its literals, i.e.,
the maximum number of lattice cells assigned to the same literal.
Definition 7.2 An area denotes a maximal connected subgraph of G (or connected
portion of the lattice) where all vertices have the same literal assigned, called the
literal of the area.
Note that two areas A 1 , A 2 with the same literal must be disjoint and no two vertices
a 1 ∈ A 1 , a 2 ∈ A 2 may be adjacent in G.
Both notions play an important role in the physical implementation of switching
lattices. The degree is related to the current supply needed for the literals in the
lattice, while the areas are related to the number of layers needed for connecting