6 Synthesis of Majority Expressions Through Primitive Function Manipulation
147
Table 6.13 Generation of vector v
Minterms
f = {0, 1, 5, 8}
X 1 = {0, 1, 4, 5}
X 2 = {0, 1, 2, 8, 10}
v
0
1
1
1
2
1
1
1
1
2
2
0
0
1
1
3
0
0
0
0
4
0
1
0
1
5
1
1
0
1
6
0
0
0
0
7
0
0
0
0
8
1
0
1
1
9
0
0
0
0
10
0
0
1
1
11
0
0
0
0
12
0
0
0
0
13
0
0
0
0
14
0
0
0
0
15
0
0
0
0
7. For every function in P 3 composed by a gate that also composes X 1 or X 2 , we
reduce its cost by 1. This rule exists because each gate is counted only once in
the calculation of a majority function size.
8. Select the lowest cost function in P 3 , that hasn’t been selected yet, as X 3 . If
there’s no valid X 3 , we go back to step 3 and find a new primitive pair.
9. With the selection of X 3 we now have a valid output M(X 1 , X 2 , X 3 ). To
minimize inverters, Ω.I is applied to every level of the function built. If
the function post Ω.I application has a lower cost, the previous function is
substituted.
10. The loop ends when every possible pair in P has been combined with a function
from M 2 , and every M(X 1 , X 2 , X 3 ) found is stored in table Z.
11. By the end of the loop, the algorithm returns the function with the lowest cost
in Z. If no function could be found the second loop starts.
To exemplify an iteration of the first loop, consider n = 4 and f =
{4, 5, 6, 9, 15}. A valid output function can be found in the iteration where
X 1 = M(A, D, 0) and X 2 = M(A, B, C), X 1 covering the minterms {9, 11, 13, 15}
and X 2 covering {2, 3, 4, 5, 6, 7, 14, 15}. Table 6.14 shows vector v updated from
X 1 and X 2 .
The minterms considered don’t care states, where v i = 2 or v i = 0, are
{0, 1, 8, 10, 12, 15}. The minterms where v i = 1 and f i = 1 are {4, 5, 6, 9},
and the minterms where v i = 1 and f i = 0 are {2, 3, 7, 11, 13, 14}. Therefore,
X 3 f = xx001110x1x0x00x.
We select as X 3 , from the M 2 table, the lowest cost function that fits the truth
table pattern formed by X 3 f . We select X 3 = M(C, M(B, D, 1), M(A, B, 0))
147
Table 6.13 Generation of vector v
Minterms
f = {0, 1, 5, 8}
X 1 = {0, 1, 4, 5}
X 2 = {0, 1, 2, 8, 10}
v
0
1
1
1
2
1
1
1
1
2
2
0
0
1
1
3
0
0
0
0
4
0
1
0
1
5
1
1
0
1
6
0
0
0
0
7
0
0
0
0
8
1
0
1
1
9
0
0
0
0
10
0
0
1
1
11
0
0
0
0
12
0
0
0
0
13
0
0
0
0
14
0
0
0
0
15
0
0
0
0
7. For every function in P 3 composed by a gate that also composes X 1 or X 2 , we
reduce its cost by 1. This rule exists because each gate is counted only once in
the calculation of a majority function size.
8. Select the lowest cost function in P 3 , that hasn’t been selected yet, as X 3 . If
there’s no valid X 3 , we go back to step 3 and find a new primitive pair.
9. With the selection of X 3 we now have a valid output M(X 1 , X 2 , X 3 ). To
minimize inverters, Ω.I is applied to every level of the function built. If
the function post Ω.I application has a lower cost, the previous function is
substituted.
10. The loop ends when every possible pair in P has been combined with a function
from M 2 , and every M(X 1 , X 2 , X 3 ) found is stored in table Z.
11. By the end of the loop, the algorithm returns the function with the lowest cost
in Z. If no function could be found the second loop starts.
To exemplify an iteration of the first loop, consider n = 4 and f =
{4, 5, 6, 9, 15}. A valid output function can be found in the iteration where
X 1 = M(A, D, 0) and X 2 = M(A, B, C), X 1 covering the minterms {9, 11, 13, 15}
and X 2 covering {2, 3, 4, 5, 6, 7, 14, 15}. Table 6.14 shows vector v updated from
X 1 and X 2 .
The minterms considered don’t care states, where v i = 2 or v i = 0, are
{0, 1, 8, 10, 12, 15}. The minterms where v i = 1 and f i = 1 are {4, 5, 6, 9},
and the minterms where v i = 1 and f i = 0 are {2, 3, 7, 11, 13, 14}. Therefore,
X 3 f = xx001110x1x0x00x.
We select as X 3 , from the M 2 table, the lowest cost function that fits the truth
table pattern formed by X 3 f . We select X 3 = M(C, M(B, D, 1), M(A, B, 0))