Machines with Memory - Models of Computation: Exploring the Power of Computing - page 107

this circuit be fully propagated to its outputs in the intervals when the clock is low. A circuit
that operates this way is considered safe . Designers of sequential circuits calculate the time for
signals to pass through a logic circuit and set the interval between clock pulses to insure that
the operation of the sequential circuit is safe.
Sequential circuits are designed from finite-state machines (FSMs) in a series of steps.
Consider an FSM M =(Σ , Ψ , Q , δ , λ , s ) with input alphabet Σ , output alphabet Ψ , state
set Q ,next-statefunction δ : Q

Ψ , and initial state s .
(For this discussion we ignore the set of final states; they are important only when discussing
language recognition.) We illustrate the design of a sequential machine using the FSM of
Fig. 3.10 , which is repeated in Fig. 3.13 .
The first step in producing a sequential circuit from an FSM is to assign unique binary
tuples to each input letter, output letter, and state (the state-assignment problem). This is
illustrated for our FSM by the tables of Fig. 3.14 in which the identity encoding is used on
inputs and outputs. This step can have a large impact on the size of the logic circuit produced.
Second, tables for δ : B 4

× Σ → Q , output function λ : Q →

B 2 and λ : B 2 B , the next-state and output functions of

the FSM, respectively, are produced from the description of the FSM, as shown in the same
figure. Here c ∗ and s ∗ represent the successor to the state ( c , s ) . Third, circuits are designed
that realize the binary functions associated with c ∗ and s ∗ . Fourth and finally, these circuits are
connected to clocked binary memory devices, as shown in Fig. 3.15 ,toproduceasequential
circuit that realizes the FSM. We leave to the reader the task of demonstrating that these circuits
compute the functions defined by the tables. (See Problem 3.11 .)
Since gates and clocked memory devices can be constructed from semiconductor materials,
a sequential circuit can be assembled from physical components by someone skilled in the use
of this technology. We design sequential circuits in this topic to obtain upper bounds on the
size and depth of the next-state and output functions of a sequential machine so that we can
derive computational inequalities.

→ →

00 11 01, 10

Start

q 0 / 0 q 2 / 0

11

01, 10 00 11 01, 10

00

q 1 / 1 q 3 / 1

01, 10 00 11

Figure 3.13 A finite-state machine that simulates the ripple adder of Fig. 2.14 . It is in state q r
if the carry-and-sum pair ( c j + 1 , s j ) generated by the j th full adder of the ripple adder represents
the integer r ,0

≤ r ≤

3. The output produced is the sum bit.