O'Reilly logo

VLSI Digital Signal Processing Systems: Design and Implementation by Keshab K. Parhi

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 zy means that z must go low before y can go low. Some of the terminologies associated with the STG are discussed next.

image

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.

image

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+rsr+ , 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. ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required