Page 470 - Engineering Digital Design

440 CHAPTER 10 / INTRODUCTION TO SYNCHRONOUS STATE MACHINE DESIGN

10.6 PROCEDURE FOR FSM (FLIP-FLOP) DESIGN
AND THE MAPPING ALGORITHM

The following three-step procedure will be used in the design of FSMs including flip-flops:

1. Select the FSM (e.g., a flip-flop type) to be designed and represent this FSM in the
form of a state diagram. The output-forming logic can be mapped and obtained at
this point.
2. Select the memory element (e.g., a basic cell or flip-flop) to be used in the design of
the FSM (e.g., in the design of another flip-flop) and represent this memory element
in the form of an excitation table.
3. Obtain the NS function(s) for the FSM in the form of NS K-maps by combining the
information represented in the state diagram with that represented in the excitation
table for the memory. To accomplish this, apply the following mapping algorithm:

Mapping Algorithm for FSM Design
AND the memory input logic value in the excitation table with the corresponding branch-
ing condition (BC) in the state diagram for the FSM to be designed, and enter the result
in the appropriate cell of the NS K-map.

The mapping algorithm is of general applicability. It will be used not only to design and
convert flip-flops, but also to design synchronous and asynchronous state machines of any
size and complexity. The idea behind the mapping algorithm is that all FSMs, including
flip-flops, are characterized by a state diagram and a memory represented in the form of an
excitation table. The mapping algorithm provides the means by which these two entities can
be brought together in some useful fashion so that the NS functions can be obtained. For
now, the means of doing this centers around the NS K-maps. But the procedure is general
enough to be computerized for CAD purposes by using a state table in place of the state
diagram. Use will be made of this fact in the latter chapters of this text.

10.7 THE D FLIP-FLOPS: GENERAL

Every properly designed and operated D-FF behaves according to a single internationally
accepted definition that is expressed in any one or all of the three ways. Presented in
Fig. 10.23 are the three means of defining the D flip-flop of any type. The first is the
operation table for any D-FF given in Fig. 10.23a. It specifies that when D is active Q must
be active (Set condition), and when D is inactive Q must be inactive (Reset condition). The
state diagram for any D-FF, given in Fig. 10.23b, is best derived from the operation table
and expresses the same information about the operation of the D-FF. Thus, state 0 is the
Reset state (Q, = 0) when D = 0, and state 1 is the Set state (Q, = 1) when D = 1.
The excitation table for any D-FF, given in Fig. 10.23c, is the third means of expressing
the definition of a D-FF. It is best derived directly from the state diagram in Fig. 10.23b. In
this table the Q t —> Q t+\ column represents the state variable change from PS to NS, and
the D column gives the input logic value for the corresponding branching path in the state