Algebras for Hazard Detection

J. A. Brzozowski
Department of Computer Science
University of Waterloo
Waterloo, Ontario, Canada N2L 3G1
brzozo@uwaterloo.ca

Z. Esik
Department of Computer Science
University of Szeged
Szeged, Hungary
esik@inf.u-szeged.hu

Y. Iland
Department of Computer Science
University of Waterloo
Waterloo, Ontario, Canada N2L 3G1
yiland@uwaterloo.ca

January 25, 2001

Abstract

Hazards pulses are undesirable short pulses caused by stray delays in digital circuits.
Such pulses not only may cause errors in the circuit operation, but also consume energy,
and add to the computation time. It is therefore very important to detect hazards in circuit
designs. Two-valued Boolean algebra, which is commonly used for the analysis and synthesis of
digital circuits, cannot detect hazard conditions directly. To overcome this limitation several
multi-valued algebras have been proposed for hazard detection. This paper surveys these algebras,
and studies their mathematical properties. Also, some recent results unifying most of the multi-valued
algebras presented in the literature are described. Our attention in this paper is restricted to the
study of static and dynamic hazards in gate circuits.