Mihaela Gheorghiu

Department of Computer Science

University of Waterloo

Waterloo, Ontario

Canada N2L 3G1

December, 2001

(supervised by Janusz Brzozowski)

** Abstract **

Hazards are unwanted signal changes that may affect the correctness of
computations in asynchronous circuits. For this reason, it is very
important to have accurate and efficient methods of hazard
detection. Recently, Brzozowski and Esik proposed a new
infinite-valued algebra for the detection of hazards, and a simulation
algorithm based on this algebra. Their simulation method seems to be
able not only to detect hazards, but also to count all the signal
changes that may occur in gate circuits in the worst case. In this
thesis we study the correctness of the new simulation method, by
comparing it to binary analysis. Binary analysis is a model of
behavior for asynchronous circuits that considers all possible
behaviors under different delay distributions. We prove that, for any
gate circuit started in any state, the result of the binary analysis
is covered by the result of the simulation, in the sense that all
signal changes occurring in the binary analysis occur also in the
simulation. Conversely, we prove that, for feedback-free circuits
composed of one- and two-input gates and started in a stable state,
the result of the simulation is covered by the result of the binary
analysis, in the sense that all the changes predicted by the
simulation occur in the binary analysis, if input, wire, and fork
delays are taken into consideration.

This research was supported by the Natural Sciences and Engineering
Research

Council of Canada under grant No. OGP0000871.