162
A. Bernasconi et al.
is exploited in [3, 4] where the authors propose a synthesis method for switching
lattices simultaneously implementing a function f according to the connectivity
between the top and the bottom plates, and its dual function 1 f D according to the
connectivity between the left and the right plates. This method produces lattices
with a size that grows linearly with the number of products in an irredundant sum
of products (SOP) representation of f , and consists of the following steps:
1. find an irredundant, or a minimal, SOP representation for f and f D :
SOP (f ) = p 1 + p 2 + · · · + p M SOP (f
D ) = q 1 + q 2 + · · · + q N ;
2. form a N × M switching lattice and assign each product p j (1 ≤ j ≤ M) of
SOP (f ) to a column and each product q i (1 ≤ i ≤ N ) of SOP (f D ) to a row;
3. for all 1 ≤ i ≤ N and all 1 ≤ j ≤ M, assign to the switch on the lattice site
(i, j ) one literal which is shared by q i and p j (the fact that f and f D are duals
guarantees that such a shared literal exists for all i and j , as proved in [4]).
If several literals are shared by the two products q i and p j in step 3, the choice of
the controlling literal is arbitrary.
This synthesis algorithm produces a lattice for f whose size depends on the
number of products in the irredundant SOP representations of f and f D , and it
comes with the dual function implemented for free. For instance, the lattice depicted
in Fig. 7.1 has been built according to this algorithm, and it implements both the
function f = x 1 x 2 x 3 + x 1 x 3 + x 2 x 3 and its dual f D = x 1 x 2 x 3 + x 1 x 3 + x 2 x 3 .
The time complexity of the algorithm is polynomial in the number of products.
However, the method does not always build lattices of minimal size for every target
function, since it ties the dimensions of the lattices to the number of products in
the SOP forms for f and f D . In particular this method is not effective for Boolean
functions whose duals have a very large number of products, as the size of the lattice
is M × N and both factors can be exponential in the number n of variables. An
immediate comparison can be carried out between the lattice and the layout of a
PLA implementing the same function whose size is 2n × M. In the example of
Fig. 7.1 the lattice consists of 3 × 3 = 9 cells, while an equivalent PLA would
require 6 × 3 = 18 cells, but other functions may be strongly negative for the lattice.
A different approach was proposed in [26] where the synthesis of minimalsized lattices was formulated as a satisfiability problem in quantified Boolean logic
and solved by quantified Boolean formula solvers. This method uses the previous
algorithm to find an upper bound on the dimensions of the lattice, then searches
for successively better implementations until either an optimal solution is found
or a preset time limit has been exceeded. Experimental results show how this
alternative method can decrease lattice sizes considerably. In this approach the use
1 The dual of a Boolean function f of n binary variables is the function f D such that
f (x 1 , x 2 , . . . , x n ) = f D (x 1 , x 2 , . . . , x n ).
A. Bernasconi et al.
is exploited in [3, 4] where the authors propose a synthesis method for switching
lattices simultaneously implementing a function f according to the connectivity
between the top and the bottom plates, and its dual function 1 f D according to the
connectivity between the left and the right plates. This method produces lattices
with a size that grows linearly with the number of products in an irredundant sum
of products (SOP) representation of f , and consists of the following steps:
1. find an irredundant, or a minimal, SOP representation for f and f D :
SOP (f ) = p 1 + p 2 + · · · + p M SOP (f
D ) = q 1 + q 2 + · · · + q N ;
2. form a N × M switching lattice and assign each product p j (1 ≤ j ≤ M) of
SOP (f ) to a column and each product q i (1 ≤ i ≤ N ) of SOP (f D ) to a row;
3. for all 1 ≤ i ≤ N and all 1 ≤ j ≤ M, assign to the switch on the lattice site
(i, j ) one literal which is shared by q i and p j (the fact that f and f D are duals
guarantees that such a shared literal exists for all i and j , as proved in [4]).
If several literals are shared by the two products q i and p j in step 3, the choice of
the controlling literal is arbitrary.
This synthesis algorithm produces a lattice for f whose size depends on the
number of products in the irredundant SOP representations of f and f D , and it
comes with the dual function implemented for free. For instance, the lattice depicted
in Fig. 7.1 has been built according to this algorithm, and it implements both the
function f = x 1 x 2 x 3 + x 1 x 3 + x 2 x 3 and its dual f D = x 1 x 2 x 3 + x 1 x 3 + x 2 x 3 .
The time complexity of the algorithm is polynomial in the number of products.
However, the method does not always build lattices of minimal size for every target
function, since it ties the dimensions of the lattices to the number of products in
the SOP forms for f and f D . In particular this method is not effective for Boolean
functions whose duals have a very large number of products, as the size of the lattice
is M × N and both factors can be exponential in the number n of variables. An
immediate comparison can be carried out between the lattice and the layout of a
PLA implementing the same function whose size is 2n × M. In the example of
Fig. 7.1 the lattice consists of 3 × 3 = 9 cells, while an equivalent PLA would
require 6 × 3 = 18 cells, but other functions may be strongly negative for the lattice.
A different approach was proposed in [26] where the synthesis of minimalsized lattices was formulated as a satisfiability problem in quantified Boolean logic
and solved by quantified Boolean formula solvers. This method uses the previous
algorithm to find an upper bound on the dimensions of the lattice, then searches
for successively better implementations until either an optimal solution is found
or a preset time limit has been exceeded. Experimental results show how this
alternative method can decrease lattice sizes considerably. In this approach the use
1 The dual of a Boolean function f of n binary variables is the function f D such that
f (x 1 , x 2 , . . . , x n ) = f D (x 1 , x 2 , . . . , x n ).