Unit-5

Synchronous Sequential Circuits

Basic Design Steps
• Moore Model
• Output:
• depends only on the state of the system
• does not depend on the present input
• occurs after desired pattern
we wish to design a circuit that meets the following specification:
• 1. The circuit has one input, w, and one output, z.
• 2. All changes in the circuit occur on the positive edge of a clock signal.
• 3. The output z is equal to 1 if during two immediately preceding clock cycles the
input w was equal to 1. Otherwise, the value of z is equal to 0.
• From this specification it is apparent that the output z cannot depend solely on
the present value of w.
• consider the sequence of values of the w and z signals during 11 clock
cycles, as shown in Figure 8.2.
• The values of w are assumed arbitrarily ; the values of z correspond to
our specification.
• These sequences of input and output values indicate that for a given
input value the output may be either 0 or 1.
• For example, w = 0 during clock cycles t2 and t5, but z = 0 during t2 and
z = 1 during t5.
• Similarly, w = 1 during t1 and t8, but z = 0 during t1 and z = 1 during t8.
• This means that z is not determined only by the present value of w, so
there must exist different states in the circuit that determine the value
of z.
State Diagram
• A good way to begin is to select one particular state as a starting state; this is the state
that the circuit should enter when power is first turned on or when a reset signal is
applied.
• For our example let us assume that the starting state is called state A.
• As long as the input w is 0, the circuit need not do anything, and so each active clock
edge should result in the circuit remaining in state A.
• When w becomes equal to 1, the machine should recognize this, and move to a
different state, which we will call state B. This transition takes place on the next active
clock edge after w has become equal to 1.
• In state B, as in state A, the circuit should keep the value of output z at 0, because it
has not yet seen w = 1 for two consecutive clock cycles.
• When in state B, if w is 0 at the next active clock edge, the circuit should move back to
state A.
• However, if w = 1 when in state B, the circuit should change to a third state, called C,
and it should then generate an output z = 1. The circuit should remain in state C as long
as w = 1 and should continue to maintain z = 1.
• When w becomes 0, the machine should move back to state A.
• The conceptually simplest method is to use a pictorial representation in the form
• of a state diagram, which is a graph that depicts states of the circuit as nodes (circles)
• and transitions between states as directed arcs.
• The state diagram in Figure 8.3 defines the behavior that corresponds to our specification.
States A, B, and C appear as nodes in the diagram. Node A represents the starting state, and
it is also the state that the circuit
• will reach after an input w = 0 is applied. In this state the output z should be 0, which
• is indicated as A/z=0 in the node.
• The circuit should remain in state A as long as w = 0, which is indicated by an arc with a label
w = 0 that originates and terminates at this node.
• The first occurrence of w = 1 (following the condition w = 0) is recorded by moving from
state A to state B.
• This transition is indicated on the graph by an arc originating at A and terminating at B. The
label w = 1 on this arc denotes the input value that causes the transition. In state B the
output remains at 0, which is indicated as B/z=0 in the node.
• When the circuit is in state B, it will change to state C if w is still equal
to 1 at the next active clock edge.
• In state C the output z becomes equal to 1. If w stays at 1 during
• subsequent clock cycles, the circuit will remain in state C maintaining
z = 1. However, if
• w becomes 0 when the circuit is either in state B or in state C, the
next active clock edge will cause a transition to state A to take place.
State Table
• The table indicates all transitions from each present state to the next
state for different values of the input signal.
• Note that the output z is specified with respect to the present state,
namely, the state that the circuit is in at present time. Note also that
we did not include the Reset input; instead, we made an implicit
assumption that the first state in the table is the starting state.
State Assignment
• The state table in Figure 8.4 defines the three states in terms of letters
A, B, and C.
• When implemented in a logic circuit, each state is represented by a
particular valuation (combination of values) of state variables.
• Each state variable may be implemented in the form of a flip-flop.
Since three states have to be realized, it is sufficient to use two state
variables.
• Let these variables be y1 and y2.
• Two flip-flops represent the state variables.
• the output z is determined only by the present state of the circuit. Thus the
block diagram in Figure 8.5 shows that z is a function of only y1 and y2; our
design is of Moore type.
• We need to design a combinational circuit that uses y1 and y2 as input
signals and generates a correct output signal z for all possible valuations of
these inputs.
• The signals y1 and y2 are also fed back to the combinational circuit that
determines the next state of the FSM.
• This circuit also uses the primary input signal w. Its outputs are two signals,
Y1 and Y2, which are used to set the state of the flip-flops.
• Each active edge of the clock will cause the flip-flops to change their state
to the values of Y1 and Y2 at that time.
• Therefore, Y1 and Y2 are called the next-state variables, and y1 and y2 are
called the present-state variables.
• We need to design a combinational circuit with inputs w, y1, and y2,
such that for all valuations of these inputs the outputs Y1 and Y2 will
cause the machine to move to the next state that satisfies our
specification.
• The next step in the design process is to create a truth table that
defines this circuit, as well as the circuit that generates z.
• To produce the desired truth table, we assign a specific valuation of
variables y1 and y2 to each state.
• One possible assignment is given in Figure 8.6, where the states A, B,
and C are represented by y2y1 = 00, 01, and 10, respectively.
• The fourth valuation, y2y1 = 11, is not needed in this case.
•The type of table given in Figure 8.6 is usually called a state-assigned table.
This table can serve directly as a truth table for the output z with the inputs y1 and y2.

Although for the next-state functions Y1 and Y2 the table does not have the appearance of a normal truth table,
because there are two separate columns in the table for each value of w, it is obvious that the table includes all of
the information that defines the next-state functions in terms of valuations of inputs w, y1, and y2.
Timing Diagram
Mealy Models
• Mealy-type machines are machines in which the output values are generated
based on both the state of the circuit and the present values of its inputs.
• Output depends on present state as well as present input

• The essence of the first sequential circuit in section 8.1 is to generate an

output z = 1 whenever a second occurrence of the input w = 1 is detected in
consecutive clock cycles.
• The specification requires that the output z be equal to 1 in the clock cycle
that follows the detection of the second occurrence of w = 1.
• Suppose now that we eliminate this latter requirement and specify instead
that the output z should be equal to 1 in the same clock cycle when the
second occurrence of w = 1 is detected.
• we begin by selecting a starting state, A. As long as w = 0, the
machine should remain in state A, producing an output z = 0.
• When w = 1, the machine has to move to a new state, B, to record the
fact that an input of 1 has occurred.
• If w remains equal to 1 when the machine is in state B, which
happens if w = 1 for at least two consecutive clock cycles, the
machine should remain in state B and produce an output z = 1.
• As soon as w becomes 0, z should immediately become 0 and the
machine should move back to state A at the next active edge of the
clock.
• Thus the behavior specified in Figure 8.22 can be achieved with a two-
state machine, which has a state diagram shown in Figure 8.23.
•
• The table shows that the output z depends on the present value of input w
and not just on the present state.
• there are only two states, it is sufficient to use a single state variable, y.
• Assuming that y is realized as a D-type flip-flop, the required next-state and
output expressions are
• Y = D = w , z = wy
• The resulting circuit is presented in Figure 8.26 along with a timing diagram.
• The timing diagram corresponds to the input-output sequences in Figure
8.22
• The greater flexibility of Mealy-type FSMs often leads to simpler circuit
realizations.
• This certainly seems to be the case in our examples that produced the
circuits in Figures 8.8, 8.17, and 8.26, assuming that the design requirement
is only to detect two consecutive occurrences of input w being equal to 1.
• If we wanted to produce exactly the same output behavior using the
Mealy approach as Moore, we could modify the circuit in Figure 8.26a
by adding another flip-flop as shown in Figure 8.27.
• This flip-flop merely delays the output signal, Z, by one clock cycle
with respect to z, as indicated in the timing diagram.
• By making this change, we effectively turn the Mealy-type circuit into
a Moore-type circuit with output Z.
State Minimization
• minimization procedure is the procedure that searches for any states that are
equivalent and minimal.

• Two states Si and Sj are said to be equivalent if and only if for every
possible input sequence, the same output sequence will be produced regardless of
whether Si or Sj is the initial state.

• Instead of trying to show that some states in a given FSM are equivalent, it is
often easier to show that some states are definitely not equivalent.
• This idea can be exploited to define a simple minimization procedure
Partitioning Minimization Procedure
Partitioning Minimization Procedure
• Suppose that a state machine has a single input w.
• Then if the input signal w = 0 is applied to this machine in state Si and the
result is that the machine moves to state Su,
• we will say that Su is a 0-successor of Si .
• Similarly, if w = 1 is applied in the state Si and it causes the machine to
move to state Sv, we will say that Sv is a 1-successor of Si .
• In general, we will refer to the successors of Si as its k-successors. When
the FSM has only one input, k can be either 0 or 1.
• But if there are multiple inputs to the FSM, then k represents the set of all
possible combinations (valuations) of the inputs.
• A partition consists of one or more blocks, where each block
comprises a subset of states that may be equivalent, but the states in
a given block are definitely not equivalent to the states in other
blocks.

• The initial partition contains all states in a single block

• P1 = (ABCDEFG)
• The next partition separates the states that have different outputs
(note that this FSM is of Moore type), which means that the states A,
B, and D must be different from the states C, E, F, and G. Thus the
new partition has two blocks
• P2 = (ABD)(CEFG)
• Now we must consider all 0- and 1-successors of the states in each block.
• For the block (ABD), the 0-successors are (BDB), respectively. Since all of these
successor states are in the same block in P2, we should still assume that the
states A, B, and D may be equivalent.
• The 1-successors for these states are (CFG).
• Since these successors are also in the same block in P2, we conclude that (ABD)
should remain in one block of P3.
• Next consider the block (CEFG). Its 0-successors are (FFEF), respectively. They
are in the same block in P2. The 1-successors are (ECDG). Since these states are
not in the same block in P2,
• it means that at least one of the states in the block (CEFG) is not equivalent to
the others.
• In particular, the state F must be different from the states C, E, and G because its
1-successor is D, which is in a different block than C, E, and G. Hence
• P3 = (ABD)(CEG)(F)
• The 0-successors of (ABD) are (BDB), which are in the same block of
P3. The 1-successors are (CFG), which are not in the same block.
• Since F is in a different block than C and G, it follows that the state B
cannot be equivalent to states A and D.
• The 0- and 1-successors of (CEG) are (FFF) and (ECG), respectively.
• Both of these subsets are accommodated in the blocks of P3.
Therefore
• P4 = (AD)(B)(CEG)(F)
• If we follow the same approach to check the 0- and 1-successors of the
blocks (AD) and (CEG), we find that
• P5 = (AD)(B)(CEG)(F)
• Since P5 = P4 and no new blocks are generated, it follows that states in
each block are equivalent.
• If the states in some block were not equivalent, then their k-successors
would have to be in different blocks.
• Therefore, states A and D are equivalent, and C, E, and G are equivalent.
Since each block can be represented by a single state, only four states
are
• needed to implement the FSM defined by the state table in Figure 8.51.
• If we let the symbol A represent both the states A and D in the figure
and the symbol C represent the states C, E, and G, then the state table
reduces to the state table in Figure 8.52.
Design of Sequence Detector
• A Moore Sequence Detector:

State Register
s(t+1) z(t)
C1 C2
next s(t)
state present
x(t)
state
present
inputs
clock

32
Sequence Detector
• 101 sequence Detector

X = 0 0 1 1 0 1 1 0 0 1 0 1 0 1 0 0

Z = 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0

(time: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15)

33
Design of a Sequence Detector
S0: start
S1: got 1
S2: got 10
S3: got 101

34
Design of a Sequence Detector
S0: start
S1: got 1
S2: got 10
S3: got 101

35
Design of a Sequence Detector

State Table Transition Table with State as-

signment

DA DB
Prese Next State Present
nt Output (Z) A + B+
X=0 X=1
state AB X=0 X=1 Z

S0 S0 S1 0 00 00 01 0
S1 S2 S1 0 01 11 01 0
0 11 00 10 0
S2 S0 S3
1 10 11 01 1
S3 S2 S1

36
State Assignment
• Each of the m states must be assigned a unique
code.
• Minimum number of bits required is n such
that
n ≥ log2 m
where x is the smallest integer ≥ x.
• There are 2n - m unused states.
• (There are useful state assignments that use
more than the minimum number of bits).

38
Algorithmic State Machine (ASM) Charts
• For larger machines the designers often use a different form of
representation, called the algorithmic state machine (ASM) chart.
• An ASM chart is a type of flowchart that can be used to represent the
state transitions and generated outputs for an FSM.
• The three types of elements used in ASM charts which are shown in
next slide
• State box – A rectangle represents a state of the FSM. It is equivalent
to a node in the state diagram or a row in the state table.
• The name of the state is indicated outside the box in the top-left
corner. The Moore-type outputs are listed inside the box.
• it may be useful to indicate an action that must be taken; for example,
Count ← Count +1 specifies that the contents of a counter have to be
incremented by 1.
Decision Box
• Decision box –A diamond indicates that the stated condition expression
is to be tested and the exit path is to be chosen accordingly.
• The condition expression consists of one or more inputs to the FSM.
• For example, w indicates that the decision is based on the value of the
input w, whereas w1 ・ w2 indicates that the true path is taken if w1 =
w2 = 1
• and the false path is taken otherwise.
Condition output Box
• Conditional output box – An oval shaped, denotes the output signals
that are of Mealy type.
• These outputs depend on the values of the state variables and the
inputs of the FSM;
• we will refer to these outputs simply as Mealy outputs.
• The condition that determines whether such outputs are generated is
specified in a decision box.
•
• The transitions between state boxes depend on the decisions made
by testing the value of the input variable w.
• In each case if w = 0, the exit path from a decision box leads to state
A.
• I f w = 1, then a transition from A to B or from B to C takes place.
• If w = 1 in state C, then the FSM stays in that state.
• The chart specifies a Moore output z, which is asserted only in state C,
as indicated in the state box.
• In states A and B, the value of z is 0 (not asserted), which is implied
by leaving the corresponding state boxes blank.
• Figure 8.88 provides an example with Mealy outputs.
• This chart represents the FSM in Figure 8.23.
• The output, z, is equal to 1 when the machine is in state B and w = 1.
• This is indicated using the conditional output box.
• In all other cases the value of z is 0,
• which is implied by not specifying z as an output of state B for w = 0
and state A for w equal to 0 or 1.
• ASM charts are similar to traditional flowcharts.
• Unlike a traditional flowchart, the ASM chart includes timing
information because it implicitly specifies that the FSM changes
(flows) from one state to another only after each active clock edge.