148
E. C. Ferraz et al.
Table 6.14 Vector v updated
from X 1 and X 2 , for the first
loop example
Minterms f X 1 X 2
v
0
0 0
0
0
1
0 0
0
0
2
0 0
1
1
3
0 0
1
1
4
1 0
1
1
5
1 0
1
1
6
1 0
1
1
7
0 0
1
1
8
0 0
0
0
9
1 1
0
1
10
0 0
0
0
11
0 1
0
1
12
0 0
0
0
13
0 1
0
1
14
0 0
1
1
15
1 1
1
2
that covers the minterms {0, 1, 4, 5, 6, 8, 9, 12}, and has 1100111011001000 as
truth table. Accordingly, we have M(X 1 , X 2 , X 3 ) = M(M(A, D, 0), M(A, B, C),
M(C, M(B, D, 1), M(A, B, 0))).
The dual form of M(M(A, D, 0), M(A, B, C), M(C, M(B, D, 1), M(A, B, 0)))
is equal to M(M(A, D, 1), M(A, B, C), M(C, M(B, D, 0), M(A, B, 1))), which
has a higher amount of inverters. Therefore, for f = {4, 5, 6, 9, 15}, the MP C
algorithm adds M(M(A, D, 0), M(A, B, C), M(C, M(B, D, 1), M(A, B, 0))) to
its table of possible outputs Z. The loop ends when every pair of functions in P
are selected and combined with a function from M 2 , and returns the lowest cost
function in Z as output.
From all 55,184 sets of minterms that can be covered by a 3-level function,
50,016 can be covered by functions where two elements of X c are primitives. Those
functions are found by the first loop.
Among the 5168 remaining sets, 5056 can be covered by functions where only
one element of X c is a primitive. The 112 remaining sets can only be covered by
functions where all elements of X c are 2-level functions from M 2 . Those functions
are found by the second loop.
The second loop is composed by the following steps:
1. Select X 1 from the primitives table. If every primitive function has been
selected as X 1 and a valid output function could not be found, X 1 is selected
from a group of functions R. The group R is formed by every M 2 function with
size r, where r represents the number of gates in a M 2 function. Therefore, r
starts at 2, the lowest number of gates that a 2-level majority function can have,
and is incremented if a group R with higher size functions must be defined.
E. C. Ferraz et al.
Table 6.14 Vector v updated
from X 1 and X 2 , for the first
loop example
Minterms f X 1 X 2
v
0
0 0
0
0
1
0 0
0
0
2
0 0
1
1
3
0 0
1
1
4
1 0
1
1
5
1 0
1
1
6
1 0
1
1
7
0 0
1
1
8
0 0
0
0
9
1 1
0
1
10
0 0
0
0
11
0 1
0
1
12
0 0
0
0
13
0 1
0
1
14
0 0
1
1
15
1 1
1
2
that covers the minterms {0, 1, 4, 5, 6, 8, 9, 12}, and has 1100111011001000 as
truth table. Accordingly, we have M(X 1 , X 2 , X 3 ) = M(M(A, D, 0), M(A, B, C),
M(C, M(B, D, 1), M(A, B, 0))).
The dual form of M(M(A, D, 0), M(A, B, C), M(C, M(B, D, 1), M(A, B, 0)))
is equal to M(M(A, D, 1), M(A, B, C), M(C, M(B, D, 0), M(A, B, 1))), which
has a higher amount of inverters. Therefore, for f = {4, 5, 6, 9, 15}, the MP C
algorithm adds M(M(A, D, 0), M(A, B, C), M(C, M(B, D, 1), M(A, B, 0))) to
its table of possible outputs Z. The loop ends when every pair of functions in P
are selected and combined with a function from M 2 , and returns the lowest cost
function in Z as output.
From all 55,184 sets of minterms that can be covered by a 3-level function,
50,016 can be covered by functions where two elements of X c are primitives. Those
functions are found by the first loop.
Among the 5168 remaining sets, 5056 can be covered by functions where only
one element of X c is a primitive. The 112 remaining sets can only be covered by
functions where all elements of X c are 2-level functions from M 2 . Those functions
are found by the second loop.
The second loop is composed by the following steps:
1. Select X 1 from the primitives table. If every primitive function has been
selected as X 1 and a valid output function could not be found, X 1 is selected
from a group of functions R. The group R is formed by every M 2 function with
size r, where r represents the number of gates in a M 2 function. Therefore, r
starts at 2, the lowest number of gates that a 2-level majority function can have,
and is incremented if a group R with higher size functions must be defined.