Synchronous Sequential Logic

Part I

Sheis Abolmaali

School of ECE
Semnan University
1
 Sequential Logic
• Digital circuits we have learned, so far, have
been combinational
– no memory,
– outputs are entirely defined by the “current” inputs
• However, many digital systems encountered
everyday life are sequential (i.e. they have
memory)
– the memory elements remember past inputs
– outputs of sequential circuits are not only dependent
on the current input but also the state of the memory
elements.
2
 Sequential Circuits Model

inputs outputs
Combinational
Circuit

current next
state state
Memory
Elements

current state is a function of past inputs and initial

state 3
 Classification 1/2
• Two types of sequential circuits
1. Synchronous
– Signals affect the memory elements at discrete
instants of time.
– Discrete instants of time requires synchronization.
– Synchronization is usually achieved through the use
of a common clock.
– A “clock generator” is a device that generates a
periodic train of pulses.

4
 Classification 2/2
1. Synchronous
• The state of the memory elements are updated with
the arrival of each pulse
• This type of logical circuit is also known as clocked
sequential circuits.
2. Asynchronous
• No clock
• behavior of an asynchronous sequential circuits
depends upon the input signals at any instant of time
and the order in which the inputs change.
• Memory elements in asynchronous circuits are
regarded as time-delay elements
5
 Clocked Sequential Circuits
• Memory elements are flip-flops which are logic
devices, each of which is capable of storing one
bit of information.

inputs outputs
Combinational
Circuit

current next
state state
Flip-Flops
clock
6
 Clocked Sequential Circuits
• The outputs of a clocked sequential circuit can
come from the combinational circuit, from the
outputs of the flip-flops or both.
• The state of the flip-flops can change only
during a clock pulse transition
– i.e. low-to-high and high-to-low
– clock edge
• When the clock maintains its value, the flip-flop
output does not change
• The transition from one state to the next occurs
at the clock edge.
7
 Latches
• The most basic types of memory elements are
not flip-flops, but latches.
• A latch is a memory device that can maintain a
binary state indefinitely.
• Latches are, in fact, asynchronous devices and
they usually do not require a clock to operate.
• Therefore, they are not directly used in clocked
synchronous sequential circuits.
• They rather be used to construct flip-flops.

8
 SR-Latch
• made of cross-coupled NOR (or NAND) gates
R
Q1

Q2
S

S R Q1 Q2
1 0 1 0
0 0 1 0 Q2 = Q1’
0 1 0 1
0 0 0 1
1 1 0 0 Undefined 9
 Undefined State of SR-Latch
• S = R = 1 may result in an undefined state
– the next state is unpredictable when both S and R
goes to 0 at the same time.
– It may oscillate
– Or the outcome state depend on which of S and R goes
to 0 first.

0 10 1 0 1 0
R
Q
It oscillates

010 Q’
S 0 01 0
10
 SR-Latches with NAND Gates
S
Q

Q’
R
Also known as S’R’-latch
S R Q Q’
1 0 0 1
1 1 0 1 After S = 1, R = 0
0 1 1 0
1 1 1 0 After S = 0, R = 1
0 0 1 1 Undefined
11
 SR-Latch with Control Input
• Control inputs allow the changes at S and R to change the
state of the latch.
S
Q

Q’
R
C S R Q Q’
0 X X No change
1 0 0 No change
1 0 1 Q = 0 Reset state
1 1 0 Q = 1 Set state
1 1 1 Indeterminate 12
 D-Latch
• SR latches are seldom used in practice because
the indeterminate state may cause instability
• Remedy: D-latches

D S
Q

R Q’

This circuit guarantees that the inputs to the SR-latch

is always complement of each other when C = 1. 13
 D-Latch
C D Next state of Q
0 X No change
1 0 Q = 0; reset state
1 1 Q = 1; set state

• We say that the D input is sampled when C = 1

S Q S Q D Q

R Q’ R Q’ C Q’

SR-latch S’R’-latch D-latch

14
 D-Latch as a Storage Unit
• D–latches can be used as temporary storage
• The input of D-latch is transferred to the Q
output when C = 1
• When C = 0 the binary information is retained.
• We call latches level-sensitive devices.
– So long as C remains at logic-1 level, any change in data
input will change the state and the output of the latch.
– Level sensitive latches may suffer from a serious
problem.
• Memory devices that are sensitive to the rising
or falling edge of control input is called flip-
flops. 15
 Need for Flip-Flops 1/2
• Outputs may keep changing so long as C = 1

inputs outputs
Combinational
Circuit

current next
state state
Latches
C
16
 Need for Flip-Flops 2/2
• Another issue (related to the first one)
– The states of the memory elements to change
synchronously
– memory elements should respond to the changes in
input at certain points in time.
– This is the very characteristics of synchronous
circuits.
– To this end, we use flip-flops that change states
during a signal transition of control input (clock)

17
 Edge-Triggered D Flip-Flop
• An edge-triggered D flip-flop can be constructed
using two D latches
Y
D D Q D Q Q
D latch D latch
(master) (slave)
C C

clk’
clk Y=D
clk
clk
Q=Y=D
D
clk’
Y
Negative edge-triggered
Q
D flip-flop 18
Positive Edge-Triggered D Flip-Flop
Y
D D Q D Q Q
D latch D latch
(master) (slave)
clk’ C C

clk
clk
Y= D
clk’ Y does not change

Q=Y=D
clk

19
 Symbols for D Flip-Flops

D Q
Positive edge-triggered
D FF
D Flip-Flop
clk C

D Q
Negative edge-triggered
D FF
D Flip-Flop
clk C

20
 Setup & Hold Times 1/2
• Timing parameters are associated with the
operation of flip-flops
• Recall Q gets the value of D in clock transition

clk
D Q
ts th
D FF

D clk C

tp, FF 21
 Setup & Hold Times 2/2
• Setup time, ts
– The change in the input D must be made before the
clock transition.
– Input D must maintain this new value for a certain
minimum amount time.
– If a change occurs at D less than ts second before the
clock transition, then the output may not acquire this
new value.
– It may even demonstrate unstable behavior.
• Hold time, th,
– Similarly the value at D must be maintained for a
minimum amount of time (i.e. th) after the clock
transition.
22
 Propagation Time
• Even if setup and hold times are achieved, it
takes some time the circuit to propagate the
input value to the output.
• This is because of the fact that flip-flops are
made of logic gates that have certain
propagation times.

23
 D Flip-Flop
D Q
Positive edge-triggered
D FF
D Flip-Flop
clk C

• Characteristic equation
– Q(t+1) = D
D Q(t+1)
0 0
1 1

Characteristic Table 24
 Other Flip-Flops
• D flip-flop is the most common
– since it requires the fewest number of gates to
construct.
• Two other widely used flip-flops
– JK flip-flops
– T flip-flops
• JK flip-flops
– Three FF operations
1. Set
2. Reset
3. Complement
25
 JK Flip-Flops
J K Q(t+1) next state
J Q
0 0 Q(t) no change
C
0 1 0 Reset
K 1 0 1 Set
1 1 Q’(t) Complement

Characteristic Table

• Characteristic equation
– Q(t+1) = JQ’(t) + K’Q(t)

26
 T (Toggle) Flip-Flop
• Complementing flip-flop
T Q(t+1) next state
T Q
0 Q(t) no change
C 1 Q’(t) Complement

Characteristic Table

• Characteristic equation
– Q(t+1) =

T J Q
T
D Q

C C
K
27
 Characteristic Equations
• The logical properties of a flip-flop can be
expressed algebraically using characteristic
equations
• D flip-flop
– Q(t+1) =
• JK flip-flop
– Q(t+1) =
• T flip-flop
– Q(t+1) =

28
 Asynchronous Inputs of Flip-Flops
• They are used to force the flip-flop to a
particular state independent of clock
– “Preset” (direct set) set FF state to 1
– “Clear” (direct reset) set FF state to 0
• They are especially useful at startup.
– In digital circuits when the power is turned on, the
state of flip-flops are unknown.
– Asynchronous inputs are used to bring all flip-flops to
a known “starting” state prior to clock operation.

29
 Asynchronous Inputs
data D Q clk
C
D
R

reset Q

reset

reset C D Q Q’

1 X X 0 1 Starting State
0  0 0 1

0  1 1 0
30
Analysis of Clocked Sequential Circuits
• Goal:
– to determine the behavior of clocked sequential
circuits
– “Behavior” is determined from
• Inputs
• Outputs
• State of the flip-flops
– We have to obtain
• Boolean expressions for output and next state
– output & state equations
• (state) table
• (state) diagram
31
 State Equations
• Also known as “transition equations”
– specify the next state as a function of the present
state and inputs
• Example
A(t+1)
D Q A
x C
A’

B(t+1)
D Q B
C
B’

y
32
clk
 Output and State Equations
• A(t+1) =
• B(t+1) =
• y=

A(t+1)
D Q A
x C
A’

B(t+1)
D Q B
C
B’

y 33
clk
 Flip Flop Input Equations

• Flip-Flop input (excitation) equations

• Same as the state equations in D flip-flops

34
Example: State (Transition) Table
A(t+1) = ? B(t+1) = ? y=?

Present state input Next state output

A B x A B y
0 0 0 0 0 0
0 0 1 0 1 0
0 1 0 0 0 0
0 1 1 1 0 0
1 0 0 0 0 0
1 0 1 1 1 0
1 1 0 0 0 0
1 1 1 0 0 1

A sequential circuit with m FFs and n inputs needs 2m+n

rows in the transition table 35
Example: State Diagram
Present input Next output
0/0 1/1 state state
A B x A B y
0/0 0 0 0 0 0 0
00 11
0 0 1 0 1 0
0 1 0 0 0 0
0 1 1 1 0 0
1/0 0/0 1 0 0 0 0 0
0/0 1/0
1 0 1 1 1 0
1 1 0 0 0 0
1 1 1 0 0 1
01 10

1/0 What is this circuit

doing?
State diagram provides the same information as state table
36
 Analysis with JK Flip-Flops
• For a D flip-flop, the state equation is the same
as the flip-flop input equation
– Q(t+1) = D
• For JK flip-flops, situation is different
– Goal is to find state equations
– Method
1. determine flip-flop input equations
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
37
 Example: Analysis with JK FFs
x JA
J Q A
C
KA
K

JB
J
D Q B
clk C
C
1 K
KB

• Flip-flop input equations

– JA = and KA =
– JB = and KB = 38
 Example: Analysis with JK FFs
• JA = Bx and KA = x’+B
• JB = x and KB = 1

present State input next state FF inputs

A B x A B JA KA JB KB
0 0 0 0 0 0 1 0 1
0 0 1 0 1 0 0 1 1
0 1 0 0 0 0 1 0 1
0 1 1 1 0 1 1 1 1
1 0 0 0 0 0 1 0 1
1 0 1 1 1 0 0 1 1
1 1 0 0 0 0 1 0 1
1 1 1 0 0 1 1 1 1 39
 Example: Analysis with JK FFs
• Characteristic equations
– A(t+1) = JAA’ + K’AA
– B(t+1) = JBB’ + K’BB
• Input equations
– JA = Bx and KA = x’+B
– JB = x and KB = 1
• State equations
– A(t+1) =
=
– B(t+1) =

40
 State Diagram
0/0 1/1

Present input Next output

00 0/0 11 state state
A B x A B y
0 0 0 0 0 0

1/0 0 0 1 0 1 0
0/0 0/0 1/0 0 1 0 0 0 0
0 1 1 1 0 0
1 0 0 0 0 0
1 0 1 1 1 0
01 10
1 1 0 0 0 0
1 1 1 0 0 1
1/0

What is the circuit

doing? 41
 Analysis with T Flip-Flops
• Method is the same TA =
• Example TB =

TA A
x T Q y1
C

TB
T
D Q y0
B
clk C
C

y1 = A
reset
y0 = B
42
Example: Analysis with T Flip-Flops
• Characteristic equation
– A(t+1) = TA  A
– B(t+1) = TB  B
• Input equations
– TA = xB
– TB = x
• Output equations
– y1 = A
– y0 = B
• State equations
– A(t+1) =
– B(t+1) =
43
 State Table & Diagram
• A(t+1) = xB  A
0 0
• B(t+1) = x  B
• y1 = A; y0 = B
Present Next 1
00/00 01/01
state input state output
A B x A B y1 y0
0 0 0 0 0 0 0 1
1
0 0 1 0 1 0 0
0 1 0 0 1 0 1
0 1 1 1 0 0 1
1 0 0 1 0 1 0 11/11 10/10
1
1 0 1 1 1 1 0
1 1 0 1 1 1 1 0
0
1 1 1 0 0 1 1 44
 Mealy and Moore Models
• There are two models for sequential circuits
– Mealy
– Moore
• They differ in the way the outputs are
generated
– Mealy:
• output is a function of both present states and
inputs
– Moore
• output is a function of present state only

45
 Example: Mealy and Moore Machines
x
y Q
D
C
clock C

reset

Mealy machine
• External inputs, x and y, are asynchronous
• Thus, outputs may have momentary (incorrect) values
• Inputs must be synchronized with clocks
• Outputs must be sampled only during clock edges
46
Timing Diagram (11) + (01) = 100

clk

reset

S
47
S=xyC C(t+1) = xy + xC + yC
 Timing Diagram
clk

reset

S
48
S=xyC C(t+1) = xy + xC + yC
 Example: Moore Machines
x Q
A
T
y
C

T
D Q
B
clk C
C

reset

• Outputs are already synchronized with clock.

• They change synchronously with the clock edge.
49