EE1001 - Digital Logic

Chapter 5
Synchronous Sequential Logic

FALL-2020
Chapter 5 Synchronous Sequential
Logic
5-1 Sequential Circuits
5-2 Latches
5-3 Flip-Flops
5-4 Analysis of Clocked Sequential Circuits
5-5 HDL for Sequential Circuits
5-6 State Reduction and Assignment
5-7 Design Procedure
Introduction
 Conclusions
 Output now depends upon inputs and outputs
 The system is able to store information and behaves
as a storage element
 The binary information stored in these elements at
any given time defines the state of the sequential
circuit at that time.
 The sequential circuit receives binary information
from external inputs that, together with the present
state of the storage elements, determine the binary
value of the outputs
 For storage elements we call output => state
 A sequential circuit is specified by a time sequence
of inputs, outputs, and internal states
 5-2 Sequential Circuits
„ Combinational circuits
z The outputs are entirely dependent on the current inputs
z Contains no storage elements, no feedback

„ Sequential circuits
z Consists of a combinational circuit to which storage elements
are connected to form a feedback path
z Outputs are a function of both the current inputs and the
present state of the storage elements
„ Storage/memory elements
z capable of storing binary information
z defining the state of the sequential circuit
z Next state is a function of external inputs and current state
‹ (inputs, current state) ⇒ (outputs, next state)
 Types of Sequential Circuits
Two major types: depending on timing of their signals
„ Asynchronous sequential circuits
z The transition happens at any instant of time
z Do not use clock pulses. Change of internal state occurs

when there is a change in input variables

‹ Instability problem: may become unstable at times
z Storage elements work as time-delay device
‹ May be regarded as a combinational circuit with feedback
„ Synchronous sequential circuits
The transition happens at discrete instants of time
z

z The circuit responds only to pulses on particular inputs

z Storage elements are affected only with the arrival of each

pulse
Synchronous is like ringing of a bell at every hour in the uni.
Anyone entering within 10 minutes of the ring is marked present
 Synchronous Clocked Sequential Circuits

„ Clocked sequential circuits (CSC)

z Synchronous sequential circuits that use clock pulses in the
inputs of storage elements
z Synchronization is achieved by a master-clock generator to

generate a periodic train of clock pulses

z most commonly used, no instability problems
z The clock signal is commonly denoted by the identifiers

clock and clk

z The clock pulses are distributed throughout the system in

such a way that storage elements are affected only with the
arrival of each pulse.
z The clock pulses determine when computational activity

will occur within the circuit, and other signals (external

inputs and otherwise) determine what changes will take
place affecting the storage elements and the outputs.
 Synchronous Clocked Sequential Circuits

„ They are called synchronous circuits because the

activity within the circuit and the resulting updating of
stored values is synchronized to the occurrence of
clock pulses.

„ Flip-flops: the storage elements used in CSC

z binary cells capable of storing one bit of information
z Maintains a binary state indefinitely until directed by an

input signal to switch states

‹ The states change only during a clock pulse transition
z major differences in the number of inputs they possess and
in the manner in which the inputs affect the binary state
„ The outputs can come either from the combinational circuit or
from the flip-flops or both
„ The flip-flops receive their inputs from the combinational
circuit and also from a clock signal with pulse that occurs at
fixed intervals of time
z The flip-flop outputs cannot change and the feedback loop is broken
when a clock pulse is not active
z the speed at which the combinational logic circuits operate is critical.
 5-3 Latches
„ metal bar with a catch/ lever used for fastening a gate.
„ Latches: basic circuits to construct flip-flops
z capable of storing binary information, impractical for use in
synchronous sequential circuits
‹ more complicated types can be built upon it
„ SR Latch
z Two states: Set and Reset states
z an asynchronous sequential circuit with two cross-coupled

NOR gates
„ S’-R’ Latch
z SR latch with two cross-coupled NAND gates
‹ 0 signal to change its state
„ SR latch with control input
z Determines when the state of the latch can be changed
„ D Latch
z eliminate undesirable condition of indeterminate state in
SR latch
 SR Latch
Two inputs labeled S for set and R for reset
(S,R)=(1,0): set (Q=1, the set state)
(S,R)=(0,1): reset (Q=0, the reset/clear state)
(S,R)=(0,0): normal condition
z no operation, in either the set or the reset state
z depending on which input was most recently at 1
(S,R)=(1,1): indeterminate state (Q=Q'=0)
z consider (S,R) = (1,1) ⇒ (0,0)
unpredictable next state when both inputs return to 0
(depend on which input returns to 0 first)
Q = [R+(S+Q)’]’ = R’(S+Q)
Q’ = [S+(R+Q’)’]’ = S’(R+Q’)

(S+Q)’

(R+Q’)’
 S’-R’ Latch – SR Latch with NAND Gates
0 signal to change its state
(S,R)=(0,1): set (Q=1, the set state)
(S,R)=(1,0): reset (Q=0, the reset/clear state)
(S,R)=(1,1): normal condition
(S,R)=(0,0): indeterminate state (Q=Q’=1)
unpredictable next state

9
 SR Latch with Control Input
An additional input as an enable signal
C=0 ⇒ quiescent condition, no change - in a state or period of
inactivity or dormancy.
C=1 ⇒ S or R is allowed to affect the SR latch
(1 signal to change its state)
S_ 1/S'

0/1

R_ 1/R'
 D Latch
„ S=D and R=D’
z Ensure S and R are never equal to 1 at the same time
z Eliminate the undesirable conditions of the indeterminate

state in the RS latch

„ One output Q and two inputs: D (data) and C (control)
Q=D when C=1 Also called transparent latch
Q = no change when C=0

S_ 1/D'

0/1

R_ 1/D

11
Graphic Symbols for Latches
 5-4 Flip-Flops
„ The storage elements (memory) used in clocked sequential circuits are
called flip flops.
„ A flip-flop is a binary storage device capable of storing one bit of
information.
„ Because of the control signal with latch:
• The state transitions of the latches start as soon as the clock pulse
changes to the logic-1 level. The new state of a latch appears at the
output while the pulse is still active.
• If the inputs applied to the latches (from feedback) change while the
clock pulse is still at the logic-1 level, the latches will respond to new
values and a new output state may occur.
„ Because of this unreliable operation, the output of a latch cannot be
applied to the input of the same or another latch when all the latches are
triggered by a common clock source.
„ Flip-flop circuits are constructed in such a way as to make them operate
properly when they are part of a sequential circuit that employs a
common clock.
 5-4 Flip-Flops
„ The key to the proper operation of a flip-flop is to trigger it only during a
signal transition
„ A trigger: the momentary change to switch the state of a latch or flip-flop
zThe transition it causes is said to trigger the flip-flop

„ Types of triggers
zLevel triggered – latches (causes unreliable operation)

‹
D latch is triggered every time the pulse on its control input stays at logic 1
‹
Be used as a temporary storage between a unit and its environment
z Edge triggered – flip-flops
‹ If level-triggered flip-flops are
used, the feedback path may
cause instability problem as
long as the clock pulse stays in
the active level triggered only
during a signal transition (0⇒1
or 1⇒0)
 Edge-triggered
D flip-flop
Store binary info during transition
„Method 1: Master-slave D flip-flop
z two separate flip-flops
a master flip-flop (positive-level triggered)
a slave flip-flop (negative-level triggered)
z change only during negative edge of clock
‹ longer propagation delay
 Edge-triggered D flip-flop (cont.)
Method 2: D-type positive-edge-triggered flip-flop
z Two latches respond to the external D (data) and Clk (clock) inputs.
z The third latch provides the outputs for the flip-flop.
 Edge-triggered D flip-flop (cont.)
z The most efficient flip-flop constructed with 3 SR latches
CLK=0 ⇒ S=R=1, no change
CLK=positive transition ↑⇒ Q=D (state changes once)
D=0 when CLK becomes 1 ⇒ R=1 to 0 ⇒ D changes further, no effect
D=1 when CLK becomes 1 ⇒ R=stay 1 ⇒ D changes further, no effect
CLK=negative transition or 1 ⇒ quiescent condition (state holds)
(RD)’
[S(RD)’]’=S’+RD
S
S=CLK’+S(RD)’
[S(RD)’]’ Q=R ⇒ Q=D

S
(RD)’
R=CLK’+S’+RD
R
(RD)’
  Consider the scenarios:
• Clk = 0 -> Output unchanged
• Clk = 1 - > D = 0 - > Q = 0
• Clk = 1 -> D = 1 -> Q = 1

 When the input clock in the positive-edge-triggered flip-flop makes a positive

transition, the value of D is transferred to Q.

 A negative transition of the clock (i.e., from 1 to 0) does not affect the output, nor
is the output affected by changes in D when Clk is in the steady logic-1 level or
the logic-0 level.

 Hence, this type of flip-flop responds to the transition from 0 to 1 and nothing else.
 (RD)’ D=0 D=1
[S(RD)’]’=S’+RD S=CLK’+S S=CLK’+SR’
S
R=CLK’+S’ R=CLK’+(SR’)’
S=CLK’+S(RD)’
[S(RD)’]’ CLK=0 CLK=1
S=R=1 S=S
D=0
S Q=Q R=S’
S=R=1 S=SR’
(RD)’ D=1
R=CLK’+S’+RD Q=Q R=(SR’)’=S’
=CLK’+[S(RD)’]’
R
(RD)’

S=0, R=1, Q=1

t 0 1 2 3 4 5 6 7 8 9 10 12 14 16 18 20 22 24 26 28 30
CLK __--__--__--__--__--__--__--__--
D _______--------________--------_

Q --________--------________-----
Setup Time and Hold Time

Setup time
„ a minimum time for which the D input must be
maintained at a constant value (or be ready)
prior to the occurrence of the clock transition
„ data to the internal latch

Hold time
„ a minimum time for which the D input must not
changes after the application of the positive
transition of the clock
„ clock to the internal latch

These parameters are usually specified in

manufacturer’s data books.
 The propagation delay time of the flip-flop is defined
as the interval between the trigger edge and17the
stabilization of the output to a new state.
 Graphic Symbols

> dynamic
indicator
 JK Flip-Flop
„ Edge-triggered D flip-flop
z Store binary information during edge trigger
z Require the smallest number of gates
z Other types of flip-flops can be constructed using it
„ JK Flip-Flop: D=JQ'+K'Q
J=0, K=0: D=Q ⇒ Q no change
J=0, K=1: D=0 ⇒ Q =0 reset to 0
J=1, K=0: D=1 ⇒ Q =1 set to 1
J=1, K=1: D=Q’ ⇒ Q =Q’ complement output
 T Flip-Flop

T (toggle) flip-flop: D = T⊕Q = TQ'+T'Q

T=0: D=Q, no change
T=1: D=Q' ⇒ Q=Q'
 Characteristic Tables and Equations
Characteristic Tables

Characteristic equations
D flip-flop Q(t+1) = D
JK flip-flop Q(t+1) = JQ’+K’Q
T flop-flop Q(t+1) = T⊕Q = TQ’ + T’Q
 Direct Inputs
„ preset/direct set: the inputs that sets the flip-flop to 1
„ clear/direct reset: the inputs that clears the flip-flop to 0
z to a known starting state
„ asynchronous reset
reset=0 ⇒ force Q=0, resetting
 5-5 Analysis of Clocked Sequential Circuits
„ Methods of describing sequential circuit operation:
o A table or a diagram for the time sequence of inputs,
outputs, and internal states.
o State equation - a Boolean expression describing behavior
of the circuit
 5-5 Analysis of Clocked Sequential Circuits
„ State equation (transition equation)
„ Specifies the next state as a function of the present state
and inputs.
„ Consider the sequential circuit
A(t+1) = A(t)x(t) + B(t)x(t)
B(t+1) = A’(t)x(t)
y(t)=[A(t)+B(t)]x’(t)
or
A(t+1)=Ax+Bx
B(t+1)=A’x
y=(A+B)x’

CSC diagram ⇒ state equation

 State Table or Transition Table
state table ⇐ state equation ⇐ CSC diagram
„ Four sections: present state, input, next state and output

„ List all possible binary combinations of present state and inputs

„ Determine next states and outputs from the logic diagram or

from the state equations

A(t+1)=Ax+Bx
B(t+1)=A’x
y=(A+B)x’

m flip-flops and n inputs

• 2m+n rows
• m column of next-state
 Second Form of State Table

„ Only 3 sections: present state, next state, and output

z Given one input, there are two possible next states and
outputs for each present state
„ What form to be used depends on applications
State Diagram - pictorial view of state transitions

input/output
x/y

state diagram
A(t+1)=Ax+Bx ⇔ state table
B(t+1)=A’x ⇔ state equation
y=(A+B)x’ ⇔ logic diagram
 Input/Output Equations
„ logic diagram of a sequential circuit consists of flip-flops + gates
z output equations: the circuit that generates external outputs
z input equations: the circuit that generates inputs to flip-flops
output equations
input
equations state
characteristic
(or excitation equations) equations equations

Symbol convention: DQ = x + y x
y
an OR gate with inputs x and y
connected to the D input of a
flip-flop whose output is
labeled with the symbol Q
Flip-Flop Input Equations

FF Input
State Equations Equations
A(t+1)=Ax+Bx DA=Ax+Bx
B(t+1)=A’x ⇒ DB=A’x
Output Equation
y=(A+B)x’ y=(A+B)x’

D/JK/T FF input equation

⇔ state equation
⇔ CSC logic diagram
⇔ state diagram
⇔ state table
 Analysis with D Flip-Flops
Given: Find:
input function: DA=A⊕x⊕y ⇔ logic diagram
state equation: A(t+1)=A⊕x⊕y ⇔ state table
one flip-flop and 2 inputs ⇔ state diagram
 Analysis with JK Flip-Flops
The next-state values of
a sequential circuit that
uses JK - or T -type flip-
flops can be derived as
follows:
1. Determine the flip-flop
input equations in terms
of the present state and
input variables.
2. List the binary values
of each input equation.
3. Use the
corresponding flip-flop
characteristic table to
determine the next-state
values in the state table.
 Analysis with JK Flip-Flops
(1) Flip-flop input equations

(2) State equations

(3)

(4)

30
 Analysis with T Flip-Flops
Characteristic equation: Q(t+1)=T⊕Q=T’Q+TQ’
Input equations and output equation:
TA=Bx; TB=x; y=AB
State equations
A(t+1)=(Bx)’A+(Bx)A’=AB’+Ax’+A’Bx
B(t+1)=x⊕B

Given logic
circuit, find
the others
31
 Mealy and Moore Models
Mealy model
„ The output is a function of both the present state and input
— The outputs may change if the inputs change during the clock cycle
— The outputs may have momentary false values due to delay
— To synchronize, the outputs must be sampled only during the clock edge
„ Mealy finite state machine (FSM, machine): the Mealy model of
a sequential circuit
„ example: Fig. 5-15 (D)

Moore model
„ The output is a function of the present state only
— The outputs are synchronized with the clock
„ Moore finite state machine (FSM, machine): the Moore model
of a sequential circuit
„ example: Figure 5-19 (JK), 5-20 (T)
 5-7 State Reduction and Assignment
„ Sequential circuit analysis:
z starts from a circuit diagram and
z culminates in a state table or state diagram

„ Sequential circuit design:

z starts from a set of specifications and
z culminates in a logic diagram

„ State reduction problem: reduction of the number of

flip-flops in a sequential circuit, while keeping the
external input-output requirements unchanged
z m flip-flops produce 2m states
z State reduction ⇒ fewer flip-flops

‹ but may require more combinational gates

 State Reduction
„ Example: Figure 5-22 (7 states)
z Given a state table or state diagram
z Find ways of reducing the number of states

without altering the input-output relationships

„ Test sequence
•Initial state: a
•Input sequence: 01010110100
 State Equivalence
State equivalence: Two states are 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

Algorithm:
1.Look for two present states that
„ go to the same next state and
„ have the same output for both input combinations

2.Remove one of the equivalent state and replace by

the other state each time it occurs in the table

Another approach: systematic reduction with an implication table

(see Section 9-5)
State Reduction Example
 State Assignment
„ State assignment: assign coded binary values to the state
z In order to design a sequential circuit with physical components
z A circuit with m states need n bits where 2n >= m
„ Transition table: a state table with a binary assignment
z To distinguish it from a stable table with symbolic names for states
 5-7 Design Procedure
„ Design of a clocked sequential circuit
z starts from a set of specifications
z obtains a state table/diagram (or equivalences) first
z culminates in a logic diagram (or a list of Boolean functions)

„ Tasks
z Choosing the flip-flops
‹ Determined from the number of states needed
z Finding a combinational gate structure
‹ Derived from the state table by evaluating the flip-flop input
equations and output equations
„ Summarized procedure
most challenging
Synthesis
 Example: Sequence Detector
Specification: Design a circuit that detects three or more
consecutive 1’s in a string of bits combining through an input line

1st Step – deriving state diagram or state table

Moore model circuit –output is 1 when circuit is in state S3 and 0 otherwise

 Synthesis Using D Flip-Flops
„ Step 2-4: Assign binary codes and list state table (Table 5-11)
„ Step 5:Choose type of flip-flops
„ Step 6:Derive simplified input and output equations

0
1
2
3
4
5
6
7
 Synthesis Using D Flip-Flops (cont.)
„ Step 7 – Draw the logic diagram (using simplified functions)

Excitation table: a
table that lists
required inputs
 Excitation Tables
„ The input equations for the circuit using flip-flops other than the D
type, i.e. JK and T types, must be derived indirectly from the state
table
„ The manual synthesis procedure for sequential circuits with JK
flipflops is the same as with D flip-flops, except that the input
equations must be evaluated from the present state to the next-
state transition ~derived from the excitation table.
„ Excitation table: list the required inputs for a given change of state
 Synthesis Using JK Flip-Flops
„ The input equations must be evaluated
from the present-state to next-state
transition derived from the excitation table
(1)

(2)
Logic Diagram for Sequential Circuit with JK Flip-Flops

(3)

JA=Bx’ KA=Bx JB=x KB=(A⊕ x)’

 Synthesis Using T Flip-Flops
Example: 3-bit counter (1)
(0)

(2)
 Logic Diagram of 3-Bit Binary Counter

(3)

TA2=A1A0 TA1=A0 TA0=1

 Summary
Chapter 5 Synchronous Sequential Logic
5-2 Sequential Circuits
5-3 Latches
— SR latch, S’R’ latch, D latch
5-4 Flip-Flops
— edge-triggered D, JK, T flip-flops
5-5 Analysis of Clocked Sequential Circuits
5-6 HDL for Sequential Circuits
5-7 State Reduction and Assignment
5-8 Design Procedure
circuit diagram⇔input equation⇔state equation⇔state table⇔state diagram