B.

Tech III semester

DIGITAL SYSTEM DESIGN
Topic FSM
BY
Veena M Kurup

DEPARTMENT OF ECE
INSTITUTE OF AERONAUTICAL ENGINEERING
 FSM

• Finite state machine (FSM) is a mathematical model to describe any

sequential system that has a limited number of conditional states.
• It is an abstract machine that can be in exactly one of a finite number
of states at any given time.
• The FSM can change from one state to another in response to
some inputs; the change from one state to another is called a transition.
• An FSM is defined by a list of its states, its initial state, and the inputs that
trigger each transition.
• Within an FSM, all states in consideration exist in a finite list and the
abstract machine can only take on one of those states at a time.
 FSM

• A synchronous sequential circuit is also called as Finite State Machine

FSM if it has finite number of states.
• A FSM can be represented as
• State diagram
• State table
• State equation
• ASM
• There are two types of FSMs.
• Mealy State Machine
• Moore State Machine
 FSM

• A state is a description of the status of a system that is waiting to

execute or it is the binary information that a flip flop contain
• When a finite state machine switches between states, it is called a state
transition.
• A transition is a set of actions to be executed when a condition is
fulfilled or when an event is received.
• State diagrams can be used to graphically represent finite-state
machines. The state diagram consists of nodes which represent the
states and arrows (sometimes called edges) which give the possible
transitions between states
 FSM

• The state diagram is the pictorial representation of the behavior of

sequential circuits. It clearly shows the transition of states from the
present state to the next state and output for a corresponding input.
• In this diagram, each present state is represented inside a circle.
• The transition from the present state to the next state is represented
by a directed line connecting the circles.
• If the directed line connects the circle itself, which indicates that
there is no change in the state(the next state is the same as the
present state).
 FSM

• A state-transition table is one of many ways to specify a finite-state

machine.
• The information contained in the state diagram is transformed into a
table called a state table or state synthesis table.
• It is essentially a truth table in which the inputs include the current
state along with other inputs, and the outputs include the next state
along with other outputs
• Although the state diagram describes the behavior of the sequential
circuit, in order to implement it in the circuit, it has to be transformed
into the tabular form.
 FSM

• Mealy State Machine

Mealy machine is a finite-state machine whose output values are determined both
by its current state and the current inputs

• Moore State Machine

A Finite State Machine is said to be Moore state machine, if outputs depend only
on present states.
 FSM

The number of states required in Mealy state machine is less than or equal to the
number of states required in Moore state machine. There is an equivalent Moore
state machine for each Mealy state machine.
 FSM

Moore Machine Mealy Machine

Output depends on the present state as well as present

Output depends only upon the present state.
input.

If input changes, output does not change If input changes, output also changes.

More states are required. Less number of states are required.

There is less hardware requirement for circuit There is more hardware requirement for circuit
implementation. implementation.

They react slower to inputs(One clock cycle later). They react faster to inputs.

Output is placed on states. Output is placed on transitions.

Easy to design. It is difficult to design.

Has fewer or the same states as that of the Mealy Has fewer or the same states as that of the Moore
machine. machine.
 FSM

Limitations
• No infinite sequence :Infinite sequence cannot be produced by FSM.
• Limited memory : FSM has limited memory and due to that it cannot
produce certain outputs.
• Complexity: Can't handle very complicated tasks. The implementation of
huge systems using FSM is hard for managing without any idea of design.
• Limited flexibility: FSMs are based on predefined states and transitions,
which can make it difficult to adapt .
• based on predefined rules, which means they cannot handle uncertainty or
randomness.
• Limited ability to handle parallel tasks: FSMs are based on sequential
execution, which means they cannot handle parallel tasks. This can make it
difficult to perform multiple tasks simultaneously.
 FSM

• Applications

Traffic Lights
Vending Machines
Video Games
CPU Controllers
Protocol Analysis
Natural Language Processing
Speech Recognition
 Sequence Detector

• A sequence detector is a sequential state machine that takes an input

string of bits and generates an output 1 whenever the target
sequence has been detected.
• Sequence detector is of two types: Overlapping and Non-Overlapping
• In an overlapping sequence detector, the last bit of one sequence
becomes the first bit of the next sequence.
• In a non-overlapping sequence detector, the last bit of one sequence
does not become the first bit of the next sequence.
 Sequence Detector

• Step 1: Develop the state diagram

• Step 2: Code Assignment
• Step 3:Write State table
• Step 4:Excitation table for selected FF
• Step 5: Draw K-maps and solve for input and output
• Step 6: Finally implement the circuit
 Sequence Detector

• Design a Melay type sequence detector to detect a serial input

sequence of 101
 Sequence Detector

Design a non-overlapping 101 Mealy sequence detector

Step 1: Develop the state diagram

 Sequence Detector

Step 2: Code Assignment

 Sequence Detector

Step 3: Make Present State/Next State table

 Sequence Detector

Step 4: Draw K-maps for Dx, Dy and output (Z)

 Sequence Detector

Step 5: Finally implement the circuit

 Sequence Detector

• Design a sequence detector to detect sequence 110 using JK flip flop

 Sequence Detector

• Design a sequence detector to detect sequence 110 using JK flip flop

JB=X KB=1
 Sequence Detector

• Problems
• Draw the diagram of Mealy type FSM for serial adder
• Design a clocked sequential circuit to detect 1111 or 0000 and it will
produce an output z=1 at the end of the sequence. Overlapping is
allowed. Draw the circuit using D flip flops.
HW
• Draw the state diagram of a Mealy machine that produces a 1 output
if there have been four or more consecutive 1 inputs or two or more
consecutive 0 inputs.
 ASM

• An ASM ,algorithmic state machine , is a special type of flow chart that is

used to describe the sequential operations of a digital circuit.
• It describes the sequence of events as well as timing relationship
between the states of FSM. It specifies the step-by-step procedure in
order to complete a given digital design.
• An ASM block is a structure consisting of one state box and all decision
and conditional boxes connected to its exit path.
• The ASM diagram is like a state diagram but more structured and, thus,
easier to understand.
• An ASM chart is resembles a conventional flow chart but the difference
is, a conventional flow chart does not have timing relationships but the
ASM takes timing relationship into account.
 ASM

• An ASM chart and a flow chart are both diagrams that are used to represent
the flow of control in a computer program or system.
• An ASM chart is a type of finite state machine that represents the behavior of a
system using a set of states and transitions between them.
• It is often used to model the behavior of software systems, and can be used to
verify the correctness of a system's design.A flow chart, on the other hand, is a
diagram that represents the flow of control in a process or program using a
series of shapes that represent different types of actions or decisions.
• Flow charts are often used for flowcharting, process flow diagrams, data flow
diagrams, and other types of diagrams.In summary, an ASM chart is a type of
finite state machine that models the behavior of a system, while a flow chart
represents the flow of control in a process or program
 ASM

The ASM chart is composed of three basic elements, which are

• State box
• Decision box
• Conditional box
State box
• A state in the control sequence is described by State box.
• The shape of the state box is rectangular in which register operations or output signal
names can be specified.
• The state name is given a symbolic name which is written in the upper left corner of
the box.
• After the state assignment, the binary code is placed at upper right corner of the box.
 ASM

Decision box :

• It describes the effect of the input on the control subsystem.

• It is a diamond-shaped box with two or more exit paths. The input condition which
needs to be checked is written inside the box.
• One exit path is taken when the condition is true, otherwise other is taken when
the condition is false.
• When the input condition is assigned to a binary value, then the two paths are
indicated by 1 and 0.
 ASM

Condition box :

• It has an oval shape.

• The input path of the conditional box must come from the exit path of the decision
box.
• The register operations and output lists are written inside the conditional box which is
generated in a particular state but the input condition must be true.
 ASM

• ASM for D Flip flop

• ASM for counter

 ASM

• Design a sequential logic circuit of a 4 bit counter to start counting from

0000 to 1000 and this process should go on. Draw the ASM
• Explain in detail the Moore state diagram and ASM chart for it with an
example?
• Draw an ASM chart and state diagram for the synchronous circuit having
the following descriptions: The circuit has control input C, clock and
output x, y and z. i) if C=1, on every rising edge of the clock code on
output x, y and z changes from 000-010-100-110-000 and repeats. ii) If C
= 0, the circuit holds the present state.
 Sequence generator

• The sequence generator or pulse train generator generates, in synchronism

with a clock ,a prescribed sequence of binary bits (information).
• Shift registers can be used to generate pulse trains.
• The length of the sequence is related to the number of flip-flops that are
required to produce a sequence generator.
• First, count the number of zeros and ones in the given sequence,let this
number will be ‘N’.(length of the sequence)
• The no. of flip flops can be calculated as N = 2n-1
 Sequence generator

• Write the bits in vertical order.

• Form groups of n bits starting from the top bit and convert them to state
numbers
• If entire train of pulse can be examined without repeating a state,the
design can be done by n FFs.
• If there is a repetition of states take n+1 FFs.
• If repeated states still occur,take n+2 FFs
 Sequence generator

• Problems
• Design a pulse train generator using shift register for the following pulse
train ......1110......
• Design a pulse train generator using shift register for the following pulse
train ......111010......
Sequence generator
Sequence generator
Sequence generator
 Pseudo Random Binary Sequence generator

• A linear-feedback shift register (LFSR) is a shift register whose input bit is

a linear function of its previous state.
• The most commonly used linear function of single bits is exclusive-or(XOR).
• LFSR can generate a pseudo-random binary sequence using an n-bit shift
register with feedback through an exclusive or (XOR) function.
• The sequence of random numbers is a function of the current state and
some previous states.
 Pseudo Random Binary Sequence generator

• When the outputs of the flip-flops are loaded with a seed value (anything
except all 0s, which would cause the LFSR to produce all 0 patterns) and
when the LFSR is clocked, it will generate a pseudorandom pattern of 1s
and 0s.
• A maximal-length LFSR produces the maximum number of PRPG patterns
possible and has a pattern count equal to 2n – 1, where n is the number of
flip flop in the LFSR.
THANK YOU