Designs based on Finite State Machines - Digital Design of Signal Processing Systems: A Practical Approach - page 409

111101 S 0

111101 S 0

111100

111110 S 1 S 61

111110 S 1

S 7

111111 S 2 111111 S 2 S 7

S 6

000001 S 3 000001 S 3

S 8

S 8

000000

000010 S 4

000010 S 4 S 60

000011 S 5

000011 S 5

(a) (b)

Figure 9.18 FSM optimization by splitting a critical state to reduce the hamming distance of state
transitions. (a) Portion of original FSM with critical state. (b) Splitting of critical state into two

the many available optimization algorithms, one is to find a critical state that is connected to many
states where the transitions into the critical state cause large hamming distances, thus generating
significant switching activity. The algorithm, after identifying the critical state, splits it into two to
reduce the hamming distance among the connected states and then analyzes the FSM to evaluate
whether the splitting results in a power reduction without adding too much area in the design.
This is illustrated in Figure 9.18. Part (a) shows the original FSM, and (b) shows the transformed
FSM with reduced switching activity as a result of any transition into the states formed by splitting
the critical state. In an FSM with a large number of states, modeling the problem for an optimal
solution is an 'NP complete' problem. Several heuristics are proposed in the literature, and an
effective heuristic for the solution is given in [16].

9.6 Designing for Testability
From the testability perspective it is recommended to add reset and status reporting capabilities in an FSM.
To provide an FSMwith a reset capability, there should be an input that makes the FSM transition from any
state to some defined initial state. An FSMwith status message capability also increases the testability of the
design. An FSM with this capability always returns its current state for a defined query input.

9.6.1 Methodology
The general methodology of testing digital designs discussed in Chapter 2 should be observed.
Additionally, the methodology requires a specification or design document of the FSM that
completely defines the FSMbehavior for all possible sequences of inputs. This requires the developer
to generate minimum length sequences of operations that must test all transitions of the FSM.
For initial white-box module-level testing, the stimulus should keep a record of all the transitions,
corresponding internal states of the FSM, and inputs and output before a fault appears. This helps the
designer to trace back and localize a bug.