Synchronous Sequential Logic

Chapter 5
 Chapter Objectives
 Know how to distinguish a sequential circuit from a
combinational circuit.
 Understand the functionality of a 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, statetable, and
state diagram of a clocked sequential circuit.
 Know the difference between Mealy and Moore finite
state machines.
 Given the state diagram of a finite state machine, be
able to write a HDL model of the machine.

Synchronous Sequential Logic 2

 Chapter Objectives
 Understand the HDL models of latches and flip-flops.
 Know how to write synthesizable HDL models of clocked
sequential circuits.
 Know how to design a state machine using manual
methods.
 Know how to eliminate equivalent states in a state table.
 Know how to define a one-hot state assignment code.
 Be able to design a sequential circuit with (a) D flip-flops,
(b) JK flip-flops, and (c) T flip-flops.

Synchronous Sequential Logic 3

 5.1 Introduction
 Combinational circuits
 contains no memory elements
 the outputs depends on the inputs

Synchronous Sequential Logic 5-4

 5.2 Sequential Circuits
 Sequential circuits

 a feedback path
 the state of the sequential circuit
 (inputs, current state) ⇒ (outputs, next state)
 synchronous: the transition happens at discrete
instants of time
 asynchronous: at any instant of time
Synchronous Sequential Logic 5-5
 Synchronous sequential circuits
 a master-clock generator to generate a periodic
train of clock pulses
 the clock pulses are distributed throughout the
system
 clocked sequential circuits
 most commonly used
 no instability problems
 the memory elements: flip-flops
 binary cells capable of storing one bit of information
 two outputs: one for the normal value and one for the
complement value
 maintain a binary state indefinitely until directed by an
input signal to switch states

Synchronous Sequential Logic 5-6

Synchronous Sequential Logic 5-7
5.3 Latches
 Basic flip-flop circuit
 two NOR gates

 more complicated types can be built upon it

 directed-coupled RS flip-flop: the cross-coupled connection
 an asynchronous sequential circuit
 (S,R)= (0,0): no operation
(S,R)=(0,1): reset (Q=0, the clear state)
(S,R)=(1,0): set (Q=1, the set state)
(S,R)=(1,1): indeterminate state (Q=Q'=0)
 consider (S,R) = (1,1) ⇒ (0,0) Synchronous Sequential Logic 5-8
 SR latch with NAND gates

Synchronous Sequential Logic 5-9

 SR latch with control input
 C=0, no change
 C=1,

Synchronous Sequential Logic 5-10

 D Latch (Transparent Latch)
 eliminate the undesirable conditions of the
indeterminate state in the RS flip-flop
 D: data
 gated D-latch
 D ⇒ Q when C=1; no change when C=0

Synchronous Sequential Logic 5-11

Graphic symbols

Synchronous Sequential Logic 5-12

5.4 Storage Element: Flip-Flops
 A trigger
 The state of a latch or flip-flop is switched by a
change of the control input
 Level triggered – latches
 Edge triggered – flip-flops

Synchronous Sequential Logic 5-13

 If level-triggered flip-flops are used
 the feedback path may cause instability problem
 Edge-triggered flip-flops
 the state transition happens only at the edge
 eliminate the multiple-transition problem

Synchronous Sequential Logic 5-14

Edge-triggered D flip-flop
 Master-slave D flip-flop
 two separate flip-flops
 a master flip-flop (positive-level triggered)
 a slave flip-flop (negative-level triggered)

Synchronous Sequential Logic 5-15

 Edge-triggered flip-flops
 the state changes during a clock-pulse transition
 A D-type positive-edge-triggered flip-flop

Synchronous Sequential Logic 5-16

 three basic flip-flops
 (S,R) = (0,1): Q = 1
 (S,R) = (1,0): Q = 0
 (S,R) = (1,1): no operation
 (S,R) = (0,0): should be avoided

Synchronous Sequential Logic 5-17

 The setup time
 D input must be maintained at a constant value prior to the
application of the positive CP pulse
 = the propagation delay through gates 4 and 1
 data to the internal latches
 The hold time
 D input must not changes after the application of the positive
CP pulse
 = the propagation delay of gate 3
 clock to the internal latch

Synchronous Sequential Logic 5-18

Graphic symbols
 The edge-triggered D flip-flops
 The most economical and efficient
 Positive-edge and negative-edge

Synchronous Sequential Logic 5-19

Other Flip-Flops
 JK flip-flop

 D=JQ'+K'Q
 J=0, K=0: D=Q, no change
 J=0, K=1: D=0 ⇒ Q =0
 J=1, K=0: D=1 ⇒ Q =1
 J=1, K=1: D=Q' ⇒ Q =Q'
Synchronous Sequential Logic 5-20
 T flip-flop

 D = T⊕Q = TQ'+T'Q
 T=0: D=Q, no change
 T=1: D=Q' ⇒ Q=Q'

Synchronous Sequential Logic 5-21

 Characteristic Tables

Synchronous Sequential Logic 5-22

 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

Synchronous Sequential Logic 5-23

Direct inputs
 asynchronous set and/or asynchronous reset

Synchronous Sequential Logic 5-24

Synchronous Sequential Logic 5-25
 5.5 Analysis of Clocked Sequential Ckts
 A sequential circuit
 (inputs, current state) ⇒ (output, next state)
 a state transition table or state transition diagram

Synchronous Sequential Logic 5-26

State equations
 A(t+1) = A(t)x(t) + B(t)x(t)
 B(t+1) = A'(t)x(t)
 A more compact form
 A(t+1) = Ax + Bx
 B(t+1) = Ax
 The output equation
 y(t) = (A(t)+B(t))x'(t)
 y = (A+B)x'

Synchronous Sequential Logic 5-27

State table
 State transition table
 = state equations

Synchronous Sequential Logic 5-28

State equation

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

Synchronous Sequential Logic 5-29

State diagram
 State transition diagram
 a circle: a state
 a directed lines connecting the circles: the
transition between the states
 Each directed line is labeled 'inputs/outputs‘

 a logic diagram ⇔ a state table ⇔ a state diagram

Synchronous Sequential Logic 5-30
Flip-flop input equations
 The part of circuit that generates the inputs to
flip-flops
 Also called excitation functions
 DQ = x + y
 DA = Ax +Bx
 DB = A'x
 The output equations
 to fully describe the sequential circuit
 y = (A+B)x'

Synchronous Sequential Logic 5-31

Analysis with D flip-flops
 The input equation
 DA=A⊕x⊕y
 The state equation
 A(t+1)=A⊕x⊕y

Synchronous Sequential Logic 5-32

Analysis with JK flip-flops
 Determine the flip-flop input function in terms of
the present state and input variables
 Used the corresponding flip-flop characteristic
table to determine the next state

Synchronous Sequential Logic 5-33

 JA = B, KA= Bx'
 JB = x', KB = A'x + Ax‘
 derive the state table

 Or, derive the state equations using characteristic eq.

Synchronous Sequential Logic 5-34
  State transition diagram

A(t + 1) = JA′ + K ′A
B(t + 1) = JB′ + K ′B

State equation for A and B:

A(t + 1) = BA′ + ( Bx′)′ A= A′B + AB′ + Ax

B(t + 1) = x′B + ( A ⊕ x )′B = B′x + ABx + A′Bx′

Synchronous Sequential Logic 5-35

Analysis with T flip-flops
 The characteristic equation
 Q(t+1)= T⊕Q = TQ'+T'Q

Synchronous Sequential Logic 5-36

 The input and output functions
 TA=Bx
 TB= x
 y = AB
 The state equations
 A(t+1) = (Bx)'A+(Bx)A' =AB'+Ax'+A'Bx
 B(t+1) = x⊕B

Synchronous Sequential Logic 5-37

State Table

Synchronous Sequential Logic 5-38

Mealy and Moore models
 the Mealy model: the outputs are functions of
both the present state and inputs (Fig. 5-15)
 the outputs may change if the inputs change
during the clock pulse period
 the outputs may have momentary false values unless the
inputs are synchronized with the clocks
 The Moore model: the outputs are functions
of the present state only (Fig. 5-20)
 The outputs are synchronous with the clocks

Synchronous Sequential Logic 5-39

Synchronous Sequential Logic 5-40
 5.6 Synthesizable HDL Models of Sequential
Circuits
 Behavioral Modeling
Example: Two ways to provide free-running clock

Example: Another way to describe free-running clock

Synchronous Sequential Logic 5-41

 Behavioral Modeling
♣ always statement

Examples:

Two procedural blocking assignments: Two nonblocking assignments:

Synchronous Sequential Logic 5-42

Mealy_Zero_Detector

Synchronous Sequential Logic 5-43

Simulation Output of HDL Example 5-6

Synchronous Sequential Logic 5-44

Simulation Output of HDL Example 5-7

Synchronous Sequential Logic 5-45

 5.7 State Reduction and Assignment
 State Reduction
 reductions on the number
of flip-flops and the
number of gates
 a reduction in the number
of states may result in a
reduction in the number
of flip-flops
 a example state diagram

Synchronous Sequential Logic 5-46

 only the input-output sequences
are important
 two circuits are equivalent
 have identical outputs for all input
sequences
 the number of states is not important

Synchronous Sequential Logic 5-47

 Equivalent states
 two states are said to be equivalent
 for each member of the set of inputs, they give exactly
the same output and send the circuit to the same state or
to an equivalent state
 one of them can be removed

Synchronous Sequential Logic 5-48

 Reducing the state table
 e=f
 d=?

Synchronous Sequential Logic 5-49

 the reduced finite state machine

Synchronous Sequential Logic 5-50

 the checking of each pair of states for possible
equivalence can be done systematically
 the unused states are treated as don't-care
condition ⇒ fewer combinational gates

Synchronous Sequential Logic 5-51

State assignment
 to minimize the cost of the combinational circuits
 three possible binary state assignments

Synchronous Sequential Logic 5-52

 any binary number assignment is satisfactory as
long as each state is assigned a unique number
 use binary assignment 1

Synchronous Sequential Logic 5-53

5.8 Design Procedure
 the word description of the circuit behavior (a state
diagram)
 state reduction if necessary
 assign binary values to the states
 obtain the binary-coded state table
 choose the type of flip-flops
 derive the simplified flip-flop input equations and
output equations
 draw the logic diagram

Synchronous Sequential Logic 5-54

Synthesis using D flip-flops
 An example state diagram and state table

Synchronous Sequential Logic 5-55

 The flip-flop input equations
 A(t+1) = DA(A,B,x) = Σ(3,5,7)
 B(t+1) = DB(A,B,x) = Σ(1,5,7)
 The output equation
 y(A,B,x) = Σ(6,7)
 Logic minimization using the K map
 DA= Ax + Bx
 DB= Ax + B'x
 y = AB

Synchronous Sequential Logic 5-56

Synchronous Sequential Logic 5-57
Sequence detector
 The logic diagram

Synchronous Sequential Logic 5-58

Excitation tables
 A state diagram ⇒ flip-flop input functions
 straightforward for D flip-flops
 we need excitation tables for JK and T flip-flops

Synchronous Sequential Logic 5-59

Synthesis using JK flip-flops
 The same example
 The state table and JK flip-flop inputs

Synchronous Sequential Logic 5-60

 JA = Bx'; KA = Bx
 JB = x; KB = (A⊕x)‘
 y=?

Synchronous Sequential Logic 5-61

Synchronous Sequential Logic 5-62
Synthesis using T flip-flops
 A n-bit binary counter
 the state diagram

 no inputs (except for the clock input)

Synchronous Sequential Logic 5-63
 The state table and the flip-flop inputs

Synchronous Sequential Logic 5-64

Synchronous Sequential Logic 5-65
 Logic simplification using the K map
 TA2 = A1A2
 TA1 = A0
 TA0 = 1
 The logic diagram

Synchronous Sequential Logic 5-66