Y.-H.

Huang, Digital Logic Design 2025

Digital Logic Design

Lecture 8
Analysis of Sequential Systems

Yu-Hui Huang
April 24, 2025

1
Y.-H. Huang, Digital Logic Design 2025

Announcements

• Tutoring class every Monday from 18:30 to 20:00 in

Room 70111
• Make-up class schedule survey (fill it in by Thursday)
(check Portal)

2
Y.-H. Huang, Digital Logic Design 2025

Final Project (9%)

• 12-mins Presentations in the final two weeks (17th&18th)

- Topic list available on Portal
- Register your group members and topic by May 5. The form
will open at 9pm on April 30.
- 3-4 people per group
-Grading Criteria
Correctness : 30%
Structure & Clarity: 20%
Teamwork& Delivery: 20%
Creativity & Insight: 15%
Q&A Performance: 15%

3
Y.-H. Huang, Digital Logic Design 2025

Recap: Combinational Circuits

• Contains no memory elements

• The outputs depends on the inputs

4
Y.-H. Huang, Digital Logic Design 2025

A Modern CPU

Source: https://www.extremetech.com/wp-content/uploads/2020/09/Intel-TigerLake-Overview.jpg 5
Y.-H. Huang, Digital Logic Design 2025

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

6
Y.-H. Huang, Digital Logic Design 2025

Sequential Systems

7
Y.-H. Huang, Digital Logic Design 2025

Finite State Machine (FSM)

• A model to design sequential logic circuits.
• It transitions between a finite number of state based on
input and produces output accordingly.

• Key components: Input, output, state, initial state, state

transition logic.

• Two main types of FSM:

Moore model & Mealy Model

8
Y.-H. Huang, Digital Logic Design 2025

Moore Model
• A finite-state machine whose current output are
determined only by its current state.
• Example:
A system with one input x and one out z s.t. z = 1 iff x has
been 1 for at least three consecutive clock times.

x 0 1 1 0 1 1 1 0 0 1 0 1 0 1 1 1 1 1 0 0
z ? 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0

9
Y.-H. Huang, Digital Logic Design 2025

Sequential Systems
• Two tools for describing sequential systems.
• A State Table
• A State Diagram (State Graph)

10
Y.-H. Huang, Digital Logic Design 2025

State Tables and Diagrams

Timing trace
x 0 1 1 0 1 1 1 0 0 1 0 1 0 1 1 1 1 1 0 0
q ? A B C A B C D A A B A B A B C D D D A A ?
z ? 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0

State table
Input
Present Next state Present
state x=0 x=1 output State
Output
A A B 0
B A C 0
C A D 0
D A D 1

11
Y.-H. Huang, Digital Logic Design 2025

Mealy Models
• In some systems, the output depends not only on the
present state of the machine, but also on the present
input.
• This type of system is referred to as a Mealy model.

12
Y.-H. Huang, Digital Logic Design 2025

Mealy Models

x=1,
output=0

13
Y.-H. Huang, Digital Logic Design 2025

Exercise
• For the following state table, show a state diagram
and completing the time tracing as far as possible
(even after the input is unknown)

q q* z
x=0 x=1
A A B 0
B C B 0
C A D 0
D C B 1

x 1 1 0 1 0 1 0 1 0 0 1 0 1 1
q
z
14
Y.-H. Huang, Digital Logic Design 2025

Storage Elements
• Latches are level-sensitive devices
• Operate with signal levels
• Flip-flops are edge-sensitive devices
• Controlled by a clock transition

Credit: Andy Chen

15
Y.-H. Huang, Digital Logic Design 2025

Latches
• Latches are asynchronous sequential circuits
• State changes whenever inputs change
• Building blocks of flip-flops
• Not practical for use in synchronous sequential circuits

Credit: Andy Chen

16
Y.-H. Huang, Digital Logic Design 2025

SR Latches
• Two NOR gates

• More complicated types can be built upon it

• 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): forbidden state (Q=Q'=0)

17
Y.-H. Huang, Digital Logic Design 2025

SR Latches

P
1 Q
0
0 0
S R
S=R=0, Q+=Q

P=Qʼ
P
0 Q
1
0 0
S R

18
Y.-H. Huang, Digital Logic Design 2025

SR Latches
P
0 Q S=1, R=0, Q=1, Q+=1
1
1 0
S R
P=Qʼ

0
P
Q
S=1, R=0, Q=0, Q+=1

1 0 0à1
S R

Set: S=1, R=0, à Q+=1

19
Y.-H. Huang, Digital Logic Design 2025

SR Latches

P
1 Q S=0, R=1, Q=0, Q+=0
0
0 1
S R
P=Qʼ

0à1 P Q S=0, R=1, Q=1, Q+=0

0 1 1à 0
S R

Reset: S=0, R=1, à Q+=0

20
Y.-H. Huang, Digital Logic Design 2025

SR Latches
P
Q

S R

Original circuit

R
Q
R R Q Q

S
P (Qʼ) S S Q Q'

Restructured circuit Symbol

21
Y.-H. Huang, Digital Logic Design 2025

SR Latches
Timing diagram
Reset
S
Set

Q ε1 ε2
e1 = 2 gate delays e 2 = 1 gate delay

0
R 0→1
1→0 Q

0 Qʼ
S 1→0
0→1 22
Y.-H. Huang, Digital Logic Design 2025

SR Latches

S (t ) R(t ) Q(t ) Q(t + e ) (= Q+ (t))

1→0
S
P 0 →1 →0 →1
0 0 0 0
0 0 1 1
0 1 0 0
R Q 0 →1 →0 →1 0 1 1 0
1→0
1 0 0 1
if S = R = 1 ® 0 at the same time,
1 0 1 1
Þ Q = P(Q')
= 0 ® 1 ® 0... ( not allowed ) 1 1 0 -ü
ý inputs not allowed
or Q = 1 first 1 1 1 -þ
Q' = 1 first ( undetermined )

23
Y.-H. Huang, Digital Logic Design 2025

SR Latches
Q ( t + e ) = S ( t ) + R' ( t ) Q ( t ) or
+
Q
!" = #""
" S + R'Q
$ (when SR = 0 or SR ¹ 11)
characteristic equation

S(t)
R(t) 0 1
Q(t)
00 0 1 S R Qn +1
0 0 Qn
Q n : present state
01 1 1 0 1 0
Q n +1 : next state
1 0 1
11 0 X 1 1 -

0 X
10
24
Y.-H. Huang, Digital Logic Design 2025

Exercise
• How to implement a SR latch with only NAND gates?

S R Q Q’
0 1 1 0
Set state 1 1 1 0
Reset state 1 0 0 1
1 1 1 1
Undefined 0 0 1 1

25
Y.-H. Huang, Digital Logic Design 2025

Gated Latches
SR latch with control input:
Gate=0: no change
Gate=1: operates as a normal SR latch

1/S'

0/1

1/R'

26
 Y.-H. Huang, Digital Logic Design 2025

Usage of SR latch
1. As a component in more complex latches and F/Fs
2. For debouncing switches

S
S
b
R
+V
1
a Q
Q
R

27
 Y.-H. Huang, Digital Logic Design 2025

D Latch • Eliminate the undesirable

conditions of the indeterminate

(Transparent Latch) state in the SR latch

• D: data
• Gated D-latch
• D Þ Q when En = 1 (transparent);
no change when En = 0
S
1/D'

0/1

1/D
R

28
 Y.-H. Huang, Digital Logic Design 2025

D Latch (Transparent Latch)

Transparent latch since G=1, Q = D

G
D
S Q D
G L
Qʼ Q
R

(a) (b)
GD
G D Q Q+ 00 01 11 10
Q
0 0 0 0
D Q 0 0 1 1 0 0 0 1 0
L 0 1 0 0
G Q’ 0 1 1 1
1 1 1 1 0
1 0 0 0
1 0 1 0
1 1 0 1
1 1 1 1 29
Y.-H. Huang, Digital Logic Design 2025

Various Graphic Symbols

for Latches

30
Y.-H. Huang, Digital Logic Design 2025

Exercise
Determine the Q and Q’ output states of this D-type
gated latch, given the following input conditions:

31
Y.-H. Huang, Digital Logic Design 2025

Exercise
Determine the Q and Q’ output states of this D-type
gated latch, given the following input conditions:

32
Y.-H. Huang, Digital Logic Design 2025

Flip Flops

• A flip-flop is a clocked binary storage device that stores

either a 0 or a 1.
• Flip-flops have one or two outputs. One output is the
state of the flip-flop. If there are two, the other output is
the complement of the state.

0
0 05
s 1 I o
CD1
R 0
0 1 R0
0
1 0
1 LO keep mode 33
Y.-H. Huang, Digital Logic Design 2025

Flip-Flops A

Trigger
• The state of a latch/flip-flop is switched by a change of the control
input
Level triggered – Latch
•
flap
The state transition starts as soon as the clock is during logic 1
(positive level-sensitive) or logic 0 (negative level-sensitive)
Edge triggered – Flip-Flop
1Pa clkiorclk.tl
• The state transition starts only at positive (positive edge-triggered) or
negative edge (negative edge-triggered) of the clock signal

34
Y.-H. Huang, Digital Logic Design 2025

Level-Triggered vs. Edge-Triggered

Level-triggered latch
• The feedback path may cause instability problem
Edge-triggered
filpflop
• The state transition happens only at the edge
• Eliminate the multiple-transition problem
35
Y.-H. Huang, Digital Logic Design 2025

Reeay
D Flip-Flop
Similar to D latch, but changes only to clock edge
a
Qʼ Q output Qʼ Q
FF FF
Ck D Ck D
input
positive nagative
Leading-edge triggered Trailinging-edge triggered

D Qn Qn +1 D Q +n
0 0 0 0 0
0 1 0 1 1
1 0 1
1 1 1 Q+ = D 36
Y.-H. Huang, Digital Logic Design 2025
o
D Flip-Flop
ok1 o
9 edge triggered D F/F
Timing diagram of Traillng

Ck
Q

iay
CIK 時 回去 看 D 是多少

37
Y.-H. Huang, Digital Logic Design 2025

Exercise
Plot the timing diagram of Leading-edge triggered D flip flop

Ck
Q
Traillng edge triggered D F/F

an

38
Y.-H. Huang, Digital Logic Design 2025

Two D Flip-Flop

clk

39
Y.-H. Huang, Digital Logic Design 2025

D Flip-Flop with clear/present

everything
F PRE evevthing
0

p1 0 p 1 sáx 1 000
㞸
c 0 c 1 áxo 重要

40
Y.-H. Huang, Digital Logic Design 2025

D Flip-Flop with clear/present

41
Y.-H. Huang, Digital Logic Design 2025

SR Flip-Flop
SR (Set-Reset) Flip-Flop

cnn.io
ii keepmod seemo

42
Y.-H. Huang, Digital Logic Design 2025

SR Flip-Flop

ǎ S tR 9

43
Y.-H. Huang, Digital Logic Design 2025

T Flip-Flop
T (Toggle) Flip-Flop

下
e
O 仁1

Traieirgadge
0
4k1
44
Y.-H. Huang, Digital Logic Design 2025

T Flip-Flop

45
Y.-H. Huang, Digital Logic Design 2025

JK Flip-Flop

oe
․ JK Flip-Flop is a combination of the SR and T.
Ttilptlop
․ It behaves like an SR flip-flop, except that J=K=1 causes
flip-flop to change state (as T=1) ntiti the

46
Y.-H. Huang, Digital Logic Design 2025

JK Flip-Flop

keep
SR reset

FF set

TFF
Él change
47
Y.-H. Huang, Digital Logic Design 2025

JK Flip-Flop

48
Y.-H. Huang, Digital Logic Design 2025

JK Flip-Flop

49
Y.-H. Huang, Digital Logic Design 2025

Flip-Flop Conversions

50
Y.-H. Huang, Digital Logic Design 2025

Characteristic Equations
• D flip-flop
Q(t+1) = D
• JK flip-flop
Q(t+1) = JQ'+K'Q
• T flop-flop
7
Q(t+1) = T⊕Q

51
Y.-H. Huang, Digital Logic Design 2025

Exercise
• Construct a D flip flop using an inverter and
an S-R flip flop.

52
Y.-H. Huang, Digital Logic Design 2025

Analysis of a Sequential System

o
D1 = ?
D2 = ?
z=?
53
Y.-H. Huang, Digital Logic Design 2025

Analysis of a Sequential System

54
Y.-H. Huang, Digital Logic Design 2025

Analysis of a Sequential System

55
Y.-H. Huang, Digital Logic Design 2025

Analysis of a Sequential System

Why Moore Machine?

Ａ B

Ａ B

JＡ = ? KA= ?
JB = ?
z=?
56
Y.-H. Huang, Digital Logic Design 2025

Analysis of a Sequential System

57
Y.-H. Huang, Digital Logic Design 2025

Analysis of a Sequential System

58
Y.-H. Huang, Digital Logic Design 2025

Analysis of a Sequential System

59
Y.-H. Huang, Digital Logic Design 2025

Analysis of a Sequential System

Why Mealy Machine?

60
Y.-H. Huang, Digital Logic Design 2025

Analysis of a Sequential System

61
Y.-H. Huang, Digital Logic Design 2025

Analysis of a Sequential System

62
Y.-H. Huang, Digital Logic Design 2025

Questions?

63