146
E. C. Ferraz et al.
For n = 4, S = 65,536 and 90 of these functions are primitives, with at most
one majority gate. In the formulation of M 2 , only 10,260 functions can be covered.
For the remaining 55,186, 55,184 can be covered by majority expressions with three
levels. The remaining two functions need a majority expression with four levels to
be covered.
6.3.2 MP C Synthesis for 4-Input Functions
This section presents the synthesis used in MP C for the construction of majority functions where n = 4. The objective of this synthesis is to formulate
M(X 1 , X 2 , X 3 ) with the combination of primitives and M 2 functions, generating
a majority function that covers the same minterms of f . Note that this synthesis
is only applied if f can’t be covered by any function in the M 2 table or by any
primitive.
The synthesis is composed by two different loops, each one having their own
characteristics. If an output function couldn’t be found in the first loop the second
starts.
The first loop is composed by the following steps:
1. Any primitive or M 2 function that doesn’t cover at least one minterm of f is
discarded from its respective table.
2. Build a new table P , selecting every pair of primitives (p 1 + p 2 ), where:
– Every minterm covered by f is also covered at least once by p 1 + p 2 ;
– The pair p 1 + p 2 only covers minterms covered by f .
3. Select a pair of primitives from P , as X 1 and X 2 .
4. Create a vector v with 2 n elements that will be used to build the truth table for
X 3 . Every element in v represents a minterm in f . The vector v is updated
according to the set of minterms covered by X 1 and X 2 . If a minterm i is
covered by both functions, v i = 2. If it’s covered by only one function,
v i = 1. And if it isn’t covered by any function, v i = 0. For example, given
f = {0, 1, 5, 8}, X 1 = {0, 1, 4, 5} and X 2 = {0, 1, 2, 8, 10}. Then v has the
values shown in Table 6.13.
5. Create the truth table for X 3 , represented by the vector X 3 f . Positions where
v i = 2 or v i = 0 are considered as don’t care states (represented by x). For
positions where v i = 1 and i is also covered by f , we have X 3 f i = 1. If
v i = 1 and i isn’t covered by f , we have X 3 f i = 0. Therefore, for the example
presented in Table 6.13, we have X 3 f = [xx0x01xx1x0xxxxx].
6. Generate every possible truth table manipulating the don’t care states in X 3 f .
Each possibility is searched in the M2 table. From the functions, a new table,
P 3 , is constructed.
E. C. Ferraz et al.
For n = 4, S = 65,536 and 90 of these functions are primitives, with at most
one majority gate. In the formulation of M 2 , only 10,260 functions can be covered.
For the remaining 55,186, 55,184 can be covered by majority expressions with three
levels. The remaining two functions need a majority expression with four levels to
be covered.
6.3.2 MP C Synthesis for 4-Input Functions
This section presents the synthesis used in MP C for the construction of majority functions where n = 4. The objective of this synthesis is to formulate
M(X 1 , X 2 , X 3 ) with the combination of primitives and M 2 functions, generating
a majority function that covers the same minterms of f . Note that this synthesis
is only applied if f can’t be covered by any function in the M 2 table or by any
primitive.
The synthesis is composed by two different loops, each one having their own
characteristics. If an output function couldn’t be found in the first loop the second
starts.
The first loop is composed by the following steps:
1. Any primitive or M 2 function that doesn’t cover at least one minterm of f is
discarded from its respective table.
2. Build a new table P , selecting every pair of primitives (p 1 + p 2 ), where:
– Every minterm covered by f is also covered at least once by p 1 + p 2 ;
– The pair p 1 + p 2 only covers minterms covered by f .
3. Select a pair of primitives from P , as X 1 and X 2 .
4. Create a vector v with 2 n elements that will be used to build the truth table for
X 3 . Every element in v represents a minterm in f . The vector v is updated
according to the set of minterms covered by X 1 and X 2 . If a minterm i is
covered by both functions, v i = 2. If it’s covered by only one function,
v i = 1. And if it isn’t covered by any function, v i = 0. For example, given
f = {0, 1, 5, 8}, X 1 = {0, 1, 4, 5} and X 2 = {0, 1, 2, 8, 10}. Then v has the
values shown in Table 6.13.
5. Create the truth table for X 3 , represented by the vector X 3 f . Positions where
v i = 2 or v i = 0 are considered as don’t care states (represented by x). For
positions where v i = 1 and i is also covered by f , we have X 3 f i = 1. If
v i = 1 and i isn’t covered by f , we have X 3 f i = 0. Therefore, for the example
presented in Table 6.13, we have X 3 f = [xx0x01xx1x0xxxxx].
6. Generate every possible truth table manipulating the don’t care states in X 3 f .
Each possibility is searched in the M2 table. From the functions, a new table,
P 3 , is constructed.