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

on-set vertices are exactly the same (one face and another vertex above it), and the
only difference between them is they are in different positions.
If one can find all possible on-set structures in a 4-D cube/K-map and determine
the most simplified majority expression for each structure, any four-variable problem
could be targeted to these solutions to get the most simplified majority expression.
These structures are referred to as standard functions.

3.4 Identifying Standard Functions

In this work, a 4-D cube with 16 vertices is considered as a graph. Its subgraphs are
the 4-D structures that are constructed by all of the on-set vertices in Boolean logic
functions. If two 4-D structures are isomorphic, they are essentially the same struc-
tures, but just located in different positions in a 4-D cube. One structure can be moved
to overlap another structure. So if two 4-D structures of Boolean logic functions are
isomorphic, these two functions belong to the same category, which means they have
a common standard function. If all graph isomorphism categories can be identified,
then a full set of standard functions are obtained.
The Nauty algorithm is used to identify if two subgraphs are isomorphic. Since a
subgraph is a graph itself, the term ''graph'' will be used for convenience. Based on
Nauty, a new method has been developed to find all standard functions, as shown in
Fig. 13 . All possible four-variable Boolean logic functions, a total of 2 16

= 65536, are

Fig. 13. Flowchart for finding standard functions