6 Synthesis of Majority Expressions Through Primitive Function Manipulation
137
algorithm combines theories of majority algebra, Shannon decomposition [15], and
disjoint-support decomposition (DSD)[5].
In [17] the authors proposed adaptations of the exact synthesis used in the
exact_mig, applied to normal Boolean functions. New technologies based on
constraints and SMT solvers are also presented and compared.
In this work the MP C algorithm is proposed. Similar to the methodology
proposed in [20], the algorithm checks all possible combinations among primitive
functions and creates a table to store them. For each function, the covered set
of minterms is also stored. If there are two functions that cover the same set of
minterms, the lowest cost function is kept and the other function is discarded. As
a result, we have a table (M 2 ) that lists all the sets covered by majority functions
with two levels. As cost criteria the algorithm considers the depth, followed by the
number of gates, the number of inverters, and the number of gate inputs in the output
function.
The MP C can be used to synthesize Boolean functions with a maximum of
5-input variables. For 3-input variables the algorithm returns an optimal solution
for all possible functions. For 4 and 5-input variables the algorithm guarantees an
optimal solution for functions covered by M 2 or by a primitive, and uses a specific
synthesis to cover functions with a higher number of levels. For five variables
however, functions with four or more levels are generated by the application of the
Shannon theorem.
This article is organized as follows: In Sect. 6.2, we present an explanation about
majority algebra, including its axiomatization and the concept of primitive majority
functions. Section 6.3 presents the MP C algorithm, explaining how it works for
3, 4, and 5-input variables. Section 6.4 presents the results obtained comparing the
MP C and the exact_mig. Section 6.5 presents the conclusion of what was realized
in the paper.
6.2 Majority Boolean Algebra
The majority Boolean algebra is composed by the set {B, ¬, M}. The elements B
and ¬, as in classical Boolean algebra, represent the binary values {0, 1} and the
inversion operator, respectively, and M represents the majority operator [6].
A majority function returns as output the most present binary value among its
inputs. Therefore, an operator M that has a total of three input variables will return
a true value only if two or more inputs are true. The truth table presented in Table 6.1
exemplifies a majority operation for the variables X, Y , and Z.
From a majority operation it’s also possible to obtain AN D and OR functions,
performed by fixing one of the input variables to a constant binary value.
As an example, the function M(A, B, C) is considered. Setting the value of A to
0, we have an AN D function between B and C. Setting the value of A to 1, we have
an OR function between B and C. This example is shown in Table 6.2.
137
algorithm combines theories of majority algebra, Shannon decomposition [15], and
disjoint-support decomposition (DSD)[5].
In [17] the authors proposed adaptations of the exact synthesis used in the
exact_mig, applied to normal Boolean functions. New technologies based on
constraints and SMT solvers are also presented and compared.
In this work the MP C algorithm is proposed. Similar to the methodology
proposed in [20], the algorithm checks all possible combinations among primitive
functions and creates a table to store them. For each function, the covered set
of minterms is also stored. If there are two functions that cover the same set of
minterms, the lowest cost function is kept and the other function is discarded. As
a result, we have a table (M 2 ) that lists all the sets covered by majority functions
with two levels. As cost criteria the algorithm considers the depth, followed by the
number of gates, the number of inverters, and the number of gate inputs in the output
function.
The MP C can be used to synthesize Boolean functions with a maximum of
5-input variables. For 3-input variables the algorithm returns an optimal solution
for all possible functions. For 4 and 5-input variables the algorithm guarantees an
optimal solution for functions covered by M 2 or by a primitive, and uses a specific
synthesis to cover functions with a higher number of levels. For five variables
however, functions with four or more levels are generated by the application of the
Shannon theorem.
This article is organized as follows: In Sect. 6.2, we present an explanation about
majority algebra, including its axiomatization and the concept of primitive majority
functions. Section 6.3 presents the MP C algorithm, explaining how it works for
3, 4, and 5-input variables. Section 6.4 presents the results obtained comparing the
MP C and the exact_mig. Section 6.5 presents the conclusion of what was realized
in the paper.
6.2 Majority Boolean Algebra
The majority Boolean algebra is composed by the set {B, ¬, M}. The elements B
and ¬, as in classical Boolean algebra, represent the binary values {0, 1} and the
inversion operator, respectively, and M represents the majority operator [6].
A majority function returns as output the most present binary value among its
inputs. Therefore, an operator M that has a total of three input variables will return
a true value only if two or more inputs are true. The truth table presented in Table 6.1
exemplifies a majority operation for the variables X, Y , and Z.
From a majority operation it’s also possible to obtain AN D and OR functions,
performed by fixing one of the input variables to a constant binary value.
As an example, the function M(A, B, C) is considered. Setting the value of A to
0, we have an AN D function between B and C. Setting the value of A to 1, we have
an OR function between B and C. This example is shown in Table 6.2.