6 Synthesis of Majority Expressions Through Primitive Function Manipulation
157
Therefore, the MP C was able to generate results 66% faster than exact_mig.
The MP C’s average memory usage was 40.32 MB, while the exact_mig’s was only
5.05 MB.
Note that results for n = 3 are not presented because both algorithms return
optimal solutions for all 256 possible functions.
6.5 Conclusions
In this paper we present the MP C algorithm, which aims to generate majority
functions based on an input truth table. We also present a study on the main concepts
of majority Boolean algebra and primitive functions. With the proposed cost criteria
the MP C presented, in the most part, results better or equal to exact_mig. It’s
important to point out that the MP C is able to find better results only considering
two additional cost criteria: the number of inverters and gate inputs.
For functions with n = 4, from a total of 65,536 possible functions, the MP C
generated functions with lower cost in 42,987 (66%) cases and functions with equal
cost in 7198 (11%) cases, reaching a total of 50,185 (77%) functions with equal or
lower cost than exact_mig. The MP C had an average computational time of 5.50 s
and an average memory usage of 5.56 MB, while the exact_mig had an average
computational time of 3.54 s and an average memory usage of 3.52 MB.
For functions with n = 5, from a sample of 1000 functions, the MP C found
better or equal results for a total of 589 (59%) functions, where 477 (48%) had
lower cost and 112 (11%) had equal cost. The MP C’s average computational
time and memory usage were 41.63 s and 40.32 MB, while exact_mig’s average
computational time and memory usage were 1.15 min and 5.05 MB, respectively.
The MP C’s code is available at: https://github.com/EvandroFerraz/mpc. The list
of functions used to compare MP C and exact_mig for 5-input functions can also be
find in the link.
References
1. Akers, S.B.: A truth table method for the synthesis of combinational logic. IRE Trans. Electron.
Comput. 4, 604–615 (1961)
2. Akers, S.B.: Synthesis of combinational logic using three-input majority gates. In: Proceedings
of the Third Annual Symposium on Switching Circuit Theory and Logical Design, 1962.
SWCT 1962, pp. 149–158. IEEE, Sri Lanka (1962)
3. Amarú, L., Gaillardon, P.E., De Micheli, G.: Majority-inverter graph: a novel data-structure
and algorithms for efficient logic optimization. In: Proceedings of the 51st Annual Design
Automation Conference, pp. 1–6. ACM, New York (2014)
4. Amaru, L., Gaillardon, P.E., Chattopadhyay, A., De Micheli, G.: A sound and complete
axiomatization of majority-n logic. IEEE Trans. Comput. 65(9), 2889–2895 (2016)
5. Bertacco, V., Damiani, M.: The disjunctive decomposition of logic functions. In: International
conference on Computer-aided design (ICCAD), pp. 78–82. IEEE, San Jose (1997)
157
Therefore, the MP C was able to generate results 66% faster than exact_mig.
The MP C’s average memory usage was 40.32 MB, while the exact_mig’s was only
5.05 MB.
Note that results for n = 3 are not presented because both algorithms return
optimal solutions for all 256 possible functions.
6.5 Conclusions
In this paper we present the MP C algorithm, which aims to generate majority
functions based on an input truth table. We also present a study on the main concepts
of majority Boolean algebra and primitive functions. With the proposed cost criteria
the MP C presented, in the most part, results better or equal to exact_mig. It’s
important to point out that the MP C is able to find better results only considering
two additional cost criteria: the number of inverters and gate inputs.
For functions with n = 4, from a total of 65,536 possible functions, the MP C
generated functions with lower cost in 42,987 (66%) cases and functions with equal
cost in 7198 (11%) cases, reaching a total of 50,185 (77%) functions with equal or
lower cost than exact_mig. The MP C had an average computational time of 5.50 s
and an average memory usage of 5.56 MB, while the exact_mig had an average
computational time of 3.54 s and an average memory usage of 3.52 MB.
For functions with n = 5, from a sample of 1000 functions, the MP C found
better or equal results for a total of 589 (59%) functions, where 477 (48%) had
lower cost and 112 (11%) had equal cost. The MP C’s average computational
time and memory usage were 41.63 s and 40.32 MB, while exact_mig’s average
computational time and memory usage were 1.15 min and 5.05 MB, respectively.
The MP C’s code is available at: https://github.com/EvandroFerraz/mpc. The list
of functions used to compare MP C and exact_mig for 5-input functions can also be
find in the link.
References
1. Akers, S.B.: A truth table method for the synthesis of combinational logic. IRE Trans. Electron.
Comput. 4, 604–615 (1961)
2. Akers, S.B.: Synthesis of combinational logic using three-input majority gates. In: Proceedings
of the Third Annual Symposium on Switching Circuit Theory and Logical Design, 1962.
SWCT 1962, pp. 149–158. IEEE, Sri Lanka (1962)
3. Amarú, L., Gaillardon, P.E., De Micheli, G.: Majority-inverter graph: a novel data-structure
and algorithms for efficient logic optimization. In: Proceedings of the 51st Annual Design
Automation Conference, pp. 1–6. ACM, New York (2014)
4. Amaru, L., Gaillardon, P.E., Chattopadhyay, A., De Micheli, G.: A sound and complete
axiomatization of majority-n logic. IEEE Trans. Comput. 65(9), 2889–2895 (2016)
5. Bertacco, V., Damiani, M.: The disjunctive decomposition of logic functions. In: International
conference on Computer-aided design (ICCAD), pp. 78–82. IEEE, San Jose (1997)