« Unleash the nerd!The Great Microcontroller Showdown '10 »

Intro to finite state machines (FSM)

07/04/11 | by Jfkfhhfj | Categories: Informative, General, Code

I've been out of the game of writing blog posts for a while now, but i promise its only because I've been working on some cool stuff. I'm going to be making a few posts on simple concepts before i roll out some larger projects I've been working on.

Finite State Machines:
A very important part of digital/software design is being able to control how a piece of software "flows", how the user interacts the software and how it behaves to certain stimuli. Finite State Machines associate actions (things your software/hardware does) with a current state and an input combination (Mealy State Machine) or just the current state alone (Moore Machine).

Finite state machines involve breaking your problem down into states, in which each state; the possible inputs to your code produce different results. Its a very simple paradigm, but its often hard to abstract, so we'll start with an example.

An Example:
Lets say we have a digital clock, and we have 3 buttons, there are several features we'd like to implement. Lets say for now, we can only set the time, the alarm time and turn on and off the alarm. If we list all the possible actions we find we can:

-Turn on and off the alarm
-Change the hours of the alarm
-Change the minutes of the alarm
-Change the hours of the actual time
-Change the minutes of the actual time
-So and and so forth.

So now we can do several things; one thing we can do is to have a button for every action. This really tends to eat up hardware and makes the end result sloppy and very user unfriendly (imagine having a button for every aspect of the operation of a more complicated device) Plus we stated above, we only have 3 buttons!

A much better example is to use a finite state machine, in which each button will have a different function dependent on the state that it is in.

For simplicity sake, we will be implementing the design as a Mealy machine (where the action is determined by the inputs and current state.

State Diagrams:
A state diagram is a way of representing the states that a system can take, for our clock we have Three:

State 1: The idle state, in this state we simply keep time, the user can enter programming mode from here or turn on and off the alarm

Button 1 - Will turn on or off the alarm
Button 2 - Enters programming mode (goes to state 2)
Button 3 - Does nothing

State 2: Programming mode for clock/alarm HOURS setting

Button 1 - Does nothing
Button 2 - Sets the current HOURS setting (goes to state 3)
Button 2 - Increments the set value

State 3: Programming mode for clock/alarm MINUTES Setting

Button 1 - Does nothing
Button 2 - Sets the current MINUTES setting (goes back into run mode after)
Button 3 - Increments the set values

So here, we implemented all the functions we wanted to do, with the buttons we had, and we even had ability to add extra functionality to each state!

Here is the state diagram for such a system:

Why FSM:
Besides for making hardware much more simple, FSM also has some major code benefits. The most major is now we can abstract our design into actions. We assign actions to a state/input combination and call this action when the criteria is met, with this we can break down out code and avoid "spaghetti code." This allows us to segment our code into different parts, making things easier to work on in the long run. FSM also allows us to avoid duplicate code, for example, with our clock, we have to increment the minutes and the hours, with this FSM we can write one routine to increment a register and have the current state determine what register to increment. Here we use the current state as a parameter to avoid having two routines for one thing(a simple example). There are many benefits to using FSM in your code, below i included a FSM routine for PIC microcontrollers using lookup tables. The same routine can be written with ROM tables as well.

Some Code:
Below I've written very simple code for a PIC18F micro which allows you to implement a Mealy FSM into your design. It's very simple code and is completely stand-alone, so you can implement it into any project you wish!

cblock 0x00
	INPUT
	CURRENTSTATE
	NEXTSTATE
	TEMP
endc

org 0x00
 
PORTS:
;;;;;;;;;;;;;;;;;;;;;;;
;SETUP STUFF GOES HERE;
;;;;;;;;;;;;;;;;;;;;;;;
	

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;MAIN                             ;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
INIT:
	movlw		0x00
	movwf		CURRENTSTATE
	movwf		NEXTSTATE      ;Initialize States to idle

	
MAIN_LOOP:
	call		FSM
        goto        MAIN_LOOP
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;This is the main FSM Code           ;
;INPUT must be from 0-256            ;               
;Each state calls the INPUT numbered ;
;Action from the lookup table        ;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
FSM:
	rlncf 		CURRENTSTATE,w
	call		GETSTATE
	movff		NEXTSTATE,CURRENTSTATE
	return

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;Lookup Tables
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
GETSTATE:
	movff		PCL,TEMP
	addwf 		PCL
	goto		STATE0
	goto		STATE1
	goto		STATE2
	return
STATE0:
	rlncf       INPUT,w
	movff		PCL,TEMP	;Pics are stupid
	addwf		PCL
	goto		ACTION0
	goto		ACTION1
	goto		ACTION2
	goto		ACTION3
	return
STATE1:
	rlncf       INPUT,w
	movff		PCL,TEMP	;Pics are stupid
	addwf		PCL
	goto		ACTION0
	goto		ACTION1
	goto		ACTION2
	goto		ACTION3
	return
STATE2:
	rlncf       INPUT,w
	movff		PCL,TEMP	;Pics are stupid
	addwf		PCL
	goto		ACTION0
	goto		ACTION1
	goto		ACTION2
	goto		ACTION3
	return

;State actions
ACTION0:
	movlw 0x01
	movwf NEXTSTATE
	return
ACTION1:
	movlw 0x02
	movwf NEXTSTATE
	return
ACTION2:
	movlw 0x03
	movwf NEXTSTATE
	return
ACTION3:
	movlw 0x00
	movwf NEXTSTATE
	return
end

Code Explanation:
Essentially, we have three system variables, NEXTSTATE, PRESENTSTATE and INPUT, when we call FSM the program uses PRESENTSTATE as an offset for a look-up table, calling the current set state. Once a state is loaded, we use INPUT as a offset for the action associated with a state. Thus we get an action that is associated with an input/state combination.

The major downside to this code is that STATE and INPUT MUST BE FORMATTED! If they are not, you will get erratic program behavior. (I.e. if there is 3 states, the first must be equivalent to 0x00, second, 0x01, and third 0x02, same for input)

This code can also be used with interrupts as well.

 

Trackback address for this post

This is a captcha-picture. It is used to prevent mass-access by robots.

Please enter the characters from the image above. (case insensitive)

Array

No feedback yet


Form is loading...

February 2017
Sun Mon Tue Wed Thu Fri Sat
 << <   > >>
      1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28        

Ads by Google

Mcuplace.com Store!

This blog is dedicated to working with digital circuitry and the use of microcontrollers, small compact computers on a chip. I will be encompassing many techniques to develop projects, tools to use to write and assemble code and i will be sharing any projects i am currently working on. User feedback is a must! I do not know it all, hell im not even that experienced, but without a general place to get all the info needed i find it very hard to get into the world of microcontrollers without pursing a CE degree. So come one come all and enter the world of mystery and creativity!

Search

  XML Feeds

powered by b2evolution