Notes on hazard-free circuits

DOI10.1137/20M1355240MaRDI QIDQ4986809zbMATHFDO

Authors Stasys Jukna

Publication date 28 April 2021

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

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

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)

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).

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)

Cites work

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

Cited in

(5)

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

Describes a project that uses

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)