1 of 135

Adapted from Dr. Bassam Kahhaleh’ Slides by Prof. Iyad Jafar

Digital Logic

0907231

0

2 of 135

Chapter 6

Sequential Logic Circuits

1

3 of 135

Outline

Introduction
Storage Elements
Analysis of Synchronous Sequential Circuits
Design of Synchronous Sequential Circuits

2

4 of 135

Introduction

3

5 of 135

Introduction

The circuits we studied so far are Combinational Logic Circuits (CLC)

The output is only dependent on the current input value/combination

Consider the design of a circuit that counts from 0 to 9?

We need our circuit to memorize the current count and use it to determine the next count!

Combinational

Circuit

Inputs

Outputs

m

n

X_i

Y_r

Y_r = F_r(X_n-1, , … , X₀)

4

6 of 135

Introduction

Sequential Logic Circuits

Combinational logic circuits with memory/storage

The output(s) is dependent on the current input and the stored value (Present State)

Two types

Asynchronous
Synchronous

5

7 of 135

Sequential Circuits

Asynchronous Sequential Circuits

Output and next state are function of current input and stored value (present state)
Asynchronous

stored value (state) is allowed to change at any time

Fast but complex to design and analyze!

Combinational

Circuit

Memory�Elements

Inputs

Outputs

m

n

X_i

Y_r

Y_r = F_r(Q_k-1,Q_k-2, … , Q₀,X_n-1, , … , X₀)

k

Q_j(t)

Present

State

Q_j(t+1)

Q_j(t+1) = G_j(Q_k-1,Q_k-2, … , Q₀,X_n-1, , … , X₀)

6

8 of 135

Sequential Circuits

Synchronous Sequential Circuits

Output and next state are function of current input and stored value (present state)
Synchronous

state is allowed to change during/at specific time

Slow but easier to design and analyze!

Clock

Combinational

Circuit

Memory�Elements

Inputs

Outputs

m

n

X_i

Y_r

Y_r = F_r(Q_k-1,Q_k-2, … , Q₀,X_n-1, , … , X₀)

k

Qj(t)

Present

State

Qj(t+1)

Q_j(t+1) = G_j(Q_k-1,Q_k-2, … , Q₀,X_n-1, , … , X₀)

7

9 of 135

Storage Elements

8

10 of 135

Storage Elements

Storage element is a logic circuit that can store one bit as long as power is available

The input is used to specify how and when the stored value changes

The output is the stored value

Q

Input

Stored Value

Complement of

stored Value

9

11 of 135

Storage Elements

Operations performed by the input could be

Set (change stored value to 1)
Reset (change stored value to 0)
Hold (no change)
Toggle (complement the stored value)

Types of Storage Elements

Latches
Controlled/Clocked Latches
Flip-Flops

10

12 of 135

Latches

SR Latch

S R Q	Q+	Q+’
0 0 0

0

1

0

0	1

Q+ = Q

Initial Value

Q is Q(t); the present state

Q+ is Q(t+1); the next state

Reset

Set

11

13 of 135

Latches

SR Latch

S R Q	Q+	Q+’
0 0 0	0	1
0 0 1

1

0

1	0

Q+ = Q

12

14 of 135

Latches

SR Latch

S R Q	Q+	Q+’
0 0 0	0	1
0 0 1	1	0
0 1 0	0

0

1

0

	1

Q+ = 0

Q+ = Q

13

15 of 135

Latches

SR Latch

S R Q	Q+	Q+’
0 0 0	0	1
0 0 1	1	0
0 1 0	0	1
0 1 1

1

0

1

0

0	1

Q+ = 0

Q+ = Q

Q+ = 0

1

0

14

16 of 135

Latches

SR Latch

S R Q	Q+	Q+’
0 0 0	0	1
0 0 1	1	0
0 1 0	0	1
0 1 1	0	1
1 0 0

0

1

0

1

1	0

Q+ = 0

Q+ = Q

Q+ = 1

0

1

15

17 of 135

Latches

SR Latch

S R Q	Q+	Q+’
0 0 0	0	1
0 0 1	1	0
0 1 0	0	1
0 1 1	0	1
1 0 0	1	0
1 0 1

1

0

1

1	0

Q+ = 0

Q+ = Q

Q+ = 1

16

18 of 135

Latches

SR Latch

S R Q	Q+	Q+’
0 0 0	0	1
0 0 1	1	0
0 1 0	0	1
0 1 1	0	1
1 0 0	1	0
1 0 1	1	0
1 1 0

0

1

0	0

Q+ = 0

Q+ =Q₀

Q+= 1

Q+ = Q+’

0

17

19 of 135

Latches

SR Latch

S R Q	Q+	Q+’
0 0 0	0	1
0 0 1	1	0
0 1 0	0	1
0 1 1	0	1
1 0 0	1	0
1 0 1	1	0
1 1 0	0	0
1 1 1

1

0

1

0	0

Q+ = 0

Q+ = Q

Q+ = 1

Q+ = Q+’

0

18

20 of 135

Latches

SR Latch Summary

S R	Q(t+1)
0 0	Q(t)
0 1	0
1 0	1
1 1	Q=Q’=0

No change

Reset

Set

Invalid

S

Q

R

19

21 of 135

Latches

SR Latch

S R	Q(t+1)
0 0	Q(t)
0 1	0
1 0	1
1 1	Q=Q’=0

Hold

Reset

Set

Invalid

S

Q

R

Timing Diagram

Set

Hold

Reset

Hold

Set

S

R

Q

Time

20

22 of 135

Latches

S R	Q(t+1)
0 0	Q=Q’=1
0 1	1
1 0	0
1 1	Q(t)

Invalid

Set

Reset

No change

S

Q

R

21

23 of 135

Latches

In latches, the change in the stored value may happen as soon as the input changes, i.e. at any time
This makes it difficult to analyze and design circuits
Add an input to control when the input is allowed to affect the stored value
Controlled/Clocked Latches

22

24 of 135

Controlled Latches

SR Latch with Control Input

C S R	Q(t+1)
0 x x	Q(t)
1 0 0	Q(t)
1 0 1	0
1 1 0	1
1 1 1	Q=Q’

No change

Reset

Set

Invalid

S

Q

R

C

Reset

Set

Control

(Clock)

23

25 of 135

Example 1

C S R	Q(t+1)
0 x x	Q(t)
1 0 0	Q(t)
1 0 1	0
1 1 0	1
1 1 1	Q=Q’

No change

Hold

Reset

Set

Invalid

S

Q

R

C

Timing Diagram

Set

No

Change

Reset

Hold

S

R

Q

C

Hold

No

Change

Output may change

24

26 of 135

Controlled Latches

D Latch (D = Data)

C D	Q(t+1)
0 x	Q(t)
1 0	0
1 1	1

No change

Reset

Set

C

Timing Diagram

D

Q

Output may change

D

Q

C

25

27 of 135

Controlled Latches

D Latch (D = Data)

C

Timing Diagram

D

Q

t

Output may change

C D	Q(t+1)
0 x	Q(t)
1 0	0
1 1	1

No change

Reset

Set

26

28 of 135

Latches Summary

S

Q

R

C

D

Q

C

+ve pulse-triggered D latch

+ve pulse-triggered SR latch

C = 0 🡪 Hold

C = 1 🡪 Change

S

Q

R

C

D

Q

C

-ve pulse-triggered D latch

-ve pulse-triggered SR latch

C = 1 🡪 Hold

C = 0 🡪 Change

27

29 of 135

Real Stuff

SN54/74LS75
4-BIT D LATCH

28

30 of 135

Controlled Latches

In controlled latches, the stored value may change as long as the latch is enabled
In other words, we say that controlled latches are level-triggered

What if we need to have more control such that the stored value is allowed to change at specific time?
Flip-flops!

C

29

31 of 135

Flip-Flops

Flip-Flops are edge-triggered storage elements
They allow the input to affect the stored value at the edge of the clock only

positive
negative

CLK

Positive Edge

(Rising)

CLK

Negative Edge

(Falling)

30

32 of 135

Flip-Flops

Master-Slave D Flip-Flop

D Latch

(Master)

D

C

Q

D Latch

(Slave)

D

C

Q

D

CLK

D

Q_Master

Q_Slave

Looks like it is negative edge-triggered

Master

Slave

31

33 of 135

Flip-Flops

Edge-Triggered D Flip-Flop

D

Q

D

Q

Positive Edge

Negative Edge

32

34 of 135

Flip-Flops

JK Flip-Flop

J

Q

K

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

Hold

Reset

Set

Toggle

33

35 of 135

Flip-Flops

T Flip-Flop

J

Q

K

T

D

Q

T

Q

T	Q(t+1)
0	Q(t)
1	Q’(t)

Hold

Toggle

34

36 of 135

Flip-Flop Characteristic Tables (For Analysis)

D

Q

D	Q(t+1)
0	0
1	1

Reset

Set

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

Hold

Reset

Set

Toggle

J

Q

K

T

Q

T	Q(t+1)
0	Q(t)
1	Q’(t)

Hold

Toggle

35

37 of 135

Flip-Flop Characteristic Tables (For Analysis)

D

Q

J

Q

K

T

Q

D	Q(t+1)
0	0
1	1

Reset

Set

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

Hold

Reset

Set

Toggle

T	Q(t+1)
0	Q(t)
1	Q’(t)

Hold

Toggle

36

38 of 135

Example 2

Clock

T

Q

Hold

Toggle

T

Q

Clock

Toggle

T	Q(t+1)
0	Q(t)
1	Q’(t)

Hold

Toggle

37

39 of 135

Flip-Flop Characteristic Equations (For Analysis)

D

Q

D	Q(t+1)
0	0
1	1

Q(t+1) = D

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

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

J

Q

K

T

Q

T	Q(t+1)
0	Q(t)
1	Q’(t)

Q(t+1) = T ⊕ Q

38

40 of 135

Flip-Flop Characteristic Equations

Analysis / Derivation

J

Q

K

J	K	Q(t)	Q(t+1)
0	0	0	0
0	0	1	1
0	1	0
0	1	1
1	0	0
1	0	1
1	1	0
1	1	1

No change

Reset

Set

Toggle

39

41 of 135

Flip-Flop Characteristic Equations

Analysis / Derivation

J

Q

K

J	K	Q(t)	Q(t+1)
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	0
1	0	0
1	0	1
1	1	0
1	1	1

No change

Reset

Set

Toggle

40

42 of 135

Flip-Flop Characteristic Equations

Analysis / Derivation

J

Q

K

J	K	Q(t)	Q(t+1)
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	0
1	0	0	1
1	0	1	1
1	1	0
1	1	1

No change

Reset

Set

Toggle

41

43 of 135

Flip-Flop Characteristic Equations

Analysis / Derivation

J

Q

K

J	K	Q(t)	Q(t+1)
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	0
1	0	0	1
1	0	1	1
1	1	0	1
1	1	1	0

No change

Reset

Set

Toggle

42

44 of 135

Flip-Flop Characteristic Equations

Analysis / Derivation

J

Q

K

J	K	Q(t)	Q(t+1)
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	0
1	0	0	1
1	0	1	1
1	1	0	1
1	1	1	0

			K
			K
	0	1	0	0
J	1	1	0	1
		Q
		Q

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

43

45 of 135

Exercise

Derive the characteristic table for the T-FF

T	Q(t+1)
0	Q(t)
1	Q’(t)

T	Q(t)	Q(t+1)
0	0
0	1
1	0
1	1

44

46 of 135

Flip-Flops with Direct Inputs

In practice, it is required to initialize or to force the stored value to take some value independent of the clock, i.e., asynchronously.
Asynchronous Reset Input

D

Q

R

Reset

D	CLK	Q(t+1)

1	0	↑	0

1	1	↑	1

0	x	x	0

45

47 of 135

Flip-Flops with Direct Inputs

Asynchronous Preset and Clear

		D	CLK	Q(t+1)
1	0	x	x	0
0	1	x	x	1
1	1	0	↑	0
1	1	1	↑	1

D

Q

CLR

Reset

PR

Preset

46

48 of 135

Example 3

D

Q

CLR

Reset

PR

Preset

Clock

D

Q

Preset

Reset

Output changed without edges due to direct inputs

47

49 of 135

Example 4

Assume negative edge triggered D-FF

48

50 of 135

Direct Inputs

D

Q

CLR

Reset

PR

Preset

D

Q

CLR

Reset

PR

Preset

+ve Edge-triggered D-FF with active-high direct inputs

+ve Edge-triggered D-FF with active-low direct inputs

49

51 of 135

Real Stuff

SN74F74
DUAL POSITIVE-EDGE-TRIGGERED D-TYPE FLIP-FLOPS WITH CLEAR AND PRESET

50

52 of 135

Real Stuff

SN74LS76A
DUAL J-K FLIP-FLOPS WITH PRESET AND CLEAR

51

53 of 135

Analysis of Sequential Circuits

52

54 of 135

Analysis of Clocked Sequential Circuits

Given a synchronous sequential circuit, we want to determine the output(s) and the next state for each possible combination of the input(s) and the present state

Clock

Combinational

Circuit

Memory�Elements

Inputs

Outputs

m

n

X_i

Y_r

Y_r = F_r(Q_k-1,Q_k-2, … , Q₀,X_n-1, , … , X₀)

k

Q_j(t)

Present

State

Q_j(t+1)

Q_j = G_j(Q_k-1,Q_k-2, … , Q₀,X_n-1, , … , X₀)

53

55 of 135

Analysis of Clocked Sequential Circuits

The State

State = Values of all Flip-Flops
Number of states = 2^{Number of FFs}

State Variables

Possible States

A B = 0 0

A B = 0 1

A B = 1 0

A B = 1 1

54

56 of 135

Analysis of Clocked Sequential Circuits

Remember!

Present State (PS) is the current value in the FFs
Next State (NS) is the value to be stored once the edge is received. It becomes the stored value after the edge (after some delay).

55

57 of 135

Analysis of Clocked Sequential Circuits

Analysis Steps

From circuit, obtain the logic expressions for the FFs inputs and the output(s) as a function of the external inputs and PS variables.
The next state equations are determined based on the characteristic equation/table of each FF in the circuit
Using these equations, we can derive the State Table

It is similar to the truth table
The input section has the PS variables and the external inputs
The output section has the NS variables and the output(s)
Determine the next state and the outputs using the characteristic equations we determined earlier in steps 1 and 2.

56

58 of 135

Example 5 – Analysis of Sequential Circuits

FFs Input Equations

D_A = A(t) +x(t)

= A + x

y(t) = A’(t) x(t)

= A’ x

Output Equations

57

59 of 135

Example 5 – Analysis of Sequential Circuits

State Equations

For D FF, Q(t+1) = D

A(t+1) = D_A

= A(t) +x(t)

= A + x

58

60 of 135

Example 5 – Analysis of Sequential Circuits

State Table (Transition Table)

Present State	Input	Next State	Output
A(t)	x	A(t+1)	y
0	0
0	1
1	0
1	1

t+1

t

0 0

1 1

1 0

A(t+1) = A + x

y(t) = A’ x

59

61 of 135

Example 6 – Analysis of Sequential Circuits

FFs Input Equations

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

= A x + B x

D_B = A’(t) x(t)

= A’ x

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

= (A + B) x’

Output Equations

60

62 of 135

Example 6 – Analysis of Sequential Circuits

State Equations

For D FF, Q(t+1) = D

A(t+1) = D_A

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

= A x + B x

B(t+1) = D_B

= A’(t) x(t)

= A’ x

61

63 of 135

Example 6 - – Analysis of Sequential Circuits

State Table (Transition Table)

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

B(t+1) = A’ x

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

Present State		Input	Next State		Output
A	B	x	A	B	y
0	0	0
0	0	1
0	1	0
0	1	1
1	0	0
1	0	1
1	1	0
1	1	1

t+1

t

0 0 0

0 1 0

0 0 1

1 1 0

0 0 1

1 0 0

0 0 1

1 0 0

62

64 of 135

Example 6 – Analysis of Sequential Circuits

State Table (Transition Table)

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

B(t+1) = A’ x

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

Present State		Next State				Output
Present State		x = 0		x = 1		x = 0	x = 1
A	B	A	B	A	B	y	y
0	0	0	0	0	1	0	0
0	1	0	0	1	1	1	0
1	0	0	0	1	0	1	0
1	1	0	0	1	0	1	0

t+1

t

63

65 of 135

Analysis of Clocked Sequential Circuits

State Diagram

A graphical representation of the state table
Each state is represented by a circle
A transition between state is represented by an arc
The arc is labeled by the input value that causes the transition and the value of the output

AB

input/output

64

66 of 135

Analysis of Clocked Sequential Circuits

State Diagram

0 0

1 0

0 1

1 1

0/0

0/1

1/0

0/1

AB

input/output

Present State		Next State				Output
Present State		x = 0		x = 1		x = 0	x = 1
A	B	A	B	A	B	y	y
0	0	0	0	0	1	0	0
0	1	0	0	1	1	1	0
1	0	0	0	1	0	1	0
1	1	0	0	1	0	1	0

65

67 of 135

Example 7 – Analysis of Sequential Circuits

D Flip-Flops

D

Q

x

CLK

y

A

Present State	Input		Next State
A	x	y	A
0	0	0
0	0	1
0	1	0
0	1	1
1	0	0
1	0	1
1	1	0
1	1	1

0

1

0

1

0

1

0

1

00,11

01,10

A(t+1) = D_A= A ⊕ x ⊕ y

0

1

11

01

10

00

11

00

66

68 of 135

Example 8 – Analysis of Sequential Circuits

JK Flip-Flops

J_A= B K_A= B x’

J_B= x’ K_B= A ⊕ x

A(t+1) = J_AQ’_A+ K’_AQ_A

= A’B + AB’ + Ax

B(t+1) = J_BQ’_B+ K’_BQ_B

= B’x’ + ABx + A’Bx’

Present State		I/P	Next State		Flip-Flop�Inputs
A	B	x	A	B	J_A	K_A	J_B	K_B
0	0	0
0	0	1
0	1	0
0	1	1
1	0	0
1	0	1
1	1	0
1	1	1

0 0 1 0

0 0 0 1

1 1 1 0

1 0 0 1

0 0 1 1

0 0 0 0

1 1 1 1

1 0 0 0

0 1

0 0

1 1

1 0

1 1

1 0

0 0

1 1

For JK FF, Q(t+1) = JQ’ + K’Q

67

69 of 135

Example 8 – Analysis of Sequential Circuits

JK Flip-Flops

Present State		I/P	Next State		Flip-Flop�Inputs
A	B	x	A	B	J_A	K_A	J_B	K_B
0	0	0
0	0	1
0	1	0
0	1	1
1	0	0
1	0	1
1	1	0
1	1	1

0 0 1 0

0 0 0 1

1 1 1 0

1 0 0 1

0 0 1 1

0 0 0 0

1 1 1 1

1 0 0 0

0 1

0 0

1 1

1 0

1 1

1 0

0 0

1 1

0 0

1 1

0 1

1 0

1

0

1

0

1

0

1

68

70 of 135

Example 9 – Analysis of Sequential Circuits

T Flip-Flops

T_A= B x T_B= x

y = A B

A(t+1) = T_AQ’_A+ T’_AQ_A

= AB’ + Ax’ + A’Bx

B(t+1) = T_BQ’_B+ T’_BQ_B

= x ⊕ B

Present State		I/P	Next State		F.F�Inputs		O/P
A	B	x	A	B	T_A	T_B	y
0	0	0
0	0	1
0	1	0
0	1	1
1	0	0
1	0	1
1	1	0
1	1	1

0 0

0 1

0 0

1 1

0 0

0 1

0 0

1 1

0 0

0 1

1 0

1 1

0 0

0

1

For T FF, Q(t+1) = T ⊕ Q(t)

69

71 of 135

Example 9 – Analysis of Sequential Circuits

T Flip-Flops

Present State		I/P	Next State		F.F�Inputs		O/P
A	B	x	A	B	T_A	T_B	y
0	0	0
0	0	1
0	1	0
0	1	1
1	0	0
1	0	1
1	1	0
1	1	1

0 0

0 1

0 0

1 1

0 0

0 1

0 0

1 1

0 0

0 1

1 0

1 1

0 0

0

1

0 0

0 1

1 1

1 0

0/0

1/0

0/0

1/0

1/1

0/0

0/1

70

72 of 135

Mealy and Moore Models

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

Mealy

For the same state,�the output changes with the input

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

Moore

For the same state,�the output does not change with the input

71

73 of 135

Mealy and Moore Models

Mealy Machine

Mealy type output depends on state and input

State

In/out

01

1/0

to next state

Moore Machine

Moore type output depends only on state

State

out

in

to next state

01

1

72

74 of 135

Moore State Diagram

State / Output

0 0 / 0

0 1 / 0

1 1 / 1

1 0 / 0

0

1

0

1

73

75 of 135

Timing Diagram (Moore Circuit)

0 0 / 0

0 1 / 0

1 1 / 1

1 0 / 0

0

1

0

1

CLK

State

A

B

y

x

No effect

0

1

0

1

0

1

A

B

x

y

74

76 of 135

Timing Diagram (Mealy Circuit)

0 0

0 1

1 1

1 0

0/0

1/0

1/1

0/0

1/1

1/0

CLK

State

A

B

y

x

1

0

A

B

x

y

75

77 of 135

Execise

Assuming that the present state Q₂Q₁Q₀ = 100. Determine the state after the first rising edge on the clock.

76

78 of 135

Design of Synchronous Sequential Circuits

77

79 of 135

Design of Synchronous Sequential Circuits

Given a state table, state diagram, or a circuit description, it is required to determine the number of FFs and design the combinational part

Clock

Combinational

Circuit

Memory�Elements

Inputs

Outputs

m

n

X_i

Y_r

Y_r = F_r(Q_k-1,Q_k-2, … , Q₀,X_n-1, , … , X₀)

k

Q_j(t)

Present

State

Q_j(t+1)

Q_j = G_j(Q_k-1,Q_k-2, … , Q₀,X_n-1, , … , X₀)

78

80 of 135

Flip-Flop Excitation Tables

In designing sequential circuits, we usually know the transition between states.
We need to know what should be the FFs input value to cause this transition.
Excitation Tables: These tables tell what value(s) should be placed on the FFs inputs to obtain Q(t+1) from Q(t) when the edge appears at clock

Present State	Next State	F.F. Input
Q(t)	Q(t+1)	D
0	0
0	1
1	0
1	1

0

1

0

1

D-FF Excitation Table

D

Q

79

81 of 135

Flip-Flop Excitation Tables

Present State	Next State	F.F. Input
Q(t)	Q(t+1)	J	K
0	0
0	1
1	0
1	1

0 0 (No change)

0 1 (Reset)

0 x

1 x

x 1

x 0

1 0 (Set)

1 1 (Toggle)

0 1 (Reset)

1 1 (Toggle)

0 0 (No change)

1 0 (Set)

Q(t)	Q(t+1)	T
0	0
0	1
1	0
1	1

0

1

0

T-FF Excitation Table

JK-FF Excitation Table

T = 0 (No change)

T = 1 (Toggle)

T = 0 (Hold)

80

82 of 135

Example 10

Design the circuit with the following state table. Use D flip-flops.

One input 🡺 x

One output 🡺 y

Four states 🡺 Two FFs

State Variables🡺 A and B

Two FFs inputs 🡺 D_A and D_B

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

81

83 of 135

Example 10

Using D FFs

D

Q

D

Q

????

y(t)

A(t)

B(t)

Clock

x(t)

D_A

D_B

82

84 of 135

Example 10

Determine the values of D_A and D_B based on the required transitions and using the D-FFexcitation table

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

F.F�Inputs
D_A	D_B

Present State	Next State	F.F. Input
Q(t)	Q(t+1)	D
0	0	0
0	1	1
1	0	0
1	1	1

0

1

0

1

0

1

0

1

0

D-FF Excitation Table

83

85 of 135

Example 10

Simplify D_A, D_B and y as function of x, A, and B

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

F.F�Inputs
D_A	D_B

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

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

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

D_A = A(t) x

0

1

0

1

0

1

0

1

0

D_B = B’(t)x + B(t)x’

y = A(t) + x

84

86 of 135

Example 10

Using D FFs

D

Q

D

Q

y(t)

A(t)

B(t)

Clock

x(t)

D_A

D_B

D_A = A(t) x

D_B = B’(t)x + B(t)x’

y = A(t) + x

85

87 of 135

Example 10

Let’s try to design the circuit using T FFs

T

Q

T

Q

????

y(t)

A(t)

B(t)

Clock

x(t)

T_A

T_B

86

88 of 135

Example 10

Determine the values of T_A and T_B based on the required transitions and using the T-FFexcitation table

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

F.F�Inputs
T_A	T_B

Present State	Next State	F.F. Input
Q(t)	Q(t+1)	T
0	0	0
0	1	1
1	0	1
1	1	0

0

1

0

1

0

1

0

1

0

1

0

1

T-FF Excitation Table

87

89 of 135

Example 10

Simplify T_A, T_B and y as function of x, A, and B

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

F.F�Inputs
T_A	T_B

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

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

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

T_A = A(t) x’

T_B = x

y = A(t) + x

0

1

0

1

0

1

0

1

0

1

0

1

88

90 of 135

Example 10

Using T FFs

T

Q

T

Q

y(t)

A(t)

B(t)

Clock

x(t)

T_A

T_B

T_A = A(t) x’

T_B = x

y = A(t) + x

89

91 of 135

Example 10

Let’s try using JK FFs

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

F.F�Inputs
J_A	K_A	J_B	K_B

Q(t)	Q(t+1)	J	K
0	0	0	x
0	1	1	x
1	0	x	1
1	1	x	0

JK-FF Excitation Table

90

92 of 135

Example 10

A(t)

Clock

J

Q

K

B(t)

J

Q

K

y(t)

x(t)

91

93 of 135

Example 11

Design the circuit that counts continuously through the pattern 0, 2, 1, 3, 0, 2, 1, 3, … . Use JK flip-flops.

No input 🡺 Free running

Output 🡺 Count value (Q₁ and Q₀)

Four states 🡺 Two FFs

State Variables🡺 Q₁ and Q₀

Four FFs inputs 🡺 J₁, K₁, J₀and K₀

2

0

1

3

92

94 of 135

Example 11

????

Q₁(t)

Clock

J1

Q

K1

Q₀(t)

J0

Q

K0

93

95 of 135

Example 11

Present State		Next State
Q1	Q0	Q1	Q0
0	0	1	0
0	1	1	1
1	0	0	1
1	1	0	0

F.F�Inputs
J1	K1	J0	K0
1	x	0	x
1	x	x	0
x	1	1	x
x	1	x	1

1	1
x	x

Q1

Q0

x	x
1	1

Q1

Q0

0	x
1	x

Q1

x	0
x	1

Q1

J₁ = 1

K₁ = 1

J₀ = Q₁

K₀ = Q₁

Q(t)	Q(t+1)	J	K
0	0	0	x
0	1	1	x
1	0	x	1
1	1	x	0

JK-FF Excitation Table

94

96 of 135

Example 11

Q₁(t)

Clock

J1

Q

K1

Q₀(t)

J0

Q

K0

1

J₁ = 1

K₁ = 1

J₀ = Q₁

K₀ = Q₁

95

97 of 135

Example 12

Design a counter that has one input and counts such that:

If the input is 0, the counter counts 0, 1, 2, 3, 0, 1, 2, ….
If the input is 1, the counter pauses

One input 🡺 x

Output 🡺 Count value (Q₁ and Q₀)

Four states 🡺 Two FFs

State Variables🡺 Q₁ and Q₀

1

0

2

3

0

1

96

98 of 135

Example 12

Solution – Using T-FF

Present State		IN	Next State
Q₁(t)	Q₀(t)	x	Q₁(t+1)	Q₀(t+1)

1	1	0	0	0
1	1	1	1	1

0	0	0	0	1
0	0	1	0	0

0	1	0	1	0
0	1	1	0	1

1	0	0	1	1
1	0	1	1	0

T₁	T₀

97

99 of 135

Example 12

Solution – Logic diagram using T-FF

T

Q

T

Q

Q1(t)

Q0(t)

Clock

T₁

T₀

98

100 of 135

Exercise

Design the counter in Example 12 using JK FFs

PS		IN	NS
Q₁	Q₀	x	Q₁+	Q₀+

1	1	0	0	0
1	1	1	1	1

0	0	0	0	1
0	0	1	0	0

0	1	0	1	0
0	1	1	0	1

1	0	0	1	1
1	0	1	1	0

J₁	K₁

J₀	K₀

99

101 of 135

Exercise

Design the JK flip-flop using D flip-flop

PS	IN		NS
Q	J	K	Q+

0	0	0
0	0	1
0	1	0
0	1	1
1	0	0
1	0	1
1	1	0
1	1	1

D

100

102 of 135

Exercise

Design the T flip-flop using JK flip-flop

PS	IN	NS
Q(t)	T	Q+

0	0
0	1
1	0
1	1

J

K

101

103 of 135

Example 13

Design a serial adder. Use D-FF.

No

Carry

x

y

Sum

Reset

00/0

01/1

10/1

11/1

11/0

00/1

01/0

10/0

102

104 of 135

Example 13

Solution

PS	IN		NS	Out
Q	x	y	Q+	sum

0	0	0	0
0	1	0	1
1	0	0	1
1	1	1	0

1	0	0	0	1
1	0	1	1	0
1	1	0	1	0
1	1	1	1	1

Need to assign binary codes to the states!

No Carry 🡪 0

Carry State 🡪 1

D

103

105 of 135

Example 13

Solution – Logic Diagram

D

Q

sum

x

y

104

106 of 135

Exercise

Design the serial adder as a Moore circuit.

105

107 of 135

Exercise

Can you design the serial adder without deriving the state table?

Use a full adder and one flip-flop to store the carry

106

108 of 135

Real Stuff

MC14032B
Triple Serial Adders (positive edge)

107

109 of 135

Example 14

Design a serial 2s complementer. Use JK FF.

First 1

has not

arrived

First 1

Has arrived

x

y

Reset

0/0

1/1

1/0

0/1

108

110 of 135

Example 14

Solution

PS	IN	NS	OUT
Q(t)	x	Q+	y

0	0	0	0
0	1	1	1

1	0	1	1
1	1	1	0

Need to assign binary codes to the states!

First 1 has not arrived 🡪 0

First 1 arrived 🡪 1

J

K

109

111 of 135

Example 14

Solution – Logic diagram

110

112 of 135

Exercise

Design the serial 2s complementer as a Moore circuit.

111

113 of 135

Example 15

Design a circuit that samples an input continuously and outputs 1 as long as the circuit has seen 3 consecutive ones (sequence detector).

S₀ / 0

S₁ / 0

S₃ / 1

S₂ / 0

0

1

0

1

0

1

State	A B
S₀	0 0
S₁	0 1
S₂	1 0
S₃	1 1

Reset

Clock

Input

Output

112

114 of 135

Example 15

Present State		Input	Next State		Output
A	B	x	A	B	y
0	0	0
0	0	1
0	1	0
0	1	1
1	0	0
1	0	1
1	1	0
1	1	1

0 0 0

0 1 0

0 0 0

1 0 0

0 0 0

1 1 0

0 0 1

1 1 1

S₀ / 0

S₁ / 0

S₃ / 1

S₂ / 0

0

1

0

1

0

1

Detect 3 or more consecutive 1’s (Sequence detector)

113

115 of 135

Example 15

Present State		Input	Next State		Output
A	B	x	A	B	y
0	0	0
0	0	1
0	1	0
0	1	1
1	0	0
1	0	1
1	1	0
1	1	1

0 0 0

0 1 0

0 0 0

1 0 0

0 0 0

1 1 0

0 0 1

1 1 1

A(t+1) = D_A(A, B, x)

= ∑ (3, 5, 7)

B(t+1) = D_B(A, B, x)

= ∑ (1, 5, 7)

y(A, B, x) = ∑ (6, 7)

Synthesis using D Flip-Flops

Detect 3 or more consecutive 1’s (Sequence detector)

114

116 of 135

Example 15

D_A(A, B, x) = ∑ (3, 5, 7)

= A x + B x

D_B (A, B, x) = ∑ (1, 5, 7)

= A x + B’ x

y(A, B, x) = ∑ (6, 7)

= A B

Synthesis using D Flip-Flops

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

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

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

Detect 3 or more consecutive 1’s (Sequence detector)

115

117 of 135

Example 15

D_A = A x + B x

D_B = A x + B’ x

y = A B

Synthesis using D Flip-Flops

116

118 of 135

Example 15

Present State		Input	Next State		Flip-Flop Inputs
A	B	x	A	B	J_A	K_A	J_B	K_B
0	0	0	0	0
0	0	1	0	1
0	1	0	0	0
0	1	1	1	0
1	0	0	0	0
1	0	1	1	1
1	1	0	0	0
1	1	1	1	1

0 x

1 x

x 1

x 0

x 1

x 0

J_A(A, B, x) = ∑ (3)

d_JA(A, B, x) = ∑ (4,5,6,7)

K_A(A, B, x) = ∑ (4, 6)

d_KA(A, B, x) = ∑ (0,1,2,3)

J_B(A, B, x) = ∑ (1, 5)

d_JB(A, B, x) = ∑ (2,3,6,7)

K_B(A, B, x) = ∑ (2, 3, 6)

d_KB(A, B, x) = ∑ (0,1,4,5)

Synthesis using JK F.F.

0 x

1 x

x 1

0 x

1 x

x 1

x 0

117

119 of 135

Example 15

J_A= B x K_A= x’

J_B= x K_B= A’ + x’

Synthesis using JK Flip-Flops

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

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

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

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

118

120 of 135

Example 15

Present State		Input	Next State		F.F. Input
A	B	x	A	B	T_A T_B
0	0	0	0	0
0	0	1	0	1
0	1	0	0	0
0	1	1	1	0
1	0	0	0	0
1	0	1	1	1
1	1	0	0	0
1	1	1	1	1

0

1

0

1

0

Synthesis using T Flip-Flops

0

1

0

1

0

T_A(A, B, x) = ∑ (3, 4, 6)

T_B(A, B, x) = ∑ (1, 2, 3, 5, 6)

119

121 of 135

Example 15

T_A= A x’ + A’ B x

T_B= A’ B + B ⊕ x

Synthesis using T Flip-Flops

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

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

120

122 of 135

Exercise

Design the sequence detector in example 15 as a Mealy circuit.

121

123 of 135

State Assignment

When we assign binary codes to state names, we may use different options

Counting order assignment:

00, 01, 10, 11

Gray code assignment:

00, 01, 11, 10

One-hot state assignment

0001, 0010, 0100, 1000

Different options result in different circuits usually
Cost!

122

124 of 135

Design with Unused States

Unused states

Number of states < 2^{Number of FFs}
For example, three states need 2 FFs which can provide 4 states?

How to deal with when designing sequential circuits when there are unused states?
Three options:

Assume the next state for the unused state to be don’t care
Force the next state for the unused state to be one of the used states
Include a special output to indicate that the present state is unused. This output can change the state asynchronously through direct inputs of the state flip-flops

123

125 of 135

Example 16

Use D-FFs to design the sequential circuit that implements the following state table. Note that state (11) is not used.

A	B	x	A+	B+
0	0	0	1	0
0	0	1	0	0
0	1	0	0	1
0	1	1	1	0
1	0	0	0	0
1	0	1	0	1

1	1	0	?	?
1	1	1	?	?

Unused State

124

126 of 135

Example 16

Approach 1. Assume next state as don’t care.

A	B	x	A+	B+
0	0	0	1	0
0	0	1	0	0
0	1	0	0	1
0	1	1	1	0
1	0	0	0	0
1	0	1	0	1

1	1	0	X	X
1	1	1	X	X

D_A	D_B

		B
		B

A
	x
	x

		B
		B

A
	x
	x

D_A =

D_B =

What if the PS is 11 and x is 1?

125

127 of 135

Example 16

Approach 2. Assume next state as one of the used states.

A	B	x	A+	B+
0	0	0	1	0
0	0	1	0	0
0	1	0	0	1
0	1	1	1	0
1	0	0	0	0
1	0	1	0	1

1	1	0	0	0
1	1	1	0	0

D_A	D_B

		B
		B

A
	x
	x

		B
		B

A
	x
	x

D_A =

D_B =

Cost of CLC?

When does the circuit is allowed to change PS?

126

128 of 135

Example 16

Approach 3. Force the circuit to go to state 00 asynchronously whenever it enters state 11.

Assume that you have designed your circuit using the first or second approach
Design a small circuit to detect the unused state and use the direct inputs

D

Q

S

R

D

Q

S

R

CLC

A(t)

B(t)

x

B(t)

127

129 of 135

Exercises

128

130 of 135

131 of 135

Exercises

*	Show that the characteristic equation for the complement output of a JK flip-flop is Q’(t+1) = J’Q’+ K Q

130

132 of 135

Exercises

*	A sequential circuit with two D flip-flops, A and B; two inputs, x and y; and one output, z, is specified by the following next-state and output equations: A(t+1) = x’ y + x A B(t+1) = x’ B + x A z = B (a) Draw the logic diagram of the circuit. (b) List the state table for the sequential circuit. (c) Draw the corresponding state diagram.

131

133 of 135

Exercises

*

132

134 of 135

Exercises

*	A sequential circuit has two JK flip-flops A and B and one input x. The circuit is described by the following flip-flop input equations: J_A = x K_A = B’ J_B = x K_B = A (a) Derive the state equations A(t+1) and B(t+1) by� substituting the input equations for the J and K� variables. (b) Draw the state diagram of the circuit.

133

135 of 135

Exercises

134