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

In the best-case scenario this leads to only clocking one of the sub-FSMs in any given cycle.
Disabling of the clock trees for all other sub-FSMs by gating the clock signal can greatly reduce
power consumption [25].
The example here illustrates the grouping of an FSM into sub-FSMs using a graph partitioning
method. The technique uses the probability of transition of states to pack a set of nodes that are
related with each other into individual sub-FSMs. Consider an FSM be divided into M partitions
of sub-FSMs with each having number of states S 0 , S 1 , ... , S M 1 . Then, for easy coding, the number
of bits allocated for a state register for each of the sub-FSMs is:

max log 2 S 0 ; f log 2 S 1 ; ... ; log 2 S M 1 g

and log 2 M bits is required for switching across sub-FSMs.
Many algorithms translating into complex FSMs are hierarchical in nature. This property can be
utilized in optimally partitioning the FSM into sub-FSMs for power reduction. The algorithm is
broken into different levels, with each level leading to a different sub-FSM. The hierarchical approach
ensures that, when the transition is made fromhigher level to lower level, the other sub-FSMs will not
be triggered for the current frame or buffer of data. This greatly helps in reducing power consumption.
A video decoder is a good application to be mapped on hierarchical FSMs. The design for an
H.264 decoder otherwise needs 186 states in a flattened FSM. Thewhole FSMis active and generates
huge switching activity. By adopting hierarchical parsing of decoder frames and then traversing the
FSM, the design can be decomposed into six levels with 13 sub-FSMs [25]. The designer, knowing
the state transition patterns, can also assign state code that has minimum hamming distance among
closely transitioned states to reduce switching activities.
Many algorithms in signal processing can be hierarchically decomposed. A representative
decomposition is given in Figure 9.23. Each sub-FSM should preferably have a single point of
entry to make it convenient to design and test. Each sub-FSM should also be self-contained to
maximize transitions within the sub-FSM and to minimize transitions across sub-FSMs. The design
is also best for power gating for power optimization.

subFSM_L1

Level 1

subFSM_L2

Level 2

Level 3 subFSM_L3 0 subFSM_L3 1

Level 4

subFSM_L4 10 subFSM_L4 11

Level 5

subFSM_L5 100 subFSM_L5 101 subFSM_L5 102 subFSM_L5 110 subFSM_L5 111

subFSM_L6 1120

Level 6

subFSM_L6 1080 subFSM_L6 1100

Figure 9.23 An FSM hierarchically partitioned into sub-FSMs for effective design, implementation,
testing and power optimization