FINITE STATE MACHINE (FSM)

FINITE STATE MACHINE (FSM)

        We all know that different systems behave differently in various conditions. Finite State Machine (FSM) is an easy technique used to model the behaviour of a system in various conditions. The function of a Finite State Machine is to detect the particular behavioural pattern of the system when it is subjected to various conditions. Let’s call this Finite State Machine as an FSM simply. Now the next thing is how the FSM models the behaviour of a system. That is the main content in this tutorial.

      Have you heard about ‘state’? I am asking this question because of a specific reason. That is, ‘state’ and ‘state transition’ are the two important things that you should learn before learning FSM. Because FSM models the behaviour of a system by representing it in different states it can be in and the transition between each state.

       A state is simply a specific action. Example for action is waiting for button 1 is to be pressed, or rotating the dc motor to any direction etc. So, what I am trying to explain is FSM is a computer program that, at any point in time, can be in one of a predetermined number of states. The first thing before creating an FSM model is to learn the particular behavioural pattern of a system. We can explain that with the help of an example. In order to get the basic concepts of FSM, we can start with an example of a simple sequence detector.

      FSM can be created in two ways. By using Mealy machine and Moore machine. In the Mealy machine, the output of the system depends on the present state and the present input also. But in the case of Moore machine, the output of the system depends on the present state only.

Mealy Machine

If the output of the system depends not only on the present state but also on the present input, we can call this system as a Mealy machine. If you are a beginner in FSM, I am sure that you will not be satisfied by this definition. So I will explain Mealy machine with an example of a sequence detector.

        Let’s consider a sequence 1101. If we want to generate this sequence, the first thing that we do is to find the possible states. In order to get 1101 sequence, we can divide the whole process into four steps.

Step 1

       Consider, initially the system is in state S0. From the given sequence, it is clear that in the first state what we want is 1 (because our sequence is 1101). So initially the system is in state S0 and to get 1 we will just provide an input 1. Whenever input 1 is given, the system moves to state S1. Refer fig.1. Here, initially, the system is in state S0. If we provide an input 0, the system will remain in state S0 itself. If we provide an input 1, the system will go to state S1.

Fig.1: If the present input is 1 or 0 in State 0

The reason for providing 1/0 in fig.1 is that we are providing an input 1 and the output is 0.

       I think you got confused now. Only when we get the last output (1101), we give as 1/1. What do you understand from this? If we notice that any 1/1 or 0/1 in a state diagram, just recall that, that would be the last state of that state machine.

Step 2

        The next state we want is 11 (ie, 1101). So we provide an input 1 so that it can go to state S2.

Fig.2: If the present input is 1 in State 1

Also, you should check what if the input is 0 from S1. If the input is 0, we should start the state machine again in this case. So, again the system goes to state S0. Refer Fig 3.

Fig.3: If the present input is 0 in state 1

Step 3

        The next input we want is 0 (1101). We already have 11 at S2. To get 110, we provide an input 0 so that it can move to state S3. So to reach S3 the sequence 110 should be given.

Fig.4: If the present input is 0 in state 2

        We should also check the input 1 condition in state S2. We already checked what if the input from S2 is 0. Next, we should check what if the input from S2 is 1. If input from S2 is 1, it should remain in that state itself.

         Let me explain. We want a sequence 1101. At S2 we got up to 11 of the 1101 sequence. Next, we want to check whether the next input is 1 or 0. More specifically, we want to check whether 111 or 110. If 110, it will go to next state S3 that I mentioned in the earlier case. If input at s2 state is 1(we will get 111), we select the last 11 of 111. Because the next digit may be 0, what we exactly wanted. So, the state diagram will remain in S2 itself, to detect 11. Refer fig.5.

Fig.5: If the present input is 1 in state 2

Step 4

        By the next transition, we will get the output sequence. The next state we want is 1101 (1101). We already have 110 at our state S3. To get the last digit in our sequence, remember that digit is 1, we can go back to the particular state whose outcome is 1. That’s exactly state S1. And remember one thing. This is the output state. So don’t forget to write 1/1. Refer Fig.6.

Fig.6: If the present input is 1 in state 3

         Also, we want to check the zero condition of state S3. That is, if we have 1101 (mentioned in the earlier case), we will go to state S1. But if we have 1100, we will go to state S0 to start the state machine again. Refer Fig.7.

Fig.7: FSM Model of 1101 sequence

The program in MPLAB regarding the 1101 sequence detector is provided below.

#include <stdio.h>

#include <stdlib.h>

#define _XTAL_FREQ 4000000



// PIC16F877A Configuration Bit Settings



// 'C' source line config statements



#include <xc.h>



// #pragma config statements should precede project file includes.

// Use project enums instead of #define for ON and OFF.



// CONFIG

#pragma config FOSC = HS       

#pragma config WDTE = OFF      

#pragma config PWRTE = OFF     

#pragma config BOREN = ON      

#pragma config LVP = OFF       

#pragma config CPD = OFF       

#pragma config WRT = OFF       

#pragma config CP = OFF   

    

char rx();

void tx(unsigned char);

void string(char *);

int count=0;



void main()

{

   int input=0;

   int state=0;



   char s[20];

   TXSTA=0X24;

   RCSTA=0X90;

   SPBRG=25;

   TRISC=0X80;

   string("WELCOME\n\r");

   string("GIVE THE PATTERN\n\r");

    while(1)

    {

        input=rx();

        tx(input);



        switch (state)

        {

            case 0:



                if(input=='0')

                  state=0;

                else

                  state=1;

                break;





            case 1:



                if(input=='0')

                  state=0;

                else

                  state=2;

                break;





            case 2:



                if(input=='0')

                  state=3;

                else

                  state=2;

                break;



            case 3:



                if(input=='0')

                    state=0;

                else

                {

                    state=1;

                    string("\n\rMATCH FOUND:::::1101\n\r");

                    count++;

                    sprintf(s,"PATTERN COUNTED= %d\n\r",count);

                    string(s);

                    state=0;

                    string("CONTINUE GIVING PATTERN\n\r");

                }

          

                break;

        }

    }



}





void tx(unsigned char a)

{

    TXREG=a;

    while(!TRMT);

}

void string(char *p)

{

    int i;

    for(i=0;*(p+i)!='\0';i++)

    {

        tx(*(p+i));

    }

}

char rx()

{

    while(!RCIF);

    return RCREG;

}

Simulation diagram in proteus and the output regarding that is provided in Fig.8 and Fig.9 respectively.

Fig.8: Simulation diagram in proteus

Fig.9: Output of the 1101 pattern detector

RELATED LINK

• https://www.youtube.com/watch?v=GAzjQBZZXMc