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

used as inputs. By comparing them and selecting the distinct ones, this method will
generate an exhaustive list of standard functions.
At the beginning of the process, a Boolean logic function needs to be encoded into
a graph. For the first step, a 16-bit vector is used to represent the on-set and off-set
vertices for a function. If a particular minterm appears in a function, the corresponding
bit in the vector is set to ''1'' otherwise it is set to ''0''. For example, the vector for
f ¼ a 0 bd 0 þ ac 0 d þ abd þ ab 0 cd 0 is 1 ; 0 ; 1 ; 0 ; 0 ; 1 ; 1 ; 0 ; 0 ; 1 ; 0 ; 1 ; 0 ; 0 ; 0 ; f g as shown
in Fig. 14 . The rightmost bit in the vector is ''0'' because the minterm a 0 b 0 c 0 d 0 does not
appear in the function. Similarly, the 13th bit is ''1'' because the minterm abc 0 d is
included in f. Then each bit in the vector is mapped to a corresponding vertex in the
4-D cube as shown in Fig. 15 (a). For example, the mapping of the vector in Fig. 14 on
to a 4-D cube is shown in Fig. 15 (b). In this figure, the vertices labeled as 4, 6, 9, 10,
13 and 15 are mapped as on-set vertices because the 4th, 6th, 9th, 10th, 13th and 15th
bits in the vector are ''1''. The rest vertices are off-set because their corresponding bits
in the vector are ''0''.
As shown in Fig. 13 , a 16-bit null vector 0 ; 0 ; 0 ; 0 ; 0 ; 0 ; 0 ; 0 ; 0 ; 0 ; 0 ; 0 ; 0 ; 0 ; 0 ; f g is
generated. It is translated to a graph and be directly saved since there is nothing to
compare it with. Then ''1'' is added to the current vector, which makes the vector
become 0 ; 0 ; 0 ; 0 ; 0 ; 0 ; 0 ; 0 ; 0 ; 0 ; 0 ; 0 ; 0 ; 0 ; 0 ; f g . Now the new vector becomes the
current vector and it is mapped to a graph and compared with all saved graphs. If an
isomorphism exists in the saved graphs, this vector is discarded. Otherwise the graph
of the vector is added to the saved graph. The method then adds ''1'' to the current
vector and repeats the same graph isomorphism check procedure repeatedly.
The method ends when all possible 16-bit vectors have been used as an input once,

16-bit vector for f ¼ a 0 bd 0 þ ac 0 d þ abd þ ab 0 cd 0 Fig. 14.

Fig. 15. (a) Rules for mapping a vector to a cube (b) 4-D structure for vector

f 1 ; 0 ; 1 ; 0 ; 0 ; 1 ; 1 ; 0 ; 0 ; 1 ; 0 ; 1 ; 0 ; 0 ; 0 ; 0 g