TRIBHUVAN UNIVERSITY

INSTITUTE OF ENGINEERING
THAPATHALI CAMPUS

Digital Logic-EX152
Unit 7 : Sequential Machines
Presented By
Er. Ganesh Kumal
Department of Electronics & Computer Engineering
IOE ,Thapathali Campus

20 July, 2025
Prepared By: Er. Ganesh Kumal 1
 Contents
7.1 Machine Design Procedures
7.2 Primitives State Diagram
7.3 Transition / Flow Tables
7.4 Redundant States
7.5 Pure Binary Assignment Tables
7.6 Excitation Maps
7.7 Realization of Models
7.8 Circuit Diagram of Synchronous Machines
7.9 One Bit and Two-Bit Inputs Sequence Detector
 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 • Output is a function of
present state only. inputs as well as present
state.
• Input changes do not affect • Input changes may affect
the output. the output of the circuit.
• Moore model requires more • It requires less number of
number of states for states for implementing
implementing same same function.
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
 Contniue….
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.

8/1/2025 Prepared By: [Link] Kumal 9

 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

8/1/2025 Prepared By: [Link] Kumal 10

 Reduced state table

State assignment:
a = 000
b = 001
c = 010
d = 011
e = 100
Figure: Reduced state diagram

8/1/2025 Prepared By: [Link] Kumal 11

 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: 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

Table:
8/1/2025State table Prepared By: [Link] Kumal 13
 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).
8/1/2025 Prepared By: [Link] Kumal 14
 Figure: Logic diagram of sequential circuit

8/1/2025 Prepared By: [Link] Kumal 15

 Example: 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

8/1/2025 Prepared By: [Link] Kumal 16

 DA = AB’ + BX’
DB = A’X + B’X + ABX’
Y = B’X

Figure: Logic diagram of sequential circuit with D flip-flop

8/1/2025 Prepared By: [Link] Kumal 17
 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.

8/1/2025 Prepared By: [Link] Kumal 18

 Design 3-bit counter

Figure: State diagram

8/1/2025 Prepared By: [Link] Kumal 19

 Maps for 3-bit binary counter

Figure: Logic diagram for 3-bit binary counter

8/1/2025 Prepared By: [Link] Kumal 20

 Counter with Non-binary Sequence
Design a counter as shown in state diagram below.

000

001 110

010 101

100

Figure: State diagram

8/1/2025 Prepared By: [Link] Kumal 21

Inputs KB and KC have only I's and X's in their columns, so these
inputs are always equal to I. 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

8/1/2025
Figure: Logic diagram of counter
Prepared By: [Link] Kumal 22
Question: 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

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: 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).
(3) 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
(4) 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
 State table and excited inputs of D F/F
Present State Inputs Next State
DA DB
A B P Q A B
0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 1 0 1 0 1 0
0 0 1 1 0 1 0 1
0 1 0 0 0 1 0 1
0 1 0 1 0 1 0 1
0 1 1 0 0 0 0 0
0 1 1 1 1 0 1 0
1 0 0 0 1 0 1 0
1 0 0 1 1 0 1 0
1 0 1 0 0 1 0 1
1 0 1 1 0 0 0 0
Design K-map and circuit in similar basis
Unit 7 End !!!

Any Queries ???