Direct synthesis of hazard-free asynchronous circuits from STGs based on lock relation and MG-decomposition approach

A new realization algorithm is proposed to synthesize asynchronous hazard-free circuits directly from signal transition graphs (STGs) with underlying free-choice Petri nets. Based on a signal lock relation and MG-decomposition approach, the synthesis method does not use state diagrams and thereby maintains problem size polynomially proportional only to the number of signals. Moreover, the synthesized circuits are guaranteed to be hazard-free under unbounded gate-delay mode without any post-realization analysis and modification. A sufficient condition for hazard-free realization is also derived based on the signal lock relation in STGs. The high-levelness of this condition allows easier manipulation of the specification for realizability. The proposed direct-synthesis algorithm has been shown successful on over thirty academic and industrial examples