Logic and Computer Design Fundamentals
Chapter 5 – Sequential
Circuits
– Storage
Part 1Part 1 - Storage Elements
Elements and Sequential
Circuit Analysis
Charles Kime & Thomas Kaminski
© 2008 Pearson Education, Inc.
(Hyperlinks are active in View Show mode)
Overview
Part 1 - Storage Elements
• Introduction to sequential circuits
• Types of sequential circuits
• Storage elements
Latches
Flip-flops
Part 2 - Sequential Circuit Analysis
Part 3 - Sequential Circuit Design
Part 4 – State Machine Design
Chapter 5 - Part 1 2
Introduction to Sequential Circuits
Inputs Outputs
Combina-
A Sequential tional
circuit contains: Storage
Logic
Elements
• Storage elements:
Latches or Flip-Flops Next
State State
• Combinational Logic:
Implements a multiple-output
switching function
Inputs are signals from the outside.
Outputs are signals to the outside.
Other inputs, State or Present State, are
signals from storage elements.
The remaining outputs, Next State are
inputs to storage elements.
Chapter 5 - Part 1 3
Introduction to Sequential Circuits
Inputs Outputs
Combina-
tional
Storage
Logic
Elements
Combinatorial Logic Next
• Next state function State State
Next State = f(Inputs, State)
• Output function (Mealy)
Outputs = g(Inputs, State)
• Output function (Moore)
Outputs = h(State)
Output function type depends on specification and affects
the design significantly
Chapter 5 - Part 1 4
Types of Sequential Circuits
Depends on the times at which:
• storage elements observe their inputs, and
• storage elements change their state
Synchronous
• Behavior defined from knowledge of its signals at discrete
instances of time
• Storage elements observe inputs and can change state only in
relation to a timing signal (clock pulses from a clock)
Asynchronous
• Behavior defined from knowledge of inputs an any instant of
time and the order in continuous time in which inputs change
• Nevertheless, the synchronous abstraction makes complex
designs tractable!
Chapter 5 - Part 1 5
Basic (NAND) S – R Latch
“Cross-Coupling” S (set)
Q
two NAND gates gives
the S -R Latch:
Which has the time R (reset) Q
sequence behavior:
Time R S Q Q Comment
1 1 ? ? Stored state unknown
1 0 1 0 “Set” Q to 1
1 1 1 0 Now Q “remembers” 1
S = 0, R = 0 is 0 1 0 1 “Reset” Q to 0
forbidden as 1 1 0 1 Now Q “remembers” 0
input pattern 0 0 1 1 Both go high
1 1 ? ? Unstable!
Chapter 5 - Part 1 6
Basic (NOR) S – R Latch
Cross-coupling two R (reset)
Q
NOR gates gives the
S – R Latch:
Which has the time S (set) Q
sequence
Time R S Q Q Comment
behavior: 0 0 ? ? Stored state unknown
0 1 1 0 “Set” Q to 1
0 0 1 0 Now Q “remembers” 1
1 0 0 1 “Reset” Q to 0
0 0 0 1 Now Q “remembers” 0
1 1 0 0 Both go low
0 0 ? ? Unstable!
Chapter 5 - Part 1 7
Clocked S - R Latch
Adding two NAND S
gates to the basic Q
S - R NAND latch C
gives the clocked
S – R latch: Q
R
Has a time sequence behavior similar to the basic S-R
latch except that the S and R inputs are only observed
when the line C is high.
C means “control” or “clock”.
Chapter 5 - Part 1 8
Clocked S - R Latch (continued)
The Clocked S-R Latch can be described by a table:
S
Q(t) S R Q(t+1) Comment
Q 0 0 0 0 No change
C 0 0 1 0 Clear Q
Q
0 1 0 1 Set Q
R 0 1 1 ??? Indeterminate
1 0 0 1 No change
The table describes 1 0 1 0 Clear Q
what happens after the 1 1 0 1 Set Q
clock [at time (t+1)] 1 1 1 ??? Indeterminate
based on:
• current inputs (S,R) and
• current state Q(t).
Chapter 5 - Part 1 9
Clocked S - R Latch – Example 1
CLOCK
Chapter 5 - Part 1 10
Clocked S - R Latch – Example 1
CLOCK
0 1 1
0 0 0 0 00
S
1 1
0 0 0 0 0 0 0
R
Chapter 5 - Part 1 11
Clocked S - R Latch – Example 2
CLOCK
Chapter 5 - Part 1 12
Clocked S - R Latch – Example 2
CLOCK
0 1 1
0 0 0 0 0 00
S
1 1 1
0 0 0 0 0 0 0
R
Chapter 5 - Part 1 13
D Latch
Adding an inverter D
to the S-R Latch, Q
gives the D Latch: C
Note that there are Q
no “indeterminate”
states! The graphic symbol for a
Q D Q(t+1) Comment D Latch is:
0 0 0 No change D Q
0 1 1 Set Q
1 0 0 Clear Q
C Q
1 1 1 No Change
Chapter 5 - Part 1 14
D Latch – Example 1
CLOCK
Chapter 5 - Part 1 15
D Latch – Example 1
CLOCK
1 1 1 1 1
D 0 0 0 0 0
Chapter 5 - Part 1 16
D Latch – Example 2
CLOCK
Chapter 5 - Part 1 17
D Latch – Example 2
CLOCK
1 1 1 1 1 1
D 0 0 0 0 0 0 0
Chapter 5 - Part 1 18
Flip-Flops
The latch timing problem
Master-slave flip-flop
Edge-triggered flip-flop
Standard symbols for storage elements
Direct inputs to flip-flops
Chapter 5 - Part 1 19
The Latch Timing Problem
In a sequential circuit, paths may exist through
combinational logic:
• From one storage element to another
• From a storage element back to the same storage
element
The combinational logic between a latch output
and a latch input may be as simple as an
interconnect
For a clocked D-latch, the output Q depends on
the input D whenever the clock input C has
value 1
Chapter 5 - Part 1 20
The Latch Timing Problem (continued)
Consider the following circuit:
D Q Y
Clock C Q
Suppose that initially Y = 0.
Clock
Y
As long as C = 1, the value of Y continues to change!
The changes are based on the delay present on the loop
through the connection from Y back to Y.
This behavior is clearly unacceptable.
Desired behavior: Y changes only once per clock pulse
Chapter 5 - Part 1 21
The Latch Timing Problem (continued)
A solution to the latch timing problem is
to break the closed path from Y to Y
within the storage element
The commonly-used, path-breaking
solutions replace the clocked D-latch
with:
• a master-slave flip-flop
• an edge-triggered flip-flop
Chapter 5 - Part 1 22
S-R Master-Slave Flip-Flop
Consists of two clocked S S S
Q Q Q
S-R latches in series C C C
with the clock on the R R Q R Q Q
second latch inverted
The input is observed
by the first latch with C = 1
The output is changed by the second latch with C = 0
The path from input to output is broken by the
difference in clocking values (C = 1 and C = 0).
The behavior demonstrated by the example with D
driven by Y given previously is prevented since the
clock must change from 1 to 0 before a change in Y
based on D can occur.
Chapter 5 - Part 1 23
S-R Master-Slave Flip-Flop – Example 1
CLOCK
Q1
Q2
Chapter 5 - Part 1 24
S-R Master-Slave Flip-Flop – Example 1
M M M M
CLOCK S S S S
1 1
0 0 0 0 0 00
S
1 1
R 0 0 0 0 0 0 0
Q1
Q2
Chapter 5 - Part 1 25
S-R Master-Slave Flip-Flop – Example 2
CLOCK
Q1
Q2
Chapter 5 - Part 1 26
S-R Master-Slave Flip-Flop – Example 2
M M M M
CLOCK S S S S
1 1 1
0 0 0 0 0 0 00
S
1 1
R 0 0 0 0 0 0 0 0 0
Q1
Q2
Chapter 5 - Part 1 27
Flip-Flop Solution
Use edge-triggering instead of master-slave
An edge-triggered flip-flop ignores the pulse
while it is at a constant level and triggers only
during a transition of the clock signal
Edge-triggered flip-flops can be built directly at
the electronic circuit level, or
A master-slave D flip-flop which also exhibits
edge-triggered behavior can be used.
Chapter 5 - Part 1 28
Edge-Triggered D Flip-Flop
The edge-triggered D D S
Q Q Q
D flip-flop is the
C
same as the master- C C Q R Q Q
slave D flip-flop
It can be formed by:
• Replacing the first clocked S-R latch with a clocked D latch or
• Adding a D input and inverter to a master-slave S-R flip-flop
The delay of the S-R master-slave flip-flop can be
avoided since the 1s-catching behavior is not present
with D replacing S and R inputs
The change of the D flip-flop output is associated with
the negative edge (falling edge) at the end of the pulse
It is called a negative-edge triggered flip-flop
Chapter 5 - Part 1 29
Edge-Triggered D Flip-Flop – Example 1
CLOCK
Chapter 5 - Part 1 30
Edge-Triggered D Flip-Flop – Example 1
M M M M
CLOCK S S S S
1 1 1 1 1
D 0 0 0 0 0
Chapter 5 - Part 1 31
Edge-Triggered D Flip-Flop – Example 2
CLOCK
Chapter 5 - Part 1 32
Edge-Triggered D Flip-Flop – Example 2
M M M M
CLOCK S S S S
1 1 1 1 1 1
D 0 0 0 0 0 0 0
Chapter 5 - Part 1 33
Positive-Edge Triggered D Flip-Flop
Formed by D D Q S Q
Q
adding inverter C
to clock input C C Q R Q Q
Q changes to the value on D applied at the
positive clock (rising edge) edge within timing
constraints to be specified
Our choice as the standard flip-flop for most
sequential circuits
Chapter 5 - Part 1 34
Positive-Edge Triggered D Flip-Flop –
Example 1
CLOCK
Chapter 5 - Part 1 35
Positive-Edge Triggered D Flip-Flop –
Example 1
S S S S
CLOCK M M M M
1 1 1 1 1
D 0 0 0 0 0
Chapter 5 - Part 1 36
Standard Symbols for Storage
Elements
S S D D
R R C C
SR SR D with 1 Control D with 0 Control
Master-Slave:
(a) Latches
Postponed output S S D D
indicators C C
R R C C
Triggered SR Triggered SR Triggered D Triggered D
Edge-Triggered: (b) Master-Slave Flip-Flops
Dynamic D D
indicator
C C
Triggered D Triggered D
(c) Edge-Triggered Flip-Flops
Chapter 5 - Part 1 37
Direct Inputs
At power up or at reset, all or part
of a sequential circuit usually is S
initialized to a known state before D Q
it begins operation
This initialization is often done C Q
R
outside of the clocked behavior
of the circuit, i.e., asynchronously.
Direct R and/or S inputs that control the state of the
latches within the flip-flops are used for this
initialization.
For the example flip-flop shown
• 0 applied to R resets the flip-flop to the 0 state
• 0 applied to S sets the flip-flop to the 1 state
Chapter 5 - Part 1 38
Other Flip-Flop Types
J-K and T flip-flops
• Behavior
• Implementation
Basic descriptors for understanding and
using different flip-flop types
• Characteristic tables
• Characteristic equations
• Excitation tables
For actual use, see Reading Supplement - Design
and Analysis Using J-K and T Flip-Flops
Chapter 5 - Part 1 39
J-K Flip-flop
Behavior
• Same as S-R flip-flop with J analogous to S and K
analogous to R
• Except that J = K = 1 is allowed, and
• For J = K = 1, the flip-flop changes to the opposite
state
• As a master-slave, has same “1s catching” behavior
as S-R flip-flop
• If the master changes to the wrong state, that state
will be passed to the slave
E.g., if master falsely set by J = 1, K = 1 cannot reset it
during the current clock cycle
Chapter 5 - Part 1 40
J-K Flip-flop (continued)
Small Glitch
The small glitch in J
propagates through the flip-
flop even though it is small.
This is due to the fact that the
JK has the 1’s catching
problem.
Chapter 5 - Part 1 41
J-K Flip-flop (continued)
Implementation Symbol
• To avoid 1s catching
behavior, one solution
used is to use an J
edge-triggered D as
the core of the flip-flop C
K
J D
K
C
Chapter 5 - Part 1 42
J-K Flip-flop (continued)
K
J ?
D
1
K C
J 1 1 1
J K Q Q(t+1) Q
0 0 0 0
D = J Q’ + K’Q
0 0 1 1
0 1 0 0
0 1 1 0
1 0 0 1 J D
1 0 1 1
K
1 1 0 1 C
1 1 1 0
Chapter 5 - Part 1 43
T Flip-flop
Behavior
• Has a single input T
For T = 0, no change to state
For T = 1, changes to opposite state
Same as a J-K flip-flop with J = K = T
As a master-slave, has same “1s catching”
behavior as J-K flip-flop
Cannot be initialized to a known state using the
T input
• Reset (asynchronous or synchronous) essential
Chapter 5 - Part 1 44
T Flip-flop (continued)
Implementation Symbol
• To avoid 1s catching
behavior, one solution
used is to use an T
edge-triggered D as
the core of the flip-flop
C
D
T
C
Chapter 5 - Part 1 45
T Flip-flop (continued)
T ?
D
1
C
T 1
Q
T Q Q(t+1)
D=TQ
0 0 0
0 1 1
1 0 1
1 1 0 T D
C
Chapter 5 - Part 1 46
Basic Flip-Flop Descriptors
Used in analysis
• Characteristic table - defines the next state of
the flip-flop in terms of flip-flop inputs and
current state
• Characteristic equation - defines the next
state of the flip-flop as a Boolean function of
the flip-flop inputs and the current state
Used in design
• Excitation table - defines the flip-flop input
variable values as function of the current
state and next state
Chapter 5 - Part 1 47
D Flip-Flop Descriptors
Characteristic Table
D Q(t + 1) Operation
0 0 Reset
1 1 Set
Characteristic Equation
Q(t+1) = D
Excitation Table
Q(t +1) D Operation
0 0 Reset
1 1 Set
Chapter 5 - Part 1 48
T Flip-Flop Descriptors
Characteristic Table
T Q(t +1) Operation
0 Q(t) No change
1 Q(t) Complement
Characteristic Equation
Q(t+1) = T Q
Excitation Table
Q(t +1) T Operation
Q(t) 0 No change
Q(t) 1 Complement
Chapter 5 - Part 1 49
S-R Flip-Flop Descriptors
Characteristic Table
S R Q(t +1) Operation
0 0 Q(t) No change
0 1 0 Reset
1 0 1 Set
1 1 ? Undefined
Characteristic Equation
Q(t+1) = S + R Q, S.R = 0
Excitation Table
Q(t) Q(t+ 1) S R Operation
0 0 0 X No change
0 1 1 0 Set
1 0 0 1 Reset
1 1 X 0 No change
Chapter 5 - Part 1 50
S-R Flip-flop
R
S ?
D
1 -
R C SR=0
S 1 1 - 1
S R Q Q(t+1) Q
0 0 0 0
0 0 1 1 D = S + R’Q , SR = 0
0 1 0 0
0 1 1 0
1 0 0 1
1 0 1 1
1 1 0 X
1 1 1 X
Chapter 5 - Part 1 51
J-K Flip-Flop Descriptors
Characteristic Table
J K Q(t+1) Operation
0 0 Q(t) No change
0 1 0 Reset
1 0 1 Set
1 1 Q(t) Complement
Characteristic Equation
Q(t+1) = J Q + K Q
Excitation Table
Q(t) Q(t +1) J K Operation
0 0 0 X No change
0 1 1 X Set
1 0 X 1 Reset
1 1 X 0 No Change
Chapter 5 - Part 1 52
Example 1: Flip-flop Behavior
Use the characteristic tables to find the output waveforms
for the flip-flops shown:
Clock
D,T
D QD
C
T QT
Chapter 5 - Part 1 53
Example 1: Flip-Flop Behavior (continued)
Use the characteristic tables to find the output waveforms
for the flip-flops shown:
Clock
S,J
R,K
S QSR ?
C
R
J QJK
C
K
Chapter 5 - Part 1 54
Terms of Use
All (or portions) of this material © 2008 by Pearson
Education, Inc.
Permission is given to incorporate this material or
adaptations thereof into classroom presentations and
handouts to instructors in courses adopting the latest
edition of Logic and Computer Design Fundamentals as
the course textbook.
These materials or adaptations thereof are not to be
sold or otherwise offered for consideration.
This Terms of Use slide or page is to be included within
the original materials or any adaptations thereof.
Chapter 5 - Part 1 55