Русский
Complexity of basic boolean operators for digital circuit design
Sergeev I. S.
Received: 12 Jan 2026 Accepted: 19 Mar 2026
Published: 2026, vol. 30, issue 1, pp. 164–186
Abstract
This article provides a survey of circuit complexity bounds for basic boolean transforms exploited in digital circuit design and efficient methods for synthesizing such circuits. The exposition covers structurally simple functions and operators, such as counters, adders, encoders, and multiplexors, and excludes more complex algebraic operations with numbers, polynomials, and matrices. Several applications to implementing more specific operations are also discussed.
Keywords: boolean circuits, complexity, depth, parallel circuits, prefix circuits, incrementor, up-down counter, Gray counter, adder, comparator, decoder, multiplexor, encoder, compressor, threshold symmetric functions, priority encoder, unary coding, sorting
BibTeX
@article{IS-Sergeev2026,
author = {Sergeev, Igor Sergeevich},
title = {{Complexity of basic boolean operators for digital circuit design}},
journal = {Intelligent Systems. Theory and Applications},
year = {2026},
volume = {30},
number = {1},
pages = {164--186},
}
AMSBIB
\Bibitem{IS-Sergeev2026}
\by I.\,S.~Sergeev
\paper Complexity of basic boolean operators for digital circuit design
\jour Intelligent Systems. Theory and Applications
\yr 2026
\vol 30
\issue 1
\pages 164--186
\lang In Russian