6 Synthesis of Majority Expressions Through Primitive Function Manipulation
155
As an example consider f = 1000000000000001. The MP C returns the
function M(M(B, C, 1), M(B, D, 0), M(1, M(A, C, 0), M(A, D, 1))) as output
that has 3 levels and 6 gates. The exact_mig algorithm returns M(M(0, C, D),
M(1, D, M(A, B, D)), M(0, C, M(A, B, D))), which has 3 levels and 5 gates.
In the presented case, the MP C generated a result prioritizing the use of two
primitive functions (X 1 = M(B, C, 1) and X 2 = M(B, D, 0)), and a single 2level function (X 3 = M(1, M(A, C, 0), M(A, D, 1))), while exact_mig was able
to generate better results with a single primitive and 2-level functions, since the
combination of both functions uses the gate M(A, B, D) twice and the cost of
repeated gates is disconsidered.
As example of a function where the MP C generated better results, we have
f = 0000001001000100, where the MP C generated the function M(M(A, C, 0),
M(C, D, 1), M(0, B, M(A, D, 1))) as output that has 3 levels, 5 gates, and 2
inverters. The exact_mig generated the function M(M(0, B, C), M(0, D, M(A, C,
D)), M(D, M(A, C, D), M(0, B, C))) for the same truth table f that has 3 levels,
5 gates, and 5 inverters. Note that the MP C generates a function with the same
number of levels and gates, but with less inverters.
In Tables 6.19 and 6.20, comparisons about the runtime of both algorithms are
presented. Table 6.19 shows the total and average runtime for every S i . Table 6.20
shows the total and average runtime for all functions with a specific depth. The
comparisons were made in a computer with 8 GB RAM and a 1.7 GHZ CPU.
Table 6.19 Runtime comparison between MP C and exact_mig by S i
MP C
exact mig
i
S i
Total runtime
Avg. runtime
Total runtime
Avg. runtime
0
1
0.01 s
0.01 s
0.01 s
0.01 s
1
16
1.10 s
0.06 s
1.65 s
0.10 s
2
120
30.02 s
0.25 s
17.85 s
0.14 s
3
560
8.29 min
0.88 s
4.57 min
0.49 s
4
1820
23.41 min
0.77 s
21.44 min
0.70 s
5
4368
3.10 h
2.55 s
2.09 h
1.72 s
6
8008
11.39 h
5.12 s
3.84 h
1.73 s
7
11,440
24.76 h
7.79 s
21.74 h
6.84 s
8
12,870
19.64 h
5.49 s
9.36 h
2.61 s
9
11,440
24.85 h
7.82 s
20.76 h
6.53 s
10
8008
11.69 h
5.25 s
3.54 h
1.59 s
11
4368
3.67 h
3.03 s
2.27 h
1.89 s
12
1820
29.81 min
0.98 s
22.12 min
0.73 s
13
560
7.42 min
0.79 s
4.81 min
0.51 s
14
120
31.56 s
0.26 s
18.68 s
0.15 s
15
16
0.99 s
0.06 s
2.24 s
0.14 s
16
1
0.01 s
0.01 s
0.01 s
0.01 s
Total
65, 536
100.26 h
5.50 s
64.49 h
3.54 s
155
As an example consider f = 1000000000000001. The MP C returns the
function M(M(B, C, 1), M(B, D, 0), M(1, M(A, C, 0), M(A, D, 1))) as output
that has 3 levels and 6 gates. The exact_mig algorithm returns M(M(0, C, D),
M(1, D, M(A, B, D)), M(0, C, M(A, B, D))), which has 3 levels and 5 gates.
In the presented case, the MP C generated a result prioritizing the use of two
primitive functions (X 1 = M(B, C, 1) and X 2 = M(B, D, 0)), and a single 2level function (X 3 = M(1, M(A, C, 0), M(A, D, 1))), while exact_mig was able
to generate better results with a single primitive and 2-level functions, since the
combination of both functions uses the gate M(A, B, D) twice and the cost of
repeated gates is disconsidered.
As example of a function where the MP C generated better results, we have
f = 0000001001000100, where the MP C generated the function M(M(A, C, 0),
M(C, D, 1), M(0, B, M(A, D, 1))) as output that has 3 levels, 5 gates, and 2
inverters. The exact_mig generated the function M(M(0, B, C), M(0, D, M(A, C,
D)), M(D, M(A, C, D), M(0, B, C))) for the same truth table f that has 3 levels,
5 gates, and 5 inverters. Note that the MP C generates a function with the same
number of levels and gates, but with less inverters.
In Tables 6.19 and 6.20, comparisons about the runtime of both algorithms are
presented. Table 6.19 shows the total and average runtime for every S i . Table 6.20
shows the total and average runtime for all functions with a specific depth. The
comparisons were made in a computer with 8 GB RAM and a 1.7 GHZ CPU.
Table 6.19 Runtime comparison between MP C and exact_mig by S i
MP C
exact mig
i
S i
Total runtime
Avg. runtime
Total runtime
Avg. runtime
0
1
0.01 s
0.01 s
0.01 s
0.01 s
1
16
1.10 s
0.06 s
1.65 s
0.10 s
2
120
30.02 s
0.25 s
17.85 s
0.14 s
3
560
8.29 min
0.88 s
4.57 min
0.49 s
4
1820
23.41 min
0.77 s
21.44 min
0.70 s
5
4368
3.10 h
2.55 s
2.09 h
1.72 s
6
8008
11.39 h
5.12 s
3.84 h
1.73 s
7
11,440
24.76 h
7.79 s
21.74 h
6.84 s
8
12,870
19.64 h
5.49 s
9.36 h
2.61 s
9
11,440
24.85 h
7.82 s
20.76 h
6.53 s
10
8008
11.69 h
5.25 s
3.54 h
1.59 s
11
4368
3.67 h
3.03 s
2.27 h
1.89 s
12
1820
29.81 min
0.98 s
22.12 min
0.73 s
13
560
7.42 min
0.79 s
4.81 min
0.51 s
14
120
31.56 s
0.26 s
18.68 s
0.15 s
15
16
0.99 s
0.06 s
2.24 s
0.14 s
16
1
0.01 s
0.01 s
0.01 s
0.01 s
Total
65, 536
100.26 h
5.50 s
64.49 h
3.54 s