Hacettepe University

ELE 225 Fundamentals of Digital

Systems

Chapter 5:
Synchronous Sequential Logic

Assoc. Prof. S. Esen Yüksel

1
Topics

2
 Previously on ELE 225
We learned how to
Analyze a combinational circuit from its logic
diagram.
Realize the half adder, full-adder, binary adder-

subtractor, carry lookahead adder, BCD adder, binary

multiplier, magnitude comparator.
Realize decoders, encoders, priority encoders,

multiplexers, demultiplexers and use three-state

gates.
Implement a Boolean function with a decoder and

additional gates.
Implement a Boolean function with a multiplexer.

3
 Chapter Objectives
 Know how to distinguish a sequential circuit from a
combinational circuit.
 Understand the SR latch, transparent latch, D flip-flop, JK
flip-flop, and T flip-flop.
 Know how to use the characteristic table and
characteristic equation of a flip-flop.
 Know how to derive the state equation, state table, and
state diagram of a clocked sequential circuit.
 Know the difference between Mealy and Moore machines.
 Know how to eliminate equivalent states in a state table.
 Know how to define different codes for the binary state
assignment.
 Be able to design a sequential circuit with D, JK, T flip-
flops.
4
 5-2 Sequential Circuits
Every digital system is likely to have combinational
circuits, most systems encountered in practice also
include storage elements, which require that the
system be described in term of sequential logic.

5
 Synchronous Clocked Sequential
Circuit
A sequential circuit may use many flip-flops to store
as many bits as necessary. The outputs can come
either from the combinational circuit or from the flip-
flops or both.

6
 5-3 Latches: SR Latch
The SR latch is a circuit with two cross-coupled NOR
gates or two cross-coupled NAND gates. It has two
inputs labeled S for set and R for reset.

7
SR Latch with NOR Gates

8
SR Latch with NAND Gates

9
SR Latch with NAND Gates

10
 SR Latch with Control
Input
 The operation of the basic SR latch can be modified
by providing an additional control (enable) input
that determines when the state of the latch can be
changed.
 In Fig. 5-5, it consists of the basic SR latch and two
additional NAND gates.

11
SR Latch with Control
Input

12
 D Latch
 One way to eliminate the undesirable condition of
the indeterminate state in SR latch is to ensure
that inputs S and R are never equal to 1 at the
same time in Fig 5-5.
 This is done in the D latch (transparent latch).

13
D Latch

14
 Graphic Symbols for
latches
 A latch is designated by a rectangular block with
inputs on the left and outputs on the right.
 One output designates the normal output, and the
other designates the complement output.

15
 5-4 Flip-Flops
 The state of a latch or flip-flop is switched by a
change in the control input.

This momentary change is called a trigger and the
transition it cause is said to trigger the flip-flop.
 The D latch with pulses in its control input is
essentially a flip-flop that is triggered every time
the pulse goes to the logic 1 level.
 As long as the pulse input remains in the level, any
changes in the data input will change the output
and the state of the latch.

16
 Clock Response in Latch
 The problem with the latch is that it responds to a
change in the level of a clock pulse.
 In Fig (a), a positive level response in the enable
input allows changes in the output when the D
input changes while the clock pulse stays at logic
1.

17
 Clock Response in Flip-
Flop
 The key to the proper operation of a flip-flop is to
trigger it only during a signal transition.

18
 Edge-Triggered D Flip-Flop
 The first latch is called the master and the second
the slave.
 The circuit samples the D input and changes its
output Q only at the negative-edge of the
controlling clock.

19
Edge-Triggered D Flip-Flop

20
 D-Type Positive-Edge-Triggered Flip-
Flop
 Another more
efficient
construction of an
edge-triggered D
flip-flop uses
three SR latches.

 Two latches
respond to the
external D(data)
and CLK(clock)
inputs.

 The third latch

provides the 21
Graphic Symbol for Edge-Triggered D
Flip-Flop

22
 Setup Time and Hold Time

 Setup time is the minimum time during which the data input
must be maintained at a constant value prior to the trigger
edge.
 Hold time is the minimum time during which the data input
must not change after the application of the trigger edge.
 Propagation delay time is the interval between the trigger
edge and the stabilization of the output to a new state.
 These and other parameters are specified in manufacturers’ 23
data books for specific logic families.
Example

24
 Other Flip-Flops
 VLSI circuits contain several thousands of gates
within one package.
 Circuits are constructed by interconnecting the
various gates to provide a digital system.
 Each flip-flop is constructed from an
interconnection of gates.
 The most economical and efficient flip-flop constructed in
this manner is the edge-triggered D flip-flop, because it
requires the smallest number of gates.
 Other types of flip-flops can be constructed by using the D
flip-flop and external logic.
 A characteristic table defines the logical
properties of a flip-flop by describing its operation
in tabular form.
25
 JK Flip-Flop
 Four operations can be performed with a JK flip-
flop:
 No change, reset to 0, set to 1, or complement.
 The J input sets the flip-flop to 1, the K input resets
it to 0, and when both inputs are enabled, the
output is complemented.

26
 JK Flip-Flop
 The circuit diagram of a JK flip-flop constructed
with a D flip-flop and gates is shown below.
 This can be verified by investigating the circuit
applied to the
D =DJ input:
Q’ + K’ Q

27
JK Flip-Flop

28
 T Flip-Flop
 The T(toggle) flip-flop is a complementing flip-
flop and can be obtained from a JK flip-flop when
inputs J and K are tied together.

29
 T Flip-Flop
 The T flip-flop can be constructed with a D flip-flop
and an exclusive-OR gates as shown below.
 The expression for the D input Dis:= T  Q = TQ’ +
T’Q

30
T Flip-Flop

31
 Characteristic Equations
A characteristic equation defines the logical
properties of a flip-flop by describing its operation
algebraically.
D flip-flop Characteristic Equation:
Q(t + 1) = D

JK flip-flop Characteristic Equation:

Q(t + 1) = JQ’ + K’Q

T flip-flop Characteristic Equation:

Q(t + 1) = T  Q = TQ’ + T’Q

32
 Direct Inputs
 Some flip-flops have asynchronous inputs that are
used to force the flip-flop to a particular state
independent of the clock.
 The input that sets the flip-flop to 1 is called
preset or direct [Link] input that clears the flip-
flop to 0 is called clear or direct reset.
 When power is turned on a digital system, the
state of the flip-flops is unknown.
 The direct inputs are useful for bringing all flip-
flops in the system to a known starting state prior
to the clocked operation.

33
 D Flip-Flop with Asynchronous
Reset
A positive-edge-
triggered D flip-flop with
asynchronous reset is
shown in Fig.5-14(a).

34
 5-5 Analysis of Clocked Sequential
Ccts
 The analysis of a sequential circuit consists of
obtaining a table or a diagram for the time
sequence of inputs, outputs, and internal states.
 It is also possible to write Boolean expressions that
describe the behavior of the sequential circuit.
 These expressions must include the necessary
time sequence, either directly or indirectly.

35
 State Equations
 The behavior of a clocked sequential circuit can be
described algebraically by means of state
equations.
 A state equation (transition equation)
specifies the next state as a function of the
present state and inputs.
 Consider the sequential circuit shown in Fig. 5-15.
It consists of two D flip-flops A and B, an input x
and an output y.

36
Fig.5-15 Example of Sequential
Circuit

37
 State Equation
A(t+1) = A(t) x(t) + B(t)
x(t)

B(t+1) = A’(t) x(t)

 A state equation is an algebraic expression that
specifies the condition for a flip-flop state
transition.
 The left side of the equation with (t+1) denotes
the next state of the flip-flop one clock edge later.
 The right side of the equation is Boolean
expression that specifies the present state and
input conditions that make the next state equal to
y(t) = (A(t) + B(t)) x(t)’
1.
38
 State Table
 The time sequence of inputs, outputs, and flip-flop
states can be enumerated in a state table
(sometimes called transition table).

39
 State Diagram
 The information available in a state table can be
represented graphically in the form of a state
diagram.
 In this type of diagram, a state is represented by a
circle, and the transitions between states are
indicated by directed lines connecting the circles.
1/0 : means input =1
output=0

40
 Flip-Flop Input Equations
 The part of the combinational circuit that
generates external outputs is described
algebraically by a set of Boolean functions called
output equations.
 The part of the circuit that generates the inputs to
flip-flops is described algebraically by a set of
Boolean functions called flip-flop input equations.
 The sequential circuit of Fig. 5-15 consists of two D
flip-flops A and B, an input x, and an output y. The
logic diagram of the circuit can be expressed
algebraically with two flip-flop input equations and
DA = Ax + Bx
an output equation:
DB = A’x
y = (A + B)x’
41
 Analysis with D Flip-Flop
 The circuit of Fig. 5-17(a) is described by the input
equation DA = A  x  y
 The DA symbol implies a D flip-flop with output A.
 The x and y variables are the inputs to the circuit.
 No output equations are given, so the output is implied to
come from the output of the flip-flop.

42
 Analysis with D Flip-Flop
 The binary numbers under Axy are listed from 000
through 111 as shown in Fig. 5-17(b). The next state
values are obtained from the state equation A(t+1) =
Axy
 The state diagram consists of two circles-one for each
state as shown in Fig. 5-17(c).

43
Analysis with JK Flip-Flops

44
 Analysis with JK Flip-Flops
 The circuit can be specified by the flip-flop input
JAequations
=B KA = Bx’
JB = x’ KB = A’x + Ax’ = A  x

45
 Analysis with JK Flip-Flops
 The next-state values can also be obtained by evaluating
the state equations from the characteristic equation.
A(t + 1) = JA’ + K’A
B(t + 1) = JB’ + K’B
 Substituting the values of JA and KA from the input
equations, we obtain the state equation for A:
A(t + 1) = BA’ + (Bx’)’ A = A’B + AB’ + Ax
 The state equation provides the bit values for the column
under next state of A in the state table.
 Similarly, the state equation for flip-flop B can be derived
from the characteristic equation by substituting the
values of JB and KB:
B(t + 1) = x’B’ + (A  x)’ B = B’x’ + ABx + A’Bx’ 46
 Analysis with JK Flip-Flops
 The state diagram of the sequential circuit is shown in
Fig. 5-19.

47
 Analysis with T Flip-Flops
 The sequential circuit shown
in Fig. 5-20(a) has:
TA = Bx
TB = x
y = AB
 Characteristic equation:
Q(t + 1) = T  Q = T’Q +
TQ’
 Next state equations:

A(t+1)=(Bx)’A+(Bx)A’
=AB’+Ax’+A’Bx
B(t+1)=xB
 The next-state values for A
and B in the state table are 48
Analysis with T Flip-Flops
Use present state
00/0 : means
as inputs
state is 00
output is 0

49
 Mealy and Moore Models
 The most general model of a sequential circuit has
inputs, outputs, and internal states.
 It is customary to distinguish between two models of
sequential circuits:
the Mealy model and the Moore model
 They differ in the way the output is generated.
 In the Mealy model, the output is a function of both
the present state and input.
 In the Moore model, the output is a function of the
present state only.

50
Mealy and Moore Models

51
 Mealy and Moore Models
 When dealing with the two models, some books and
other technical sources refer to a sequential circuit
as a finite state machine abbreviated FSM.
 The Mealy model of a sequential circuit is referred to
as a Mealy FSM or Mealy machine.
 The Moore model is referred to as a Moore FSM or
Moore machine.

52
 5-7 State Reduction and
Assignment
 The analysis of sequential circuits starts from a
circuit diagram and culminates in a state table or
diagram.
 The design (synthesis) of a sequential circuit
starts from a set of specifications and culminates
in a logic diagram.
 Design procedures are presented in the next
section.
 This section discusses certain properties of
sequential circuits that may be used to reduce the
number of gates and flip-flops during the design.

53
 5-7 State Reduction and
Assignment
 The reduction of the number of flip-flops in a
sequential circuit is referred to as the state-
reduction problem.
 State-reduction algorithms are concerned with
procedures for reducing the number of states in a
state table, while keeping the external input-
output requirements unchanged.
 Since m flip-flops produce 2m states, a reduction in
the number of states may result in a reduction in
the number of flip-flops.
 An unpredictable effect in reducing the number of
flip-flops is that sometimes the equivalent circuit
may require more combinational gates.
54
 State Reduction
Example :
Consider the circuit specified by
the given state diagram and the
input sequence 01010110100
starting from the initial state a.

state a a b c d e f f g f g a
input 0 1 0 1 0 1 1 0 1 0 0
output 0 0 0 0 0 1 1 0 1 0 0

55
 State Reduction
 First, we need the state table; it is more convenient to apply
procedures for state reduction using a table rather than a
diagram.
 The state table of the circuit is listed in Table 5-6 and is
obtained directly from the state diagram.

56
 State Reduction Algorithm
 Two states are said to be equivalent if, for each member of
the set of inputs, they give exactly the same output and
send the circuit either to the same state or to an equivalent
state.
 When two states are equivalent, one of them can be
removed without altering the input–output relationships.

57
 State Reduction
 Present states g and e are two such states: they both go to
states a and f and have outputs of 0 and 1 for x=0 and x=1,
respectively.
 Therefore, states g and e are equivalent and one of these
states can be removed.

58
 State Reduction
 The procedure of removing a state and replacing it by its
equivalent is demonstrated in Table 5-7.
 The row with state g is removed and state g is replaced by
state e each time it occurs in the next-state columns.

59
 State Reduction
 State f now has next states e and f and outputs 0 and 1 for
x=0 and x=1, respectively.
 The same next states and outputs appear for present state
d.
 Therefore, states f and d are equivalent and state f is
removed and replaced by d.

60
 State Reduction
 The final reduced table is shown in Table 5-8 with only five
states.
 The state diagram for the reduced table is also shown in Fig.
5-26.

61
State Assignment

62
 5-8 Design Procedure
 The procedure for designing synchronous
sequential circuits can be summarized by the
following steps:
1. From the word description and specifications of the desired
operation, derive a state diagram for the circuit.
2. Reduce the number of states if necessary.
3. Assign binary values to the states.
4. Obtain the binary-coded state table.
5. Choose the type of flip-flops to be used.
6. Derive the simplified flip-flop input equations and output
equations.
7. Draw the logic diagram.

63
 Design Procedure
Example: Design a circuit that detects a sequence of three
or more consecutive 1’s in a string of bits coming through
an input line.

64
 Synthesis Using D Flip-
Flops
 When D-type flip-flops are used, the input equations are
obtained directly from the next state.
A(t + 1) = DA(A, B, x) = ∑ (3, 5,
7)
B(t + 1) = DB(A, B, x) = ∑ (1, 5,
y(A, B, x) = ∑ (6,
7)
7)

65
Synthesis Using D Flip-
Flops

66
Synthesis Using D Flip-
Flops

67
 Synthesis Using JK Flip-
Flops
 When JK and T type flip-flops are used, the input equations
cannot be obtained directly from the next state.
 We need a table that lists the required inputs for a given
change of state. Such a table is called an excitation table.

68
 Synthesis Using JK Flip-
Flops
 Design the sequential circuit specified by
Table 5.13.
 The flip-flop inputs are derived from the state
table in conjunction with the excitation table
for the JK flip-flop.

69
Synthesis Using JK Flip-
Flops

70
Synthesis Using JK Flip-
Flops

71
 Synthesis Using T Flip-
Flops
 The synthesis using T flip-flops will be demonstrated by
designing a binary counter.
 An n-bit binary counter consists of n flip-flops that can count
in binary from 0 to 2n-1.
 The state diagram of a 3-bit counter is shown in Fig. 5-29.

72
 Synthesis Using T Flip-
Flops
 The flip-flop inputs are derived from the
state table in conjunction with the
excitation table for the T flip-flop.

73
Synthesis Using T Flip-
Flops

74
Synthesis Using T Flip-
Flops

75
 What can you do with it?
 Traffic lights (also add a timer,
ambulance reset etc.)
 A digital clock or a counter (count up,
down, reset)
 LED lights (print H A P P Y one after the
other etc.)
 A washing machine (start, wash,
prewash, dry, wait etc. states. If you
open its door, it should start from where
it left).
76
 What can you do with it?
 A vending machine (a counter for
coins. How many coins left to release a
coke?)
 An ATM machine (depending on button
pressed, watch for balance, give
money if it exists, bring the «bye»
screen … )
 A locker (watch for a sequence of
ABBAA …)
77
 Ex:
 Design a FSM that checks for a pattern
‘10’ and asserts 1 when it is detected.
Use Moore and Mealy.

S0
(0
received)

S1
(1
received)

78
79
 Moore:
S0
(0
received)

S1
(1
received)

S2
(10
received)

80
81
 Ex:
 Draw the state diagram for a ‘1011’
sequence detector using Mealy and
Moore.

82
83
1011 Moore

84