Distributed system and switching circuits optimization methods for Boolean functions of small number of variables

Lozhkin, S.A.; Shupletsov, M.S.; Konovodov, V.A.; Danilov, B.R.; Zhukov, V.V.; Bagrov, N.Yu.

Home Authors Papers Year of conference Themes Organizations To MES conference

Distributed system and switching circuits optimization methods for Boolean functions of small number of variables

Authors

Date of publication

2016

Abstract

The synthesis of optimal or suboptimal switching circuits is an actual problem of theory of discrete control systems. Libraries of such circuits could be used in various algorithms of logic synthesis (see., Eg, [1]). The structure analysis of optimal circuits for functions of few variables may be useful in the development of elements for the library design process of integrated circuits.
The first catalogs of minimal switching circuits that implement Boolean functions (BF) of small number of variables appeared [2,3,4] in the 1950s. They contained the upper bounds for complexities of all typical 4-variables BF (total 402 functions).
In [5] G.N. Povarov showed that only one of these 402 BF’s requires at most 14 contacts, four BF’s require at most 13 contacts, and the rest require at most 12 contacts. Then various authors [4-8] showed that only one of them has the complexity 13. In [9] Shannon showed that upper bound for 5-variables BF in the class of switching circuits is 30 contacts. Later, G.N. Povarov [10] lowered this estimate to 28. V.Yu. Susov [8] has found the BF of 5 variables which complexity is at least 19. Thus the question for finding more precise upper bounds for the complexity of 5-variables BF in the class of switching circuits remains.
A number of circuit synthesis algorithms have been developed to approach the problem for 5-variables BF’s. These algorithms have been implemented in a number of tools that have been used to improve known circuits for a large number of 5-variable BF’s. As a result it was shown that upper bound for 5-varibale BF’s size-complexity is 22.

Keywords

switching circuit, size-complexity, circuits synthesis methods, database, cascade circuit synthesis.

Library reference

Lozhkin S.A., Shupletsov M.S., Konovodov V.A., Danilov B.R., Zhukov V.V., Bagrov N.Yu. Distributed system and switching circuits optimization methods for Boolean functions of small number of variables // Problems of Perspective Micro- and Nanoelectronic Systems Development - 2016. Proceedings / edited by A. Stempkovsky, Moscow, IPPM RAS, 2016. Part 1. P. 40-47.

URL of paper

http://www.mes-conference.ru/data/year2016/pdf/D180.pdf