On minimal circuits for linear functions over some bases
Yu. A. Kombarov · Discrete Mathematics and Applications · 2013
In this research we consider realisations of linear Boolean functions by circuits of functional elements over the basis B which consists of two-input functional elements realising nonlinear functions and an inverter. The weight of a two-input element over the basis B is set equal to one, and the weight of the inverter is zero. We give a description of all minimal circuits realising linear function over the basis B and show that all these circuits are of specific block form. This research was supported by the Russian Foundation for Basic Research, grant 11- 01-00508, and the Program of Basic Research of the Department of Mathematical Sciences of the Russian Academy of Sciences ‘Algebraic and Combinatorial Methods of Mathematical Cybernetics and Information Systems of New Generation,’ project ‘Problems of Optimal Synthesis of Control Systems.’