Field-Programmable Gate Arrays: Reconfigurable Logic for Rapid Prototyping and Implementation of Digital Systems

2.4   PETRI NETS FOR STATE MACHINES*

The finite state machines described earlier are sequential machines: only one state can be active at a time. This makes it difficult to design an FSM that is required to control parallel processes. One approach is to divide the specification into a number of sequential machines, which are linked together to implement a parallel controller. However, this does not explicitly represent the concurrency, and so makes it difficult to detect synchronization errors such as deadlock (when two processes are waiting for each other). A more satisfactory method of representing the concurrency is to use a single parallel controller that can have several states active simultaneously. Such a parallel controller can be represented using a Petri net model. This gives a clear specification of the parallelism in the design. The specification can then be analyzed for correctness, and used as a basis for the implementation.

2.4.1   Basic Concepts

A Petri net is a directed graph comprising nodes of two kinds—places and transitions—and directed arcs that connect places to transitions and vice versa. Places are commonly represented by circles and transitions by bars. A place can contain a token, which is depicted as a black dot. A marking of a Petri net is a mapping of a set of tokens to places in the net. The behavior of the system represented by the Petri net is defined by the movement of tokens. A simple Petri net is shown in Figure 2–10.

In the general case, arcs ...