150
E. C. Ferraz et al.
For n = 5, S = 4,294,967,296 and 172 of these sets can be covered by primitives,
with at most one majority gate. The M 2 table stores the 253,560 sets that can be
covered by majority functions with 2 levels. The remaining sets need more than 2
levels to be covered.
To build 3-level functions the algorithm also uses the expression M(X 1 , X 2 , X 3 ),
realizing the combination of primitives and M 2 functions, selected by their lowest
cost.
The complete synthesis for 3-level functions is composed by the following
steps:
1. Order by cost every function from the primitives and M 2 tables.
2. Select the function with the lowest cost as X 1 .
3. Reduce the cost by one for every primitive or M 2 function that is composed by a
gate that also composes X 1 .
4. Create v 0 and v −1 , where v 0 = f − X 1 and v −1 = X 1 − f .
5. Select X 2 , firstly from the primitives, as the lowest cost function that:
– Covers all minterms in v 0 .
– Doesn’t cover any minterm in v −1 .
If no valid X 2 could be found among the primitives, select X 2 from the M 2
table. If still no valid X 2 could be found, go back to step 2 and select a new X 1 .
6. Again, update the cost of the primitives and M 2 functions based on the gates in
X 1 and X 2 .
7. Create v 1 , where v 1 stores the minterms covered by f and only once by X c .
8. Select X 3 , firstly from the primitives, the lowest cost function that:
– Covers all minterms in v 1 .
– Doesn’t cover any minterm in v −1 .
If no valid X 3 could be found among the primitives, select X 3 from the M 2
table. If still no valid X 3 could be found, go back to step 5 and select a new X 2 .
9. With the selection of X 3 we now have a valid output. Next apply Ω.I to every
level of M(X 1 , X 2 , X 3 ) and return the lowest cost version as output.
To exemplify the second loop, consider n = 5 and f = {2, 4, 6, 7, 8, 11, 13,
14, 15}. A valid output function can be found in the iteration where X 1 = C,
covering the minterms {4, 5, 6, 7, 12, 13, 14, 15, 20, 21, 22, 23, 28, 29, 30, 31}.
Updating the vector v based on X 1 , we have v 0 = {2, 8, 11} and v −1 =
{5, 12, 20, 21, 22, 23, 28, 29, 30, 31}. Table 6.15 shows v after the selection of X 1 .
As X 2 , we select the lowest cost function from M 2 that covers every minterm in
v 0 but doesn’t cover any of the minterms in v −1 .
We select X 2 = M(M(C, D, 1), M(B, E, 0), M(A, B, E)) that covers
{0, 1, 2, 4, 6, 8, 9, 11, 13, 15, 16, 17, 24, 25}. From X 2 , we update v again, generating v 1 = {2, 7, 8, 11, 14} and v −1 = {0, 1, 5, 9, 12, 16, 17, 20, 21, 22, 23, 24, 25,
28, 29, 30, 31}. Table 6.16 shows v updated after X 2 ’s selection.
As X 3 , we select the lowest cost function from M 2 that doesn’t cover any
minterms in v −1 and covers all minterms in v 1 .
E. C. Ferraz et al.
For n = 5, S = 4,294,967,296 and 172 of these sets can be covered by primitives,
with at most one majority gate. The M 2 table stores the 253,560 sets that can be
covered by majority functions with 2 levels. The remaining sets need more than 2
levels to be covered.
To build 3-level functions the algorithm also uses the expression M(X 1 , X 2 , X 3 ),
realizing the combination of primitives and M 2 functions, selected by their lowest
cost.
The complete synthesis for 3-level functions is composed by the following
steps:
1. Order by cost every function from the primitives and M 2 tables.
2. Select the function with the lowest cost as X 1 .
3. Reduce the cost by one for every primitive or M 2 function that is composed by a
gate that also composes X 1 .
4. Create v 0 and v −1 , where v 0 = f − X 1 and v −1 = X 1 − f .
5. Select X 2 , firstly from the primitives, as the lowest cost function that:
– Covers all minterms in v 0 .
– Doesn’t cover any minterm in v −1 .
If no valid X 2 could be found among the primitives, select X 2 from the M 2
table. If still no valid X 2 could be found, go back to step 2 and select a new X 1 .
6. Again, update the cost of the primitives and M 2 functions based on the gates in
X 1 and X 2 .
7. Create v 1 , where v 1 stores the minterms covered by f and only once by X c .
8. Select X 3 , firstly from the primitives, the lowest cost function that:
– Covers all minterms in v 1 .
– Doesn’t cover any minterm in v −1 .
If no valid X 3 could be found among the primitives, select X 3 from the M 2
table. If still no valid X 3 could be found, go back to step 5 and select a new X 2 .
9. With the selection of X 3 we now have a valid output. Next apply Ω.I to every
level of M(X 1 , X 2 , X 3 ) and return the lowest cost version as output.
To exemplify the second loop, consider n = 5 and f = {2, 4, 6, 7, 8, 11, 13,
14, 15}. A valid output function can be found in the iteration where X 1 = C,
covering the minterms {4, 5, 6, 7, 12, 13, 14, 15, 20, 21, 22, 23, 28, 29, 30, 31}.
Updating the vector v based on X 1 , we have v 0 = {2, 8, 11} and v −1 =
{5, 12, 20, 21, 22, 23, 28, 29, 30, 31}. Table 6.15 shows v after the selection of X 1 .
As X 2 , we select the lowest cost function from M 2 that covers every minterm in
v 0 but doesn’t cover any of the minterms in v −1 .
We select X 2 = M(M(C, D, 1), M(B, E, 0), M(A, B, E)) that covers
{0, 1, 2, 4, 6, 8, 9, 11, 13, 15, 16, 17, 24, 25}. From X 2 , we update v again, generating v 1 = {2, 7, 8, 11, 14} and v −1 = {0, 1, 5, 9, 12, 16, 17, 20, 21, 22, 23, 24, 25,
28, 29, 30, 31}. Table 6.16 shows v updated after X 2 ’s selection.
As X 3 , we select the lowest cost function from M 2 that doesn’t cover any
minterms in v −1 and covers all minterms in v 1 .