Page 722 - Engineering Digital Design

688 CHAPTER 14/ASYNCHRONOUS STATE MACHINE DESIGN AND ANALYSIS

The subscripts in Eqs. (14.2) are assigned the ranges of values

/=0, 1,2, ...,/i-l
7=0, 1,2, ...,m - 1

* = 0, 1,2, ...,m - 1
/ = 0, 1,2, .--,r- l

The fact that the inputs, jc/, can be multivariable functions implies that one asynchronous
FSM may be controlled by another asynchronous FSM.
Inspection of Eqs. (14.2) indicates that corresponding NS and PS variables are separated
in time by distinct lumped delay memory elements, A?y. This leads directly to the important
stability criteria for asynchronous FSMs operated in the fundamental mode:

Stability Criteria
If the PS is logically equal to the NS at some point in time, then

Yj(t) = yj(t) (far all j\ (14.3)

and the asynchronous FSM is stable in that state.
If the PS and NS are not logically equal at any point in time, then

Yj(t}^ yj(t} (for any j), (14.4)

and the asynchronous FSM is unstable in that state and must transit to another state.

Here, the presence of a lumped memory element for each feedback loop ensures that all
path delays within the NS forming logic are represented. A much less attractive alternative
is the distributed path delay model, which requires a memory element for each gate and as
many state variables. The LPD model has the decided advantage of simplicity — it requires
a minimum of lumped memory elements and hence a minimum number of state variables.
Use of the distributed path delay model would be prohibitively difficult for all but the
simplest state machines.

14.4 THE EXCITATION TABLE FOR THE LPD MODEL

The excitation table for the LPD model of Fig. 14.2 and all of its degenerate forms is derived
directly from the stability criteria given by Eqs. (14.3) and (14.4). The results are shown in
Figs. 14.3a and 14.3b, where a stable condition exists for y t = Y t, and an unstable condition
exists if y t ^ Y t. Here, y, —> y t+\ represents a transition from the PS to the NS, implying
that y t+\ = Y, = NS. It is important to notice the similarity between the excitation table
in Fig. 14.3b and that for the D flip-flop in Fig. 14.3c. Thus, it is expected that some LPD
design methods apply to synchronous D flip-flop designs and vice versa. The excitation
table for the LPD model is essential to the design of asynchronous FSMs to be operated in
the fundamental mode and will be used extensively throughout the remainder of this text.