Grade this article: A B C D F

Using State Machines In Your Designs (C) 2003 Hank Wallace What Are State Machines? Programmers today need every trick they can muster to reduce time to market and increase code reliability and maintainability. One of the tools that many programmers are somewhat familiar with but do not use often is the state machine. This is especially true of self-taught programmers who have not been force fed by a computer science professor, and many engineers fit this description. However, state machines are one of the most useful simple tools that we have at our disposal. They are not so much a different computing mechanism as a different thinking mechanism, allowing us to divide complex or tedious algorithms into manageable pieces. The state machine is an abstract mechanism that has a number of well defined resting states. Inputs to the state machine cause the resting state to change depending on the intended purpose. We are concerned here with finite state machines (which have a finite number of states) implemented in software and hardware, and will examine a number of examples. Small state machines are represented by bubble diagrams, with each bubble representing a resting state. See Figure 1. Lines between the states are called edges or transitions. The state machine can occupy only one state at a time and can only transition from one state to another along the edges leading to other states, and only under the labeled conditions. In the example, the state machine is looking for occurrences of the letters 'A' and 'B' in a text stream. (Where the text is coming from and how the state machine senses the characters are details not generally expressed on the diagram.) When an 'A' is detected in the stream in state 0, the machine makes a transition from state 0 to state 1, following the edge in the direction of the arrow. If a 'B' is detected in state 1, a transition is made to state 0. Since the state machine can only occupy one state at a time, the active state indicates whether the last character detected was either 'A' or 'B'. Conceiveably, another character could be received ('C'), in which case no transition occurs. This is a trivial example, of course. In real life, actions are also associated with each transition. For example, light a green LED when 'A' is detected, and a red LED when 'B' is detected. If a condition out of a state becomes true, the state is changed and some action may be taken as a result. The action is noted on the edge. See Figure 2. The two primary formats of state machines are Mealy and Moore. Mealy machines perform an action when a transition occurs. Moore machines perform actions from within each state. Though you may use them interchangeably according to your taste, the machines described here are Mealy machines. The code in each state merely examines input conditions related to transitions exiting the state. This is a very important point. As you think about a state machine and mentally emulate a certain state, you only need worry about the transitions out of that state. Once the machine is in a state, how it got there is unimportant. Therefore, the program you write only need be concerned about the transitions out of a state. Consider a baseball illustration. The four bases are the states. The goal is to transition from home plate to first base, then to second base, third base, and again to home plate. Once you make it to second base, who cares how you got there? Your goal now is to seek a transition (edge) to third base. (You could steal third or wait for a base hit.) The input edges to the state of interest are considered only as outputs from other states. The state has no concern how it came to be, only what it is to do. This simplifies the implementation process. Why Use State Machines? So, before we spend a lot of time delving into coding state machines, why use them? For some tasks, state machines are easier to think and read about than procedural methods such as flow charts or pseudocode. A procedural definition of a task is usually laden with much of the detail of the operation at hand, whereas a state diagram lives at a higher level, leaving out much of the boring detail that we could code in our sleep. I am not committing a heresy, denying the usefulness of other methods, but there are times when state machines are just the right tool. State machines are good for any problem where the system occupies various distinct resting states. State machines are not generally good for mathematical algorithms, for example numerical integration. On the other hand, state machines are good for user interfaces, communications protocols, and some pattern recognition tasks because the function of the system or process can be broken down into discrete steps. Another advantage of state machines is that the current state of the system is completely summarized by one number. The state machine is designed to embody meaningful system operation in each resting state, and this design process illuminates naturally occurring divisions in the function of the system. The result is that the state of the machine is objectively meaningful to the designer, as a high level view, more so than a program counter value, flowchart page number, if-then-else nesting level, or variable value. Even complicated systems with tens of thousands of lines of code may be rendered in a few dozen states, splitting system function into small chunks which can be readily understood. State machine designs are also generally easy to modify. Depending on your specific implementation and hardware/software restrictions, wiring another state into an existing machine is not difficult. This is a frequent demand on user interfaces in embedded programs: "Yes, Sue, that automated hairdo machine looks great, but can you add three more actions to the key?" State machines make that easy, and Sue doesn't even have to work through lunch! Last, with care (and you are a careful programmer), it is possible to modify one state in a machine without worrying about debugged code in another state, in contrast to large, inter-knit procedural programs which may share vast amounts code in nonintuitive and sneaky ways. How To Solve Your Problem With A State Machine Let's solve some sample problems with state machines to get a feel for them. Our first problem is one of simple pattern recognition. We are looking for a text string "OOFOO" in a stream of passing text, possibly on a serial link. The bubble diagram is shown in Figure 3. The machine starts in state zero. As the text passes, the string "OOFOO" causes the machine to transition from one state to the next, until it ends in state 5, the terminal state. If a character is received out of sequence, the machine transitions back to state zero to start the search over. To search the text stream, all we do is pump characters into the state machine and wait for it to terminate in state 5. When that happens, the pattern has been recognized. In C++, we would code this state machine as: state=0; // initialize the state control variable while (1) { switch (state) // perform actions for each state { case 0: // state 0 if (getc() == 'O') // a match state=1; // next state break; case 1: // state 1 if (getc() == 'O') // a match state=2; // next state else state=0; // no match, reset state machine break; case 2: // state 2 temp=getc(); if (temp == 'F') state=3; else if (temp != 'O') // <<<--- new condition handles 'OOOO...' state=0; break; case 3: // state 3 if (getc() == 'O') state=4; else state=0; break; case 4: // state 4 if (getc() == 'O') { printf("string detected!\n"); state=5; } else state=0; break; case 5: // state 5, terminal state break; } } Notice that we took an action in state four upon the transition to state five. That makes this a Mealy state machine. Now, you could do the same pattern recognition by shifting characters through a buffer and using the C function strncmp(): while (1) { buf[4]=buf[3]; buf[3]=buf[2]; buf[2]=buf[1]; buf[1]=buf[0]; buf[0]=getc(); if (strncmp(buf,"OOFOO",5) == 0) printf("string detected!\n"); } That sure looks simpler! But observe the extra computer work involved. For each character received, it has to move all the data in the string once, and it likely will have to make more than one comparison in the strncmp() call. Another unknown is the implementation of strncmp(), which could be good on one processor and lousy on the next, depending on whose string library you use. In the state machine, there is one comparison per character received and no shifting or storage of previously received characters. Even though the state machine looks like more code, it is very fast in real life. The advantage of the state machine is widened when the length of the search string increases to hundreds of characters. Shifting the string would be silly; you would use a circular buffer. But the number of comparisons increases linearly with the size of the search string. The state machine scales with no extra work (CPU time) per character. And it requires only one character of storage. Of course, if you were detecting a string of hundreds of characters, you would not code the state machine as a switch statement. Using a string index (representing the state) and one comparison statement in a loop would be the efficient way to do it, but it still would have the form of a state machine. A good discussion on various string matching algorithms, including the use of state machines, can be found in reference 1. This and other texts on discrete math provide a theoretical treatment of state machines, as in reference 2. Another State Machine Example: XMODEM A good application of state machines is coding communications protocols. The XMODEM protocol is a good candidate for our purposes here. This protocol has been used for years to communicate data between computers. A simplified diagram of the receive state machine for XMODEM is shown in Figure 4. The C++ code follows. state=0; while (1) switch (state) { case 0: // send ASCII "C" as an invitation putc('C'); state=1; break; case 1: // wait for response if (getc() == SOH) // start of a block of data { for (i=0; i<132; i++) // read characters in the XMODEM block buffer[i]=getc(); state=2; } else state=0; break; case 2: // absorb data and place in a buffer if (xmodem_crc(buffer) != 0) // CRC error putc(NAK); // send a negative acknowledge else // data is OK, save { save_buffer(buffer); putc(ACK); // acknowledge the block } state=3; break; case 3: // wait for next data block c=getc(); if (c == SOH) // start of next block { for (i=0; i<132; i++) // read characters in the XMODEM block buffer[i]=getc(); state=2; } else if (c == EOT) // end of data { putc(ACK); state=0; // start over } else state=0; // trash received; reset break; } State zero sends out an ASCII 'C' character to invite the transmitter of data to start sending. The first data block sent by the transmitter starts with an ASCII SOH character (Start Of Header), detected here in state one. This is followed by a block number, some data, and a CRC check code, 132 bytes in all. This data is collected in state one. The save_buffer() call saves the data to a file, for example. State two also sends an ACK or NAK depending on the validity of the data as determined by the CRC computation routine, xmodem_crc(). State three waits for the start of the next block, or the reception of the ASCII EOT (End Of Text) character, signalling the end of the transfer. The machine always returns to state 0 to invite another transmission. Have you seen protocols like this implemented with if-then statements and gotos? What a mess of spaghetti code! Just take a look at the popular ZMODEM source code. It is impossible to visually inspect such a program and feel confident that it will run properly, but the operation of the state machine above is obvious. I have found that I can produce debugged results faster using state machines, where the problem permits. This XMODEM state machine is missing some important failsafe functions for the sake of brevity, but the basic idea is intact. To make it more robust, timeouts on each character reception should be added, with transitions to the zero state if a timeout occurs. Also, XMODEM transmits a block number with each data block, and it should be checked to ensure all data is received correctly. With the growth of the Internet, not many people use XMODEM. We use TCP/IP over the Internet. TCP/IP can be specified using state machines as well, though it is more complex than the example cited here. See RFC 793 (at http://www.ietf.org/rfc/rfc0793.txt) for a good example of the specification of a protocol using state machines. Correspondence I also received a note from a colleague, Scot Kornak. Scot has some good suggestions regarding the C-switch coding of state machines. He uses defined names (or enumerated constants) for the cases in the switch instead of numbers, which would be a good modification to the XMODEM state machine above. So, state 0 would be SEND_INVITATION, state 1 would be WAIT_FOR_SOH, and so on. This makes the states easy to renumber when adding a state, too. Scot also codes the body of each state as a function, which makes the main switch statement easier to read. Do you have a favorite way of coding state machines? If so, let me know and I will share the tips with the other readers (both of them). User Interfaces Many embedded micros are connected to some sort of keypad or switch input system. Picture a typical keypad and LCD display setup where the user can press a key to increment a counter pertaining to a temperature setting. One click of the key increments the temperature one degree, but holding the key down for more than one second increments the temperature one degree every half second. Add to that the requirement to debounce the key with a 50ms timer and you have an application ripe for a state machine. Implementing this function in if-then statements results in code that would take another programmer several cups of coffee to decipher. But using a state machine, the high and low level details are apparent. See Figure 5. The equivalent C++ code follows. The timer is assumed to be maintained by a timer interrupt or other facility. It could even be a dedicated delay. state=0; while (1) switch (state) { case 0: // key open if (key_closed()) { state=1; timer=50; // milliseconds (this is a downcounter) } break; case 1: // wait for debounce delay if (!key_closed()) { state=0; break; } if (timer == 0) // debounce timer expired { temperature=temperature+1; display(temperature); timer=1000; // milliseconds state=2; } break; case 2: // wait to repeat the key action if (!key_closed()) { state=0; break; } if (timer == 0) // timer expired, increment again { temperature=temperature+1; display(temperature); timer=500; // milliseconds // stay in this state } break; } Isn't that simple? Adding a temperature decrement key is as easy as wiring in a couple more states connected to state zero. I have created huge embedded user interfaces encompassing dozens of screens using this approach and they are very easy to maintain, debug, and expand. In such large interfaces, each part is implemented as a sub-state machine in a subroutine. For example, you would have a separate interface for the factory configuration screens, field setup screens, user data entry screens, etc. When your user interface is drawn out as a state diagram, it's easy to see unnecessary states or inefficient operation. For example, my printed circuit board CAD program responds to many keyboard commands, but almost all start with the letter M. Bad idea! Why must I type M at the start of each command? Well, to differentiate them from four commands that don't start with M. Seventy five start with M, and four don't. If the programmer had written the user interface out in state diagram form, he or she would have seen the wasted keystrokes and redesigned the software. A related example to the user interface is the adventure game. I remember when adventure games were played without graphics, when most terminals had no graphics capability. The complexity of these programs was staggering, even without all the glitz and sound. Just how do those programmers keep all that detail straight? State machines! Each room (or space) in the game is effectively a state. There are edges out of the state, such as tunnels or magic passages. Conditions are attached to each edge that determine whether you may pass, like the possession of a certain object or defeating a guard or troll. See? The entire space can be mapped onto a state machine, making this complex world manageable. The staff engineer gets a lesson from the V.P. of Engineering. How Does One Code A State Machine? We have seen one way of coding a state machine, the switch statement in C or C++. This method is actually a formal way around the goto paranoia that most structured programmers suffer from, including me. Usually when I find a goto in a C++ program, I can be assured that the program is garbage! It is obvious that the goto's were stuffed in during a late night debugging session, about three hours before shipment. Unwinding the code to get at the function of the program is daunting. (Please, goto-holics, no flames! If you use gotos sparingly, slack shall be cut for you. Not all programmers who use gotos are stupid, but all stupid programmers use gotos!) But haven't you suspected that there are just some problems that demand goto's? Are there some problems that can be solved more efficiently by a nasty little knot of spaghetti code? I think so, but instead of sending time bombs of gnarly code into the next century to persecute your grandchildren, let's use state machines. The switch statement brings order to goto chaos. The destinations of the 'gotos' are actually the limited number of cases in the switch. We also have a state diagram that corresponds directly to the code. When was the last time you found (or made) a flowchart for that 1000 lines of spaghetti code? Without goto's, we can branch arbitrarily between system states, and the branches make intuitive sense, being directly related to real world conditions, not whether some variable is less than some other variable mod 34! Most state machines written in a high level language are best expressed in terms of switch statements for simplicity. However, in several systems I have had the problem of detecting a bit stream from a radio or serial link. When programming a small, dedicated micro in assembly language, it is sometimes expedient to code the state machine as a tight sequence of instructions, making the processor itself the state machine. For example, say we need to detect the unique pattern of 16 bits 0x4d7c. I have used this pattern as a unique word tacked to the front of data packets transmitted over radio. The most significant bit is transmitted first, a zero. The diagram in Figure 6 illustrates the state machine. This diagram is more complicated than the others we have looked at because the pattern to be detected is more complex: '0100110101111100'. There are several edges that move to previous states but not state zero. To see why, look at an example where the first nine bits of the word have been received: 010011010. If the next bit is a 1, it matches what was expected and all is well. However, if the next bit is a zero, a mismatch occurs. But do we reset the machine to state zero? No, because in what has been received so far (0100110100), the last four bits look like the start of the pattern. So, instead of transitioning to state zero on this particular error, we move to state four, as if we have already received the first four bits of the pattern (which we have). This prevents a partially correct pattern from causing the machine to miss the full pattern following. It is easy to see where cases like this occur. Slide the pattern by a copy of itself and look for sections in the middle that match the start of the pattern. I have written a small C program that generates C source code for a state machine given a binary pattern to be detected. It performs the comparisons of the pattern against itself and creates the proper state transitions. The source to this state machine generator and the output for the diagram above is found at the end of this article. It takes the tedium out of determining the error transitions. Implemented on a PIC micro, the state machine for the bitstream detector follows. The subroutine rxclk simply waits for the falling edge of the clock. The data bit is sampled on input RA0. The program cycles around this code until the pattern is detected, when it falls out the bottom. This is a small state machine, consisting of only three instructions per state. A PIC running at 20MHz could digest data at a rate of several hundred kilobits per second using this method. st00 call rxclk ;wait for falling clock edge btfsc ra,0 ;skip to next state if bit correct goto st00 ;else, do error transition st01 call rxclk btfss ra,0 goto st01 st02 call rxclk btfsc ra,0 goto st00 st03 call rxclk btfsc ra,0 goto st02 st04 call rxclk btfss ra,0 goto st01 st05 call rxclk btfss ra,0 goto st03 st06 call rxclk btfsc ra,0 goto st00 st07 call rxclk btfss ra,0 goto st01 st08 call rxclk btfsc ra,0 goto st00 st09 call rxclk btfss ra,0 goto st04 st10 call rxclk btfss ra,0 goto st03 st11 call rxclk btfss ra,0 goto st01 st12 call rxclk btfss ra,0 goto st01 st13 call rxclk btfss ra,0 goto st01 st14 call rxclk btfsc ra,0 goto st00 st15 call rxclk btfsc ra,0 goto st02 ;pattern detected! This method is only useful if the processor can be dedicated to the task; no other work may be done, except possibly some in the rxclk subroutine. State Machine Source Code Generator Here is the state machine generator program. It can generate state machines of up to 100 states. Just feed it the pattern to be detected on the command line. The source code for the pattern detector is written to the standard output device. /* This is C program that generates a state machine detector for the specified binary bit stream. Use it as you wish, at your own risk. Hank Wallace 06-Apr-00 Revision 06-Apr-00 */ #include #include #include struct // this structure holds one state's edges { char s1; char s2; } states[100]; void main(int argument_count, char *argument[], char *environment[]) { char s[200]; // holds the string to be detected int len; // length of detected string int i,j; // general index if (argument_count < 2) { printf("This program generates a state machine in C source code\n"); printf("given a binary string to be detected.\n\n"); printf("Usage:\n\n"); printf(" A> STATEGEN DETECT_STRING\n\n"); printf("Where DETECT_STRING is a series of 1's and 0's.\n"); printf("The maximum string size is 100 bits.\n"); exit(1); } // fetch the string to be detected strncpy(s,argument[1],100); s[100]=0; len=strlen(s); // initialize the state machine with default values for (i=0; i<len; i++) { states[i].s1=i+1; // matched character advances machine one state states[i].s2=0; // mismatched character resets the machine } // fixup the mismatched character state transitions to // accommodate repeated substrings in the stream for (i=1; i<len; i++) // fake an error in each symbol { s[i]=(s[i]=='0') ? '1' : '0'; // invert the symbol for (j=1; j<=i; j++) // compare substrings from largest to smallest { if (strncmp(s,&s[j],i-j+1) == 0) { states[i].s2=i-j+1; // adjust the transition break; } } s[i]=(s[i]=='0') ? '1' : '0'; // fix the symbol } // dump the results as C source code printf("// detecting the pattern '%s'\n",s); printf("switch (state)\n"); printf(" {\n"); for (i=0; i<len; i++) { printf(" case %d: // '%c'\n",i,s[i]); printf(" if (getc() == '%c')\n",s[i]); printf(" state=%d;\n",states[i].s1); printf(" else\n"); printf(" state=%d;\n",states[i].s2); printf(" break;\n"); } printf(" case %d: // terminal state\n",len); printf(" break;\n"); printf(" }\n"); } This is the output of the program given the pattern used in the example. // detecting the pattern '0100110101111100' switch (state) { case 0: // '0' if (getc() == '0') state=1; else state=0; break; case 1: // '1' if (getc() == '1') state=2; else state=1; break; case 2: // '0' if (getc() == '0') state=3; else state=0; break; case 3: // '0' if (getc() == '0') state=4; else state=2; break; case 4: // '1' if (getc() == '1') state=5; else state=1; break; case 5: // '1' if (getc() == '1') state=6; else state=3; break; case 6: // '0' if (getc() == '0') state=7; else state=0; break; case 7: // '1' if (getc() == '1') state=8; else state=1; break; case 8: // '0' if (getc() == '0') state=9; else state=0; break; case 9: // '1' if (getc() == '1') state=10; else state=4; break; case 10: // '1' if (getc() == '1') state=11; else state=3; break; case 11: // '1' if (getc() == '1') state=12; else state=1; break; case 12: // '1' if (getc() == '1') state=13; else state=1; break; case 13: // '1' if (getc() == '1') state=14; else state=1; break; case 14: // '0' if (getc() == '0') state=15; else state=0; break; case 15: // '0' if (getc() == '0') state=16; else state=2; break; case 16: // terminal state break; } This state machine corresponds to the PIC pattern detection code, above. State Machine via Tables Another way to implement state machines is using tables. This method can be applied to software and hardware situations. To illustrate, let's create both types of tabular state machines for the serial detection example, above. First the software table driven state machine. Let's continue with the bit stream detector. We are trying to detect the pattern '0100110101111100'. The trick is to create a table of data that embodies the expected bit values and state transitions in case of a correct bit or an error. The table is shown below. const char table[]= {01,00, // state 0 00,02, // state 1 03,00, 04,02, 00,05, 03,06, 07,00, 00,08, 09,00, 04,10, 03,11, 00,12, 00,13, 00,14, 15,00, 0xFF,02}; // state 15 Each state consists of two consecutive table entries, shown here on the same line for clarity. The left hand entry is the next state if the input bit is a zero. The right hand entry is the next state if the input bit is a one. So, in state zero, the machine advances to state one if the input bit is zero. In state one, the input bit has to be a one to advance to state two. Errors cause transitions, too, but to lower state numbers, per the diagram. In state 15, if the input bit is zero, a value of 0xFF flags the successful recognition of the bitstream. Here is a C++ code fragment that implements this state machine based on the table above. state=0; while (state != 0xff) { bit=get_input_bit(); state=table[state*2+bit]; // get next state } printf("pattern detected!\n"); That's pretty simple! All the complexity is embodied in the table. This method is advantageous if your state machine does not have to perform any complex actions when it changes state, or within each state. Otherwise, the switch style works better. If the actions needed can be coded into instructions of a sort, you could even include them in the table. The algorithm then interprets (executes) the instructions at each step based on the transition taken. (Did we just design a microprocessor?) This tabular method also works well if your system changes its state machine dynamically while it is running. In this case you have one routine that executes any size state machine by simply supplying it a pointer to the table. You can burn this table into an EPROM and execute it from there. The schematic in Figure 7 shows the EPROM, an address latch, and a clock. The data input bit toggles the least significant address line, A0, on the EPROM. Thus, the input data bit selects one of two locations in the memory containing either the state corresponding to a matching bit value, or an error state transition. The circuit is clocked once for every bit. The data coming out of the EPROM becomes the state number and EPROM address for the next bit. You can load the EPROM with the same data as in the table above. When the state machine terminates, the D7 bit will go high because of the 0xFF in the table. That signal can be routed to other circuits to indicate a valid detection. Be sure you have a signal to clear the address latch to initialize the state machine. Tabular state machines are adaptable easily to inputs of more than one bit. Instead of using the least significant address bit, A0, for the input, several address bits would be used. For example, if you have four binary inputs to the state machine, they would be connected to address lines A0 through A3, and each state entry in the table would consist of 16 possible transitions, selected by the four input bits. State machines such as this one can be clocked very fast. Using a 15ns SRAM as the memory, one could conceivably run the state machine at 50 megabits per second! State machines may also be rendered in FPGAs or other programmable logic families, resulting in speeds well over 100MHz. When you start thinking state machines, you see them everywhere. Effectively, any sequential circuit is a state machine. Technician Vipperman and engineer Higgins apply a bug fix to state one. Debugging State Driven Code I mentioned previously that debugging state machine code is easier than the usual if-then-goto abominations. This is because the function of the program is divided neatly into states, and not apportioned randomly over a zillion disconnected functions. Every bug is associated with typically one state, narrowing the field of investigation greatly. You will just have to try state machines yourself to see what I mean. There is an additional debugging benefit when using state machines and it is that the numeric state value represents real, useful information about what the program is doing at any time. As some correspondents have pointed out already, you can use enumerated constants to give each state a descriptive name, too, lending more readability to the program. (I have not done this here for bare simplicity.) Now the computer's program counter is also a state machine indicator, showing the state of the CPU. About every third program I run under Windows 98 crashes, displaying an obtuse dump including the program counter value, as if it helped. The problem is that the program counter is not easily related to the program's or programmer's intentions, especially for dynamically relocatable code, and especially when the entire description of the crashing program is some cryptic module name. Thanks again, Bill! However, when an algorithm is coded using a state machine, the state value contains much information about the program's condition. A tool that I put in most every program I write is a state machine history list. In communications code, everything is done using state machines. Sometimes hierarchies of state machines are used, as with the OSI seven layer communications model. Each layer is implemented as a state machine. If the program logs the state machine values periodically, or runs them through a FIFO that can be queried, you can find out exactly what the program thinks it is doing when it is behaving poorly. Regardless the ultimate size of the program, most states only check a few exit conditions, and if the program is stuck, one of those conditions must be responsible. Thus, this technique eliminates the vast majority of the code from suspicion. You may only need a small FIFO. Just update the FIFO with the current state values when they change. If you use an event logging facility, saving a time/date stamp on each state change is valuable. For example, here is XMODEM state machine we looked at previously: state=0; while (1) switch (state) { case 0: // send ASCII "C" as an invitation putc('C'); state=1; break; case 1: // wait for response if (getc() == SOH) // start of a block of data { for (i=0; i<132; i++) // read characters in the XMODEM block buffer[i]=getc(); state=2; } else state=0; break; case 2: // absorb data and place in a buffer if (xmodem_crc(buffer) != 0) // CRC error putc(NAK); // send a negative acknowledge else // data is OK, save { save_buffer(buffer); putc(ACK); // acknowledge the block } state=3; break; case 3: // wait for next data block c=getc(); if (c == SOH) // start of next block { for (i=0; i<132; i++) // read characters in the XMODEM block buffer[i]=getc(); state=2; } else if (c == EOT) // end of data { putc(ACK); state=0; // start over } else state=0; // trash received; reset break; } What should the typical pattern of state transitions look like? With the machine sitting idle, it sends out an ASCII 'C' in state zero, then goes to state one to wait for a response. If none is had within some timeout period, a transition to state zero occurs. The state sequence would be 0, 1, 0, 1, ... For a complete data transfer, the sequence would be: 0, 1, 2, 3, 2, 3, 2, 3, ... 0 States two and three repeat as the data is received and acknowledged. It's easy to see how you can visually judge the health of the state machine by glancing at the state history buffer. With more complex state machines, you learn to recognize patterns of good and bad behavior as you debug the system during development. For example, with this XMODEM machine you should never see a transition to state one in the middle of a data transfer. Here is some sample code illustrating how to save state history with a buffer and a function call at the top of the state machine: // create the state history buffer #define STATES 10 int state_buf[STATES]; state=0; while (1) save_state(state_buf,state); <--- save current state switch (state) { case 0: // send ASCII "C" as an invitation putc('C'); state=1; break; . . . } The function save_state() follows. void save_state(int *state, int value) // This function saves state values in a queue for debug purposes. { int i; if (state[0] != value) /* state has changed */ { for (i=STATES-1; i>=1; i--) /* shift buffer */ state[i]=state[i-1]; state[0]=value; } } The state is only stored in the buffer when the value changes. This function is intended for short history buffers of ten states or so. If you use a longer buffer, don't shift it manually but use a circular buffer. Extending the benefit of state oriented debugging (or SOD; I'll see you on the seminar circuit), in a multitasking program where many tasks are interacting and performing complex operations, having state value FIFOs for each task effectively partitions the program into a matrix. See Figure 8. Thus, if you have access to the task number and state number when a program hangs (or the state number of a frozen task), you have eliminated 95% of the code. I have used this advantage to debug programs far afield, where my only connection was through a low speed modem link. The debugging power is amazing, and the overhead is minimal. The code that runs the state machine saves the state value to the FIFO only when it changes, which takes little processing time. Multitasking Without Interrupts We have been discussing the care and feeding of state machines. Next we will see how state machines can help you easily write complex programs. State machines are useful to implement multitasking on micros with limited interrupt capabilities. The Microchip PIC series has several members with no interrupt facility. I remember my first CP/M-80 machine with WordStar and how it could print while I edited a file -- without interrupts (though slowly). How do you make the processor perform several complex tasks at once? State machines! For example, let's use a low-end processor to receive a file via XMODEM while tending to a keyboard interface (using a couple code examples previously presented). The high level structure of the program is as follows: void main (void) { int // state machine control variables xmodem_state=0, keyboard_state=0; initialize_hardware(); while (1) // a super loop program { xmodem_state_machine(&xmodem_state); keyboard_state_machine(&keyboard_state); } } This is called cooperative multitasking. The state machines are switch based code, as illustrated before in several examples, only without their own while() loops: void xmodem_state_machine(int *state) { switch (state) { case 0: // send ASCII "C" as an invitation putc('C'); state=1; break; case 1: // wait for response if (getc() == SOH) // start of a block of data { for (i=0; i<132; i++) // read characters in the XMODEM block buffer[i]=getc(); state=2; } else state=0; break; case 2: // absorb data and place in a buffer if (xmodem_crc(buffer) != 0) // CRC error putc(NAK); // send a negative acknowledge else // data is OK, save { save_buffer(buffer); putc(ACK); // acknowledge the block } state=3; break; case 3: // wait for next data block c=getc(); if (c == SOH) // start of next block { for (i=0; i<132; i++) // read characters in the XMODEM block buffer[i]=getc(); state=2; } else if (c == EOT) // end of data { putc(ACK); state=0; // start over } else state=0; // trash received; reset break; } } The same XMODEM code is used as before, except that every call of the state machine runs through it only once, checking the conditions in the currently selected state. (Our getc() here returns some dummy value (-1) if no character is available.) The state control variables must live apart from the functions for persistence between calls, and they are declared here in main(). For the keyboard control state machine, we also use the state machine developed in a past installment. void keyboard_control_state_machine(int *state) { switch (state) { case 0: // key open if (key_closed()) { state=1; timer=50; // milliseconds } break; case 1: // wait for debounce delay if (!key_closed()) { state=0; break; } if (timer == 0) // expired { temperature=temperature+1; display(temperature); timer=1000; // milliseconds state=2; } break; case 2: // wait to repeat the key action if (!key_closed()) { state=0; break; } if (timer == 0) // expired, increment again { temperature=temperature+1; display(temperature); timer=500; // milliseconds // state=2; // stay in this state } break; } } Again, the state machine function runs through only once on each call. The net effect is that the CPU spends half its time checking the conditions for each machine in a round robin fashion. You can load up the main loop with as many state machines as the processor has time to execute. Here again, the main loop has access to the state values of each machine and can implement debugging functions to make that information accessible to you, the programmer, while the program is executing. What are the limits to this method? You have to be careful in each state machine not to dwell for any period of time. For example, the putc() calls in the XMODEM routine should not wait indefinitely for a port to become ready, otherwise the other machines will not run. (I really should break up the loop in XMODEM state 3 to minimize delays.) In this case the user would notice some problems with keyboard response. This means at times you will have to create a new state to execute activities that might take a while, and execute them in a state driven fashion. A small processor can do a lot of work using this method, and the code remains readable and maintainable. Another limitation is that it's hard to do time critical tasks. If each state machine has several states, the execution times of each may vary widely, even if they are all rather fast. Thus, to make an accurate timing measurement, a hardware timer of some sort is needed. Software delay loops are out of the question. But even the most rudimentary processors have some hardware timer or counter. Conclusion We have looked at several applications of state machines, hardware and software. If you have never used state machines, go back to an old program and see how you could have applied them. When you start using state machines, you will be surprised at the power this simple tool provides. References 1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, "Introduction to Algorithms," (Cambridge: MIT Press, 1990) p. 862. 2. William Barnier, Jean B. Chan, "Discrete Mathematics," (St. Paul: West Publishing Company, 1989) p. 387. Author Biography Hank Wallace is the owner of Atlantic Quality Design, Inc., a consulting firm located in Fincastle, Virginia. He has experience in many areas of embedded software and hardware development, and system design. See www.aqdi.com for more information.