DreamCatcher Feature Article

-->

Helping You To Develop Your Product Roadmap

Feature Article: ASM for Firmware?

Algorithmic State Machine (ASM) is a method typically used in designing digital integrated circuits. While its reliability and predictability are the reasons ASMs are used, could they also be used to develop embedded firmware while retaining its benefits? As we shall see, it is certainly possible and rather straightforward, albeit with minor implications.

Let us consider a very simple stopwatch with two buttons (A and B) that has the following states:

IDLE: counter zeroed
RUN: counter increments
STOP: counter stopped

The stopwatch's ASM is shown in Figure 1. When implemented in hardware, the states are controlled by D-flip-flop, decisions by demultiplexors, and path connections by OR gates.

Figure 1: ASM of a Stopwatch

Coding the ASM in software is rather straightforward with a Finite State Machine (FSM) pattern. The FSM pattern is best implemented as a switch-case construct in the C programming language, whereby each state is coded as a case statement, as shown in Listing 1. Each case block first codes the operations of the state followed by the conditional operations (if any) and next state condition (diamond preceding each state) to determine the next state.

Two implications between implementing ASMs on hardware and software arise. Thr first implication is that software execution is sequential. The simplest way for software to stay true to the ASM is to make a copy of each variable (register) on the RHS of assignments and ensure the LHS of assignments uses this copy. A better way, as carried out in Listing 1, is to reorder the assignments so that those whose LHS requires the RHS of other assignments are executed earlier.

The second implication is the condition signals have to be read by the firmware. If a system has few inputs and/or if most conditions use most signals, it is usually easiest to read all input signals on each iteration before FSM execution, as shown in Listing 1.

#define ST_IDLE 0 //Defining states #define ST_RUN 1 #define ST_STOP 2 void main(void) { unsigned char key, state = ST_IDLE; unsigned long CNT; for(;;) { key = KeyPressed(); //Read all inputs switch(state) { case ST_RUN: { //RUN state Display(CNT); //Display counter CNT++; //Increment counter if(key == 1) state = ST_STOP; //Button A pressed break; } case ST_STOP: { //STOP state Display(CNT); //Display counter if(key == 1) state = ST_RUN; //Button A pressed else if(key == 2) state = ST_IDLE; //Button B pressed break; } default: { //ST_IDLE Display(CNT); //Display counter CNT = 0; //Reset counter if(key == 1) state = ST_RUN; //Button A pressed break; } } } }

Listing 1: ASM to FSM Programmed in C

Firmware developers may by now wonder, "Why not use flowcharts and/or state transition diagrams (STD)?". Well, ASM has a few advantages over flowcharts and STDs.

For a start, STDs state the event rather than the specific signals that cause transitions, and an STD does not indicate the amount of time it stays in a state. Flowcharts are clearer in showing transitions, but may have many complex operations within each process box. ASM on the other hand explicitly shows operations within states and state transitions. This level of explicitness allows firmware (and potentially hardware) to be automatically generated from ASM, which significantly reduces coding time and errors.

Another key advantage of ASM is during implementation. Systems designed as ASMs are easier to partition between hardware and software, and are easier to be repartitioned during subsequent iterations.

From the reliability perspective, conditional loops is a major cause of "system hang" when execution is trapped within a loop with unsatisfiable exit conditions. Unlike flowcharts and STDs that may specify loops within states/processes, loops are always non-blocking states in ASMs. Hence, the execution of loops in ASMs do not prevent (block) the execution of other ASMs of the program, making ASMs inherently more reliable than flowcharts and STDs.