What is a software State Machine all about?
Submitted By: Michael Karas FAQ Last Modified: 04/01/07
- Microcontrollers are very handy devices for performing various types of tasks. Often these tasks are simple and may be programmed in a straight forward set of program code that is either a linear or looping sequence of instructions that perform the desired task at hand. Sometimes however there is a desire to have the microcontroller perform multiple tasks at the simultaneously and give the appearance that many things are taking place at the same time. How can this be done?
There are a number of ways that embedded programmers have found to make this multiple task concept work. One method involves the use of something called an RTOS (Real Time Operating System). It is often the case however that an RTOS is expensive to implement. They usually cost money, take a lot of processor resources, and require a lot of time to understand and link into your program.
Another method of getting a microcontroller to perform multiple overlapping tasks is to design those tasks into a state machine structure. By working out a sequence of defined steps for a task it is possible to design program code blocks that can be used to perform the task step-by-step. These steps can be processed by calling the code blocks in the proper order using a variable to track which code block is the next to be called. Additionally, if these calls are done in a timed manner such that the time period between calls is long compared to the time spent executing any one code block, then it is possible to see how the microcontroller can spend only a fraction of its time performing this one task. A code structure that provides this type of behavior is called a state machine.
This FAQ entry will show a sample implementation of a state machine. The design will be explained and the code presented to implement it in 8052 type assembly language. The code may then be used as a spring board for other types of state machine designs.
The sample project will be based upon having eight switches connected to a port of an 80C51 / 80C52 controller. This same controller will also have eight LEDs connected to it on another port. The schematic of the connections is shown below:
The defined behavior for the program is the following: Whenever any switch is pressed its active press to a low level should be de-bounced and then the corresponding LED should light for 5 seconds. Such as if SW4 is pressed then LED4 would turn on for 5 seconds. While an LED is lit its corresponding switch should be ignored. After the 5 second period has expired the program should go back to looking for the high to low transition of the switch being pressed.
The program should be coded so that each switch is handled independant of the the others. Thus if SW2 was detected pressed and its LED was turned on it should appear to the user that he can also press SW3 at the same time or close to the same time and have its LED3 light as well. It should even be possible that any combination of the switches could be active at any one time.
The concept is to handle this problem using a state machine. The state handling for each switch is the same except that different port bits are applicable to each one. This means that it should be possible to write one set of state machine code that could be re-used for each of the switch inputs. The states defined for the state machine are as follows:
State 0: Waiting for the switch input to be detected low indicating that the switch has been pressed. If the switch input is seen low then the state changes to State 1.
State 1: Validation state to check if switch input is still low. If the input is not stil low it is deemed to be unstable (bouncing) and so the state should go back to State 0. If the switch input is validated as a low for this state then the LED for this switch should be turned on and a 5 second timer started that controls how long the LED should stay lit. The state number is then set to State 2.
State 2: This waits for the 5 second LED flash interval to be completed. The 5 second timer/counter is decremented and if still non-zero then the State 2 should not change. However if the 5 second timer expires then the LED should be turned off and the state number changed to State 3.
State 3. This waits for the switch input to go back to the inactive high state indicating that the switch has been released. It is possible that the switch was released during the 5 second LED flash time and if so this state catches this condition on the first pass into this state.
The state machine is designed to be called on a periodic basis. It turns out that 10 milliseconds is a good time period to debounce the switches and so the design of the state machine logic is such that if it was called each 10 milliseconds, for a particular switch, then the status of that switch could be monitored and the LED could be managed.
Since there are eight (8) separate switches to manage the sample program is designed with a timer interrupt that runs eight times faster than 10 milliseconds or equivalently at 1.25 milliseconds period. The idea is to maintain a global variable that will count from 0 -> 1 -> 2 ..... -> 7 and back to 0 again in a cyclic manner. Each occurrance or the 1.25 millisecond interrupt will call the state machine logic for the switch number in this counter. After the state subroutine is complete the counter is incremented up to the next switch number. The net effect of this is that the state machine for a particular switch is called once each 10 milliseconds.
The code needs to maintain separate state variables for each switch and a separate 5 second timer counters for each LED flash time because each is to operate independantly. It was decided to arrange these state variables and time counters into three tables that are accessed with indexing. One table is 8 bytes long and holds the current state number for each switch. A second table is 16 bytes long and holds the 8 LED flash time counters. For this program these needed to be two bytes each because the counters, which get processed every 10 milliseconds (100 times a second) need to count from 500 down to zero to arrive at a 5 second interval. A third table is a look-up-table in the code space that is used to convert the current 0 -> 7 switch number into a bit mask for the SWITCH input port and the LED output port. A single table can provide the mask for both the input switches and the LED outputs because of the 0::0, 1::1, 2::2 etc assignment for the switches to the LEDs. (If the assignment was not one to one in this manner two tables could be used).
It was decided to have the timer interrupt be a very short function that just sets a bit flag at each interrupt time. The main line code then runs the state machine process and polls on the bit flag from the timer interrupt to obtain the net 1.25 msec rate to dispatch the state machine calls.
The assembly language program code to implement the state machine can be accessed as a source code file at this link:
A flow chart of the sample code may be seen at the following link in PDF format. For those just learning about state machines it may be handy to have the flow chart as a reference to look at when studying the actual assembly language code.
Note that this code has been assembled (code format is compatible with the Keil assembler and others) till there were no assembly errors. The code was then "bench checked" by running it in the Keil debug simulator. As such this code has not been run by the author on a physical hardware platform and so it is possible that there may be some minor issues that need adjustments. One individual that is a member of the 8052 Forum web site has reported running this code on his test platform. See Tom Burdick's comments. He says it works great!
Please note that this code is written in a manner to maximize modularity and clarity. There are a number of things that could be done to reduce the size of the compiled object code and/or make the code faster. However the tightest possible code has been avoided in favor of clarity and modularity. And at the same time it will make this program easier for the learner to follow and understand how it works.
Here is an inline listing of the code. Tutorial comments have been added in the red color to clarify the comments from the code. [Further comments to be added as an ongoing effort].
These lines are special commands to the assembler.
The first one tells the assembler to not use any of its built-in
names and equates for SFRs and SFR bits. The second line tells
the assembler the name of a file to read in that contains the
equates for all of the SFR names and bits that are specific to
the particular 8052 microcontroller in use.
$NOMOD51
$INCLUDE(REG51FX.INC) ; register definitions compatible
; with standard Intel architecture FX cpu
USING 0 ; use register block 0
The following two lines are equates that define
names to be used to refer to the ports where the LEDs and
switches are connected. Names in the source code make things
much easier to read and understand.
SWTPORT EQU P2 ; switches connected to Port 2
LEDPORT EQU P3 ; LEDs connected to Port 3
Below the section is the bit segment. The BSEG directive
tells the assembler that the variables in this part of the code
are bit variables to be placed into the 20H to 2FH address range
of the internal RAM.
;***************************************************
; INTERNAL DATA BIT DEFINITIONS, locations 20H-2FH
;---------------------------------------------------
BSEG AT 00
Tick:
DBIT 1 ; 1 = 1.25 msec tick has come
;***************************************************
; INTERNAL DATA BYTE DEFINITIONS
;---------------------------------------------------
;internal data area variables.
;
DSEG AT 30H ; word locations are HIGH:LOW
SwitchNo:
DS 1 ; current switch number to process (0->7)
SwitchStates:
DS 1 ; current state of Switch 0
DS 1 ; current state of Switch 1
DS 1 ; current state of Switch 2
DS 1 ; current state of Switch 3
DS 1 ; current state of Switch 4
DS 1 ; current state of Switch 5
DS 1 ; current state of Switch 6
DS 1 ; current state of Switch 7
SwitchCounters:
DS 2 ; counter for Switch 0
DS 2 ; counter for Switch 1
DS 2 ; counter for Switch 2
DS 2 ; counter for Switch 3
DS 2 ; counter for Switch 4
DS 2 ; counter for Switch 5
DS 2 ; counter for Switch 6
DS 2 ; counter for Switch 7
STACK:
DS 20 ; reserve 20 bytes of space
RAM_END:
DS 1 ; end of allocated RAM marker
;***************************************************
; INTERRUPT VECTOR DEFINITIONS
;---------------------------------------------------
CSEG AT 0000H ; reset vector
JMP PWR_UP ; power-on entry point
CSEG AT 0003H ; intr 0 vector
CLR EX0 ; external int 0 not used
RETI
CSEG AT 000BH ; timer 0 vector
RETI ; not used
CSEG AT 0013H ; intr 1 vector
CLR EX1 ; external int 1 not used
RETI
CSEG AT 001BH ; timer 1 vector
JMP T1_ISR ; timer 1 int isr
CSEG AT 0023H ; UART vector
CLR ES ; serial port int not used
RETI
;***************************************************
; BASE OF CODE AREA
;---------------------------------------------------
CSEG AT 040H
DB 'Copyright (C) Carousel Design 2003',0
;***************************************************
; NAME: INIT_T1
; Initialize a 1.25 mSec period interrupt for a
; state machine dispatcher on timer 1. This is same
; as a frequency of 800 Hz.
; Mode 1 is 16-bit
; TMOD is not bit addressable.
;
; Timer clocks are 11.0952 mHz / 12 = 924600 Hz
; Divisor for 800 Hz = 924600 / 800 = 1155.75 (approx 1156)
;---------------------------------------------------
T1_RELOAD EQU (65536 - 1156)
INIT_T1:
MOV TMOD, #10H ; timer 1 - mode 1
;
MOV TH1, #HIGH(T1_RELOAD) ;to setup 800 Hz rate
MOV TL1, #LOW(T1_RELOAD) ;timer 1 for 1.25 ms
CLR Tick ; clear the tick indicator flag
SETB TR1 ; start the timer 1
SETB ET1 ; enable its interrupt
RET
;***************************************************
;NAME: T1_ISR
; Used to time an 800 Hz ticker bit
;---------------------------------------------------
T1_ISR:
PUSH PSW ; save entry state
SETB Tick ; show tick time
;
CLR ET1 ; stop it for a moment
MOV TH1, #HIGH(T1_RELOAD) ; to setup 800 Hz rate
MOV TL1, #LOW(T1_RELOAD) ; timer 1 for 1.25 ms
SETB ET1 ; restart the timer
;
POP PSW ; restore state
RETI
;***************************************************
;NAME: SWT_MSK
; Used to convert a switch number to a port mask
; Entry A is the 0-7 switch mask
;---------------------------------------------------
SWT_MSK:
INC A
MOVC A, @A+PC
RET
;
DB 00000001B ; Bit 0 <- 0
DB 00000010B ; Bit 1 <- 1
DB 00000100B ; Bit 2 <- 2
DB 00001000B ; Bit 3 <- 3
DB 00010000B ; Bit 4 <- 4
DB 00100000B ; Bit 5 <- 5
DB 01000000B ; Bit 6 <- 6
DB 10000000B ; Bit 7 <- 7
;***************************************************
; MAIN PROGRAM INITIALIZATION
;---------------------------------------------------
PWR_UP:
MOV SP, #STACK ; set stack pointer
;
MOV SWTPORT, #0FFH ; set to make the switch ports inputs
MOV LEDPORT, #0FFH ; fix so all LEDs are off
CALL INIT_T1 ; initialize timer 1 interrupt
CLR A ; initialize switch number variable
MOV SwitchNo, A
MOV R0, #SwitchStates ; clear all switch states to 0
MOV R2, #8
SwStInit:
MOV @R0, #0
INC R0
DJNZ R2, SwStInit
MOV R0, #SwitchCounters ; clear all switch counters
MOV R2, #8
SwCtInit:
MOV @R0, #0
INC R0
MOV @R0, #0
INC R0
DJNZ R2, SwCtInit
;
SETB EA ; enable interrupts
JMP MAIN_LOOP
;
;
; here is the main loop state table for the processing
; of the states for a specific switch.
;
; States are defined as:
; State 0: Waiting for a switch input to show it was
; detected going low.
; State 1: Waiting for second verification of a switch
; input in the low state as a debounce verification.
; State 2: Waiting for 5 second counter time to expire while LED
; is kept on for 5 seconds
; State 3: Waiting for switch input to show high again
;
STATE_TABLE:
DW MAIN_STATE_0 ; pointer to State 0 routine
DW MAIN_STATE_1 ; pointer to State 1 routine
DW MAIN_STATE_2 ; pointer to State 2 routine
DW MAIN_STATE_3 ; pointer to State 3 routine
STATE_CNT EQU ($ - STATE_TABLE)/2 ;number of states
;
;
;***************************************************
; main loop process
;
; This processes the current state each switch in a round robin manner.
; Each state is dispatched whenever the timer 1 interrupt indicates that
; 1.25 milliseconds has gone by. Then the state routine for one switch is called
; followed by an increment of the switch number variable. The main loop
; then goes back to the top to wait for another 1.25 msec period to expire.
; Since we process each of 8 switches in turn the effective processing rate
; for each switch input is 1,25 msec * 8 = 10 mSec (or 100 Hz).
;---------------------------------------------------
;
MAIN_LOOP:
JNB Tick, MAIN_LOOP ; wait till a tick has gone by
;
CLR Tick ; clear bit once seen
;
MOV A, SwitchNo ; fetch the state for the current
ADD A, #SwitchStates ; switch
MOV R0, A
MOV A, @R0
CJNE A, #STATE_CNT,ML_A ; check for legal state number
ML_A:
JC ML_B ; state number OK
CLR A ; reset to 0 if invalid
MOV @R0, A
ML_B:
MOV DPTR, #STATE_TABLE ; point to state branch table
CALL CALL_TABLE ; call to state routine
;
MOV A, SwitchNo ; increment to next switch number
INC A
ANL A, #7 ; limit to 3 bits of switch number
MOV SwitchNo, A
;
JMP MAIN_LOOP ; go wait for next tick time
;***************************************************
;NAME: MAIN_STATE_0
; This is state processing routine to wait for a
; switch to be in the pressed state where the input
; for the switch comes from the SWTPORT. If the input
; is still high then just stay in State 0 otherwise
; transition to State 1.
;
; Variable SwitchNo has the current switch number.
;---------------------------------------------------
MAIN_STATE_0:
MOV A, SwitchNo ; get the switch number
CALL SWT_MSK ; get mask for this switch number
ANL A, SWTPORT ; look at switch state
JNZ MAIN_STATE_0X ; exit no change if switch still high
;
;switch is pressed so change to State 1.
;
MOV A, SwitchNo ; set new state for the current
ADD A, #SwitchStates ; switch
MOV R0, A
MOV @R0, #1 ; force next state number to State 1
;
MAIN_STATE_0X:
RET
;***************************************************
;NAME: MAIN_STATE_1
; This is state processing routine to validate that
; switch is still in the pressed state where the input
; for the switch comes from the SWTPORT. If the input
; is still low then transfer to State 2 with LED on
; for 5 seconds. Otherwise if input is high we have
; bounce so return back to state 0.
;
; Variable SwitchNo has the current switch number.
;---------------------------------------------------
FIVE_SEC_CNT EQU 5 * 100 ; 5 seconds is 5 * 100 Hz state 2 rate (i,e, 10 msec)
MAIN_STATE_1:
MOV A, SwitchNo ; get the switch number
CALL SWT_MSK ; get mask for this switch number
ANL A, SWTPORT ; look at switch state
JZ MAIN_STATE_1B ; input low so switch still pressed
;
MAIN_STATE_1A: ; here if switch input bounced back high
MOV A, SwitchNo ; set new state for the current
ADD A, #SwitchStates ; switch
MOV R0, A
MOV @R0, #0 ; force next state number back to State 0
JMP MAIN_STATE_1X
;
MAIN_STATE_1B: ;here if switch input valid low for 10 mSec
MOV A, SwitchNo ; get bit to set on the LED for this switch
CALL SWT_MSK ; get mask for this switch number
XRL A, 0FFH ; invert mask
ANL LEDPORT, A ; drive the LED bit low to turn on the LED
;
MOV A, SwitchNo ; set the counter for this switch to 5 seconds
CLR C
RLC A ; make *2 word type index to counter table
ADD A, #SwitchCounters
MOV R0, A ; make pointer to counter word
MOV @R0, #HIGH(FIVE_SEC_CNT) ;set counter for 5 seconds
INC R0
MOV @R0, #LOW(FIVE_SEC_CNT)
;
MOV A, SwitchNo ; set new state for the current
ADD A, #SwitchStates ; switch
MOV R0, A
MOV @R0, #2 ; force next state number to State 2
;
MAIN_STATE_1X:
RET
;***************************************************
;NAME: MAIN_STATE_2
; This is state processing routine to wait out the
; five second time that the LED is activated. The
; switch input status is just ignored. If the count
; is still active then the state stays as State 2.
; When the 5 seconds has expired then the LED for
; this switch is shut off and the state is changed
; to state 3.
;
; Variable SwitchNo has the current switch number.
;---------------------------------------------------
MAIN_STATE_2:
MOV A, SwitchNo ; decrement the counter for this switch
CLR C
RLC A ; make *2 word type index to counter table
ADD A, #SwitchCounters+1 ;offset to access the low byte first.
MOV R0, A
MOV A, @R0 ; fetch low byte and decrement it
DEC A
CJNE A, #0FFH, MAIN_STATE_2A ;low byte did not underflow
DEC R0
DEC @R0 ; decrement the high byte
INC R0
MAIN_STATE_2A:
MOV @R0, A ; save the low byte
;
DEC R0 ; check for count having gone to zero
ORL A, @R0
JNZ MAIN_STATE_2X ; exit staying in state 2 if counter not expired
;
MAIN_STATE_2B: ;here when the 5 second timer has expired
MOV A, SwitchNo ; get bit to set on the LED for this switch
CALL SWT_MSK ; get mask for this switch number
ORL LEDPORT, A ; drive the LED bit high to turn off the LED
;
MOV A, SwitchNo ; set new state for the current
ADD A, #SwitchStates ; switch
MOV R0, A
MOV @R0, #3 ; force next state number to State 3
;
MAIN_STATE_2X:
RET
;***************************************************
;NAME: MAIN_STATE_2
; This is state processing routine to wait for the
; switch input to go back high, It may have already
; gone high during the 5 second LED period in
; which case we catch it high here on the first check.
; If the switch input is still low then stay in
; State 3. If the switch has gone high then transfer
; back to State 0.
;
; Variable SwitchNo has the current switch number.
;---------------------------------------------------
MAIN_STATE_3:
MOV A, SwitchNo ; get the switch number
CALL SWT_MSK ; get mask for this switch number
ANL A, SWTPORT ; look at switch state
JZ MAIN_STATE_3X ; exit no change if switch still low
;
;switch is released so change to State 0.
;
MOV A, SwitchNo ; set new state for the current
ADD A, #SwitchStates ; switch
MOV R0, A
MOV @R0, #0 ; force next state number to State 0
;
MAIN_STATE_3X:
RET
;***************************************************
;NAME: CALL_TABLE
; Routine to call a routine through a table.
; Come here with A as the 0-n index into the
; table and DPTR pointing to the base of the
; table. The return at end of called routine
; takes execution back to where this routine
; was called from. This routine also uses R0.
;---------------------------------------------------
CALL_TABLE:
CLR C ;
RLC A ; multiply * 2 for word access
MOV R0, A ; save a copy of index
INC A ; increment index to the hig byte
MOVC A, @A+DPTR ; low byte
PUSH ACC ; onto stack
MOV A, R0
MOVC A, @A+DPTR ; high byte
PUSH ACC ; onto stack
RET ; direct branch to the subroutine
END
Enjoy!
Michael Karas
Add Information to this FAQ: If you have additional information or alternative solutions to this question, you may add to this FAQ by clicking here.