136
E. C. Ferraz et al.
In majority algebra, simplification algorithms based on primitive functions are
widely used. Primitive functions are functions with at most one majority gate in their
optimized form. An algorithm that maps each of the primitive functions and uses
the obtained maps to generate more complex functions was proposed in [18]. The
mapping of functions is realized with Karnaugh maps, a graphical method proposed
by Maurice Karnaugh in 1953, which aims to simplify a classic Boolean function
by mapping its truth table [10].
In [12] a similar algorithm was developed, the B2M (Boolean to Majority). The
B2M receives a Boolean function as input and generates a majority function that
covers the same set of minterms. The generation of an output function is also done
with the combination of primitives, selected by their MLD (Modified Levenshtein
Distance).
The authors in [22] developed the program denominated as MALS (Majority
Logic Synthesizer). It was the first program to minimize majority functions with
more than three inputs. The MALS receives an algebraically minimized Boolean
function as input and returns an equivalent majority function. The algorithm starts
by preprocessing the input function, this process aims to decompose the input
function in a way that no node has more than three input variables. To do this process
the program SI ST OOL is used [14].
After the preprocessing, the algorithm converts each node in a reduced majority
function. This is done by the method presented in [18]. But this method was not
able to find minimal solutions for all functions given that the algorithm works
individually on each node instead of the function as a whole.
The authors in [20] proposed a methodology that combines lower level majority
functions, starting from primitives, to form higher level majority functions. The goal
of this method is to build a majority expressions Look-Up Table (MLU T ) that
stores the majority equivalent for all possible 4-input Boolean functions. Using the
MLU T , the algorithm will then search the equivalent majority expression for every
node in the input network, generating a majority network as output.
The authors in [16] proposed the exact_mig algorithm, which is considered state
of the art. As input, the algorithm receives a truth table or a Majority Inverter Graph
(MI G) [3], with a maximum of six input variables, and returns a majority function
that covers the same set of minterms. A MI G is a graph that represents a majority
function. The most important characteristic of this algorithm is the proposal of an
exact synthesis for majority functions. The function is built from a set of constraints
(K) that shape a given problem accordingly to the definitions of the majority
Boolean algebra. The majority output function is generated with the application
of K to an SMT (Satisfiability Module Theory) solver [9]. As cost criteria the
exact_mig takes into consideration the number of levels and gates in the output
function, making it possible to choose which of these criteria will be prioritized.
In [7] the authors developed a decomposition methodology that uses XOR
and majority operators as a base. The input function is converted into a XORMajority Graph (XMG), a MI G with the addition of the XOR operator, and
decomposed into simplified sub-functions. To perform the decomposition, the
E. C. Ferraz et al.
In majority algebra, simplification algorithms based on primitive functions are
widely used. Primitive functions are functions with at most one majority gate in their
optimized form. An algorithm that maps each of the primitive functions and uses
the obtained maps to generate more complex functions was proposed in [18]. The
mapping of functions is realized with Karnaugh maps, a graphical method proposed
by Maurice Karnaugh in 1953, which aims to simplify a classic Boolean function
by mapping its truth table [10].
In [12] a similar algorithm was developed, the B2M (Boolean to Majority). The
B2M receives a Boolean function as input and generates a majority function that
covers the same set of minterms. The generation of an output function is also done
with the combination of primitives, selected by their MLD (Modified Levenshtein
Distance).
The authors in [22] developed the program denominated as MALS (Majority
Logic Synthesizer). It was the first program to minimize majority functions with
more than three inputs. The MALS receives an algebraically minimized Boolean
function as input and returns an equivalent majority function. The algorithm starts
by preprocessing the input function, this process aims to decompose the input
function in a way that no node has more than three input variables. To do this process
the program SI ST OOL is used [14].
After the preprocessing, the algorithm converts each node in a reduced majority
function. This is done by the method presented in [18]. But this method was not
able to find minimal solutions for all functions given that the algorithm works
individually on each node instead of the function as a whole.
The authors in [20] proposed a methodology that combines lower level majority
functions, starting from primitives, to form higher level majority functions. The goal
of this method is to build a majority expressions Look-Up Table (MLU T ) that
stores the majority equivalent for all possible 4-input Boolean functions. Using the
MLU T , the algorithm will then search the equivalent majority expression for every
node in the input network, generating a majority network as output.
The authors in [16] proposed the exact_mig algorithm, which is considered state
of the art. As input, the algorithm receives a truth table or a Majority Inverter Graph
(MI G) [3], with a maximum of six input variables, and returns a majority function
that covers the same set of minterms. A MI G is a graph that represents a majority
function. The most important characteristic of this algorithm is the proposal of an
exact synthesis for majority functions. The function is built from a set of constraints
(K) that shape a given problem accordingly to the definitions of the majority
Boolean algebra. The majority output function is generated with the application
of K to an SMT (Satisfiability Module Theory) solver [9]. As cost criteria the
exact_mig takes into consideration the number of levels and gates in the output
function, making it possible to choose which of these criteria will be prioritized.
In [7] the authors developed a decomposition methodology that uses XOR
and majority operators as a base. The input function is converted into a XORMajority Graph (XMG), a MI G with the addition of the XOR operator, and
decomposed into simplified sub-functions. To perform the decomposition, the