6 Synthesis of Majority Expressions Through Primitive Function Manipulation
145
primitives table based on the sets C, V , G, and T . We also store the set of minterms
covered by every primitive function. Note that each primitive function is the optimal
solution of its respective set of minterms.
The second table built by the MP C is the M 2 table, formed by the application of all possible combinations among primitive functions in the expression
M(X 1 , X 2 , X 3 ), without considering repeated primitives. For each generated function the set of covered minterms is also stored. If a set is covered by two or
more functions, the one with the lowest cost is kept and the others are discarded.
Therefore, the table M 2 lists all sets of minterms that can be covered by a 2-level
majority function and, since they are obtained exhaustively, M 2 functions are also
an optimal solution for their respective set of minterms. It is also important to point
out that, for computational performance optimization, the M 2 is stored as a LU T
(Look-Up Table) in the MP C code.
As an example of a M 2 function, we have M(X 1 , X 2 , X 3 ) = M(A, M(A, B, 0),
M(A, B, C)), where X 1 = A, X 2 = M(A, B, 0), and X 3 = M(A, B, C).
The cost criteria used by the MP C is primarily the number of levels and gates in
the output function, followed by the number of inverters and gate inputs.
To ensure the minimization of inverters, the single gate primitives follow four
possible patterns:
– M(A, B, C), no inverters;
– M(A, B, C), a single complemented input;
– M(A, B, C), a single inverter applied to the output value;
– M(A, B, C), a single input and the output complemented.
Note that in cases where the gate has two inverters, even though the number of
inverters stay the same, it’s better to complement the output and only one input,
since M(X, Y, Z) = M(X, Y , Z). This allows the application of Ω.I to minimize
the number of inverters when the primitives are being used to build functions with
two or more levels.
To exemplify this application we consider: M(M(A, B, C), D, 0), which has 2
levels, 2 gates, and 3 inverters. By applying Ω.I we have M(M(A, B, C), D, 0) =
M(M(A, B, C), D, 1), which has the same number of levels and gates, but has one
less inverter.
It’s also important to point out that repeated gates are not considered in
the cost calculation. In the function M(M(0, A, C), M(1, A, M(B, C, D)),
M(1, C, M(B, C, D))), for example, given that the gate M(B, C, D) appears
twice, we count a total of five gates in the function cost.
The total of possible functions for a specific number of inputs is represented by
the variable S, and can be calculated by 2 m . Note that m = 2 n , and represents the
number of minterms in the input truth table f .
For n = 3, S = 256. The primitives table covers 40 of these functions. The
216 left are covered by the M 2 table. Therefore, S can be completely covered by
majority expressions with at most two levels, which makes the table formulation
phase enough for obtaining all optimal solutions for n = 3.
145
primitives table based on the sets C, V , G, and T . We also store the set of minterms
covered by every primitive function. Note that each primitive function is the optimal
solution of its respective set of minterms.
The second table built by the MP C is the M 2 table, formed by the application of all possible combinations among primitive functions in the expression
M(X 1 , X 2 , X 3 ), without considering repeated primitives. For each generated function the set of covered minterms is also stored. If a set is covered by two or
more functions, the one with the lowest cost is kept and the others are discarded.
Therefore, the table M 2 lists all sets of minterms that can be covered by a 2-level
majority function and, since they are obtained exhaustively, M 2 functions are also
an optimal solution for their respective set of minterms. It is also important to point
out that, for computational performance optimization, the M 2 is stored as a LU T
(Look-Up Table) in the MP C code.
As an example of a M 2 function, we have M(X 1 , X 2 , X 3 ) = M(A, M(A, B, 0),
M(A, B, C)), where X 1 = A, X 2 = M(A, B, 0), and X 3 = M(A, B, C).
The cost criteria used by the MP C is primarily the number of levels and gates in
the output function, followed by the number of inverters and gate inputs.
To ensure the minimization of inverters, the single gate primitives follow four
possible patterns:
– M(A, B, C), no inverters;
– M(A, B, C), a single complemented input;
– M(A, B, C), a single inverter applied to the output value;
– M(A, B, C), a single input and the output complemented.
Note that in cases where the gate has two inverters, even though the number of
inverters stay the same, it’s better to complement the output and only one input,
since M(X, Y, Z) = M(X, Y , Z). This allows the application of Ω.I to minimize
the number of inverters when the primitives are being used to build functions with
two or more levels.
To exemplify this application we consider: M(M(A, B, C), D, 0), which has 2
levels, 2 gates, and 3 inverters. By applying Ω.I we have M(M(A, B, C), D, 0) =
M(M(A, B, C), D, 1), which has the same number of levels and gates, but has one
less inverter.
It’s also important to point out that repeated gates are not considered in
the cost calculation. In the function M(M(0, A, C), M(1, A, M(B, C, D)),
M(1, C, M(B, C, D))), for example, given that the gate M(B, C, D) appears
twice, we count a total of five gates in the function cost.
The total of possible functions for a specific number of inputs is represented by
the variable S, and can be calculated by 2 m . Note that m = 2 n , and represents the
number of minterms in the input truth table f .
For n = 3, S = 256. The primitives table covers 40 of these functions. The
216 left are covered by the M 2 table. Therefore, S can be completely covered by
majority expressions with at most two levels, which makes the table formulation
phase enough for obtaining all optimal solutions for n = 3.