VLSI Digital Signal Processing Systems: Design and Implementation

16.8    SIGNAL TRANSITION GRAPHS

In this section, specification of asynchronous handshake circuits using signal transition graphs (STGs) [14] is discussed. Here, signal transitions instead of signal levels are used in the specification thereby reducing the complexity of the mapping. A typical STG is shown in Fig. 16.34, where a rising transition of a signal x is denoted by x⁺ , and a falling transition by x⁻. Moreover, an arc in an STG represents a dependence relation. For example, the arc z⁻ → y⁻ means that z must go low before y can go low. Some of the terminologies associated with the STG are discussed next.

Fig. 16.34    A typical STG.

Liveness: An STG is said to be live if every transition can be enabled eventually.

For example, the STG shown in Fig. 16.35 is not live because once transition r⁺ has fired, it may never fire again.

Fig. 16.35    STG that violates liveness.

Safety: An STG is said to be safe if no place or arc can ever contain more than one token.

For example, the STG shown in Fig. 16.36 is not safe, because after the firing sequence s⁺ → r⁻ → s⁻ → r⁺ , the arc from r⁺ to y⁺ has two tokens.

Persistence: An STG is said to be persistent if for all arcs p⁺(p⁻ ) → q⁺ in the STG, there must be other arcs that ensure that q⁺ fires before p⁻(p⁺ ).

The STG shown in Fig. ...