Digital Logic Design

-FSM Analysis and Synthesis-

 Types of Problems in Sequential Circuits (FSM)

Analysis: Starting from a circuit, create a state diagram

Synthesis / Design: Starting from a statement / state
diagram, create a circuit

Instr: Dr. Awais M. Kamboh. 2

 Analysis of Sequential Circuits

Steps involved in analysis

From the circuit, derive the FF input equations
Using characteristic table / equation derive the next
state equations
Create the state transition table using present
state, present input, next state, present output
Create the state diagram from the table

Instr: Dr. Awais M. Kamboh. 3

 EXAMPLE: ANALYSIS – D FLIPFLOP

Instr: Dr. Awais M. Kamboh. 4

 Flip Flop Input Equations

The part of the circuit that generates the inputs to flip flops
is described algebraically by a set of Boolean functions
called flip flop input equations (excitation equations).
The notation of an input equation consists of the flip flop
input symbol with a subscript to denote the name of the flip
flop output
DQ = x + y
In our example the following input equations would be used:
DA = Ax + Bx
DB = A′x
Y = (A + B)x′

Instr: Dr. Awais M. Kamboh. 5

 Example: Analysis With D Flip Flops
We start analysis of a sequential circuit described by the
following input equation:
DA = A  x  y
The symbol DA implies a D flip flop with output A.
The x and y variables are the inputs to the circuit.
No outputs are given so the output is implied to come from
the output of the flip flop.
The state table has one column for flip-flop A, two columns
for the two inputs, and one column for the next state of A.
The binary numbers under Axy are listed from 000 through
111.
The next-state values are obtained from the state equation
A(t+1)=A  x  y
Instr: Dr. Awais M. Kamboh. 6
 Example: Analysis With D Flip Flops

Input Equation: DA = A  x  y
Next-State Equation: A(t+1) = A  x  y

Instr: Dr. Awais M. Kamboh. 7

 Analysis Notes

With D type flip flops, the state equation is the same as the
input equation.
With JK and T flip flops, it is necessary to refer to the
corresponding characteristic table or characteristic equation
to obtain the next state values.

Instr: Dr. Awais M. Kamboh. 8

 EXAMPLE: ANALYSIS – JK FLIPFLOP

Instr: Dr. Awais M. Kamboh. 9

 JK and T Flip Flop Analysis

For a D type flip-flop, the state equation is same as the input

equation. When other than the D type flip-flop is used, such
as JK or T, it is necessary to refer to the corresponding
characteristic table or characteristic equation to obtain the
next-state values.
The next-state values of a sequential circuit that uses flip
flops such as JK or T type can be derived using the
following procedure:
Determine the flip flop input equations in terms of the
present state and input variables
List the binary values of each input equation
Use the corresponding flip flop characteristic table to
determine the next state values in the state table
Instr: Dr. Awais M. Kamboh. 10
 Example: JK Analysis – Input Equation

JA = B; JB = x′
KA = Bx′; KB = A′x + Ax′ = A  x
Instr: Dr. Awais M. Kamboh. 11
 Example: JK Analysis – State Table

Flip Flop Input

• JA = B
• JB = x′
• KA = Bx′
• KB = A′x + Ax′ = A  x

Instr: Dr. Awais M. Kamboh. 12

 Example: JK Analysis – State Table

Flip Flop Input

• JA = B
• JB = x′
• KA = Bx′
• KB = A′x + Ax′ = A  x

Instr: Dr. Awais M. Kamboh. 13

 Example: JK Analysis – Next State Equation
To find next state, either use characteristic table or use characteristic
equation
Input Equations Characteristic Equation
• JA = B Q(t+1) = JQ’(t) + K’Q(t)
• JB = x′
• KA = Bx′ Next State Equations
• KB = A′x + Ax′ = A  x
A(t+1) = JA A′+ KA′ A
Characteristic Table = BA′+(Bx′)′A
= A′B+AB′+Ax
B(t+1) = JB B′+ KB′ B
= x′B′+(A  x)′B
= B′x′+ABx+A′Bx′

Instr: Dr. Awais M. Kamboh. 14

 Example: JK Analysis – State Table

Flip-Flop Inputs

A(t+1) = A′B+AB′+Ax
B(t+1) = B′x′+ABx+A′Bx′

Instr: Dr. Awais M. Kamboh. 15

 Example: JK Analysis – State Diagram

Instr: Dr. Awais M. Kamboh. 16

 EXAMPLE: ANALYSIS – T FLIPFLOP

Instr: Dr. Awais M. Kamboh. 17

 T Flip Flop Analysis

Analysis of a sequential circuit with T flip flops follows the

same procedure outlined for JK flip flops.
The next state values in the state table can be obtained
either by using the characteristic table or the characteristic
equation
Q(t + 1) = T  Q = T’Q + TQ’

Instr: Dr. Awais M. Kamboh. 18

 T Flip Flop Analysis Example

• TA = Bx
• TB = x
• Y = AB

Instr: Dr. Awais M. Kamboh. 19

 T Flip Flop Analysis State Table

• TA = Bx
• TB = x
• Y = AB
• A(t + 1) = TA  A = Bx  A
• B(t + 1) = TB  B = x  B

Instr: Dr. Awais M. Kamboh. 20

 T Flip Flop Analysis State Diagram

Instr: Dr. Awais M. Kamboh. 21

 EXAMPLE: SYNTHESIS – D FLIPFLOP
SEQUENCE GENERATOR

Instr: Dr. Awais M. Kamboh. 22

 Synthesis / Design of Sequential Circuits

Steps involved in design

Derive a state diagram
Encode the states (assign binary values to them)
Obtain the binary coded state table
Choose the type of flip flops to be used
Derive the next state equation
Derive the flip flop input equations and output
equations using excitation table
Draw the logic / circuit diagram

Instr: Dr. Awais M. Kamboh. 23

 Synthesis Example – State Diagram & Table

Synthesis: Start from a statement to create a circuit

Question: Implement a simple count sequence: 100, 010,

101, 011, 110

Note three things

1. What are the inputs

2. What are the outputs
3. Is this a Mealy machine or Moore machine

Instr: Dr. Awais M. Kamboh. 24

 Synthesis Example – State Diagram & Table

Solution:
Create a state diagram: 100, 010, 101, 011, 110

010 100

101 110

011

Instr: Dr. Awais M. Kamboh. 25

 Synthesis Example – State Diagram & Table

Derive the state transition table from the state diagram

010 100

101 110

011

000, 001, 111 are invalid states, so the next state is ‘don’t care’

Instr: Dr. Awais M. Kamboh. 26

 Flip Flop input Equ - Synthesis with D Flip-flop

Find next state equations

BA BA
C+ 00 01 11 10
B+ A+ BA
C C 00 01 11 10 C 00 01 11 10
0 X X 1 1 0 X X 1 0 0 X X 0 1
1 0 0 X 1 1 1 1 X 0 1 0 1 X 0

Next-State Equations
C(t+1) = C+ = B
B(t+1) = B+ = A + B’
A(t+1) = A+ = A’C’ + AC

Instr: Dr. Awais M. Kamboh. 27

 Flip Flop input Equ - Synthesis with D Flip-flop

Derive input equations for flip-flops

For this example we chose D flip-flops
For D flip-flops, Input equation is the same as next-state
equation

Next-State Equations Input Equ. for D Flip-flops

C(t+1) = C+ = B DC = B
B(t+1) = B+ = A + B’ DB = A + B’
A(t+1) = A+ = A’C’ + AC DA = A’C’ + AC

Instr: Dr. Awais M. Kamboh. 28

 Circuit Diagram - Synthesis with D Flip-flop

Create circuit using flip-flops and input equations.

For D Flip-flops
DC = B
DB = A + B’
DA = A’C’ + AC

Instr: Dr. Awais M. Kamboh. 29

 Self-starting FSMs
Analysis after synthesis
If we perform analysis on the circuit we just created, we
get a different state diagram.
This is because we marked next-state as ‘don’t care’ for
invalid states. The invalid states have random transitions.
The original sequence is still valid.

In this implementation, states

001 010 100 000, 001 & 111 are invalid.
• 000, 001 transition to valid
111 states, but 111 does not
101 110
transition to any valid
011 state.
000

Instr: Dr. Awais M. Kamboh. 30

 Self-starting FSMs
Start-up states
At power-up, FSM may be start in a valid or invalid state
Self-starting solution: Design FSM so that all the invalid
states eventually transition to a valid state.
Design must guarantee that it (eventually) enters a valid
state

001 010 100

State 111 does not transition
111 101 110 to any valid state. Thus this is
not a self-starting solution.
011
000

Instr: Dr. Awais M. Kamboh. 31

 Self-starting FSMs

Self-starting solution
To make this solution self-starting, instead of using X in
the state table, the next state should be a valid state.

001 010 100

101 110

011
111 000

Instr: Dr. Awais M. Kamboh. 32

 EXAMPLE: SYNTHESIS – T FLIPFLOP
ODD/EVEN COUNTER

Instr: Dr. Awais M. Kamboh. 33

 Odd / Even Counter

Design a three bit binary counter

When a button is pressed it counts in the odd binary
number sequence and repeat
When the button is released it counts the even binary
number sequence and repeat

Note three things

1. What are the inputs

2. What are the outputs
3. Is this a Mealy machine or Moore machine

Instr: Dr. Awais M. Kamboh. 34

 State Diagram

If X=0, Count Even

If X=1, Count Odd

Instr: Dr. Awais M. Kamboh. 35

 Complete State Diagram

Draw all possible inputs for all possible states What if X changes
during counting.

If X=0, go to 000
If X=1, go to 001

Instr: Dr. Awais M. Kamboh. 36

 State Table – Synthesis with T Flip-Flop
Present State Input Next State Flip Flop Inputs
A B C X A+ B+ C+ TA TB TC
0 0 0 0 0 1 0
0 0 0 1 0 0 1
We know the present
0 0 1 0 0 0 0
state, we know the
0 0 1 1 0 1 1 next state.
0 1 0 0 1 0 0
0 1 0 1 0 0 1 But what FF inputs
0 1 1 0 0 0 0 will change the
0 1 1 1 1 0 1 present state to the
1 0 0 0 1 1 0
next state?
1 0 0 1 0 0 1
1 0 1 0 0 0 0
1 0 1 1 1 1 1
1 1 0 0 0 0 0
1 1 0 1 0 0 1
1 1 1 0 0 0 0
1 1 1 1 0 0 1
Instr: Dr. Awais M. Kamboh. 37
 Excitation Table

The design of sequential circuits other than D type flip

flops is complicated by the fact that input equations must
be derived indirectly from the state table.
It is necessary to derive a functional relationship
between the state table and the input equations.

During the design, we usually know the transition from

present to next state, but we need to find the flip flop
input conditions that will cause the required transition.
We need a table that lists the required inputs for a
given change of state, called an excitation table.

Instr: Dr. Awais M. Kamboh. 38

 Excitation Tables

Characteristic Table Excitation Table

If present input and present If present state and next

state are known, then what state are known, then what
will be next state is the present input.

Instr: Dr. Awais M. Kamboh. 39

 State Table – Synthesis with T Flip-Flop
Present State Input Next State Flip Flop Inputs
A B C X A+ B+ C+ TA TB TC
0 0 0 0 0 1 0 0 1 0
0 0 0 1 0 0 1 0 0 1
If ‘No change’ in
0 0 1 0 0 0 0 0 0 1
state, it means input
0 0 1 1 0 1 1 0 1 0 T is 0
0 1 0 0 1 0 0 1 1 0
0 1 0 1 0 0 1 0 1 1 If state toggles, it
0 1 1 0 0 0 0 0 1 1 means input T is 1
0 1 1 1 1 0 1 1 1 0
1 0 0 0 1 1 0 0 1 0
1 0 0 1 0 0 1 1 0 1
1 0 1 0 0 0 0 1 0 1
1 0 1 1 1 1 1 0 1 0
1 1 0 0 0 0 0 1 1 0
1 1 0 1 0 0 1 1 1 1
1 1 1 0 0 0 0 1 1 1
1 1 1 1 0 0 1 1 1 0
Instr: Dr. Awais M. Kamboh. 40
 Flip Flop Input Equ - Synthesis with T Flip-Flop

TA TB

TC

Instr: Dr. Awais M. Kamboh. 41

 Circuit Diagram – Synthesis with T Flip Flop

Instr: Dr. Awais M. Kamboh. 42

 EXAMPLE: SYNTHESIS – JK FLIPFLOP
SEQUENCE DETECTOR

Instr: Dr. Awais M. Kamboh. 43

 Design Statement

Design a circuit that detects a sequence of three or

more consecutive 1’s in a string of bits coming through
an input line (i.e., the input is a serial bit stream)

Note three things

1. What are the inputs

2. What are the outputs
3. Is this a Mealy machine or Moore machine

Instr: Dr. Awais M. Kamboh. 44

 A Sequence Detector

The following FSM detects a sequence of three ones.

S0 mean there is no 1, it
remains in S0 until a 1 arrives.
When first 1 arrives, it moves to
S1. The output remains 0.

In S1, if a zero arrives then the

sequence is broken, so move
back to S0, if a 1 arrives then
move to S2. Output is still 0.

Same in S2.

In S3, means 3 consecutive 1

have arrived, so output is 1.
Remain in S3 until a 0 arrives.

Instr: Dr. Awais M. Kamboh. 45

 State Encoding
The states are named S0, S1, S2, S3. They could be given
any other name, such as A, B, C, D.
But flipflops can only store 0 or 1. Thus the states have to
be encoded in 0s and 1s.
Total Number of states: 4
Number of bits (flipflops) needed to
represent 4 states: 2

Assign bits to each state, e.g.

S0 = 00
S1 = 01
S2 = 10
S3 = 11

You can choose any other order /

assignment if you want.

Instr: Dr. Awais M. Kamboh. 46

 State Table for Sequence Detector

A+ B+

• After state encoding, we can create the state transition

table according to the state diagram.

Instr: Dr. Awais M. Kamboh. 47

 Synthesizing Using D Flip Flops

The next step is to create a state table and then select

two D flip flops to represent the four states, labeling their
outputs as A and B.
There is one input, x, and one output, y, representing the
input sequence and the output value respectively.
Remember that the characteristic equation of the D flip
flop is
Q(t + 1) = DQ
This means that the next-state values in the state
table specify the D input condition for the flip flop.

Instr: Dr. Awais M. Kamboh. 48

 State Table for Sequence Detector

A+ B+

• Input equations can be obtained directly from the table

using minterms:
–A(t + 1) = DA(A, B, x) = ∑(3, 5, 7)
–B(t + 1) = DB(A, B, x) = ∑(1, 5, 7)
–y(A, B, x) = ∑(6, 7)

Instr: Dr. Awais M. Kamboh. 49

 Boolean Minimization

K-Maps can be used to minimize the input equations,

resulting in
DA = Ax + Bx
DB = Ax + B’x
Y = AB

Instr: Dr. Awais M. Kamboh. 50

 Logic Diagram

Instr: Dr. Awais M. Kamboh. 51

 Synthesis Using JK Flip Flops

Synthesis of circuits with JK flip flops is the same as with

D flip flops except that the input equations must be
evaluated from the present-state to the next-state
transition derived from the excitation table.

Instr: Dr. Awais M. Kamboh. 52

 Excitation Tables

Characteristic Table Excitation Table

If present input and present If present state and next

state are known, then what state are known, then what
will be next state is the present input.

Instr: Dr. Awais M. Kamboh. 53

 Example JK Synthesis

A+ B+

Instr: Dr. Awais M. Kamboh. 54

 JK Synthesis Logic

By using K-maps we can minimize the flip flop input

equations.

Y=AB

Instr: Dr. Awais M. Kamboh. 55

 EXAMPLE: LASER RANGE FINDER

Instr: Dr. Awais M. Kamboh. 56

 Design Statement

Instr: Dr. Awais M. Kamboh. 57

 Design Statement Contd.

Instr: Dr. Awais M. Kamboh. 58

 Design Specifications

Instr: Dr. Awais M. Kamboh. 59

 State Diagram

Instr: Dr. Awais M. Kamboh. 60

 State Encoding

101 110 111

000 011

Instr: Dr. Awais M. Kamboh. 61