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

combinations should be multiplied by 2 because the third input can be either logic ''1''
or logic ''0''. The total number of primitives that belong to this type is calculated as
shown in Eq. ( 7 ).

ð C 2 4 Þ 2 ¼ 48 ð 7 Þ

The last type of primitive has all of three variable-inputs. For this type, three of the
four variables ''a'' , '' b'' , '' c'' a n d '' d'' will be picked up to fill a majority gate and each
variable can appear as itself or its complement, thus giving a total number as calcu-
lated in Eq. ( 8 ). Therefore, the total number of primitives for four-variable functions is
calculated as Eq. ( 9 ).

C 3 2 3 ¼ 32

ð 8 Þ

2 þ 8 þð C 2 4 Þ 2 þ C 3 2 3 ¼ 10 þ 48 þ 32 ¼ 90 ð 9 Þ

The total number of primitives for three-variable problems can be obtained
through the same method. Equation ( 10 ) shows the detailed calculation.

8 þð C 2 3 Þ 2 þ 2 3 ¼ 40

ð 10 Þ

In summary, there are ninety primitives for four-variable problems and forty for
three-variable problems. The three-variable primitives are a subset of the four-variable
primitives. Table 1 lists all four-variable primitives.

3.2 Majority Expression

The geometric interpretations of three-variable problems have been explored in [ 10 ].
However, four-variable functions are more complex because they cannot always be
built within two levels. The basic principle will be introduced through an example
described in Eq. ( 11 ):

f ¼ ab 0 c 0 d 0 þ abcd þ ac 0 d

ð 11 Þ

As a four-variable function can be mapped on to a four by four K-map as a
collection of on-set and off-set squares, the K-map of the function f is shown in Fig. 9
with the filled squares as on-set and the white squares as off-set.
As shown in Fig. 10 , the solution can be represented by a tree structure with each
of its nodes containing at most three branches since a majority gate has only three
inputs. The top node of the tree is the result which is formed by selecting the proper
primitives as inputs to a majority gate. The rule for selecting primitives is stated as
follows:
The first primitives should cover as many on-set squares as possible and as few
off-set squares as possible. If several primitives meet this rule, any one of them can be
selected. The second primitive must cover the on-set squares that are not covered by
the first primitive and must not cover the off-set squares that are covered by the first
primitive. For the second primitive, it is also an objective to cover as many on-set
squares and as few off-set squares as possible. After the first two primitives are