Hardware Reference
In-Depth Information
11 Recursive (Category 3) State Machines
11.1 Introduction
We know that, from a hardware perspective, state machines can be classii ed into two
types, based on their
input connections
, as follows.
1)
Moore machines
: The input, if it exists, is connected only to the logic block that
computes the next state.
2)
Mealy machines
: The input is connected to both logic blocks, that is, for the next
state and for the actual output.
In section 3.6 we introduced a new classii cation, also from a hardware point of
view, based on the
transition types
and
nature of the outputs
, as follows (see i gure 11.1).
1)
Regular (category 1) state machines
: This category, illustrated in i gure 11.1a and
studied in chapters 5 to 7, consists of machines with only untimed transitions and
outputs that do not depend on previous (past) output values so none of the outputs
need to be registered for the machine to function.
2)
Timed (category 2) state machines
: This category, illustrated in i gure 11.1b and
studied in chapters 8 to 10, is similar to category 1, except for the fact that one or
more of its transitions depend on time (so these FSMs can have all four transition
types: conditional, timed, conditional-timed, and unconditional).
3)
Recursive (category 3) state machines
: This category is illustrated in i gure 11.1c and
studied in chapters 11 to 13. It can have all four types of transitions, but one or more
outputs depend on previous (past) output values so such outputs must be registered.
Recall that in the standard architecture the outputs are produced by the FSM's
combi-
national
logic block, so the current output values are “forgotten” after the machine
leaves that state; consequently, to implement a recursive (recurrent) machine, some
sort of extra memory is needed.
The name “recursive” for category 3 is due to the fact that when an output depends
on a previous output value that value is generally from that same output, so a recursive
