Page 738 - Engineering Digital Design
P. 738
704 CHAPTER 14/ASYNCHRONOUS STATE MACHINE DESIGN AND ANALYSIS
State 01 provides a cycle
path for correction
A0B ^ / §
k A D
ZiTif A
Correction path
replacement
FIGURE 14.20
State diagram of an FSM showing a critical race for the 11 -> 00 transition and its elimination by
using a correction path.
the P —> Q transition. Basically, the requirement for a critical race is that the holding
condition of any race state contain the input condition for transition from the origin state
to the destination state. Where only two state variable changes are involved in a given
state-to-state transition, detection of a critical race is easily accomplished by a cursory
inspection of the state diagram. Thus, the following procedure should be followed without
exception:
• Look for race conditions in the state diagram. If the holding condition for any
race state contains I PQ, a critical race exists.
• Make certain that valid branching paths exist between the race states and the
destination state.
• Eliminate the critical race by any one of several means discussed later in this
subsection. Critical races must never be permitted to exist in any asynchronous
FSM designed to operate in the fundamental mode.
As an example, consider the state diagram for an FSM in Fig. 14.20. Shown is a critical
race during the 11 —> 00 transition under branching condition A B. Thus, if the race path
is via state 10 during 11 -> 00 transition, the FSM will reside stably and improperly in
state 10 under holding condition B. Thus, I ca c f d which is the requirement for a critical
race according to Fig. 14.19c. On the other hand, if the race path is via the 01 state, the
FSM will cycle correctly to state 00. The problem is, of course, that it cannot be predicted
by which race path the FSM will transit. The critical race is eliminated by replacing the
11 —> 00 branching path with the 11 ->• 01 path indicated by the dashed arrow, but under
the same branching condition A B. Thus, the basic algorithm has not been altered in making
this correction. State 01 now provides an cycle path from state 11 —> 01 —>• 00 under the
same branching condition AB.
Methods for Eliminating Critical Races The methods for eliminating critical races are
straightforward and similar to those discussed in Subsection 11.2.2 relative to ORGs in
synchronous FSMs. The causal race condition can be eliminated by one of the following
actions given in descending order of importance or desirability:
