160
A. Bernasconi et al.
x 3
x 1
x 3
x 3
x 1
x 2
x 2
x 3
x 3
TOP
BOTTOM
(b)
x 3
x 1
x 2
x 2
x 3
x 3
x 3
TOP
BOTTOM
(a)
(c)
(d)
x 1
x 3
x 3
x 3
x 3
x 1
x 2
x 2
x 3
TOP
BOTTOM
x 3
x 3
x 3
x 1
x 2
x 2
x 3
x 3
TOP
BOTTOM
x 3
x 1
x 1
Fig. 7.1 A network of four-terminal switches implementing the function f = x 1 x 2 x 3 + x 1 x 3 +
x 2 x 3 (a); the corresponding lattice (b); the lattice evaluated on the assignments 1,0,1 (c) and 0, 1,
0 (d), with gray and white squares representing ON and OFF switches, respectively
If several literals are assigned to a switch the choice of the controlling literal is
arbitrary.
Starting from the lattice obtained by the Altun–Riedel method, we consider two
different minimization problems related to the assignment of one literal to each
switch in case of different choices at the switch. We first study how to assign a
single literal to each switch, in order to minimize the maximum number of lattice
switches assigned to the same literal. Then, we study how to assign the literals in
order to minimize the number of lattice portions of adjacent cells whose switches
are associated with the same literal, a problem that has already been investigated
in [21, 29].
These two problems are motivated by different aspects related to the physical
layout of switching lattices: for the first problem the goal is to keep under control
the input load for each literal in the lattice, whereas the goal of the second problem
is to minimize the number of layers needed for connecting the subsets of switches
with the same input literal. Interestingly enough, the two problems exhibit a very
A. Bernasconi et al.
x 3
x 1
x 3
x 3
x 1
x 2
x 2
x 3
x 3
TOP
BOTTOM
(b)
x 3
x 1
x 2
x 2
x 3
x 3
x 3
TOP
BOTTOM
(a)
(c)
(d)
x 1
x 3
x 3
x 3
x 3
x 1
x 2
x 2
x 3
TOP
BOTTOM
x 3
x 3
x 3
x 1
x 2
x 2
x 3
x 3
TOP
BOTTOM
x 3
x 1
x 1
Fig. 7.1 A network of four-terminal switches implementing the function f = x 1 x 2 x 3 + x 1 x 3 +
x 2 x 3 (a); the corresponding lattice (b); the lattice evaluated on the assignments 1,0,1 (c) and 0, 1,
0 (d), with gray and white squares representing ON and OFF switches, respectively
If several literals are assigned to a switch the choice of the controlling literal is
arbitrary.
Starting from the lattice obtained by the Altun–Riedel method, we consider two
different minimization problems related to the assignment of one literal to each
switch in case of different choices at the switch. We first study how to assign a
single literal to each switch, in order to minimize the maximum number of lattice
switches assigned to the same literal. Then, we study how to assign the literals in
order to minimize the number of lattice portions of adjacent cells whose switches
are associated with the same literal, a problem that has already been investigated
in [21, 29].
These two problems are motivated by different aspects related to the physical
layout of switching lattices: for the first problem the goal is to keep under control
the input load for each literal in the lattice, whereas the goal of the second problem
is to minimize the number of layers needed for connecting the subsets of switches
with the same input literal. Interestingly enough, the two problems exhibit a very