Digital Logic Design I

Synchronous Sequential
Logic

Mustafa Kemal Uyguroğlu

 Sequential Circuits
• Asynchronous
Inputs Outputs
Combinational
Circuit
Memory
Elements

• Synchronous
Inputs Outputs
Combinational
Circuit
Flip-flops
Clock

1
 Latches
S R Q0 Q Q’
• SR Latch 0 0 0 0 1 Q = Q0

R
0 0
Q

S Q
0 1

Initial Value

2
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
R
1 10 0 1 1 0 1
Q=0
Q 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’
S Q
1 0

3
Latches
• SR Latch S R Q
R Q Q0 No change
0 0
0 1 0 Reset
1 0 1 Set
S Q 1 1 Q=Q’=0 Invalid

S S’ R’ Q
Q Invalid
0 0 Q=Q’=1
0 1 1 Set
Q 1 0 0 Reset
R Q0 No change
1 1
4
Controlled Latches
• SR Latch with Control Input
R R S S
Q Q
C C
S Q R Q
S R

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) Timing Diagram

S
C
D
Q
C D
R Q
Q

t
C D Q
Output may
0 x Q0 No change change
1 0 0 Reset
1 1 1 Set

6
Controlled Latches
• D Latch (D = Data) Timing Diagram

S
C
D
Q
C D
R Q
Q

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

7
Flip-Flops
• Controlled latches are level-triggered

C
• Flip-Flops are edge-triggered

CLK Positive Edge

CLK Negative Edge

8
 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
9
Flip-Flops • Edge-Triggered D Flip-Flop

D Q

Q Positive Edge
CLK

Q
D Q

D Negative Edge

10
Flip-Flops • JK Flip-Flop

J
D Q Q
K
CLK Q Q

J Q
D = JQ’ + K’Q
K Q
11
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

12
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
1 Q’(t) Toggle
13
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)
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 Reset
0 1 1
K Q
1 0 0 Set
1 0 1
1 1 0 Toggle
1 1 1

15
Flip-Flop Characteristic
• Analysis / Derivation
Equations
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

16
Flip-Flop Characteristic
• Analysis / Derivation
Equations
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

17
Flip-Flops with
• Asynchronous Reset
Direct Inputs

D Q R’ D CLK Q(t+1)
0 x x 0
Q
R
Reset

18
Flip-Flops with
• Asynchronous Reset
Direct Inputs

D Q R’ D CLK Q(t+1)
0 x x 0
Q 1 0 ↑ 0
R 1 1 ↑ 1
Reset

19
Flip-Flops with Direct
• Asynchronous Preset and Clear
Inputs
Preset

PR PR’ CLR’ D CLK Q(t+1)

D Q 1 0 x x 0

Q
CLR
Reset

20
Flip-Flops with Direct
• Asynchronous Preset and Clear
Inputs
Preset

PR PR’ CLR’ D CLK Q(t+1)

D Q 1 0 x x 0
0 1 x x 1
Q
CLR
Reset

21
Flip-Flops with Direct
• Asynchronous Preset and Clear
Inputs
Preset

PR PR’ CLR’ D CLK Q(t+1)

D Q 1 0 x x 0
0 1 x x 1
Q 1 1 0 ↑ 0
CLR 1 1 1 ↑ 1
Reset

22
 Analysis of Clocked Sequential
• The State
Circuits
• State = Values of all Flip-Flops
x
D Q A
Example
AB=00 Q

D Q B

CLK Q

23
 Analysis of Clocked Sequential Circuits
• State Equations
A(t+1) = DA x
D Q A
= A(t) x(t)+B(t) x(t)
Q
=Ax+Bx
B(t+1) = DB D Q B

= A’(t) x(t) CLK Q

= A’ x y

y(t) = [A(t)+ B(t)] x’(t)

= (A + B) x’ 24
Analysis of Clocked Sequential Circuits
• State Table (Transition Table)
Present Next x
Input Output D Q A
State State
A B x A B y Q

0 0 0 0 0 0
0 0 1 0 1 0 D Q B

0 1 0 0 0 1 CLK 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 25
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’
26
 Analysis of Clocked Sequential Circuits
• State Diagram Present Next State Output
State x=0 x=1 x=0 x=1
A B A B A B y y
AB input/output
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 27
 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
28
 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 0 0 0 1
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’
29
 Analysis of Clocked Sequential
Circuits
• JK Flip-Flops J Q A

Example: x 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 0 0 0
1
1 1 1 1 1 1
30
 Analysis of Clocked Sequential
Circuits
• T Flip-Flops x T Q
A
y

Example: R Q

Present Next F.F

I/P O/P
State State Inputs T Q
A B x A B TA TB y B

0 0 0 0 0 0 0 0 R Q

0 0 1 0 1 0 1 0
CLK Reset
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 31
 Analysis of Clocked Sequential
Circuits
• T Flip-Flops x A
T Q y

Example: R Q

Present Next F.F

I/P O/P
State State Inputs T Q
B
A B x A B TA TB y
R Q
0 0 0 0 0 0 0 0
0 0 1 0 1 0 1 0 CLK Reset
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
1 1
0/1 0/0
1 1 1 0 0 1 1/0
32
 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.

33
Mealy and Moore Models

Fig. 5.21 Block diagram of Mealy and Moore state machine

34
 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

35
Moore State Diagram
State / Output

0 0
1
00/0 01/0

1 1

11/1 10/0
1
0 0
36
 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.
• An example state diagram
showing in Fig. 5.25.

Fig. 5.25 State diagram 37

 State Reduction
State: a a b c d e f f g f g a
Input: 0 1 0 1 0 1 1 0 1 0 0
Output: 0 0 0 0 0 1 1 0 1 0 0

• 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.

Fig. 5.25 State diagram

38
• 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.

39
• Reducing the state table
• e = g (remove g);
• d = f (remove f);

40
• The reduced finite state machine

State: a a b c d e d d e d e a
Input: 0 1 0 1 0 1 1 0 1 0 0
Output: 0 0 0 0 0 1 1 0 1 0 0
41
• The checking of each pair of
states for possible
equivalence can be done
systematically using
Implication Table.
• The unused states are
treated as don't-care
condition fewer
combinational gates.

Fig. 5.26 Reduced State diagram

42
 Implication Table
• The state-reduction procedure for completely specified state
tables is based on the algorithm that two states in a state
table can be combined into one if they can be shown to be
equivalent. There are occasions when a pair of states do not
have the same next states, but, nonetheless, go to
equivalent next states. Consider the following state table:

• (a, b) imply (c, d) and (c, d) imply (a, b). Both pairs of states are
equivalent; i.e., a and b are equivalent as well as c and d.
43
Implication Table
• The checking of each pair of states for possible
equivalence in a table with a large number of states
can be done systematically by means of an implication
table. This a chart that consists of squares, one for
every possible pair of states, that provide spaces for
listing any possible implied states. Consider the
following state table:

44
 Implication Table
• The implication table is:

45
 Implication Table
• On the left side along the vertical are listed all the states
defined in the state table except the last, and across the
bottom horizontally are listed all the states except the last.
• The states that are not equivalent are marked with a ‘x’ in the
corresponding square, whereas their equivalence is recorded
with a ‘√’.
• Some of the squares have entries of implied states that must
be further investigated to determine whether they are
equivalent or not.
• The step-by-step procedure of filling in the squares is as
follows:
1. Place a cross in any square corresponding to a pair of states whose
outputs are not equal for every input.
2. Enter in the remaining squares the pairs of states that are implied by
the pair of states representing the squares. We do that by starting
from the top square in the left column and going down and then
proceeding with the next column to the right.

46
Implication Table
3. Make successive passes through the table to determine whether any
additional squares should be marked with a ‘x’. A square in the table is
crossed out if it contains at least one implied pair that is not equivalent.
4. Finally, all the squares that have no crosses are recorded with check
marks. The equivalent states are: (a, b), (d, e), (d, g), (e, g).
We now combine pairs of states into larger groups of equivalent states.
The last three pairs can be combined into a set of three equivalent
states (d, e,g) because each one of the states in the group is equivalent
to the other two. The final partition of these states consists of the
equivalent states found from the implication table, together with all the
remaining states in the state table that are not equivalent to any other
state:
(a, b) (c) (d, e, g) (f)
The reduced state table is:

47
Implication Table

48
 State Assignment
• State Assignment
• To minimize the cost of the combinational circuits.
• Three possible binary state assignments. (m states need n-
bits, where 2n > m)

49
• Any binary number assignment is satisfactory as long as
each state is assigned a unique number.
• Use binary assignment 1.

50
 Design Procedure
• Design Procedure for sequential circuit
• The word description of the circuit behavior to get 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;

51
 Design of Clocked Sequential Circuits
• Example:
Detect 3 or more consecutive 1’s

0 1
S0 / 0 S1 / 0
0 State A B
S0 0 0
0 1
0 S1 0 1
S2 1 0
S3 / 1 S2 / 0 S3 1 1
1 1
52
Design of Clocked Sequential Circuits
• Example:
Detect 3 or more consecutive 1’s

Present Next
Input Output
State State
A B x A B y 0 1
0 0 0 0 0 0 S0 / 0 S1 / 0
0 0 1 0 1 0 0
0 1 0 0 0 0
0 1 1 1 0 0 0 0 1
1 0 0 0 0 0
1 0 1 1 1 0
S3 / 1 S2 / 0
1 1 0 0 0 1
1 1
1 1 1 1 1 1
53
 Design of Clocked Sequential Circuits
• Example:
Detect 3 or more consecutive 1’s

Present Next
Input Output
State State
A B x A B y Synthesis using D Flip-Flops
0 0 0 0 0 0
0 0 1 0 1 0 A(t+1) = DA (A, B, x)
0 1 0 0 0 0 = ∑ (3, 5, 7)
0 1 1 1 0 0
1 0 0 0 0 0 B(t+1) = DB (A, B, x)
1 0 1 1 1 0
= ∑ (1, 5, 7)
1 1 0 0 0 1
1 1 1 1 1 1 y (A, B, x) = ∑ (6, 7)
54
 Design of Clocked Sequential Circuits with D F.F.

• Example:
Detect 3 or more consecutive 1’s

Synthesis using D Flip-Flops

B
DA (A, B, x) = ∑ (3, 5, 7) 0 0 1 0
= Ax + B x A 0 1 1 0
x B
DB (A, B, x) = ∑ (1, 5, 7) 0 1 0 0
A 0 1 1 0
= A x + B’ x x
B
y (A, B, x) = ∑ (6, 7) 0 0 0 0

=AB A 0 0 1 1
x 55
 Design of Clocked Sequential Circuits with
D F.F.
• Example:
Detect 3 or more consecutive 1’s

Synthesis using D Flip-Flops

DA = A x + B x
D Q A
DB = A x + B’ x x

Q
y =AB y

D Q B

CLK Q
56
 Flip-Flop Excitation Tables
Present Next F.F. Present Next F.F.
State State Input State State Input
Q(t) Q(t+1) D Q(t) Q(t+1) J K 0 0 (No change)
0 1 (Reset)
0 0 0 0 0 0 x 1 0 (Set)
0 1 1 0 1 1 x 1 1 (Toggle)
0 1 (Reset)
1 0 0 1 0 x 1 1 1 (Toggle)
1 1 1 1 1 x 0 0 0 (No change)
1 0 (Set)

Q(t) Q(t+1) T
0 0 0
0 1 1
1 0 1
1 1 0
57
 Design of Clocked Sequential Circuits with
JK F.F.
• Example:
Detect 3 or more consecutive 1’s

Present Next Flip-Flop

Input
State State Inputs
Synthesis using JK F.F.
A B x A B JA KA JB KB
0 0 0 0 0 0 x 0 x JA (A, B, x) = ∑ (3)
0 0 1 0 1 0 x 1 x dJA (A, B, x) = ∑ (4,5,6,7)
0 1 0 0 0 0 x x 1 KA (A, B, x) = ∑ (4, 6)
0 1 1 1 0 1 x x 1 dKA (A, B, x) = ∑ (0,1,2,3)
0 x JB (A, B, x) = ∑ (1, 5)
1 0 0 0 0 x 1
dJB (A, B, x) = ∑ (2,3,6,7)
1 0 1 1 1 x 0 1 x
KB (A, B, x) = ∑ (2, 3, 6)
1 1 0 0 0 x 1 x 1
dKB (A, B, x) = ∑ (0,1,4,5)
1 1 1 1 1 x 0 x 0 58
 Design of Clocked Sequential Circuits with
JK F.F.
• Example:
Detect 3 or more consecutive 1’s

Synthesis using JK Flip-Flops

JA = B x KA = x’ B B
0 0 1 0 x x x x
JB = x KB = A’ + x’ A x x x x A 1 0 0 1
x x
J Q A
B B
x K Q y 0 1 x x x x 1 1
A 0 1 x x A x x 0 1
J Q B x x

K Q

CLK 59
 Design of Clocked Sequential Circuits with
T F.F.
• Example:
Detect 3 or more consecutive 1’s

Present Next F.F.

Input
State State Input
A B x A B TA TB Synthesis using T Flip-Flops
0 0 0 0 0 0 0
0 0 1 0 1 0 1 TA (A, B, x) = ∑ (3, 4, 6)
0 1 0 0 0 0 1 TB (A, B, x) = ∑ (1, 2, 3, 5, 6)
0 1 1 1 0 1 1
1 0 0 0 0 1 0
1 0 1 1 1 0 1
1 1 0 0 0 1 1
1 1 1 1 1 0 0
60
 Design of Clocked Sequential Circuits with
T F.F.
• Example:
Detect 3 or more consecutive 1’s

Synthesis using T Flip-Flops

TA = A x’ + A’ B x
A
TB = A’ B + B  x
T Q
x

Q y

B B
T Q B
0 0 1 0 0 1 1 1
Q
A 1 0 0 1 A 0 1 0 1
x x
CLK

61