Circuit Simulation Using a Hazard Algebra

Mihaela Gheorghiu

MMath Thesis
Department of Computer Science
University of Waterloo
Waterloo, Ontario
Canada N2L 3G1
December, 2001
(supervised by Janusz Brzozowski)


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.