Synthesis of Majority Expressions Through Primitive Function Manipulation

Abstract

Due to technology advancements and circuits miniaturization, the study of logic systems that can be applied to nanotechnology has been progressing steadily. Among the creation of nanoelectronic circuits the reversible and majority logic stand out. This paper proposes the MPC (Majority Primitives Combination) algorithm, used for majority logic synthesis. The algorithm receives a truth table as input and returns a majority function that covers the same set of minterms. The formulation of a valid output function is made with the combination of previously optimized functions. As cost criteria the algorithm searches for a function with the least number of levels, followed by the least number of gates, inverters, and gate inputs. In this paper it’s also presented a comparison between the MPC and the exact_mig, currently considered the best algorithm for majority synthesis. The exact_mig encodes the exact synthesis of majority functions using the number of levels and gates as cost criteria. The MPC considers two additional cost criteria, the number of inverters and the number of gate inputs, with the goal to further improve exact_mig results. Therefore, the MPC aims to synthesize functions with the same amount of levels and gates, but with less inverters and gate inputs. Tests have shown that both algorithms return optimal solutions for all functions with 3 input variables. For functions with 4 inputs, the MPC is able to further improve 66% functions and achieves equal results for 11%. For functions with 5 input variables, out of a sample of 1000 randomly generated functions, the MPC further improved 48% functions and achieved equal results for 11%.

6.1 Introduction

Majority logic allows the creation of nanoelectronic circuits for several different technologies, which justifies the search for majority based algorithms that generates optimized circuits. Among the first works that deal with majority logic are Lindaman [11], Cohn [8], and Akers [1]. Lindaman [11] proposed the first theorem for applying majority logic in binary decision problems, introducing the majority operator to classical Boolean algebra. The theorem, shown in Eq. (6.1), proposes a Boolean function equivalent to a majority operation.

$$\displaystyle \begin{aligned} M(A,B,C) = A\cdot B + A\cdot C + B\cdot C \end{aligned} $$

(6.1)

Subsequently, a set of axioms that defines the majority algebra independently of the classical Boolean algebra was presented in [8], creating the basis for current majority algebra axiomatization (Ω).

Moreover, the authors in [21] presented a method that performs the mapping of all 3-input Boolean functions into a 3-dimensional cube, generating 13 possible patterns, where each pattern has a different formula to convert a classical Boolean function into a majority equivalent.

Similarly, the authors in [19] presented a method that uses a 4-dimensional cube to map 4-input functions, generating a total of 143 representation patterns. All 143 patterns also have a specific formula to find their equivalent majority functions.

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 SISTOOL 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 (MLUT) that stores the majority equivalent for all possible 4-input Boolean functions. Using the MLUT, 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 (MIG) [3], with a maximum of six input variables, and returns a majority function that covers the same set of minterms. A MIG 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 XOR-Majority Graph (XMG), a MIG with the addition of the XOR operator, and decomposed into simplified sub-functions. To perform the decomposition, the 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 MPC 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 ₂) 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 MPC 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 ₂ 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 MPC algorithm, explaining how it works for 3, 4, and 5-input variables. Section 6.4 presents the results obtained comparing the MPC 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 $\left \{\mathbb {B},\neg ,M\right \}$. The elements $\mathbb {B}$ and ¬, as in classical Boolean algebra, represent the binary values $\left \{0,1\right \}$ 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.

Table 6.1 Example of a majority operation

From a majority operation it’s also possible to obtain AND 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 AND 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.

Table 6.2 Generation of functions AND and OR

Majority functions are also self-dual functions, meaning that a majority function is always equivalent to its dual form. A function’s dual form can be obtained by complementing all input variables and gates [13]. For example, the function (X ⋅ Y ) + (X ⋅ Z) is equal to its dual form $\overline {(\overline {X} + \overline {Y}) \cdot (\overline {X} + \overline {Z})}$.

Table 6.3 shows the equivalence between a majority function M(A, B, C) and its dual form $\overline {M}(\overline {A},\overline {B},\overline {C})$.

Table 6.3 Equivalence between M(A, B, C) and its dual form

6.2.1 Axiomatization of Majority Functions (Ω)

The set of axioms that defines the majority algebra is represented by Ω and can be divided into axioms of Commutativity, Associativity, Distribution, Inverter Propagation, and Majority [4]. Every axiom in Ω can be proved by perfect induction.

The Commutativity axiom (Ω.C), represented in Eq. (6.2), determines that the input order doesn’t change the output value.

$$\displaystyle \begin{aligned} M(A,B,C) = M(A,C,B) = M(C,B,A) \end{aligned} $$

(6.2)

Table 6.4 proves Ω.C by perfect induction.

Table 6.4 Proof of Ω.C by perfect induction

The Associativity axiom (Ω.A) states that the exchange of variables between two functions is possible, as long as they are at subsequent levels and have one variable in common. An example of an Ω.A application is presented in Eq. (6.3).

$$\displaystyle \begin{aligned} M(A,D,M(B,D,C)) = M(C,D,M(B,D,A)) \end{aligned} $$

(6.3)

Note that the variable shared between levels is D. Therefore, it’s possible to substitute the remaining variable in the upper level for one in the subsequent level. In the presented example, we had an exchange between the variables A and C.

Table 6.5 proves Ω.A by perfect induction.

Table 6.5 Proof of Ω.A by perfect induction

The Distribution axiom (Ω.D) determines that it’s possible to distribute a set of variables to gates in subsequent levels. In Eq. (6.4) an example of this theorem is given, where the distributed set is $\left \{A,B\right \}$.

$$\displaystyle \begin{aligned} M(A,B,M(D,E,C)) = M(M(A,B,D),M(A,B,E),M(A,B,C)) \end{aligned} $$

(6.4)

Table 6.6 proves Ω.D by perfect induction.

Table 6.6 Proof of Ω.D by perfect induction

The Inverter Propagation axiom (Ω.I), represented in Eq. (6.5), determines that a majority function is self-dual [2].

$$\displaystyle \begin{aligned} \overline{M}(A,B,C) = M(\overline{A},\overline{B},\overline{C}) \end{aligned} $$

(6.5)

Table 6.7 proves Ω.I by perfect induction.

Table 6.7 Proof of Ω.I by perfect induction

The Majority (Ω.M) can be divided in two equations. Equation (6.6) shows that the output of a majority gate is equal to the most common value among its inputs. Equation (6.7) shows that the output value will be equal to the tie-breaking variable in functions with the same number of true and false values.

$$\displaystyle \begin{aligned} M(A,A,B) = A\end{aligned} $$

(6.6)

$$\displaystyle \begin{aligned} M(A,\overline{A},B) = B \end{aligned} $$

(6.7)

Table 6.8 proves Ω.M by perfect induction.

Table 6.8 Proof of Ω.M by perfect induction

6.2.2 Primitive Majority Functions

Primitive functions can be obtained by a single gate. In the majority algebra, primitive functions (also called primitives) can be used as a base for the construction of more complex functions. All primitives can be obtained from the sets C, V , G, and T, where each set corresponds to functions with a specific number of inputs. The total number of primitives is obtained by summing the functions in C, V , G, and T [20].

The set C represents functions with no input variables, covering the constants 0 and 1. Therefore, |C| = 2.

The set V  represents all functions formed by a single input variable, in its complemented form or not. Equation (6.8) shows how to calculate the number of functions in V .

$$\displaystyle \begin{aligned} |V| = 2 \cdot n \end{aligned} $$

(6.8)

In Table 6.9, we can observe the listing of V  for three input variables. The number of input variables are represented by n. Note that the classical functions and their corresponding majority forms are equal because the V  set is composed only by functions without operators.

Table 6.9 List of set V  for n = 3

The set G is formed by functions with a single AND or OR operator, having a total of 2 input variables. The number of functions in G can be calculated by Eq. (6.9). The variables E and O represent the possible combinations of inputs, for AND and OR operations, respectively. For n = 3, we have $E = \left \{A\cdot B,A\cdot C,B\cdot C\right \}$ and $O = \left \{A+B,A+C,B+C\right \}$. Each combination has 4 inversion variations, the combination A + B, for example, has the variations $\left \{A+B,\overline {A}+B,A+\overline {B},\overline {A}+\overline {B}\right \}$.

$$\displaystyle \begin{aligned} |G| = (4 \cdot |E|) + (4 \cdot |O|) \end{aligned} $$

(6.9)

In Table 6.10, we present the functions in G for n = 3.

Table 6.10 List of set G for n = 3

The set T represents functions with a single majority gate, no constant value and no repeated variable as input. Equation (6.10) calculates the number of functions in T. The variable t represents the number of possible combinations among the input variables, considering three inputs per combination. Note that each combination has eight variations of inverters and, for n = 3, there is only one possible combination.

$$\displaystyle \begin{aligned} |T| = t \cdot 8 \end{aligned} $$

(6.10)

Table 6.11 shows the list of functions in T, for n = 3.

Table 6.11 List of set T for n = 3

Table 6.12 shows the complete primitives table for n = 3. Note that |C| + |V | + |G| + |T| = 40.

Table 6.12 Complete list of primitives for n = 3

6.3 The MPC Algorithm

In this section we propose the MPC algorithm. The MPC receives a truth table f as input and returns a majority function that covers the same set of minterms. To generate a valid output function we use the expression M(X ₁, X ₂, X ₃). Each variable X _c, where 1 ≤ c ≤ 3, represents a majority primitive or a 2-level majority function.

6.3.1 Tables Formulation

The first step of MPC is the tables formulation phase, where the functions used to build M(X ₁, X ₂, X ₃) are formulated. The algorithm receives an input truth table f, identifies the number of input variables, represented by n, and generates the 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 MPC is the M ₂ table, formed by the application of all possible combinations among primitive functions in the expression M(X ₁, X ₂, X ₃), 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 ₂ lists all sets of minterms that can be covered by a 2-level majority function and, since they are obtained exhaustively, M ₂ 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 ₂ is stored as a LUT (Look-Up Table) in the MPC code.

As an example of a M ₂ function, we have $M(X_1,X_2,X_3) = M(A,M(A,\overline {B},0),$ $\overline {M}(A,B,C))$, where X ₁ = A, $X_2 = M(A,\overline {B},0)$, and $X_3 = \overline {M}(A,B,C)$.

The cost criteria used by the MPC 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(\overline {A},B,C)$, a single complemented input;

• $\overline {M}(A,B,C)$, a single inverter applied to the output value;

• $\overline {M}(\overline {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(\overline {X},Y,\overline {Z}) = \overline {M}(X,\overline {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(\overline {M}(A,\overline {B},C),\overline {D},0)$, which has 2 levels, 2 gates, and 3 inverters. By applying Ω.I we have $M(\overline {M}(A,\overline {B},C),\overline {D},0) = \overline {M}(M(A,\overline {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ⁿ, 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 ₂ 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.

For n = 4, S = 65,536 and 90 of these functions are primitives, with at most one majority gate. In the formulation of M ₂, 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 MPC Synthesis for 4-Input Functions

This section presents the synthesis used in MPC for the construction of majority functions where n = 4. The objective of this synthesis is to formulate M(X ₁, X ₂, X ₃) with the combination of primitives and M ₂ 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 ₂ 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 ₂ 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 ₁ + p ₂), where:

  • Every minterm covered by f is also covered at least once by p ₁ + p ₂;

  • The pair p ₁ + p ₂ only covers minterms covered by f.

• 3. Select a pair of primitives from P, as X ₁ and X ₂.

• 4. Create a vector v with 2ⁿ elements that will be used to build the truth table for X ₃. Every element in v represents a minterm in f. The vector v is updated according to the set of minterms covered by X ₁ and X ₂. 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 ₁ = {0, 1, 4, 5} and X ₂ = {0, 1, 2, 8, 10}. Then v has the values shown in Table 6.13.

  Table 6.13 Generation of vector v

• 5. Create the truth table for X ₃, represented by the vector X ₃ 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 ₃ f _i = 1. If v _i = 1 and i isn’t covered by f, we have X ₃ f _i = 0. Therefore, for the example presented in Table 6.13, we have X ₃ f = [xx0x01xx1x0xxxxx].

• 6. Generate every possible truth table manipulating the don’t care states in X ₃ f. Each possibility is searched in the M2 table. From the functions, a new table, P ₃, is constructed.

• 7. For every function in P ₃ composed by a gate that also composes X ₁ or X ₂, we reduce its cost by 1. This rule exists because each gate is counted only once in the calculation of a majority function size.

• 8. Select the lowest cost function in P ₃, that hasn’t been selected yet, as X ₃. If there’s no valid X ₃, we go back to step 3 and find a new primitive pair.

• 9. With the selection of X ₃ we now have a valid output M(X ₁, X ₂, X ₃). To minimize inverters, Ω.I is applied to every level of the function built. If the function post Ω.I application has a lower cost, the previous function is substituted.

• 10. The loop ends when every possible pair in P has been combined with a function from M ₂, and every M(X ₁, X ₂, X ₃) found is stored in table Z.

• 11. By the end of the loop, the algorithm returns the function with the lowest cost in Z. If no function could be found the second loop starts.

To exemplify an iteration of the first loop, consider n = 4 and f = {4, 5, 6, 9, 15}. A valid output function can be found in the iteration where X ₁ = M(A, D, 0) and $X_2 = M(\overline {A},B,C)$, X ₁ covering the minterms {9, 11, 13, 15} and X ₂ covering {2, 3, 4, 5, 6, 7, 14, 15}. Table 6.14 shows vector v updated from X ₁ and X ₂.

Table 6.14 Vector v updated from X ₁ and X ₂, for the first loop example

The minterms considered don’t care states, where v _i = 2 or v _i = 0, are {0, 1, 8, 10, 12, 15}. The minterms where v _i = 1 and f _i = 1 are {4, 5, 6, 9}, and the minterms where v _i = 1 and f _i = 0 are {2, 3, 7, 11, 13, 14}. Therefore, X ₃ f = xx001110x1x0x00x.

We select as X ₃, from the M ₂ table, the lowest cost function that fits the truth table pattern formed by X ₃ f. We select $X_{3} = \overline {M}(C,M(\overline {B},D,1),M(A,B,0))$ that covers the minterms {0, 1, 4, 5, 6, 8, 9, 12}, and has 1100111011001000 as truth table. Accordingly, we have $M(X_1,X_2,X_3) = M(M(A,D,0),M(\overline {A},B,C),$ $\overline {M}(C,M(\overline {B},D,1),M(A,B,0)))$.

The dual form of $M(M(A,D,0),M(\overline {A},B,C),\overline {M}(C,M(\overline {B},D,1),M(A,B,0)))$ is equal to $\overline {M}(\overline {M}(\overline {A},\overline {D},1),\overline {M}(A,\overline {B},\overline {C}),M(\overline {C},\overline {M}(B,\overline {D},0),\overline {M}(\overline {A},\overline {B},1)))$, which has a higher amount of inverters. Therefore, for f = {4, 5, 6, 9, 15}, the MPC algorithm adds $M(M(A,D,0),M(\overline {A},B,C),\overline {M}(C,M(\overline {B},D,1),M(A,B,0)))$ to its table of possible outputs Z. The loop ends when every pair of functions in P are selected and combined with a function from M ₂, and returns the lowest cost function in Z as output.

From all 55,184 sets of minterms that can be covered by a 3-level function, 50,016 can be covered by functions where two elements of X _c are primitives. Those functions are found by the first loop.

Among the 5168 remaining sets, 5056 can be covered by functions where only one element of X _c is a primitive. The 112 remaining sets can only be covered by functions where all elements of X _c are 2-level functions from M ₂. Those functions are found by the second loop.

The second loop is composed by the following steps:

• 1. Select X ₁ from the primitives table. If every primitive function has been selected as X ₁ and a valid output function could not be found, X ₁ is selected from a group of functions R. The group R is formed by every M ₂ function with size r, where r represents the number of gates in a M ₂ function. Therefore, r starts at 2, the lowest number of gates that a 2-level majority function can have, and is incremented if a group R with higher size functions must be defined.

• 2. Create two new vectors, v ₀ and v ₋₁. The vector v ₀ contains the positions of f that haven’t been covered yet; therefore, v ₀ = f − X ₁. The vector v ₋₁ has the positions of v that can’t be covered one more time; therefore, v ₋₁ = X ₁ − f.

• 3. From v ₀ and v ₋₁ the truth tables for X ₂, represented by the variable X ₂ f are generated. X ₂ 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 ₀, X ₂ f _i = 1. For minterms stored in v ₋₁, X ₂ fi = 0. The other minterms are all considered don’t care states.

• 4. Every possible truth table manipulating the don’t care states in X ₂ f is generated. Each possibility is searched in the M ₂ table. From these functions a new table, P ₂, is created.

• 5. For every function in P ₂ that is composed by a gate that also composes X ₁, its cost is reduced by one.

• 6. Select the lowest cost function in P ₂, that was not selected yet, as X ₂. If there’s no valid X ₂, go back to the first step and select a new X ₁.

• 7. To find X ₃ create X ₃ f based on v ₋₁ and a new vector v ₁. The vector v ₁ stores the minterms of f covered only once by X _c. Therefore, the minterms in v ₁ must be covered by X ₃. For the minterms stored in v ₋₁, X ₃ f = 0. For the minterms stored in v ₁, X ₃ f = 1.

• 8. To find all possibilities for X ₃ f, search the respective functions in the M ₂ table and build P ₃ from them.

• 9. Again, update the cost of the functions in P ₃ based on the gates in X ₁ and X ₂.

• 10. Select the lowest cost function in P ₃, that hasn’t been selected yet, as X ₃. If there’s no valid X ₃, go back to step 6 and select a new X ₂.

• 11. With the selection of X ₃ we now have a valid output M(X ₁, X ₂, X ₃). 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 ₁, X ₂, X ₃) found is stored in table Z and the loop stops when all primitive functions are selected as X ₁. If no function could be found, the algorithm goes back to the first step and restarts selecting X ₁ from a group R, stopping when all functions in R were selected as X ₁. 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 ₁ from the primitives table, then we build X ₂ and X ₃ as 3-level functions using the explained synthesis.

6.3.3 MPC Synthesis for 5-Input Functions

The synthesis for 5-input (n = 5) functions also uses the primitives and the M ₂ table as a base to build functions with a higher number of levels.

For n = 5, S = 4,294,967,296 and 172 of these sets can be covered by primitives, with at most one majority gate. The M ₂ table stores the 253,560 sets that can be covered by majority functions with 2 levels. The remaining sets need more than 2 levels to be covered.

To build 3-level functions the algorithm also uses the expression M(X ₁, X ₂, X ₃), realizing the combination of primitives and M ₂ functions, selected by their lowest cost.

The complete synthesis for 3-level functions is composed by the following steps:

• 1. Order by cost every function from the primitives and M ₂ tables.

• 2. Select the function with the lowest cost as X ₁.

• 3. Reduce the cost by one for every primitive or M ₂ function that is composed by a gate that also composes X ₁.

• 4. Create v ₀ and v ₋₁, where v ₀ = f − X ₁ and v ₋₁ = X ₁ − f.

• 5. Select X ₂, firstly from the primitives, as the lowest cost function that:

  • Covers all minterms in v ₀.

  • Doesn’t cover any minterm in v ₋₁.

  If no valid X ₂ could be found among the primitives, select X ₂ from the M ₂ table. If still no valid X ₂ could be found, go back to step 2 and select a new X ₁.

• 6. Again, update the cost of the primitives and M ₂ functions based on the gates in X ₁ and X ₂.

• 7. Create v ₁, where v ₁ stores the minterms covered by f and only once by X _c.

• 8. Select X ₃, firstly from the primitives, the lowest cost function that:

  • Covers all minterms in v ₁.

  • Doesn’t cover any minterm in v ₋₁.

  If no valid X ₃ could be found among the primitives, select X ₃ from the M ₂ table. If still no valid X ₃ could be found, go back to step 5 and select a new X ₂.

• 9. With the selection of X ₃ we now have a valid output. Next apply Ω.I to every level of M(X ₁, X ₂, X ₃) and return the lowest cost version as output.

To exemplify the second loop, consider n = 5 and f = {2, 4, 6, 7, 8, 11, 13, 14, 15}. A valid output function can be found in the iteration where X ₁ = C, covering the minterms {4, 5, 6, 7, 12, 13, 14, 15, 20, 21, 22, 23, 28, 29, 30, 31}.

Updating the vector v based on X ₁, we have v ₀ = {2, 8, 11} and v ₋₁ = {5, 12, 20, 21, 22, 23, 28, 29, 30, 31}. Table 6.15 shows v after the selection of X ₁.

Table 6.15 Vector v updated from X ₁, for the second loop example

As X ₂, we select the lowest cost function from M ₂ that covers every minterm in v ₀ but doesn’t cover any of the minterms in v ₋₁.

We select $X_2 = \overline {M}(M(C,D,1),M(B,\overline {E},0),M(A,\overline {B},E))$ that covers {0, 1, 2, 4, 6, 8, 9, 11, 13, 15, 16, 17, 24, 25}. From X ₂, we update v again, generating v ₁ = {2, 7, 8, 11, 14} and v ₋₁ = {0, 1, 5, 9, 12, 16, 17, 20, 21, 22, 23, 24, 25, 28, 29, 30, 31}. Table 6.16 shows v updated after X ₂’s selection.

Table 6.16 Vector v updated from X ₂, for the second loop example

As X ₃, we select the lowest cost function from M ₂ that doesn’t cover any minterms in v ₋₁ and covers all minterms in v ₁.

We have $X_3 = M(M(\overline {A},D,0),M(B,\overline {C},0),\overline {M}(A,B,E))$, covering the minterms {2, 3, 6, 7, 8, 10, 11, 14}.

With the selection of X ₃, MPC returns $M(X_1,X_2,X_3) = M(C,\overline {M}(M(C,D,1),$ $M(B,\overline {E},0),M(A,\overline {B},E)),M(M(\overline {A},D,0),M(B,\overline {C},0),\overline {M}(A,B,E)))$ as output, which has less inverters than its dual form.

For functions that need more than three levels to be covered we apply the reduction of fan-ins by Shannon expansion. Equation (6.11) shows the equivalent majority version of the Shannon theorem, applied to the set of inputs {A, B, C, D, E}.

$$\displaystyle \begin{aligned} M(A,B,C,D,E) = M(M(F_1,0,A),M(F_2,0,\overline{A}),1) \end{aligned} $$

(6.11)

The variable A represents the isolated variable and F ₁ and F ₂ represent functions built with the remaining inputs {B,C,D,E}.

The first step to apply this equation in the MPC algorithm is to isolate the first input (A). Then split the input truth table f in two pieces to form 2 new truth tables, f ₁ and f ₂.

Table 6.17 shows an example of f ₁’s and f ₂’s generation. For this example, f = [01110001100010100000111001010101] and the set of inputs are {A, B, C, D, E} (n = 5).

Table 6.17 Example of f ₁’s and f ₂’s generation by Shannon theorem

Note that, by splitting f in 2 equal size tables, we have f ₁ = [0111000110001010] and f ₂ = [0000111001010101], where the set of inputs became {B, C, D, E} (n = 4) and the variable A is isolated.

To find F ₁ and F ₂ we apply the MPC synthesis for n = 4, explained in the previous section, to f ₁ and f ₂, respectively.

Note that the functions built by the Shannon Theorem aren’t an optimal solution for f, since Eq. (6.11) adds two levels and three gates by itself.

6.4 Results

In this section results obtained from the comparison of the algorithms MPC and exact_mig are presented. For n = 4 both algorithms were executed for all 65,536 possible functions. The obtained results were then compared based on the cost criteria used by the MPC that prioritizes first the number of levels in the output function, followed by the number of gates, the number of inverters, and the number of gate inputs. In Table 6.18 each column corresponds to a group S _i, where 0 ≤ i ≤ 2ⁿ. Each S _i represents a total of functions that covers a specific number of minterms. S ₄, for example, represents every function that covers 4 minterms among the 65,536 possibilities. Equation (6.12) shows the calculation of S _i. Note that m = 2ⁿ, and represents the total of minterms for a specific number of inputs. For n = 4, m = 16.

$$\displaystyle \begin{aligned} S_i = \frac{m!}{i!\cdot(m-i)!} \end{aligned} $$

(6.12)

Table 6.18 Cost comparison between MPC and exact_mig

For each S _i the table shows the quantity of functions where MPC generated results with a lower, higher, and equal cost than exact_mig.

The MPC generates lower cost results for 42,987 (66%) functions, generates results with equal cost for 7198 (11%) functions, and generates results with higher cost for the remaining 15,351 (23%).

Note that MPC is able to generate better results because exact_mig aims for the exact synthesis of only depth and size, while MPC considers also the number of inverters and the number of gate inputs as cost criteria. In this comparison, the exact_mig functions were generated with the prioritization of depth, followed by the function size, differing from MPC only by the addition of the number of inverters and gate inputs as third and fourth criteria, respectively.

Functions where the MPC returns a higher cost than exact_mig exist because the MPC builds M(X ₁, X ₂, X ₃) prioritizing X ₁ and X ₂ as primitives, only using functions from M ₂ if needed. This rule is essential for the formation of optimized functions in the majority of the cases, but there are cases where the prioritization of 2-level functions would generate a lower cost result.

As an example consider f = 1000000000000001. The MPC returns the function $M(\overline {M}(B,C,1),M(B,D,0),M(1,M(A,C,0),$ $\overline {M}(A,D,1)))$ as output that has 3 levels and 6 gates. The exact_mig algorithm returns $\overline {M}(M(0,C,\overline {D}),$ $M(1,D,M(A,B,\overline {D})),$ $\overline {M}(0,C,M(A,B,\overline {D})))$, which has 3 levels and 5 gates.

In the presented case, the MPC generated a result prioritizing the use of two primitive functions ($X_1 = \overline {M}(B,C,1)$ and X ₂ = M(B, D, 0)), and a single 2-level function ($X_3 = M(1,M(A,C,0),\overline {M}(A,D,1))$), while exact_mig was able to generate better results with a single primitive and 2-level functions, since the combination of both functions uses the gate $M(A,B,\overline {D})$ twice and the cost of repeated gates is disconsidered.

As example of a function where the MPC generated better results, we have f = 0000001001000100, where the MPC generated the function $M(M(A,\overline {C},0),$ $M(C,D,1),M(0,B,\overline {M}(A,D,1)))$ as output that has 3 levels, 5 gates, and 2 inverters. The exact_mig generated the function $M(\overline {M}(0,\overline {B},C),M(0,D,\overline {M}(\overline {A},C,$ $D)),M(\overline {D},M(\overline {A},C,D),M(0,\overline {B},C)))$ for the same truth table f that has 3 levels, 5 gates, and 5 inverters. Note that the MPC generates a function with the same number of levels and gates, but with less inverters.

In Tables 6.19 and 6.20, comparisons about the runtime of both algorithms are presented. Table 6.19 shows the total and average runtime for every S _i. Table 6.20 shows the total and average runtime for all functions with a specific depth. The comparisons were made in a computer with 8 GB RAM and a 1.7 GHZ CPU.

Table 6.19 Runtime comparison between MPC and exact_mig by S _i

Table 6.20 Runtime comparison between MPC and exact_mig by Depth

Note that even though the MPC can generate faster results for functions with 0, 1, 2, or 4 levels, in most cases it is still slower than exact_mig.

In Table 6.21, we present the average memory usage in the synthesis of every group S _i, in megabytes (MB).

Table 6.21 Comparison of average memory usage for n = 4

Note that the MPC has an average memory usage of 5.36 MB, while the exact_mig has an average memory usage of 3.52 MB.

For n = 5 a sample of 1000 randomly generated functions was used and the MPC algorithm was able to achieve lower cost results for 477 (48%) functions, and equal cost results for 112 (11%).

The MPC’s total runtime for the generated sample was 11.62 h, with an average runtime of 41.63 s. The exact_mig’s total runtime was 19.33 h, with an average runtime of 1.15 min.

Therefore, the MPC was able to generate results 66% faster than exact_mig. The MPC’s average memory usage was 40.32 MB, while the exact_mig’s was only 5.05 MB.

Note that results for n = 3 are not presented because both algorithms return optimal solutions for all 256 possible functions.

6.5 Conclusions

In this paper we present the MPC algorithm, which aims to generate majority functions based on an input truth table. We also present a study on the main concepts of majority Boolean algebra and primitive functions. With the proposed cost criteria the MPC presented, in the most part, results better or equal to exact_mig. It’s important to point out that the MPC is able to find better results only considering two additional cost criteria: the number of inverters and gate inputs.

For functions with n = 4, from a total of 65,536 possible functions, the MPC generated functions with lower cost in 42,987 (66%) cases and functions with equal cost in 7198 (11%) cases, reaching a total of 50,185 (77%) functions with equal or lower cost than exact_mig. The MPC had an average computational time of 5.50 s and an average memory usage of 5.56 MB, while the exact_mig had an average computational time of 3.54 s and an average memory usage of 3.52 MB.

For functions with n = 5, from a sample of 1000 functions, the MPC found better or equal results for a total of 589 (59%) functions, where 477 (48%) had lower cost and 112 (11%) had equal cost. The MPC’s average computational time and memory usage were 41.63 s and 40.32 MB, while exact_mig’s average computational time and memory usage were 1.15 min and 5.05 MB, respectively.

The MPC’s code is available at: https://github.com/EvandroFerraz/mpc. The list of functions used to compare MPC and exact_mig for 5-input functions can also be find in the link.