Notes on hazard-free circuits

DOI10.1137/20M1355240zbMATH Open1476.68084arXiv2012.10976MaRDI QIDQ4986809FDOQ4986809

Authors: Stasys Jukna 

Publication date: 28 April 2021

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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 is hazard-free if and only if 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 special depth-two circuits. Via an amazingly simple proof, we also strengthen a recent result Ikenmeyer et al. [J. ACM, 66:4 (2019)]: not only the complexities of hazard-free and monotone circuits for monotone Boolean functions do coincide, but every optimal hazard-free circuit for a monotone Boolean function must be monotone. Then we show that hazard-free circuit complexity of a very simple (non-monotone) Boolean function is super-polynomially larger than its unrestricted circuit complexity. This function accepts a Boolean n x n matrix iff every row and every column has exactly one 1-entry. Finally, we show that every Boolean function of n variables can be computed by a hazard-free circuit of size O(2^n/n).

Full work available at URL: https://arxiv.org/abs/2012.10976

Recommendations

• On the complexity of hazard-free circuits
• On the complexity of hazard-free circuits
• On the complexity of detecting hazards
• Elimination of static and dynamic hazards for multiple input changes in combinational switching circuits
• Hazard algebras. (Extended abstract)

zbMATH Keywords

lower boundsShannon functionmonotone circuitshazard-free circuits

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Switching theory, applications of Boolean algebras to circuits and networks (94C11) Networks and circuits as models of computation; circuit complexity (68Q06)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• The ellipsoid method and its consequences in combinatorial optimization
• The complexity of partial derivatives
• Title not available (Why is that?)
• A Way to Simplify Truth Functions
• Title not available (Why is that?)
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• On computing the determinant in small parallel time using a small number of processors
• The monotone circuit complexity of Boolean functions
• Lower bounds on monotone complexity of the logical permanent
• The gap between monotone and non-monotone circuit complexity is exponential
• Hazard Detection in Combinational and Sequential Switching Circuits
• Application of Ternary Algebra to the Study of Static Hazards
• Monotone circuits for matching require linear depth
• Title not available (Why is that?)
• A logic hazard detection and elimination method
• Elimination of static and dynamic hazards for multiple input changes in combinational switching circuits
• On the complexity of detecting hazards
• Title not available (Why is that?)
• On the Complexity of Hazard-free Circuits

Cited In (3)

• Essential Hazard Correction Without the Use of Delay Elements
• Elimination of static and dynamic hazards for multiple input changes in combinational switching circuits
• On the complexity of hazard-free circuits

Uses Software

• JBool

This page was built for publication: Notes on hazard-free circuits

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4986809)