Page 451 - Engineering Digital Design

10.2 MODELS FOR SEQUENTIAL MACHINES 421

Fig. 10. Ib. From these physical waveforms the positive logic waveforms are constructed
and a sequence of logic states is read in the order ABC as shown in Fig. 10. Ic. A group of
logic waveforms such as these is commonly known as a timing diagram, and the sequence
of logic states derived from these waveforms is seen to be a binary count sequence. Here,
A, B, and C are called state variables because their values collectively define the present
state of the machine at some point in time. Knowing the present state in a sequence of states
also reveals the next state. Thus, in Fig. 10.Ic, if state 101 is the present state, then 110 is
the next state. This short discussion evokes the following definition:

A logic state is a unique set of binary values that characterize the logic status of a
sequential machine at some point in time.

A sequential machine always has a finite number of states and is therefore called & finite
state machine (FSM) or simply state machine. Thus, if there are N state variables, there
N
can be no more than 2 states in the FSM and no fewer than 2. That is, for any FSM,
2 < (number of states) < 2 N

For example, a two-state FSM requires one state variable, a three- or four-state FSM requires
two state variables, five- to eight-state FSMs require three state variables, etc. More state
N
variables can be used for an FSM than are needed to satisfy the 2 requirement, but this
is done only rarely to overcome certain design problems or limitations. The abbreviation
FSM will be used frequently throughout the remainder of this text.
To help understand the meaning of the various models used in the description and design
of FSMs, four binary sequences of states are given in Fig. 10.2, each presenting a different
feature of the sequence. The simple ascending binary sequence (a) is the same as that in
Fig. 10.1. This sequence and the remaining three will be described as they relate to the
various models that are presented in the following section.

10.2 MODELS FOR SEQUENTIAL MACHINES

Models are important in the design of sequential machines because they permit the design
process to be organized and standardized. The use of models also provides a means of
communicating design information from one person to another. References can be made to
specific parts of a design by using standard model nomenclature. In this section the general
model for sequential machines will be developed beginning with the most elemental forms.
Notice that each state in the sequence of Fig. 10.2a becomes the present state (PS) at
some point in time and has associated with it a next state (NS) that is predictable given the
PS. Now the question is: What logic elements of an FSM are required to do what is required
in Fig. 10.2a? To answer this question, consider the thinking process we use to carry out a
sequence of events each day. Whether the sequence is the daily routine of getting up in the
morning, eating breakfast, and going to work, or simply giving our telephone number to
someone, we must be able to remember our present position in the sequence to know what
the next step must be. It is no different for a sequential machine. There must be a memory
section, as in Fig. 10.3a, which generates the present state. And there must be a next state
logic section, as in Fig. 10.3b, which has been programmed to know what the next state
must be, given the present state from the memory. Thus, an FSM conforming to the model