Digital Logic Design I

Synchronous Sequential
Logic

Mustafa Kemal Uyguroğlu

 Combinational Circuits

 Output is function of input only

i.e. no feedback

Combinational
n inputs • • m outputs
•
• Circuits •
•


When input changes, output may change (after a delay)

Eastern Mediterranean University 1 / 65

 Analysis Procedure

 Boolean Expression Approach

T2=ABC
T1=A+B+C
T3=AB'C'+A'BC'+A'B'C

F’2=(A’+B’)(A’+C’)(B’+C’)

F2=AB+AC+BC

F1=AB'C'+A'BC'+A'B'C+ABC
F2=AB+AC+BC
Eastern Mediterranean University 2 / 65
 Sequential Circuits

 Asynchronous
Inputs Outputs
Combinational
Circuit
Memory
Elements

 Synchronous
Inputs Outputs
Combinational
Circuit
Flip-flops
Clock

3
 Latches

 SR Latch
S R Q0 Q Q’
0 0 0 0 1
Q = Q0
0 0 1 1 0
0 1 0 0 1
1 10 0 1 1 0 1
Q=0

1 0 0 1 0
Q=1
1 0 1 1 0
1 1 0 0 0 Q = Q’
1 1 1 0 0 Q = Q’

1 0

Eastern Mediterranean University 4

 Latches

 SR Latch
S R Q
0 0 Q0 No change
0 1 0 Reset
1 0 1 Set
1 1 Q=Q’=0 Invalid

 SR Latch with Control Input C S R Q

0 x x Q0 No change
1 0 0 Q0 No change
1 0 1 0 Reset
1 1 0 1 Set
1 1 1 Q=Q’ Invalid 5
 Controlled Latches

 D Latch (D = Data)

D
D Q
C
Q

C D Q
0 x Q0 No change
1 0 0 Reset
1 1 1 Set

Eastern Mediterranean University 6

 Controlled Latches

 D Latch (D = Data) Timing Diagram

C
D Q
D
Q
Q

t
C D Q
Output may
0 x Q0 No change change
1 0 0 Reset Q (t+1) = D
1 1 1 Set When Clock is enabled
Q(t+1) = Q(t)
When Clock is disabled
Eastern Mediterranean University 7
 Controlled Latches (Task 1)

 D Latch (D = Data) Timing Diagram

C
D Q
D
Q
Q

t
C D Q
Output may
0 x Q0 No change change
1 0 0 Reset Q (t+1) = D
1 1 1 Set When Clock is enabled
Q(t+1) = Q(t)
When Clock is disabled
Eastern Mediterranean University 8
 Controlled Latches

 D Latch (D = Data) Timing Diagram

C
D Q
D
Q
Q

C D Q Output may
0 x Q0 No change change
1 0 0 Reset Q (t+1) = D
1 1 1 Set When Clock is enabled
Q(t+1) = Q(t)
When Clock is disabled
Eastern Mediterranean University 9
 Flip-Flops

 Controlled latches are level-triggered

Q (t+1) = D
When Clock is enabled
C
Q(t+1) = Q(t)
When Clock is disabled

 Flip-Flops are edge-triggered

CLK Positive Edge

CLK Negative Edge

Eastern Mediterranean University 10

 Flip-Flops

 Master-Slave D Flip-Flop
D D Q D Q Q
D Latch D Latch
(Master) (Slave)
C C

Master Slave
CLK
CLK

D
Looks like it is negative
edge-triggered QMaster

QSlave
Eastern Mediterranean University 11
 Flip-Flops

 JK Flip-Flop

J K Q(t+1)
D = JQ’ + K’Q J Q 0 0 Q(t)
0 1 0
Q (t+1) = D = JQ’ + K’Q K Q 1 0 1
1 1 Q’(t)
Eastern Mediterranean University 12
 Flip-Flops

 T Flip-Flop

T J Q T D Q

Q
K Q

T Q
D = JQ’ + K’Q
D = TQ’ + T’Q = T  Q Q

Eastern Mediterranean University 13

 Flip-Flop Characteristic Equations

 Analysis / Derivation
J K Q(t) Q(t+1)
0 0 0 0 No change
J Q 0 0 1 1
0 1 0 Reset
0 1 1
K Q
1 0 0 Set
1 0 1
1 1 0 Toggle
1 1 1

Eastern Mediterranean University 14

 Flip-Flop Characteristic Equations

 Analysis / Derivation
J K Q(t) Q(t+1)
0 0 0 0 No change
J Q 0 0 1 1
0 1 0 0 Reset
0 1 1 0
K Q
1 0 0 Set
1 0 1
1 1 0 Toggle
1 1 1

Eastern Mediterranean University 15

 Flip-Flop Characteristic Equations

 Analysis / Derivation
J K Q(t) Q(t+1)
0 0 0 0 No change
J Q 0 0 1 1
0 1 0 0 Reset
0 1 1 0
K Q
1 0 0 1 Set
1 0 1 1
1 1 0 Toggle
1 1 1

Eastern Mediterranean University 16

 Flip-Flop Characteristic Equations

 Analysis / Derivation
J K Q(t) Q(t+1)
0 0 0 0 No change
J Q 0 0 1 1
0 1 0 0 Reset
0 1 1 0
K Q
1 0 0 1 Set
1 0 1 1
1 1 0 1 Toggle
1 1 1 0

Eastern Mediterranean University 17

 Flip-Flop Characteristic Equations

 Analysis / Derivation
J K Q(t) Q(t+1)
0 0 0 0
J Q 0 0 1 1 K
0 1 0 0 0 1 0 0
0 1 1 0 J 1 1 0 1
K Q Q
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 0

Q(t+1) = JQ’ + K’Q

Eastern Mediterranean University 18
Flip-Flop Characteristic Tables

D Q D Q(t+1)
0 0 Reset
Q 1 1 Set

J K Q(t+1)
J Q 0 0 Q(t) No change
0 1 0 Reset
K Q 1 0 1 Set
1 1 Q’(t) Toggle

T Q T Q(t+1)
0 Q(t) No change
Q Toggle
1 Q’(t)
Eastern Mediterranean University 19
Flip-Flop Characteristic Equations

D Q D Q(t+1)
0 0 Q(t+1) = D
Q 1 1

J K Q(t+1)
J Q 0 0 Q(t)
0 1 0 Q(t+1) = JQ’ + K’Q
K Q 1 0 1
1 1 Q’(t)

T Q T Q(t+1)
0 Q(t) Q(t+1) = T  Q
Q
1 Q’(t)
Eastern Mediterranean University 20
 Clocked Sequential Circuits

1) Analyzing a clocked sequential circuit

2) Designing a sequential circuit to address a
problem

Eastern Mediterranean University 21

 Analyzing a clocked sequential circuit
1. A circuit will be given and we must understand the
boundary between combinational stage and
sequential stage
[Link] identify the following specifications
a) No. flip flops and what types
b) How many external input
c) How many external output
d) No. of state variable (n)
e) No of states, 2n

Eastern Mediterranean University 22

 Analyzing a clocked sequential circuit

3. Write down the equation of Flip Flop Input, External

Output

4. Write down the equation for flipflop output (known

as state equation). This can be written by combining
(3) with the flip flop’s driving equation.

5. Draw the state table

6. Draw the state diagram

Eastern Mediterranean University 23

 Analysis of Clocked Sequential Circuits

 The State
● State = Values of all Flip-Flops

x
Example D Q A

AB=00 Q

D Q B

CLK Q

Eastern Mediterranean University 24

 Analysis of Clocked Sequential Circuits

 State Equations
x
A(t+1) = DA D Q A

= A(t) x(t)+B(t) x(t) Q

=Ax+Bx
D Q B
B(t+1) = DB
CLK Q
= A’(t) x(t)
y
= A’ x
y(t) = [A(t)+ B(t)] x’(t)
= (A + B) x’
Eastern Mediterranean University 25
 Analysis of Clocked Sequential Circuits

 State Table (Transition Table)

x
Present Next D Q A
Input Output
State State
Q
A B x A B y
0 0 0 0 0 0 B
D Q
0 0 1 0 1 0
CLK
0 1 0 0 0 1 Q

0 1 1 1 1 0 y

1 0 0 0 0 1
1 0 1 1 0 0
A(t+1) = A x + B x
1 1 0 0 0 1
1 1 1 1 0 0 B(t+1) = A’ x
y(t) = (A + B) x’
t t+1 t
Eastern Mediterranean University 26
 Analysis of Clocked Sequential Circuits

 State Table (Transition Table)

x
Present Next State Output D Q A

State x=0 x=1 x=0 x=1 Q

A B A B A B y y
0 0 0 0 0 1 0 0 D Q B
0 1 0 0 1 1 1 0
CLK Q
1 0 0 0 1 0 1 0
1 1 0 0 1 0 1 0 y

t t+1 t A(t+1) = A x + B x
B(t+1) = A’ x
y(t) = (A + B) x’
Eastern Mediterranean University 27
 Analysis of Clocked Sequential Circuits

 State Diagram Present Next State Output

State x=0 x=1 x=0 x=1
y y
AB input/output A B A B A B
0 0 0 0 0 1 0 0
0 1 0 0 1 1 1 0
0/0 1/0
1 0 0 0 1 0 1 0
0/1 1 1 0 0 1 0 1 0
00 10
x
D Q A
0/1
Q
1/0 0/1 1/0
D Q B

CLK Q
01 11
y
1/0 Eastern Mediterranean University 28
 Analysis of Clocked Sequential Circuits

 D Flip-Flops
Example: x D Q A
Present Next
y
Input
State State CLK Q
A x y A
0 0 0 0
0 0 1 1 A(t+1) = DA = A  x  y
0 1 0 1
0 1 1 0
1 0 0 1 01,10
1 0 1 0
00,11 0 1 00,11
1 1 0 0
1 1 1 1 01,10
Eastern Mediterranean University 29
 Analysis of Clocked Sequential Circuits

 JK Flip-Flops J Q A

Example: x K Q

Present Next Flip-Flop

I/P J Q B
State State Inputs
A B x A B JA KA JB KB K Q
0 0 0 0 1 0 0 1 0 CLK
0 0 1 0 0 0 0 0 1
JA = B KA = B x’
0 1 0 1 1 1 1 1 0
JB = x’ KB = A  x
0 1 1 1 0 1 0 0 1
1 0 0 1 1 0 0 1 1 A(t+1) = JA Q’A + K’A QA
1 0 1 1 0 0 0 0 0 = A’B + AB’ + Ax
1 1 0 0 0 1 1 1 1 B(t+1) = JB Q’B + K’B QB
1 1 1 1 1 1 0 0 0 = B’x’ + ABx + A’Bx’
Eastern Mediterranean University 30
 Analysis of Clocked Sequential Circuits

 JK Flip-Flops J Q A

x
Example: K Q

Present Next Flip-Flop J Q B

I/P
State State Inputs
A B x A B JA KA JB KB K Q

0 0 0 0 1 0 0 1 0 CLK

0 0 1 0 0 0 0 0 1 1 0 1
0 1 0 1 1 1 1 1 0 00 11
0 1 1 1 0 1 0 0 1
0
1 0 0 1 1 0 0 1 1 0 0
1 0 1 1 0 0 0 0 0
1 1 0 0 0 1 1 1 1 01 10
1
1 1 1 1 1 1 0 0 0 1
Eastern Mediterranean University 31
 Analysis of Clocked Sequential Circuits

 T Flip-Flops
Example:
Present Next F.F
I/P O/P
State State Inputs
A B x A B TA TB y
0 0 0 0 0 0 0 0
0 0 1 0 1 0 1 0
0 1 0 0 1 0 0 0
TA = B x TB = x
0 1 1 1 0 1 1 0
y =AB
1 0 0 1 0 0 0 0
1 0 1 1 1 0 1 0
A(t+1) = TA Q’A + T’A QA
= AB’ + Ax’ + A’Bx
1 1 0 1 1 0 0 1
1 1
B(t+1) = TB Q’B + T’B QB
1 1 1 0 0 1
=xB
Eastern Mediterranean University 32
 Analysis of Clocked Sequential Circuits

 T Flip-Flops
Example:
Present Next F.F
I/P O/P
State State Inputs
A B x A B TA TB y
0 0 0 0 0 0 0 0
0 0 1 0 1 0 1 0
0 1 0 0 1 0 0 0 0/0 0/0
0 1 1 1 0 1 1 0 00 1/0 01
1 0 0 1 0 0 0 0
1 0 1 1 1 0 1 0 1/1 1/0
1 1 0 1 1 0 0 1 11 10
0/1 0/0
1 1 1 0 0 1 1 1 1/0
Eastern Mediterranean University 33
 Mealy and Moore Models

 The Mealy model: the outputs are functions of

both the present state and inputs
● 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.
● The outputs are synchronous with the clocks.

Eastern Mediterranean University 34

Mealy and Moore Models

Fig. 5.21 Block diagram of Mealy and Moore state machine

Eastern Mediterranean University 35
 Mealy and Moore Models

Mealy Moore
Present Next Present Next
I/P O/P I/P O/P
State State State State
A B x A B y A B x A B y
0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 1 0 0 0 1 0 1 0
0 1 0 0 0 1 0 1 0 0 1 0
0 1 1 1 1 0 0 1 1 1 0 0
1 0 0 0 0 1 1 0 0 1 0 0
1 0 1 1 0 0 1 0 1 1 1 0
1 1 0 0 0 1 1 1 0 1 1 1
1 1 1 1 0 0 1 1 1 0 0 1

For the same state, For the same state,

the output changes with the input the output does not change with the input

Eastern Mediterranean University 36

Moore State Diagram

State / Output

0 0
1
00/0 01/0

1 1

11/1 10/0
1
0 0
Eastern Mediterranean University 37