Externally Hazard-Free Implementations of Asynchronous Circuits

We present a new sum-of-product based asynchronous architecture, called the N-SHOT architecture, that operates correctly under internal hazardous responses and guarantees hazard-freeness at the observable non-input signals. We formally prove that within this architecture a verywide class of semi-modular state graphs with input choices (either distributive or non-distributive) that satisfy the complete state coding property always admit a correct implementation. As with synchronous circuits,we permit internal hazards in the combinational logic core, which means we can make use of conventional combinational logic minimization methods to produce the sum-of-product implementation. This represents a significant departure from most existing methods that require the combinational logic to be hazard-free and are mainly valid for distributive behaviors.