A new approach for checking the unique state coding property of signal transition graphs

A signal transition graph (STG) embodies the causal relationships among signal transitions in a system, and provides a useful starting point for the synthesis of asynchronous circuits. The prevalent synthesis techniques require the input STG to possess the unique state coding (USC) property. This paper describes an algorithm to ascertain whether a given STG has the USC property. The algorithm is path-oriented, and has the advantage of operating directly on the STG rather than a state graph. This approach has the advantage of being easier to visually and intuitively correlate with the STG specification, and therefore suggest ways in which a designer (or tool) may modify the input STG if it does not satisfy the USC property. The technique can also be used to compute the input set of a signal