6 Synthesis of Majority Expressions Through Primitive Function Manipulation
149
2. Create two new vectors, v 0 and v −1 . The vector v 0 contains the positions of f
that haven’t been covered yet; therefore, v 0 = f − X 1 . The vector v −1 has the
positions of v that can’t be covered one more time; therefore, v −1 = X 1 − f .
3. From v 0 and v −1 the truth tables for X 2 , represented by the variable X 2 f are
generated. X 2 f represents a truth table, with the same size of f , that can have
binary values or don’t care states. For the minterms stored in v 0 , X 2 f i = 1.
For minterms stored in v −1 , X 2 f i = 0. The other minterms are all considered
don’t care states.
4. Every possible truth table manipulating the don’t care states in X 2 f is
generated. Each possibility is searched in the M 2 table. From these functions a
new table, P 2 , is created.
5. For every function in P 2 that is composed by a gate that also composes X 1 , its
cost is reduced by one.
6. Select the lowest cost function in P 2 , that was not selected yet, as X 2 . If there’s
no valid X 2 , go back to the first step and select a new X 1 .
7. To find X 3 create X 3 f based on v −1 and a new vector v 1 . The vector v 1 stores
the minterms of f covered only once by X c . Therefore, the minterms in v 1 must
be covered by X 3 . For the minterms stored in v −1 , X 3 f = 0. For the minterms
stored in v 1 , X 3 f = 1.
8. To find all possibilities for X 3 f , search the respective functions in the M 2 table
and build P 3 from them.
9. Again, update the cost of the functions in P 3 based on the gates in X 1 and X 2 .
10. Select the lowest cost function in P 3 , that hasn’t been selected yet, as X 3 . If
there’s no valid X 3 , go back to step 6 and select a new X 2 .
11. With the selection of X 3 we now have a valid output M(X 1 , X 2 , X 3 ). For the
minimization of inverters we also apply Ω.I to every level of the function built
and we substitute it if the function post Ω.I application has a lower cost.
12. Every M(X 1 , X 2 , X 3 ) found is stored in table Z and the loop stops when
all primitive functions are selected as X 1 . If no function could be found, the
algorithm goes back to the first step and restarts selecting X 1 from a group R,
stopping when all functions in R were selected as X 1 . If yet no function could
be found, the algorithm increments r and restarts the loop with a new group R.
The algorithm returns the lowest cost function stored in Z as output.
For the two sets that need a function with four levels to be covered, we first select
X 1 from the primitives table, then we build X 2 and X 3 as 3-level functions using
the explained synthesis.
6.3.3 MP C Synthesis for 5-Input Functions
The synthesis for 5-input (n = 5) functions also uses the primitives and the M 2 table
as a base to build functions with a higher number of levels.
149
2. Create two new vectors, v 0 and v −1 . The vector v 0 contains the positions of f
that haven’t been covered yet; therefore, v 0 = f − X 1 . The vector v −1 has the
positions of v that can’t be covered one more time; therefore, v −1 = X 1 − f .
3. From v 0 and v −1 the truth tables for X 2 , represented by the variable X 2 f are
generated. X 2 f represents a truth table, with the same size of f , that can have
binary values or don’t care states. For the minterms stored in v 0 , X 2 f i = 1.
For minterms stored in v −1 , X 2 f i = 0. The other minterms are all considered
don’t care states.
4. Every possible truth table manipulating the don’t care states in X 2 f is
generated. Each possibility is searched in the M 2 table. From these functions a
new table, P 2 , is created.
5. For every function in P 2 that is composed by a gate that also composes X 1 , its
cost is reduced by one.
6. Select the lowest cost function in P 2 , that was not selected yet, as X 2 . If there’s
no valid X 2 , go back to the first step and select a new X 1 .
7. To find X 3 create X 3 f based on v −1 and a new vector v 1 . The vector v 1 stores
the minterms of f covered only once by X c . Therefore, the minterms in v 1 must
be covered by X 3 . For the minterms stored in v −1 , X 3 f = 0. For the minterms
stored in v 1 , X 3 f = 1.
8. To find all possibilities for X 3 f , search the respective functions in the M 2 table
and build P 3 from them.
9. Again, update the cost of the functions in P 3 based on the gates in X 1 and X 2 .
10. Select the lowest cost function in P 3 , that hasn’t been selected yet, as X 3 . If
there’s no valid X 3 , go back to step 6 and select a new X 2 .
11. With the selection of X 3 we now have a valid output M(X 1 , X 2 , X 3 ). For the
minimization of inverters we also apply Ω.I to every level of the function built
and we substitute it if the function post Ω.I application has a lower cost.
12. Every M(X 1 , X 2 , X 3 ) found is stored in table Z and the loop stops when
all primitive functions are selected as X 1 . If no function could be found, the
algorithm goes back to the first step and restarts selecting X 1 from a group R,
stopping when all functions in R were selected as X 1 . If yet no function could
be found, the algorithm increments r and restarts the loop with a new group R.
The algorithm returns the lowest cost function stored in Z as output.
For the two sets that need a function with four levels to be covered, we first select
X 1 from the primitives table, then we build X 2 and X 3 as 3-level functions using
the explained synthesis.
6.3.3 MP C Synthesis for 5-Input Functions
The synthesis for 5-input (n = 5) functions also uses the primitives and the M 2 table
as a base to build functions with a higher number of levels.