O'Reilly logo

Asynchronous Circuit Design by Chris J. Myers

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

4

Graphical Representations

One ought, every day at least, to hear a little song, read a good poem, see a fine picture, and if it were possible, to speak a few reasonable words.

—Johann Wolfgang von Goethe

Take nothing but pictures. Leave nothing but footprints. Kill nothing but time.

—Motto of the Baltimore Grotto (caving society)

One picture is worth a thousand words.

—Fred R. Barnard

In this chapter we present several methods for representing asynchronous circuits using graphs. While for large designs hardware description languages allow a clearer specification of behavior, graphs are a useful pictorial tool for small examples. They are also the underlying data structure used by virtually all automated analysis, synthesis, and verification tools. Most graphical representation methods can be loosely categorized as either state machine-based or Petri net-based. We present various different types of each and conclude with a description of timed event/level (TEL) structures, which unify some of the key properties of both.

4.1 GRAPH BASICS

In this section we present a brief introduction to basic graph terminology used in this chapter. A graph, G, is composed of a finite nonempty set of vertices, V, and a binary relation R on V (i.e., RV × V). A graph can be either undirected or directed.

image

Fig. 4.1 (a) Simple undirected graph. (b) Graph which is not connected.

In an undirected graph, ...

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