Page 518 - Engineering Digital Design

488 CHAPTER 10 / INTRODUCTION TO SYNCHRONOUS STATE MACHINE DESIGN

10.15 Design the FSM in Fig. P10.7b by using PK flip-flops that are characterized by the
excitation table in Fig. P10.5b. To do this, find the gate-minimum logic required for
the NS- and output-forming logic. Do not implement the result. Thus, the information
in Figs. P10.7b and P10.5b must be brought together via the mapping algorithm in
Section 10.6. (Hint: The easiest approach to this problem is to obtain the NS K-maps
for a D flip-flop design and then apply the conversion logic for D-to-PK K-map
conversion. See Subsection 10.12.2 for assistance if needed.)
10.16 (a) Construct a four-state state diagram for an FSM that samples (with clock) a
continuous stream of data on an input X. The FSM is to issue an output Z any time
the sequence .. .1001... occurs. Consider that the sequence can be overlapping as,
for example, .. .100100100....
(b) By using two state variables, give this state diagram any valid state code assign-
ment.
10.17 Repeat Problem 10.16 for a nonoverlapping sequence .. .0101

10.18 Construct the state diagram for an FSM that samples (with clock) a continuous
stream of data on an input X. The FSM is to issue an output Z any time the sequence
...10110... occurs. Consider that the sequence can be overlapping as, for example,
.. .10101011011010..., where an output is issued twice in this series. The state
diagram must conform to the following representations:
(a) A Moore FSM representation with six states.
(b) A Mealy FSM representation with five states.
10.19 (a) Design a serial 2 's complementer logic circuit by using two RET D flip-flops and
a gate-minimum NS and output forming logic. To do this, follow Algorithm 2.6 in
Subsection 2.6.2 and the ASM chart in Fig. 13.29b. The inputs are Start and Bin (for
binary), and the output is T (for two's complement), all active high. (Hint: There
are at least three states and the process is unending.)
(b) Test the design of the serial 2's complementer by simulation and compare the
results with the timing diagram in Fig. 13.30.
(c) Repeat part (a), except use two RET JK flip-flops. Which design is more optimum?
Explain.
10.20 Shown in Fig. P10.8 is the logic circuit for an FSM that has two inputs, X and 7,
and two outputs, P and Q. Analyze this FSM to the extent of constructing a fully
documented state diagram. To do this, follow the examples in Section 10.13.
10.21 Presented in Fig. PI0.9 is the logic circuit for a two-input/one-output FSM that is
to be analyzed. To do this, construct a fully documented state diagram by following
the example in Figs. 10.66 and 10.67. Indicate any possible branching problems this
FSM may have. Such problems may include states for which there is no entrance as,
for example, don't care states.
10.22 In Fig. PIO.IO is the logic circuit for a single-input/single-output FSM. Analyze
this FSM by constructing a fully documented state diagram. Indicate any possible
branching problems this FSM may have. Such problems may include states for which
there is no entrance.