Notes on Hazard-Free Circuits
Stasys P. Jukna · SIAM Journal on Discrete Mathematics · 2021
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), pp. 90--99] 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 of Ikenmeyer et al. [ J. ACM, 66 (2019), 25]: 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 superpolynomial 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.