What is overlapping method?

Overlapping method in Moore model is used for detecting the sequence for the given input. When there are multiple pattern overlap with each other then it will be very challenging for detecting the sequence hence we go with overlapping method.

Why overlapping method is used in FSM?

The overlapping method in finite state machines (FSM) is used to recognize multiple patterns in an input , even when those patterns overlap with each other. This method is used when we want to identify all the occurrences of multiple patterns in a given input.

Example 1:

Let us consider an example of a sequence detector where the given sequence is 1001, and x be the inputs.

Sequence=1001.

Step 1: Draw the State Diagram

In the state diagram the (/)in the circle represents the bifurcation of present state and its output.

Step 2: State Assignment

              a=00
  
              b=01
    
              c=10

              d=11

Step 3: Write the State Table

Step 4: Excitation Table for D flip flop

Step 5: Excitation Table with Flip flop inputs

Step 6: Considering the present state and the input, find the equations using Kmap

The Karnaugh maps for simplifying flip-flop inputs and the output are shown below

Kmap for DB

kmap for DA

Kmap for Y

Example 2:

Design a digital system that reads in a sequence of binary numbers using a Mealy machine that detects if the input sequence contains two consecutive 1's.Implement using D flip flop.

Solution:

State 0: Initial state

Input 0: Stay in state 0, output 0

Input 1: Transition to state 1, output 0

State 1: Detected first 1 in the input sequence

Input 0: Transition to state 0, output 0

Input 1: Transition to state 2, output 0

State 2: Detected two consecutive 1's in the input sequence

Input 0: Transition to state 0, output 0

Input 1: Transition to state 3, output 0

State 3: Detected more than two consecutive 1's in the input sequence

Input 0: Transition to state 0, output 0

Input 1: Stay in state 3, output 1

Step 1: Draw state diagram

Step 2: Draw state Table

Step 3: Excitation Table of D flip flop

Step 4: Excitation Table with Flip flop inputs

Step 5: Considering the present state and the input, find the equations using Kmap

Step 6: Design the Circuit