TRIBHUVAN UNIVERSITY
INSTITUTE OF ENGINEERING
THAPATHALI CAMPUS
Digital Logic-EX502
Unit 9 : Sequential Machines
Presented By
Er. Ganesh Kumal
Department of Electronics & Computer Engineering
IOE ,Thapathali Campus
24 July, 2023
Prepared By: Er. Ganesh Kumal
9. Sequential Machines (8 hours)
9.1. Synchronous machines
9.1.1. Clock driven models and state diagrams
9.1.2. Transition tables, Redundant states
9.1.3. Binary assignment
9.1.4. Use of flip‐flops in realizing the models
9.2. Asynchronous machines
9.2.1. Hazards in asynchronous system and use of redundant
branch
9.2.2. Allowable transitions
9.2.3. Flow tables and merger diagrams
9.2.4. Excitation maps and realization of the models
Synchronous Sequential Machine
• The logic circuit whose output depends not only one the present
value of its input signals but on the sequence of past input history is
called sequential logic circuit.
• The synchronous or clocked sequential circuits are represented by
two models.
1. Moore model
2. Mealy model
Moore Model
• The output depends only on the present state of the flip-flops.
X – Inputs
Z – Outputs
Inputs X is used to determine the
inputs of the flip-flops. It is not
used to determine the output
(Z).
The output is derived using only
present states of the flip-flops or
combinations of it.
i.e. Z
Mealy Machine
• In a mealy machine, the outputs are function of the
present state and the value of the inputs as shown in
figure.
Figure: Mealy Machine
Difference between Moore and Mealy
Machine
Moore Model Mealy Model
• Output is a function of present • Output is a function of inputs as
state only. well as present state.
• Input changes do not affect the • Input changes may affect the
output. output of the circuit.
• Moore model requires more • It requires less number of states
number of states for for implementing same function.
implementing same function.
State Table, State diagram, State equation, State reduction
and assignment
State Table
The time sequence of inputs, outputs, and flip-flop states (present state and next
state) can be enumerated in a state table.
The table consists of four sections:
Present state: Shows the states of flip-flops at any given time t.
Input: Gives a value of X for each possible present state.
Output: Gives the value of Y for each present state
Next state: Shows the state of flip-flops after one clock pulse
State Equation
▪ It is an algebraic expression that specifies the condition for a flip-flop state
transition.
State diagram:
•The information available in a state table can be represented graphically in a state
diagram. ( or vice -versa)
•State is represented by a circle, and the transition between state is indicated by
directed lines connecting to the circle.
State Reduction and Assignment
State Reduction
• Reduction on the number of flip-flops and the number of gates.
• Reduction in the number of states may result in a reduction in the number of
flip-flops.
• State-reduction algorithms are concerned with procedures for reducing the
number of states in a state-table while keeping the external input-output
requirements unchanged.
7/28/2023 Prepared By: Er.Ganesh Kumal 8
State table from the state diagram
Example:
Same next state and same output at
e and g state, so e= g and state g is
Figure: State diagram reduction.
Equivalent state
▪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.
➢One of them can be removed
7/28/2023 Prepared By: Er.Ganesh Kumal 9
Reduced state table
State assignment:
a = 000
b = 001
c = 010
d = 011
e = 100
7/28/2023
Figure: Reduced state diagram
Prepared By: Er.Ganesh Kumal 10
Design Procedure
• Design starts from a specification and results in a logic diagram or a
list of Boolean functions.
• Steps:
1. Derive a state diagram
2. Reduced the number of states.
3. Assign binary values to the states.
4. Obtain the binary coded state table.
5. Choose the type of flip-flops to be used
6. Use Excitation Tables to derive state table
7. Derive the simplified flip-flop input equations and output equations
8. Draw the logic diagram
Example 1: Design synchronous sequential circuit for the given
state diagram using J-K F/F
• The state diagram consists of four
states with binary values already
assigned.
• Directed lines contain single binary
digit without a slash, so no output
variables.
• The two flip-flops needed to
represent the four states are
designated A and B.
• The input variable is designated X.
Figure: State diagram for design example
The state table for this circuit,
derived from the state diagram.
Note that there is no output
section for this circuit
7/28/2023 Table: State table Prepared By: Er.Ganesh Kumal 12
Table
Excitation table
Figure: Maps for combinational
circuit
Since J-K flip-flops are used we need columns for the J and K
inputs of flip-flops A ( denoted by JA and KA) and B (denoted
by JB and KB).
7/28/2023 Prepared By: Er.Ganesh Kumal 13
Figure: Logic diagram of sequential circuit
7/28/2023 Prepared By: Er.Ganesh Kumal 14
Example 2: Design sequential circuit with D flip-flops having
following next states and output columns.
DA (A, B, X) = m (2, 4, 5, 6)
DB (A, B, X) = m (1, 3, 5, 6)
Y (A, B, X) = m (1, 5)
Figure: state diagram
From the K-map simplification
DA = AB’ + BX’
DB = A’X + B’X + ABX’
Y = B’X
7/28/2023 Prepared By: Er.Ganesh Kumal 15
DA = AB’ + BX’
DB = A’X + B’X + ABX’
Y = B’X
Figure: Logic diagram of sequential circuit with D flip-flop
7/28/2023 Prepared By: Er.Ganesh Kumal 16
Design Counter
• A sequential circuit that goes through a prescribed
sequence of states upon the application of input
pulses is called a counter.
• In a counter, the sequence of states may follow a
binary count or any other sequence of states.
• A counter that follows the binary sequence is called
a binary counter.
• An n-bit binary counter consists of n flip-flops and can
count in binary from 0 to 2n - 1.
7/28/2023 Prepared By: Er.Ganesh Kumal 17
Example 4:Design 3-bit counter
Figure: State diagram
7/28/2023 Prepared By: Er.Ganesh Kumal 18
Maps for 3-bit binary counter
Figure: Logic diagram for 3-bit binary counter
7/28/2023 Prepared By: Er.Ganesh Kumal 19
Example 5:Counter with Non-binary Sequence
Design a counter as shown in state diagram below.
000
001 110
010 101
100
Figure: State diagram
7/28/2023 Prepared By: Er.Ganesh Kumal 20
Inputs KB and KC have only 1's and X's in their columns, so these
inputs are always equal to 1. The other flip-flop input functions can
be simplified using min-terms 3 and 7 as don't-care conditions. The
simplified functions are:
JA = B KA = B You have to show the K-map
JB = C KB = 1 for simplification
JC = B’ KC = 1
7/28/2023
Figure: Logic diagram of counter
Prepared By: Er.Ganesh Kumal 21
Example 6 : A sequential circuit has one input and one output. The state diagram is shown
in figure. Design the sequential circuit with RS flip-flops.
The excitation table of S-R flip-flop is:
Figure: State diagram
1 0 1 0
1 1 0
Now using K-map:
Use don’t care for unused states.
• Similarly find out the other flip-flop inputs ( SB, RB, SC,
RC ) and Y output.
SB = C’X’ + A RB = CX’ + BC’X
SC = AX + A’B’X’ RC = CX
Y = A’X
• Draw the logic circuit.
Example 8: Design a sequential machine that can go through 2-bit gray code
combination of states. The machine changes its state when serial input is one and
remains in the same state when input is zero. The machine produces output 1 when it
passes through all states and finally goes back to initial state. ( Use JK flip-flop ) [ IOE
2071 Shrawan]
So the state diagram is drawn as:
Binary Gray
00 00
01 01
10 11
11 10
For 2-bit gray code, the sequence is:
00 → 01 → 11 → 10.
Sequence Detector
Q.N.1) The output of the machine is to be set high when the data in the
input 110 in sequence starting from MSB ( use SR flip-flop.)
Note: For easy use you can use T flip-flop instead of using other flip-
flops if the question do not fix the type of flip-flop. But in this case
you must use SR flip-flop.
Here,
Input X= 110
Output Z= 001
2) A synchronous state machine has one bit serial input X. The output Z of machine is
to be set high when the input contains the message 011. Draw the state diagram for
this machine and design the circuit. ( Use T flip-flops).
Design a sequential machine that has one serial input and one output Z. The
machine is required to give an output Z =1, when the input X contains the
message 1010.
Solution:
X = 101010
Z = 000101
Design a sequential circuit with two D flip-flops and two inputs P and Q. If P=0, the circuit
remains in the same state regardless of the value of Q. When P=1 and Q = 1, the circuit
goes through the state transition from 00 to 01 to 10 , and repeats. When P = 1 and Q = 0,
the circuit goes through the state transition from 00 to 10 to 01 back to 00, and repeats.
The circuit is to be designed by treating the unused state (s) as don’t care condition.
Solution:
Case I: when PQ = 0X, remains in same state
Case II: When PQ = 11, state transition as
00 - 01 10 00
Case III: When PQ = 10, state transition as
00 10 01 00
Unit 9 End !!
Any Queries ???
