Распределенная система и алгоритмы поиска минимальных и близких к ним контактных схем для булевых функций от малого числа переменных

Проблемы разработки перспективных микро- и наноэлектронных систем (МЭС). 2016. Т. 1. С. 40–47.

Ложкин С. А., Шуплецов М. С., Коноводов В. А., Danilov B. R., Жуков В. В., Багров Н. Ю.

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 (e.g., see [1]). The structure
analysis of optimal circuits for functions of few variables may be useful in the development of standard cell libraries.

The first catalogs of minimal switching circuits that implement Boolean functions (BF) of small number of
variables appeared [5,6,7] in the 1950s. They contained the upper bounds for complexities of all typical 4-variables BF (total 402 functions).

In [8] 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 [7-11] showed that only one of them has the complexity 13. In [3] Shannon showed that upper bound for 5-variables BF in the class of switching circuits
is 30 contacts. Later, G.N. Povarov [12] lowered this estimate to 28. V.Yu. Susov [11] has found the BF of 5 variables, complexity of which is at least 19. Thus, the question of finding more precise upper bounds for the complexity of 5-variable BF in the class of switching circuits remains relevant.

A number of circuit synthesis algorithms have been developed to approach the problem for 5-variable 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: булева функция, Boolean function, control systems synthesis and complexity, синтез и сложность управляющих систем, switching circuit, контактная схема