1 Introduction

Fig. 1
figure 1

a Structure of a QCA cell with four quantum dots. b QCA cell with two different polarizations

Full size image

The requirements for increasing speed and decreasing power have led to scaling of feature sizes in complementary metal–oxide–semiconductor (CMOS) technology. More scaling of feature sizes is not possible due to physical limits such as quantum effects and non-deterministic behavior of small currents [1]. Hence, in response to the mentioned limitations, a number of other methods such as quantum-dot cellular automata (QCA) [2], single-electron tunneling (SET) [3, 4], tunneling phase logic (TPL) [5], and spin-based devices [6,7,8,9] can be used as possible alternatives to CMOS.

QCA was first proposed by Lent [10, 11]. QCA is a promising transistor-less technology and beyond-CMOS technology and will play a crucial role in the future of supercomputing [12, 13]. The fundamental unit of QCA is a QCA cell which is composed of four dots located at the corners of a square. This technology acts on the basis of Coulombic interactions of electrons trapped in quantum dots. In QCA, the three-input majority and inverter gates are the fundamental primitives.

All-spin logic (ASL) [14] nanotechnology also implements majority logic gates. The fundamental logical device in TPL is a minority gate [5], which is the complement of majority logic. The minority logic synthesis problem is analogous to the majority logic synthesis problem. SET implements both majority and minority logic [3, 4].

In CMOS technology, “NAND/NOR/inverter” gates are used to implement circuits; thus, methods created for the synthesis of functions such as Karnaugh maps (K-maps), which produce simplified expressions in the two standard forms named as sum of product (SOP) and product of sum, are not efficient enough for the synthesis of functions to present the simplest possible form for the QCA technology.

Some of researchers [15,16,17,18] have proposed effective solutions to the synthesis of QCA-based logic structures. However, these methods were only suitable for small networks as they were used to manually solve the problems or synthesize three-input functions. Synthesis methods proposed in [16, 19] are based on a geometrical interpretation of only three-variable Boolean functions to reduce the majority expressions created by SOPs. These methods led to the creation of thirteen standard functions, which are used for synthesis of the three-input functions. Huo et al. in their study [20] have introduced a table consisting of twenty standard functions and their corresponding majority expressions. First, a given Boolean function is simplified to a function presented in the mentioned table, and then, as a result, a majority expression equivalent to this table is chosen. Some methods [21,22,23,24] have applied meta-heuristic algorithms such as genetic algorithm (GA) and genetic programming (GP) for simplification of logic functions. Bonyadi et al. [21] used GA for optimization of a given single-output Boolean function by majority and inverter gates, while Houshmand et al. in [22, 23] applied GP algorithm for optimization of multi-output functions. In [24], the work proposed in [21] has been extended, and a multi-objective optimization consisting of delay as well as the number of gates has been considered. In [25, 26], by using the standard functions, Boolean functions decomposed to four-feasible networks were converted to their corresponding majority expressions. However, the standard functions obtained in [25, 26] cannot be considered as a complete set. In [27], a full set of standard functions, which is not optimal, was identified according to graph theory.

In this paper, a multi-objective synthesis methodology (with the objective priority of gate counts, gate levels, and the number of NOT gates) is proposed, which can be used for the synthesis of three, four, or higher input functions. The concept of majority specification matrix (MSM) is introduced and employed. Furthermore, the synthesis flow is considered for synthesizing multi-output functions. Since the synthesized majority networks can be trivially converted into minority networks using De Morgan’s theorem, we only focus on majority logic synthesis in this study. To compare the suggested method with the other ones, benchmarks in [24] and MCNC benchmark circuits are used. This approach results in fewer majority gates and fewer logic levels as compared to existing methods [28, 29]. The resulting majority/minority network can then be used in ASL-, QCA-, TPL-, or SET-based nanotechnologies.

The rest of the paper is organized as follows: In Sect. 2, some related background materials are presented. Section 3 introduces the proposed method in detail. In Sect. 4, a synthesis flow for multi-output functions is introduced. Section 5 presents the results and finally Sect. 6 concludes the paper.

2 Background material

In this section, basic concepts in QCA technology such as QCA and QCA devices are explained.

2.1 Quantum-dot cellular automata

A standard QCA cell (Fig. 1a) is composed of four dots located at the corners of a square. Two free electrons can tunnel to any quantum dot within the cell [30]. Because of Coulombic interactions, the electrons occupy diagonally opposite positions. Depending on the position of the cell, polarization of a QCA cell can be determined with two stable cell polarization states as shown in Fig. 1b. These configurations are denoted as cell polarization \(P=+1\) (binary ‘1’ state) and \(P=-1\) (binary ‘0’ state).

2.2 QCA devices

In this section, the basic devices used in QCA such as QCA wires, QCA inverters, and QCA majority voters will be introduced. In a QCA wire, a binary signal propagates from input to output because of the Coulombic interactions between cells. In a QCA inverter, cells oriented at \(45^\circ \) to each other take on opposing polarization. A QCA majority gate can perform a three-input majority gate. Equation (1) presents the logic function of a three-input majority gate where A, B,  and C are the three inputs.

$$\begin{aligned} M(A, B, C)= AB + BC + CA. \end{aligned}$$
(1)

By forcing one of the three inputs of the majority gate to a constant logic “0” or a “1,” the majority gate can be used to perform AND/OR operations as shown in the following equations:

$$\begin{aligned} M(A, B, 0)=AB, \qquad \quad M(A, B, 1)=A+B. \end{aligned}$$
(2)

Figure 2 demonstrates a QCA wire (a), inverter gate (b), and majority gate (c).

Fig. 2
figure 2

Representation of a QCA wire, b inverter gate, and c QCA majority gate

Full size image

2.3 Spin devices

All-spin logic is a low-power switch with switching mechanism based on spin torque. In these circuits, the input and output are in the electrical domain, while the processing within the circuit happens in the spin domain. Figure 3a shows the layout of an ASL device which has four terminals: (a) terminal1: VDD, (b) terminal2: VSS, (c) terminal3: input, and (d) terminal4: output. The device is composed of one magnet (or nanomagnet), which is the information storage unit, one high-polarization \((\mathrm{{High}}_\mathrm{{P}})\) magnet–channel interface for the input, one low-polarization \((\mathrm{{Low}}_\mathrm{{P}})\) magnet–channel interface for the output, an isolation between receiving (input) and transmitting (output) sides and spin channels both at receiving and transmitting sides as shown in Fig. 3a. The two stable states of the magnet (left and right spin) are determined by magnetic anisotropy (uniaxial anisotropy, Ku) [31]. Also, in Fig. 3b, c the ASL inverter and majority gates are shown, respectively [6].

Fig. 3
figure 3

a Layout of an ASL device. b Layout of inverter using ASL_NC. c ASL majority gate M3 (direction of information propagation is shown with arrows) [6]

Full size image

2.4 SET technology

Figure 4a shows a basic minority SET gate. The inputs with three capacitors form a voltage summing system which generates a mean voltage at node A. If this voltage exceeds a certain threshold, an electron tunnels through single-electron boxes (SEBs) and negates the voltage at A. Otherwise, the voltage remains positive. Logic 1 and logic 0 are represented by positive and negative voltages, respectively.

A majority gate implemented by a balanced pair of single-electron boxes is shown in Fig. 4b [4]. An electron tunnels through one of the SEBs to make a negative voltage and prevents movements of other electron when VDD increases. Hence, the stable voltage states for the two SEBs are (1, 0) and (0, 1) based on the inputs. For example, if all inputs are 0, the voltage state is (0, 1) and node B has a negative voltage.

By fixing one of the three inputs to logic 0 or 1, “NAND” gate and “NOR” gate are achieved for SET minority gate, while “AND” gate and NOR gate are obtained for SET majority gate, respectively [3].

2.5 TPL technology

Figure 4c shows a minority gate in TPL that uses two phases. The phase of a waveform is used in TPL to represent logic values in digital circuits. \(C_{j}\) indicates the tunneling junction capacitance. The operation of TPL is based on the phase locking of SET oscillations to a pump signal that is distributed throughout the circuit. Since the pump frequency is set to twice the tunneling frequency, the electrical phase of the locked oscillation can have two different values. Each value represents a binary encoding [5, 32]. A TPL minority gate can be a two-input NOR or NAND gate by fixing one of its inputs to logic high or logic low, respectively.

Fig. 4
figure 4

a SET minority gate. b SET majority gate. c TPL minority gate

Full size image

3 Proposed method

The suggested synthesis method is based on the creation of MSM. In the mentioned matrix, all of the input states of a majority function are placed in columns of this matrix. In fact, the specification of the majority function output for each certain input state (a, b, c) is placed in each of MSM columns. As there are \(2^{3}\) possible input states for a three-input majority gate as shown in Fig. 5, the dimensions of the matrix are \(8 \times 8\), and it can be considered as a regular matrix. More details on this topic can be found in [33,34,35]. In this matrix, binary number of each column is related to a certain majority function, for instance, the binary number of the second column is 001 which is equivalent to Maj\((a',b',c)\); it means that zeros in the binary number of each column are related to an inverter gate in the input of majority gate with a certain order.

Fig. 5
figure 5

Structure representation of majority specification matrix (MSM)

Full size image

The following features can be specified in the mentioned matrix:

  • Specification of output of pair columns (4, 5), (3, 6), (2, 7), and (1, 8) are complementary.

  • With respect to each of the two non-complementary columns, there are exactly two input states with the value of one, which are common in each of the two columns.

  • If two majority gates are common in two input variables, then the following properties hold:

    $$\begin{aligned} \mathrm{Maj}\left( a,b,c \right) +\mathrm{Maj}\,\left( a,b,c^{\prime }\right)= & {} \mathrm{Maj}\,\left( a,b,c+c' \right) \nonumber \\= & {} \mathrm{Maj}\,(a,b,1),\nonumber \\ \mathrm{Maj}\left( a,b,c \right) \times \mathrm{Maj}\,\left( a,b,c^{\prime } \right)= & {} \mathrm{Maj}\,\left( a,b,c\times c' \right) \nonumber \\= & {} \mathrm{Maj}\,(a,b,0). \end{aligned}$$
    (3)

  • Changing the order of input variables does not change the specification function in each column.

In the following sections, the application of MSM for the synthesis of Boolean functions will be elaborated on.

3.1 Three-input Boolean functions

This section explains the application of MSM for the synthesis of three-input Boolean logic functions. To this end, the proposed methods are divided into two basic parts and a post-processing method. These methods have been generally designed to achieve the following two objectives:

  • First, the simplest expression based on majority function should be achieved for each function.

  • The number of common expressions in the outputs of multi-output functions should be the maximum possible number and the minimum number of inverter gates should exist in them.

3.1.1 Base of Method 1

In the first method, one majority gate and AND/OR functions are used. First, the specification function is compared to each column of MSM. One of the columns with the most identical number of ones is selected, i.e., Hamming code created between columns of MSM with the given specification function had the minimum possible number of ones. Then, through the application of AND and OR functions, additional ones are removed, and minterms with additional zeros are converted to ones, respectively. Following this step, for each part K-map is used for further simplification of the final expression. In Fig. 6, an overall schematic of Method 1 is shown.

Fig. 6
figure 6

An overall schematic of Method 1

Full size image

The impacts of AND and OR functions on the main function output and selected majority gate are presented in Table 1. In this table, the impact of AND gate applied between selected majority gate and \(F_\mathrm{And}\) and then OR gate applied between majority gate and \(F_\mathrm{OR}\) are shown. As AND and OR gates are complementary in their usage, the order of using them is not important. In Method 1, first AND and then OR gates are applied, respectively.

Table 1 Impacts of applied AND function (applied between selected majority gate and \(F_\mathrm{AND}\)) and OR function (applied between majority gate, \(F_\mathrm{AND}\) and \(F_\mathrm{OR}\)), respectively
Full size table

In this table, X denotes “don’t care” state. Moreover, the majority expressions for AND and OR gates are as follows:

$$\begin{aligned} \mathrm{AND}=\mathrm{Maj}(f_{1},f_{2},0), \qquad \quad \mathrm{OR}=\mathrm{Maj}(f_{1},f_{2},1). \end{aligned}$$
(4)

In these equations, \(f_{1}\) and \(f_{2}\) functions are obtained from Method 1. The following example explains this method in more detail:

Example 1

Consider specification \(F (a, b, c) = (0, 3, 6) \)(the numbers represent minterms contained in the function) defined as the first and the second columns of Table 2.

Table 2 Representation of the specification function related to Example 1 by the application of the proposed Method 1
Full size table

As shown in Table 2, Column 2 of MSM is selected as the most similar column to the specification function \((M(a',b',c'))\). There is an additional minterm, in which function value is 1, i.e., 010. By the application of AND function as shown in Column 4 of Table 2, additional one value is converted to zero value. In Table 2, AND operation must be applied between Columns 3 and 4. It must be noted that Column 4 is created using Table 1. For simplification of the function in Column 4, K-map is used as shown in Table 3.

Table 3 Simplification of \(F_\mathrm{AND}\) created by K-map
Full size table

As presented in Table 3, for further simplification of function, all “don’t care” states receive a value of one. Hence, one possible majority expression for \(F_\mathrm{AND}\) can be obtained as follows:

$$\begin{aligned} F_\mathrm{AND}=a+b'+c=\mathrm{Maj}\,(a,\mathrm{Maj}\left( b',c,1 \right) ,1). \end{aligned}$$
(5)

The final result is provided as follows:

$$\begin{aligned}&F=\mathrm{Maj}\left( \mathrm{Maj}\left( a',b,c' \right) ,F_\mathrm{AND},0 \right) \nonumber \\&\quad =\mathrm{Maj}(\mathrm{Maj}\left( a',b,c' \right) \mathrm{Maj}\left( a,\mathrm{Maj}\left( b',c,1 \right) ,1 \right) ,0). \end{aligned}$$
(6)

3.1.1.1 Another structure of Method 1 It is worth It is worth mentioning that instead of specifying the most similar column from MSM, it is better to compare the columns of function input (a, b, c) with the specification of function output. It is due to this issue that in some functions, the places of ones in input columns are most similar to those of output columns. Hence, one of the majority gates would be removed. This method can also be used for the proposed methods in the next sections.

3.1.2 Base of Method 2

In the second method, a majority gate with three inputs \(f_{1}, f_{2}, f_{3}\) is employed \((F=\mathrm{Maj}(f_{1},f_{2},f_{3}))\); then, expressions related to the three functions are obtained. In Fig. 7, an overall schematic of Method 2 is shown.

Fig. 7
figure 7

An overall schematic of Method 2

Full size image

In this method, similar to Method 1, first, the column of MSM which is the most similar to the function specification is selected \((f_{1})\), and then the value of function \(f_{2}\) is obtained according to Table 4.

Table 4 Obtaining \(f_{2}\) function according to \(f_{1}\) and main function
Full size table

As demonstrated in Table 4, in the process of comparing the main function and the selected majority gate, if the minterm has hamming code one, then the value of function \(f_{2}\) must be equal to the value of main function; otherwise, the value of minterm in function \(f_{2}\) should be “don’t care” (X). The mentioned point is due to the feature of majority function. If the number of ones in a minterm is greater than or equal to two, then the value of output of majority function should be one; otherwise it should be zero. Then, for further simplification of function \(f_{2}\), K-map is used. When the value of “don’t care” states is determined considering the above-stated feature for majority gate, the value of minterms of function \(f_{3}\) can be obtained considering Table 4. The following example illustrates the idea:

Example 2

Consider specification \(F (a, b, c) = (1,2,4,5, 6,7)\) defined in the second column of Table 5.

Table 5 Representation of specification function related to Example 2 after the application of Method 2
Full size table

First, the column of MSM with the least difference with the main function is selected \((f_{1}=\mathrm{Maj}(a',b',c'))\). Then, the value of function \(f_{2}\) is obtained according to Table 4 and K-map presented in Table 6 as follows \((f_{2}=a)\).

Table 6 Representation of K-map applied for simplification of function \(f_{2}\)
Full size table

The value of function \(f_{3}\) is obtained by considering \(f_{2}\) and Table 4; for example, the value obtained for \(f_{2}\) in state (001) is zero, which is not equivalent to the values of \(f_{1}\) and main function. Hence, the value of \(f_{3}\) would be equal to the value of main function. Furthermore, the values of \( f_{2}, f_{1}\), and the main function in state (011) are the same; therefore, it can be stated that the value of \(f_{3}\) is “don’t care.” For further simplification of \(f_{3}\), K-map is used as presented in Table 7.

Table 7 Applying K-map for simplification of function \(f_{3}\)
Full size table

The logic expression for \(f_{3}\) is as follows:

$$\begin{aligned} f_{3}=\left( b+c \right) =\mathrm{Maj}(b,c,1). \end{aligned}$$
(7)

The total logic expression for main function (F) is

$$\begin{aligned} F=\mathrm{Maj}(\mathrm{Maj}( a',b',c' )a,\mathrm{Maj}( b,c,1 )). \end{aligned}$$
(8)

3.1.2.1 Another structure of Method 2 For some functions, a combination of the first (AND, OR) and the second methods can lead to better results. In the following example, the above-mentioned method is explained.

Example 3

Consider function \(F (a, b, c) = (3, 4, 6)\)  as shown in Table 8.

Table 8 An example of the combination of the first and the second methods for improvement of the results
Full size table

First, the most similar column of MSM to the main function is selected \((f_{1}=\mathrm{Maj}(a,b,c))\). By selecting function \(f_{1}\) as presented in Table 8 and the examination of K-map, it can be observed that in order to apply the OR operation between \(f_{1}\) and \(F_\mathrm{OR}\) (Columns 3 and 4 in Table 8), all of the needed 1’s states should be created without adding extra majority function. It means that the logic expression for \(F_\mathrm{OR}\) is \((F_\mathrm{OR}=a\), as shown in Fig. 8).

Fig. 8
figure 8

Applying OR operation to function \(f_{1}\)

Full size image

The obtained result is shown in Column 5 \((F_{\mathrm{{tot}}}=\mathrm{Maj}(\mathrm{Maj}(a,b,c),a,1))\). Hence, by consideration of Table 4, comparison of values related to \(F_{tot}\) and the main function, and by the application of K-map, the value of \(f_{2}\) can be obtained. With respect to the specification function \(f_{2}\) obtained in Column 6, it is certain that the logic function \(f_{2}\) is zero \((f_{2}=0)\) as it is composed of “don’t care” and “zero” states. Hence, the simplest function with the minimum number of majority gates is the zero function. Moreover, the specification function \(f_{3}\) is observed to be the same as \(f_{2}\) Then, the logic function is simplified by applying K-map (as shown in Table 9). Thus, the logic expression for \(f_{3}\) is

$$\begin{aligned} f_{3}=a'+c'=\mathrm{Maj}(a',c',1). \end{aligned}$$
(9)
Table 9 Applying K-map for simplification of function \(f_{3}\)
Full size table
Table 10 Creation of new states in four-input functions according to the three-input functions for converting M(b, c, d) to M(a, b, c). Variable d is “don’t care”
Full size table

As a result, the total logic expression obtained for main function (F) is

$$\begin{aligned} F=\mathrm{Maj}(\mathrm{Maj}(\mathrm{Maj}(a,b,c),a,1),0,\mathrm{Maj}(a',c',1)). \end{aligned}$$
(10)

3.1.3 Post-processing method

To obtain better results, the post-processing method is used, which can be applied to the above-presented methods and can improve the obtained results. In this method, after applying Method 2 to the specification function and obtaining functions \(f_{2}\) and \(f_{3}\), K-maps related to \(f_{2}\) and \(f_{3}\) are studied simultaneously. It is conjectured that if some of 1’s states related to \(f_{2}\) and \(f_{3}\) are exchanged, better results would be obtained. The mentioned point is due to the feature of majority function. If the number of ones in a minterm is greater than or equal to two, then the value of output of majority function would be one; otherwise, it would be zero. Furthermore, the following steps are taken into account in this method:

  • In the K-maps of \(f_{2}\) and \(f_{3}\), minterms of main function whose corresponding function value is one are marked. Due to the mentioned feature for the majority gate, these places (cubes of K-map) can have numbers of 2 or 3 ones in the majority function (Group 1).

  • In the K-maps of \(f_{2}\) and \(f_{3}\), minterms of main function with the zero value of function can have numbers of 0 or 1 ones in the majority function (Group 2).

  • Fixed minterms in the K-map \(f_{2}\) are not considered.

  • “Don’t care” states in \(f_{2}\), which do not create a square in the K-map and generate an extra state in the K-map related to \(f_{3}\), are exchanged in response to the rules of Groups 1 and 2. This method as a search method is continued until the best square in the K-maps is obtained.

  • Equation (11) holds for each majority gate. By applying that expression, the number of inverter gates in the general expression can be decreased.

    $$\begin{aligned} \mathrm{Maj}\left( a',b',c' \right) =\mathrm{Maj}(a,b,c)' \end{aligned}$$
    (11)

    Generally, only states of \(f_{2}\), which are “don’t care,” are considered. Then, the states generated in \(f_{3}\) which do not make a square in \(f_{2}\) are taken into account, and these states are exchanged between \(f_{2}\) and \(f_{3}\) to make squares in \(f_{2}\) and \(f_{3}\). Then, the squares providing the least number of majority expressions are selected from the overall obtained squares.

  • Proposition: Suppose f, g, u, and d are Boolean functions and the following expression exists between them: \(y=u(fg'+gd), where \) \(g'\) is the complement of g. Then, the equivalent majority expression is as follows: \(y=M(u,M\left( f,g',0 \right) M(g,d,0)).\)

    Proof: By extending equivalent majority expression, we have

figure c

3.2 Four- and higher-input Boolean functions

In this section, for the synthesis of four- and higher-input Boolean functions, it must be considered that the majority gate has three inputs; thus, for instance, the methods are explained for four-input functions. Accordingly, the methods presented in this section can be generalized to higher inputs.

Fig. 9
figure 9

An overall schematic of Method 3

Full size image
Table 11 Specification function used in Example 4 and calculation of functions \(f_{2}\) and \(f_{3}\)
Full size table
Table 12 Applying K-map for obtaining function \(f_{3}\)
Full size table
Fig. 10
figure 10

a Applying K-map for function \(f_{2}\) and b applying K-map for function \(f_{3}\). Applying post-processing method to \(f_{2}\) and \(f_{3}\)

Full size image
Table 13 Specification function used in Exp. 5 and calculation of \(f_{2}\) and \(f_{3}\)
Full size table
Table 14 K-map used for calculation \(f_{2}\)
Full size table
Table 15 Consider function \(f_{2}\) as the main function for using tree method
Full size table

Taking into account that the majority gate has three inputs; thus, for four-input functions with consideration of the inputs intended to function, there would be four permutations \((C\left( 3,4 \right) =4\), where C denotes the combination of permutations.), as the order of inputs does not matter. It is assumed that the inputs of the main function are a, b, c, and d. Moreover, it must be mentioned that input (a) is the most significant one and input (d) is the least significant one.

$$\begin{aligned} \mathrm{Maj}(b,c,d), \mathrm{Maj}(a,b,c,), \mathrm{Maj}(a,c,d),\mathrm{Maj}(a,b,d) \end{aligned}$$
(12)

For each of the above-mentioned permutations, an MSM must be created according to Fig. 5. For the creation of MSM with \(b,c, and\,d\) inputs, two matrices of MSM can be created under each other. It means that two matrices of MSM are placed in one column as cascades. As a result, the matrix of MSM has 16 rows and 8 columns. For the creation of MSM in the other states, each row of MSM created in Fig. 5 must move to two new rows for four-input functions. For example, consider the \(\mathrm{Maj}(a,b,c)\) state. For the creation of the mentioned state, the majority function \(\mathrm{Maj}(a,b,c)\) must shift variables (a, b, c) to the left in comparison to state \(\mathrm{Maj}(b,c,d)\). This method is shown in Table 10. In fact, variable d in the main permutation \(\left( b,c,d \right) \) is as a “don’t care” variable for new permutation (a, b, c).

For four-input functions, the following methods are used:

  1. 1.

    In this method, the majority gate is used as a tree expression and employs Method 2 discussed in the three-input functions section. In the mentioned section, if the order of ones in each \(f_{2}\) or \(f_{3}\) function leads to the creation of complex specification functions, and as a result many majority gates will be created in each function. Hence, for the synthesis of \(f_{2}\) or \(f_{3}\) function, each of them can be considered as a main function. Then, in the process of applying Method 2 explained in three-input functions section, the mentioned functions can be synthesized once more. This method can be repeatedly carried out to determine its acceptable level. In Fig. 9, an overall schematic of this method is shown.

  2. 2.

    For synthesis of functions with more than three inputs, the methods explained in the previous section can be used.

In the following examples, the above-mentioned methods are explained.

Example 4

Consider function \(F=(9,11,14)\) defined as the first and the second columns of Table 11.

Fig. 11
figure 11

a K-map used for function \(f_{3\_2}\). b K-map used for function \(f_{3\_3}\). Applying post-processing method to \(f_{3\_2}\) and \(f_{3\_3}\) for more simplification

Full size image

According to Method 2 explained in three-input functions, first, the column of MSM that is the most similar one to the specification function is selected \((f_{1}=M(a,b,d))\). Then, specification functions \((f_{2}\) and \(f_{3})\) are obtained. It can be certainly stated that the logic function \(f_{2}\) is zero \((f_{2}=0)\) and the logic function \(f_{3}\) is obtained by the application of K-map as shown in Table 12:

Boolean logic function \(f_{3}\) is

$$\begin{aligned} f_{3}=b'+cd'=\mathrm{Maj}(b'\mathrm{Maj}(c,d',0),1). \end{aligned}$$
(13)

By the implementation of the post-processing method presented in three-input functions section, the specification functions of \(f_{2}\) and \(f_{3}\) can be exchanged as shown in Fig. 10. States of main specification function, which have the value of one, are presented in gray color in Fig. 10. Moreover, the values of states 0000 and 1000 have been changed to zero in Fig. 10(b). As the mentioned states in the main specification function are zero, the number of ones placed in these cubes can be zero or one. In this example, Column 10 is common to two Rows 00 and 10, which have been exchanged with the same column in Fig. 10(a) \((f_{2})\).

Then, states (1001, 1011) are fixed and thus, among of other states, states (0000, 0100) must be zero until it creates a square in K-map. Logic expressions for \(f_{2}\) and \(f_{3}\) are as follows:

$$\begin{aligned} f_{2}=cd'=\mathrm{Maj}(c,d',0), \quad f_{3}=b'd=\mathrm{Maj}(b',d,0). \end{aligned}$$
(14)

The total logic function is

$$\begin{aligned} F=\mathrm{Maj}(\mathrm{Maj}(a,b,d),\mathrm{Maj}(c,d',0),\mathrm{Maj}(b',d,0)). \end{aligned}$$
(15)

Example 5

Consider the specification function \(F=(3,4,7,15)\) which is defined as the first and the second columns of Table 13. The tree method is explained for this example.

First, the most similar column to main function is selected; here, \(\mathrm{Maj}(0,c,d)\) is combined with \(\mathrm{Maj}(b,c,d)\) and \(\mathrm{Maj}(b',c,d)\) Then, the logic function \(f_{2}\) according to K-map shown in Table 14 is obtained \((f_{2}=b).\)

For obtaining the specification function \(f_{3}\) as a tree method, its value is considered as the main function and is shown in Table 15.

Fig. 12
figure 12

The proposed flow for the synthesis of multi-output functions

Full size image
Table 16 Comparison between the proposed method with a multi-objective genetic programming method presented in [24]. NOI, NOM and NTG stand for number of inverter gates, number of majority gates and the total number of gates, respectively
Full size table
Table 17 Comparisons of the proposed method with the methods presented in [28] and [29]
Full size table

As shown in Table 15, function \(f_{3}\) is considered as the main function. It is important to note that in the calculation of specification functions of \(F_{3\_1}\), \(F_{3\_2}\), and \(F_{3\_3}\), the don’t care values of the main function, \(F_{3}\), are also considered to be don’t cares, i.e., their values may be either zero or one. First, the most similar column to the main function is selected \((M(a',b',c'))\), and the logic functions of \(f_{3\_2}\) and \(f_{3\_3}\) are as follows:

$$\begin{aligned} f_{3\_2}=0, \quad f_{3\_3}=d'+c=\mathrm{Maj}(d'c,1). \end{aligned}$$
(16)

Then, specification functions of \(f_{3\_2}\) and \(f_{3\_3}\) are obtained using the post-processing method as shown in Fig. 11.

New Boolean logic functions \(f_{3\_2}\) and \(f_{3\_3}\) are as follows:

$$\begin{aligned} f_{3\_2}=b', \qquad \quad f_{3\_3}=d'. \end{aligned}$$
(17)

The total specification function is

$$\begin{aligned} F=\mathrm{Maj}(\mathrm{Maj}(0,c,d),b,\mathrm{Maj}(M(a',b',c'),b',d')). \end{aligned}$$
(18)

4 A synthesis flow for multi-output functions

Having the proposed approaches from the previous section available, they can be combined with an extended synthesis flow that could be used for multi-output functions. Figure 12 illustrates this flow. As shown in this figure, first, according to the numbers of inputs of the main function, MSMs are created; then, for each of the outputs of function (fi) and their complementaries, the most similar column of MSM or inputs of function is selected, as well as it could be selected from the combination of columns in MSM that led to AND/OR functions. Then, for each of the selected columns, the proposed methods in previous sections are applied. Afterwards, the obtained results are saved. In addition, conventional K-map method is applied separately and its result is saved. Because of that, in some functions, expression obtained from this method is simpler. In order to obtain final terms including the most common expressions, in Line 10 of the algorithm, the output expressions of the previous functions are used in the synthesis of other functions. Then the results based on the objectives of priority gate counts and gate levels are ordered, and after that results to the most common terms are selected. Finally, for reducing the number of inverter gates in the final expressions, Line 12 of algorithm is applied.

5 Results and comparison

In this section, first, a comparison between the proposed synthesis flow and a multi-objective genetic programming approach [24] is made. The results are shown in Table 16. In this table, NOI, NOM, and NTG stand for the number of inverter gates, number of majority gates, and the total number of gates, respectively. The obtained synthesis results are shown in the last column of this table. In this column, the common parts of the corresponding synthesized circuit for each output are underlined. Also, in this table, the rows titled “shared gates” and “total number of gates” show the number of shared gates and the total number of gates used in the function outputs, respectively. The results illustrate that the proposed method produces the same or better results than the approach presented in [24].

In some functions, the two parameters, namely the number of gates and the number of common parts, should be considered simultaneously, e.g., for the specification function \(F=(2,6,10,11,14)\), the following expressions are obtained (this function is a sample of a multi-output function in Table 16):

$$\begin{aligned} F_{1}= & {} \mathrm{Maj}(\mathrm{Maj}(\mathrm{Maj}(a,b',0),d',1),c,0) \nonumber \\ F_{2}= & {} \mathrm{Maj}(\mathrm{Maj}(\mathrm{Maj}(1',c,d),b,\mathrm{Maj}(\mathrm{Maj}(a,b,c),b,d)')',1,c).\nonumber \\ \end{aligned}$$
(19)

Although \(F_{1}\) produces a fewer number of gates, \(F_{2}\) is chosen because it leads to the large number of common parts with the other outputs presented in Table 16. The common parts lead to a high reduction in the total number of gates.

In Table 17, an overall comparison between the best existing majority logic synthesis method [29] and the proposed synthesis flow is demonstrated. Also, in this table the proposed synthesis flow is compared with the method presented in [28]. In this table, the first column lists the names of benchmarks. The columns titled “Method [28]” and “Method [29]” show the results for the corresponding benchmarks obtained from [28] and [29] in terms of the number of levels, gates, and the number of inverter gates only for [29], as the method in [28] has not reported the number of inverter gates. The column titled “Proposed method” shows the results obtained from the proposed synthesis flow in terms of the number of levels, gates, and the number of inverter gates. The “Reduction %” columns compare the proposed method with the methods presented in [28] and [29] and give the percentage reductions. This table illustrates that there is an average reduction of 14.9% in the number of levels and, at the same time, the number of gates is reduced by 31.6% as compared to the method presented in [28]. When compared to [29], the average reduction in levels is 10.5%, the reduction in gate counts is 16.8%, and the reduction in inverter gates is 33.5%. Results show that the proposed synthesis flow outperforms the best existing methods. Also, the detailed results of the proposed synthesis flow applied to MCNC benchmarks are shown in Appendix (Table 18). Since the synthesis results are independent of the technology used, they are effective for any majority/minority-based technology including ASL, QCA, SET, and TPL.

6 Conclusion

In this paper, a multi-objective synthesis methodology for generating optimal majority expressions was presented. In this method, using an MSM and a synthesis flow presented for multi-output specification functions, the majority expressions are optimized. The corresponding minority network can be easily obtained by complementing the majority expressions. The proposed approach was applied to 20 MCNC benchmarks and was compared with the previous methods. The experimental results demonstrated that the proposed method outperforms the best existing ones.