Hardware Reference
In-Depth Information
1 The Finite State Machine Approach
1.1 Introduction
This chapter presents fundamental concepts and introduces new material on the i nite
state machine (FSM) approach for the modeling and design of sequential digital
circuits.
A summary of the notation used in the topic is presented in table 1.1.
1.2 Sequential Circuits and State Machines
Digital circuits can be classii ed as
combinational
or
sequential
. A combinational circuit
is one whose output values depend solely on the present input values, whereas a
sequential circuit has outputs that depend on previous system states. Consequently,
the former is memoryless, whereas the latter requires some sort of memory (generally,
D-type l ip-l ops [DFFs], reviewed in section 2.2).
An example of a combinational circuit is presented in i gure 1.1a, which shows
an
N
-bit adder; because the present sum is not affected by previous sums computed
by the circuit, it is combinational. An example of sequential circuit is depicted in
i gure 1.1b, which shows a synchronous three-bit counter (it counts from 0 to 7);
because its output depends on the system state (for example, if the current output is
5, then the next will be 6), it is a sequential circuit. Note the presence of a clock signal
in the latter.
An often advantageous model for sequential circuits is presented in i gure 1.2a,
which consists of a combinational logic block in the forward path and a memory
(DFFs) in the feedback loop. When this architecture is used, a
i nite state machine
(FSM)
results. Note that the state presently stored in the memory is called
pr_state
, and
the state to be stored by the DFFs at the next (positive) clock transition is called
nx_state
.
An example of such a modeling technique is depicted in i gure 1.2b, which shows
the same circuit of i gure 1.1b, now reorganized according to the architecture of
