Notes on Hazard-Free Boolean Circuits
S. Jukna
Abstract
The problem of constructing hazard-free Boolean circuits (those
avoiding electronic glitches) dates back to the 1940s and is an
important problem in circuit design and even in cybersecurity. We show that a DeMorgan circuit, that is, a Boolean AND, OR, NOT circuit with negations applied to only input variables, is hazard-free iff the circuit produces (purely syntactically) all prime implicants as
well as all prime implicates of the Boolean function it computes.
This extends to arbitrary DeMorgan circuits a classical result of
Eichelberger [IBM J. Res. Develop., 9 (1965)] showing this
property for circuits producing no terms containing a variable together with its negation. Via an amazingly simple
proof, we also strengthen a recent result Ikenmeyer et
al. [J. ACM, 66:4 (2019)]: not only do the complexities of
hazard-free and monotone circuits for monotone Boolean functions
coincide, but every minimal hazard-free circuit for a monotone
Boolean function must be monotone. We also observe that hazard-free implementations of already very simple Boolean functions require a super-polynomial increase of circuit size and depth, such as, for example, the Boolean function which
accepts a Boolean square matrix iff every row and every column has exactly one 1. Finally, we show that the order of growth of the Shannon function of hazard-free circuits is the same as that of unrestricted circuits.
hazards.pdf