Intelligent Systems.
Theory and Applications

(Intellektual'nye Sistemy. Teoriya i Prilozheniya)

Asymptotically Optimal Boolean Circuit Synthesis in Complexity with Linear Switching Activity for Arbitrary Boolean Functions

Abstract

We consider the synthesis of Boolean circuits with simultaneous bounds on weighted complexity and switching activity, the maximum number of gates whose values differ between two input assignments. For every finite complete basis \(\mathcal B\) belonging to the union of two special classes and every Boolean function \(f(x_1,\ldots ,x_n)\), we construct a circuit \(\Sigma _f\) over \(\mathcal B\) that computes \(f\). Its weighted complexity \(L(\Sigma _f)\) and switching activity \(C(\Sigma _f)\) satisfy the following bounds for \(n=1,2,\ldots\): \[\begin {gathered} L(\Sigma _f)\le \rho (\mathcal B)\frac {2^n}{n} \left (1+\frac {6\log _2 n}{n}+O\!\left (\frac 1n\right )\right ),\quad C(\Sigma _f)=O(n), \end {gathered}\] where \(\rho (\mathcal B)\) is the minimum reduced weight of the basis elements. The first bound is asymptotically equal to the corresponding Shannon function, while the second is a linear upper bound.

Keywords: Boolean circuits, weighted complexity, switching activity, Shannon function, two-parameter circuit optimization.

BibTeX
@article{IS-Dai-Lozhkin2026,
  author  = {Dai, Yue and Lozhkin, Sergey Andreevich},
  title   = {{Asymptotically Optimal Boolean Circuit Synthesis in Complexity with Linear Switching Activity for Arbitrary Boolean Functions}},
  journal = {Intelligent Systems. Theory and Applications},
  year    = {2026},
  volume  = {30},
  number  = {4},
  pages   = {212--215},
}
AMSBIB
\Bibitem{IS-Dai-Lozhkin2026}
\by Y.~Dai, S.\,A.~Lozhkin
\paper Asymptotically Optimal Boolean Circuit Synthesis in Complexity with Linear Switching Activity for Arbitrary Boolean Functions
\jour Intelligent Systems. Theory and Applications
\yr 2026
\vol 30
\issue 4
\pages 212--215
\lang In Russian
Published under Creative Commons Attribution 4.0 International (CC BY 4.0)

← Back to issue

× Issue cover