Synthesis of hazard-free asynchronous circuits from graphical specifications

The authors propose some syntactic and semantic extensions to a graphical specification called the signal transition graph (STG). They allow controlled-choice places to have fanout transitions of input signals and arbitrary Boolean expressions can be used as edge labels. They also allow one STG marking to represent more than one state. These extensions allow for a more natural and compact specification of asynchronous behavior. It is also shown that syntactic constraints on STGs are not sufficient to guarantee hazard-free implementations, and techniques are presented to synthesize hazard-free SOP, (sum of products) implementations under both SIC (single input change) and MIC (multiple input change) conditions. The synthesized circuits are speed-independent. They are hazard-free, independently of the gate delay variations, assuming that the circuit operates in fundamental mode.<>