Complexity of basic boolean operators for digital circuit design
This is an incremental survey for researchers and engineers in digital circuit design, summarizing existing knowledge without introducing new methods.
The paper surveys circuit complexity bounds for basic boolean operators used in digital circuit design and efficient synthesis methods, focusing on structurally simple functions like counters and adders while excluding complex algebraic operations.
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.