Majority Logic Synthesis Based on Nauty Algorithm - Field-Coupled Nanocomputing: Paradigms, Progress, and Perspectives - page 122

4.2 Preprocessing and Decomposing

Preprocessing will provide a good start for decomposition by algebraically factoring
out the common terms and removing the redundant terms from the Boolean equations.
Decomposing will split the larger-input nodes in the network into a set of nodes with
lesser number of inputs; thus it makes them easy to convert into majority expressions.
In particular, we are interested in obtaining all nodes with less than four inputs. These
two steps are accomplished by using proper sequence of commands in SIS.

4.3 Application of Standard Functions

The resulting decomposed four-feasible network is then be mapped to the standard
functions. This step is illustrated with an example node given by Eq. ( 12 ).

f ¼ ad 0 þ bd 0 þ cd 0 þ bcd ð 12 Þ

The function is transformed into a graph and used as an input to Nauty, which
compares the function with the whole set of standard functions in order to determine
which one is its isomorphic function. After this step, the standard function and its
majority expression are found as shown in Eqs. ( 13 ) and ( 14 ), respectively.

f ¼ a 0 bcd þ ab 0 c 0 d þ ab 0 cd 0 þ abc 0 d 0 þ abc 0 d þ abcd 0 þ abcd 0 þ abcd ð 13 Þ

f ¼ MMa ; b ; 0 ð ð Þ ; Ma ; c ; d ð Þ ; a Þ ð 14 Þ

Nauty also gives the bijections between the given function and the standard
function, which is a?d 0 ,b?c, c?a, d?b for this problem. By substituting the
variables in Eq. ( 14 ), the majority expression for the Eq. ( 12 ) can be found as shown
in Eq. ( 15 ).

f ¼ MMd 0 ; c ; 0 Þ ; Md 0 ; a ; b Þ ; d 0 ð ð ð Þ ð 15 Þ

The whole process is explained in Fig. 17 . Applying this principle to all four
feasible nodes obtained from SIS decomposition, a complete majority gate network
solution is obtained for the Boolean function.

Fig. 17. Application of Nauty based standard functions