Get Adobe Flash player
FacebookTwitterGoogle+
English Arabic French German Italian Portuguese Russian Spanish

Did you know?

There are several advantages and disadvantages to hydro electric energy production. One big advantage is that energy is free once the dam is built.
 

Help us stay online:

small donate

 

statemachinelogoControl systems that manage electrical or mechanical systems must often be able to generate, or respond to, sequential events in the system. This ability to use time as part of the driver equation is in fact one of the important abilities of a microcontroller that makes it such a good control for electrical and mechanical systems. However, implementing multiple sequences can become long and involved if a linear coding style is used.

A simple construct, called a state machine, simplifies the task of generating a sequence by breaking the sequence into a series of steps and then executing them sequentially. While this sounds like an arbitrary definition of a linear piece of code, the difference is that the individual sections, or steps in the sequence, are encoded within a SWITCH/CASE statement.

 

This breaks the sequence into logical units that can be easily recognized in the software listing and, more importantly, it allows other functions to be performed between the individual steps. It does this by only executing one step each time it is called. Repeatedly calling the state machine results in the execution of each step in the sequence.

To retain the state machine's place in the sequence, a storage variable is defined that determines which step in the sequence is to be executed next. This variable is referred to as the state variable, and it is used in the SWITCH/CASE statement to determine which step, or state, in the state machine is to be executed when the state machine is called.

For this system to work, the state variable must be incremented at the completion of each state. However, it is also true that the sequence of states may need to change due to changes in the condition of the system. Given that the state variable determines which state is executed, it follows that to change the sequence of states, one must simply load the state variable with a new value corresponding with the new direction the sequence must go. As we will see, this simple construct is very powerful, and is in fact the basis for multitasking.

So, the short definition of a state machine is a collection of steps (states) selected for execution based on the value in a state variable. Further, manipulation of the value in the state variable allows the state machine to emulate all the conditional statements previously presented in this chapter.

One of the advantages of the state machine-based design is that it allows the easy generation of a sequence of events. Another advantage of state machine-based design is its ability to recognize a sequence of events. It does this by utilizing the conditional change of the state variable, much as described in the previous paragraph. The only difference is that the state variable does not normally change its value, unless a specific event is detected. As an analogy, consider a combination lock: to open the lock, the numbers have to be entered in a specific sequence such as 5, 8, 3, 2. If the numbers were entered 2, 3, 5, 8, the lock would not open, so the combination is not only the numbers but their order. If we were to create a state machine to recognize this sequence, it would look something like the following:

    State = 0;
    SWITCH (State)
    {
    CASE 0: IF (in_key()==5) THEN state = 1;
    Break;
    CASE 1: IF (in_key()==8) THEN State = 2;
    Else State = 0;
    Break;
    CASE 2: IF (in_key()==3) THEN State = 3;
    Else State = 0;
    Break;
    CASE 3: IF (in_key()==2) THEN UNLOCK();
    Else State = 0;
    Break;
    }

Code Snippet 2.16

Provided that the values returned by in_key() are in the order of 8, 5, 3, 2, the state variable will step from 0 to 3 and the function UNLOCK() will be called. The state variable is only loaded with the value of the next state when the right value is received in the right state. If any of the values are out of sequence, even though they may be valid for another state, the state variable will reset to 0, and the state machine will start over. In this way, the state machine will step through its sequence only if the values are received in the same sequence as the states in the state machine are designed to accept.

So, state machines can be programmed to recognize a sequence of events, and they can be programmed to generate a sequence of events. Both rely on the history of the previous states and the programmable nature of the state-to-state transitions.

Implementing a state machine is just a matter of:

    1. Creating a state variable.
    2. Defining a series of states.
    3. Decoding the state variable to access the states.
    4. Tying actions to the states.
    5. Defining the sequence of the states, and any conditions that change the sequence.

For example, consider a state machine designed to make peanut and jelly sandwiches. The sequence of events is:

    1. Get two slices of bread.
    2. Open peanut butter jar.
    3. Scoop out peanut butter.
    4. Smear on first slice of bread.
    5. Open jelly jar.
    6. Scoop out jelly.
    7. Smear on second slice of bread.
    8. Invert second slice of bread.
    9. Put second slice on first slice of bread.
    10. Eat.

OK, the first thing to do is create a state variable; let's call it PBJ. It has a range of values from 1 to 10, and it probably defines as a CHAR. Next, we have to define the sequence of steps in the process, and create a means to decode the state variable.

If we take each of these instructions and build them into a CASE statement to handle decoding the state variable, then all it needs is the appropriate updates to the state variable and the state machine is complete.

SWITCH(PBJ)
    {
    case 1: Get two slices.
    PBJ = 2
    break
    case 2: Open peanut butter jar.
    PBJ = 3
    break
    case 3: Scoop out peanut butter.
    PBJ = 4
    break
    case 4: Smear on first slice of bread.
    PBJ = 5
    break
    case 5: Open jelly jar.
    PBJ = 6
    break
    case 6: Scoop out jelly.
    PBJ = 7
    break
    case 7: Smear on second slice of bread.
    PBJ = 8
    break
    case 8: Invert second slice of bread.
    PBJ = 9
    break
    case 9: Put second slice on first slice of bread.
    PBJ = 10
    break
    case 10: Eat
    break
    Default: break
    }

Algorithm 2.3

The calling routine then simply calls the subroutine 10 times and the result is an eaten peanut butter and jelly sandwich.

Why go to all this trouble? Wouldn't it be simpler and easier to just write it as one long function? Well, yes, the routine could be done as one long sequence with the appropriate delays and timing. But this format has a couple of limitations. One, making a PB and J sandwich would be all the microcontroller could do during the process. And, two, making one kind of a PB and J sandwich would be all the routine would be capable of doing. There is an important distinction in those two sentences; the first states that the microcontroller would only be able to perform one task, no multitasking, and the second states that all the program would be capable of would be one specific kind of PB and J sandwich, no variations.

Breaking the sequence up into a state machine means we can put other functions between the calls to the state machine. The other calls could cover housekeeping details such as monitoring a serial port, checking a timer, or polling a keyboard. Breaking the sequence up into a state machine also means we can use the same routine to make a peanut butter only sandwich simply by loading the state variable with state 8, instead of state 5 at the end of state 4. In fact, if we include other steps such as pouring milk and getting a cookie, and include some additional conditional state variable changes, we now have a routine that can make several different varieties of snacks, not just a PB and J sandwich.

The power of the state machine construct is not limited to just variations of a sequence. By controlling its own state variable, the state machine can become a form of specialized virtual microcontroller—basically a small, software-based controller with a programmable instruction set. In fact, the power and flexibility of the state machine will be the basis for the multitasking system. Before we dive into some of the more advanced concepts, it is important to understand some of the basics of state machine operation.

The best place to start is with the three basic types of state machines: execution-indexed, data-indexed, and the hybrid state machine. The execution-indexed state machine is the type of state machine that most people envision when they talk about a state machine, and it is the type of state machine shown in the previous examples. It has a CASE statement structure with routine for each CASE, and a state variable that controls which state is executed when the state machine is called. A good example of an Execution-indexed state machine is the PB&J state machine in the previous example. The function performed by the state machine is specified by the value held in the state variable.

The other extreme is the data-indexed state machine. It is probably the least recognized form of a state machine, even though most designers have created several, because it doesn't use a SWITCH/CASE statement. Rather, it uses an array variable with the state variable providing the index into the array. The concept behind a data-indexed state machine is that the sequence of instructions remains constant, and the data that is acted upon is controller by the state variable.

A hybrid state machine combines aspects of both the data-indexed and the execution-indexed to create a state machine with the ability to vary both its execution and the data it operates on. This hybrid approach allows the varied execution of the execution indexed with the variable data aspect of the data-indexed state machine.

We have three different formats, with different advantages and disadvantages. Execution indexed allows designers to vary the actions taken in each state, and/or respond to external sequences of events. Data indexed allows designers to vary the data acted upon in each state, but keep the execution constant. And, finally, the hybrid combines both to create a more efficient state machine that requires both the varied execution of the execution-indexed and the indexed data capability of the data-indexed state machine. Let's take a closer look at the three types and their capabilities.
Data-Indexed State Machines
Consider a system that uses an analog-to-digital converter, or ADC, to monitor multiple sensors. Each sensor has its own channel into the ADC, its own calibration offset/scaling factors, and its own limits. To implement these functions using a data-indexed state machine, we start by assigning a state to each input and creating an array-based storage for all the values that will be required.

Starting with the data storage, the system will need storage for the following:

    1. Calibration offset and scaling values.
    2. Upper and lower limit values.
    3. The final, calibrated values.

Using a two-dimensional array, we can store the values in the following format. Assume that S_var is the state value associated with a specific ADC channel:

    ADC_Data[0][ S_var] variable in the array holding the calibration offset values
    ADC_Data[1][ S_var] variable in the array holding the calibration scaling values
    ADC_Data[2][ S_var] variable in the array holding the upper limit values
    ADC_Data[3][ S_var] variable in the array holding the lower limit values
    ADC_Data[4][ S_var] variable in the array holding the ADC channel select command value
    ADC_Data[5][ S_var] variable in the array holding the calibrated final values

The actual code to implement the state machine will look like the following:

    Void ADC(char S_var, boolean alarm)
    {
    ADC_Data[4][S_var] = (ADC*ADC_Data[1][S_
    var])+ADC_Data[0][S_var];
    IF (ADC_Data[4][S_var]>ADC_Data[2][S_var]) THEN
    Alarm = true;
    IF (ADC_Data[4][S_var]<ADC_Data[3][S_var]) THEN
    Alarm = true;
    S_var++;
    IF (S_var > max_channel) then S_var = 0;
    ADC_control = ADC_Data[5][S_var];
    ADC_convert_start = true;
    }

Code Snippet 2.17

In the example, the first line converts the raw data value held in ADC into a calibrated value by multiplying the scaling factor and adding in the offset. The result is stored into the ADC_Data array. Lines 2 and 3 perform limit testing against the upper and lower limits store in the ADC_Data array and set the error variable if there is a problem. Next, the state variable S_var is incremented, tested against the maximum number of channels to be polled, and wrapped around if it has incremented beyond the end. Finally, the configuration data selecting the next channel is loaded into the ADC control register and the conversion is initiated—a total of seven lines of code to scan as many ADC channels as the system needs, including both individual calibration and range checking.

From the example, it seems that data-indexed state machines are fairly simple constructs, so how do they justify the lofty name of state machine? Simple—by exhibiting the ability to change its operation based on internal and external influences. Consider a variation on the previous example. If we add another variable to the data array and place the next state information into that variable, we now have a state machine that can be reprogrammed "on the fly" to change its sequence of conversions based on external input.

ADC_Data[6][ S_var] variable in the array holding the next channel to convert

    Void ADC(char S_var, boolean alarm)
    {
    ADC_Data[4][S_var] = (ADC*ADC_Data[1][S_
    var])+ADC_Data[0][S_var];
    IF (ADC_Data[4][S_var]>ADC_Data[2][S_var]) THEN
    Alarm = true;
    IF (ADC_Data[4][S_var]<ADC_Data[3][S_var]) THEN
    Alarm = true;
    S_var = ADC_Data[6][S_var];
    ADC_control = ADC_Data[5][S_var];
    ADC_convert_start = true;
    }

Code Snippet 2.18

Now the sequence of channels is controlled by the array ADC_Data.  If the system does not require data from a specific channel, it just reprograms the array to route the state machine around the unneeded  channel. The state machine could also be built with two or more next channels, with the actual next channel determined by whether a fault has occurred, or an external flag is set, or a value reported by one of the channels has been exceeded.

Don't let the simplicity of the state machine deceive you; there is power and flexibility in the data-indexed state machine. All that is required is the imagination to look beyond the simplicity and see the possibilities.
Execution-Indexed State Machines
Execution-indexed state machines, as described previously, are often mistakenly assumed to be little more than a CASE statement with the appropriate routines inserted for the individual states. While the CASE statement, or an equivalent machine language construct, is at the heart of an execution-based state machine, there is a lot more to their design and a lot more to their capabilities.

For instance, the capability to control its own state variable lends itself to a wide variety of capabilities that rival normal linear coding. By selectively incrementing or loading the state variable, individual states within the state machine can implement:

    Sequential execution.
    Computed GOTO instructions.
    DO/WHILE instructions.
    WHILE/DO instructions.
    FOR/NEXT instructions.
    And even GOSUB/RETURN instructions.

Let's run through some examples to demonstrate some of the capabilities of the execution-indexed state machine type.

First of all, to implement a sequence of state steps, it is simply a matter of assigning the value associated with the next state in the sequence, at the end of each state. For example:

    SWITCH(State_var)
    {
    CASE 0: State_var = 1;
    Break;
    CASE 1: State_var = 2;
    Break;
    CASE 2: State_var = 3;
    Break;
    }

Code Snippet 2.19

Somewhere in each state, the next state is loaded into the state variable. As a result, each execution of the state machine results in the execution of the current state's code block and the advancement of the state variable to the next state. If the states are defined to be sequential values, the assignment can even be replaced with a simple increment.

However, there is no requirement that the states be sequential, or that the state machine must sequence down the case statement on each successive call to the state machine. It is perfectly valid to have the state machine step through the case statement in whatever pattern is convenient, particularly if the pattern of values in the state variable is convenient for some other function in the system, such as the sequence of energized windings in a brushless motor. The next state can even be defined by the values in an array, making the sequence entirely programmable.

Computed GOTO instructions are just a simple extension of the basic concept used in sequential execution. The only difference is the assignment is made from the result of a calculation. For example:

    SWITCH(State_var)
    {
    CASE 0: State_var = 10 * Var_a;
    Break;
    CASE 10: Function_A;
    State_var = 0;
    Break;
    CASE 20: Function_B;
    State_var = 0;
    Break;
    CASE 30: Function_C
    State_var = 0;
    Break;
    }

Code Snippet 2.20

Based on the value present in Var_a, the state machine will execute one of three different states the next time it is called. This essentially implements a state machine that cannot only change its sequence of execution based on data, but can also change its execution to one of several different sequences based on data.

Another construct that can be implemented is the IF/THEN/ELSE statement. Based on the result of a comparison in one of the states, the state machine can step to one of two different states, altering its sequence. If the comparison in the conditional statement is true, then the state variable is loaded with the new state value associated with the THEN part of the IF statement and the next time the state machine is executed, it will execute the new state. If the comparison results in a false, then the state variable is loaded with a different value and the state machine executes the state associated with the ELSE portion of the IF statement. For example:

    SWITCH(State_var)
    {
    CASE 0: IF (Var_A > Var_B) THEN State_var = 1;
    ELSE State_var = 2;
    Break;
    CASE 1: Var_B = Var_A
    State_var = 0;
    Break;
    CASE 2: Var_A = Var_B
    State_var = 0;
    Break;
    }

Code Snippet 2.21

In the example, whenever the value in Var_A is larger than the value in Var_B, the state machine advances to state 1 and the value in Var_A is copied into Var_B. The state machine then returns to state 0. If the value in Var_B is greater than or equal to Var_A, then Var_B is copied into Var_A, and the state machine returns to state 0.

Now, having seen both the GOTO and the IF/THEN/ELSE, it is a simple matter to implement all three iterative statements by simply combining the GOTO and the IF/THEN/ELSE. For example, a DO/ WHILE iterative statement would be implemented as follows:

    CASE 4: Function;
    State_var = 5;
    Break;
    CASE 5: IF (comparison) THEN State_var = 4;
    ELSE State_var = 6;
    Break;
    CASE 6:

Code Snippet 2.22

In the example, state 4 holds the (DO) function within the loop, and state 5 holds the (WHILE) comparison. And, a WHILE/DO iterative statement would be implemented as follows:

    CASE 4: IF (comparison) THEN State_var = 5;
    ELSE State_var = 6;
    Break;
    CASE 5: Function;
    State_var = 4;
    Break;
    CASE 6:

Code Snippet 2.23

In this example, state 4 holds the (WHILE) comparison, and state 5 holds the (DO) function within the loop. A FOR/NEXT iterative statement would be implemented as follows:

    CASE 3: Counter = 6;
    State_var = 4;
    Break;
    CASE 4: IF (Counter > 0) THEN State_var = 5;
    ELSE State_var = 6;
    Break;
    CASE 5: Function;
    Counter = Counter " 1;
    State_var = 4;
    Break;
    CASE 6:

Code Snippet 2.24

In the last example, the variable (Counter) in the FOR/NEXT is assigned its value in state 3, is compared to 0 in state 4 (FOR), and is then incremented and looped back in state 5 (NEXT).

These three iterative constructs are all simple combinations of the GOTO and IF/THEN/ELSE described previously. Building them into a state machine just required breaking the various parts out into separate states, and appropriately setting the state variable.

The final construct to examine in an execution-indexed state machine is the CALL/RETURN. Now, the question arises, why do designers need a subroutine construct in state machines? What possible use is it? Well, let's take the example of a state machine that has to generate two different delays. State machine delays are typically implemented by repeatedly calling a do-nothing state, and then returning to an active state. For example, the following is a typical state machine delay:

   CASE 3: Counter = 6;
    State_var = 4;
    Break;
    CASE 4: IF (Counter == 0) THEN State_var = 5;
    Counter = Counter " 1;
    Break;
    CASE 5:

Code Snippet 2.25

This routine will wait in state 4 a total of six times before moving on to state 5. If we want to create two different delays, or use the same delay twice, we would have to create two different wait states. However, if we build the delay as a subroutine state, implementing both the CALL and RETURN, we can use the same state over and over, saving program memory. For example:

    CASE 3: Counter = 6;
    State_var = 20;
    Back_var = 4
    Break;
    | |
    | |
    CASE 12: Counter = 10;
    State_var = 20;
    Back_var = 13
    Break;
    | |
    | |
    CASE 20: IF (Counter == 0) THEN State_var = Back_var;
    Counter = Counter " 1;
    Break;

Code Snippet 2.26

In the example, states 3 and 12 are calling states and state 20 is the subroutine. Both 3 and 12 loaded the delay counter with the delays they required, loaded Back_var with the state immediately following the calling state (return address), and jumped to the delay state 20 (CALL). State 20 then delayed the appropriate number of times, and transferred the return value in Back_var into the state variable (RETURN). By providing a return state value, and setting the counter variable before changing state, a simple yet effective subroutine system was built into a state machine. With a little work and a small array for the Back_var, the subroutine could even call other subroutines.
Hybrid State Machines
Hybrid state machines are a combination of both formats; they have the CASE structure of an execution-based state machine, as well as the array-based data structure of a data-indexed state machine. They are typically used in applications that require the sequential nature of an execution-based state machine, combined with the ability to handle multiple data blocks.

A good example of this hybrid requirement is a software-based serial transmit function. The function must generate a start bit, 8 data bits, a parity bit and one or more stop bits. The start, parity, and stop bits have different functionality and implementing them within an execution- based state machine is simple and straightforward. However, the transmission of the 8 data bits does not work as well within the execution based format. It would have to be implemented as eight nearly identical states, which would be inefficient and a waste of program memory. So, a second data-driven state machine, embedded in the first state machine, is needed to handle the 8 data bits being transmitted. The following is an example of how the hybrid format would be implemented:

    SWITCH(Ex_State_var)
    {
    CASE 0: // waiting for new character
    IF (Data_avail == true) THEN Ex_State_var = 1;
    Break;
    CASE 1: // begin with a start bit
    Output(0);
    Ex_State_var = 2;
    DI_State_var = 0;
    Break;
    CASE 2: // sending bits 0-7
    If ((Tx_data & (2^DI_State_var))) == 0)
    Then Output(0);
    Else Output(1);
    DI_State_var++;
    If (DI_State_var == 8) Then Ex_State_var = 3;
    Break;
    CASE 3: // Output Parity bit
    Output(Parity(Tx_data));
    Ex_State_var = 4;
    Break;
    CASE 4: // Send Stop bit to end
    Output(1);
    Ex_State_var = 0
    }

Code Snippet 2.27

Note that the example has two state variables, Ex_State_var and DI_State_var. Ex_State_var is the state variable for the execution-indexed section of the state machine, determining which of the four cases in the Switch statement is executed. DI_State_var is the state variable for the data-indexed section of the state machine, determining which bit in the 8-bit data variable is transmitted on each pass through state 2.  Together the two types of state machine produce a hybrid state machine that is both simple and efficient.

On a side note, it should be noted that the Ex_State_var and DI_ State_var can be combined into a single data variable to conserve data memory. However, this is typically not done due to the extra overhead.

Text taken from site www.eetimes.com