Using finite state machines to design software - Embedded.com

Using finite state machines to design software

Designing software can be a bewildering and stressful experience. The initial creative steps are fraught with risk and uncertainty, since they define the entire course of development for a software project and affect its outcome and success.

When creating new software, many programmers find it easier to just start coding without any prior formal plan. Experience has convinced them that there may not be a design method appropriate for their project or that any formal planning wastes too much time without significantly enhancing the quality of the final product. However, the concerns for good software engineering and software quality indicate that any design method that is simple to use and that helps create better code and documentation should be welcomed by the majority of software practitioners.

A common approach these days is to apply design patterns when planning and implementing a software project. A finite state machine (FSM) is one design pattern; other patterns not discussed here include consumer/producer, message queuing, master/slave, and so forth. A variety of design patterns could be applicable at various stages of a software project, from the initial overall concept to the lowest level coding phase.

This article is a brief and practical tutorial in designing software using finite state machines. It will lead the reader from the initial design steps through the creation of source code. The employment of an FSM model has become fairly common in many software applications, particularly when a project specifies the use of the Unified Modeling Language (UML).

Note however, that this writing makes no other reference to UML and requires no exceptional knowledge other than basic programming concepts and some common sense.

All that is needed is some means to create a two-dimensional table.

Let's begin with the sales pitch for using the FSM design pattern:

• It's applicable to a large variety of software projects.

• It can be valuable at many stages of development, from top-level design to module coding.

• It provides a fairly rigorous strategy that yields a simple and consistent code structure.

• It creates a useful documentation and maintenance product that reflects the organization of the code.

• It can incorporate an effective debugging tool with minimal effort.

• It lends itself to design-by-committee and peer reviews.

The fundamental idea behind FSM design is that a large class of software problems can be viewed from the perspective of state machines and can therefore be solved using methods borrowed from other disciplines, particularly digital electronics. The type of software products that lend themselves best to the FSM model can be categorized as having distinct “modes” or being “control intensive”; that is, they contain a fairly complex logic structure that results in a relatively large number of control blocks, such as case structures and conditional statements.

Embedded and real-time systems are good candidates, as are multitasking executives, command interpreters, language processors, communication drivers, device handlers–the list goes on. And while the FSM pattern could also be appropriate for implementing some user-oriented applications such as accounting software or other business packages, it may not be ideal for designing algorithmic or computational routines.

The first order of business is to get a good grip on the concept of a finite state machine . An FSM can be informally defined as any device, be it electronic, mechanical, hydraulic, or just conceptual, that accepts a finite number of different inputs and can produce a finite number of diverse outputs. A key requirement is that the device must have some internal memory that allows it to remember sequences of inputs, so that the output is not only dependent on the combination of input values but also on the order in which they were applied.

As an example, a bicycle chain lock with three numbered dials as depicted in Figure 1 will open when the dials are set to the proper numeric code. It does not matter which dial was turned first, as long as the proper combination of digits is selected. This device requires no memory and is thus not an FSM but rather a combinational device.

On the other hand, the familiar school padlock with a single numbered dial shown in Figure 2 will only open if the right three numbers were entered in the proper sequence.

Manipulating the padlock can produce one of two visible outcomes: open or closed. You could imagine that the device generates an “Unlock” or “Lock” output signal to the shackle to command it to open or close. The padlock seems to have the ability to “remember” the order in which the numbers were entered and is thus a good example of an FSM. It is no surprise that FSMs are also known as sequential machines.

While nothing may be known about the mechanical workings of the padlock, one can conceptualize that it must have some internal configurations or “states” that are brought about by certain inputs and are also dependent on the history of the input values. So a state could be thought of as an encapsulation or a “summary” of specific sequences of past inputs; keep in mind that two or more distinct input sequences may map into the same state.

The latter point can be illustrated with another example: a telephone could be considered to be an FSM. When the receiver is picked up by the party initiating a call, normally a dial tone is heard; thus, the state could be labeled “Dial tone.” After the proper sequence of digits has been input and the receiving or called party picks up, the state could change to “Talking.” At this point, entering any more digits would modify the original input sequence but the “Talking” state would remain the same.

To modernize the padlock example, replace it with an electronic version that controls a deadbolt via a numeric keypad as in Figure 3 . The keypad is the obvious input device; the deadbolt can be thought of as the output device for the system.

Assume that the proper combination to unlock the device is 4-9-1 and that at first the device is locked. In this example, the internal configuration of the device will be arbitrarily labeled the “Initial” state, even though nothing may be known about the true state of the gates, flip-flops, or other components inside the device.

The initial state implies that the device expects the first correct digit. Upon pressing the “4” key, the device could be viewed as recognizing the start of a correct input sequence and would react by creating a new state labeled “Got 1st number.” Regardless of which key was pressed, the deadbolt should not unlock at this stage.

If the “9” key is pressed next, the new state could be called “Got 1st & 2nd number,” with the deadbolt remaining unchanged. Finally, when pressing the “1” key, the latch would output a signal for the deadbolt to unlock. One could be tempted to assign a new state to this unlocked condition, but to keep things simple, assume that the system reverts internally to the initial state; thus, avoiding adding any unnecessary states.

A very crucial point about this example is that the states are abstract notions that allow one to conceptualize a design, even though it may be totally unrelated to the actual implementation of the latch. In fact, it may not be known if the internals of the device are mechanical, electronic, or operate by magic.

Another significant requirement for an ideal FSM is that when an input is applied, the output changes instantly and the new state is immediately stable. I'll show you later why this is important, but keep in mind that most physical systems will have some delay between the time a stimulus is applied and a change in state or a new response is generated.

This description of the device can be formalized with the state transition table (STT) shown in Table 1 .

View the full-size image

Inputs in Table 1 are represented by rows; states correspond to columns that have been labeled A through C for convenience. Notice the “Default” row, which is a bucket designed to capture all inputs other than 4, 9, and 1.

In the following discussion, I will refer to individual cells in Table 1 by the column and row labels, for example, the bottom right cell is “C-Default.” Neither columns nor rows need to be ordered in any way. For a given combination of input and current state, each cell displays the next state and a list of actions or outputs to be generated at that point.

For instance, if the device is in the initial state A and receives a “4” input, cell A-4 at the top left indicates that there is a transition to state B and a “Lock” output signal is generated. Note that several cells contain only a state transition, since no output is generated. For instructional purpose, blue type is used to highlight the cells that correspond to a successful input sequence, leading to unlocking the deadbolt.

Notice that all cells in column A contain a “Lock” output. The reason for that is that once the latch is unlocked, the device ends up in the initial state A, as indicated in cell C-1; pressing any key would then allow for relocking the deadbolt. If the wrong digit was selected before the proper sequence was completed, the latch would revert to the initial state A, as indicated by row “Default,” and the deadbolt would remain closed.

The system could perhaps be improved by using a special key, say “#”, to lock the latch. That would require redesigning the table and adding another row corresponding to the input “#”.

This exceedingly simple example has very few states and only one output device that can assume two possible values. In more complex applications, each cell could list several actions or outputs to be generated.

The next step is to generate the source code that embodies the STT just created. I'll also discuss optimization of that code. In the hope of making the logic apparent to most programmers, I presented the code in a loosely syntaxed C-like pseudo-language. It will be left to the object-oriented programmers to figure out how to solve the problem using classes and objects.

In general an STT can be coded using two levels of nested multiple-decision or SWITCH structures. The first-level SWITCH contains a list of cases corresponding to all the states. Each case within the structure would contain a second-level SWITCH structure listing the various possible inputs. Or vice versa, one could start with the outer SWITCH listing all the inputs, where each input case would contain a SWITCH structure with a case for each state.

View the full-size image

In the code in Listing 1 , Set_bolt is an unspecified function that outputs a LOCK or UNLOCK signal to the deadbolt. Note that break statements are implied at the end of each case.

Note that the Default block corresponds closely to the “Default” row in our transition table.

The code in Listing 1 can be simplified by “flattening” the two-level nested SWITCH structures into a single level SWITCH , thus, reducing the overall complexity as shown in the code in Listing 2 .

View the full-size image

This example makes use of a multivariable SWITCH structure dependent on both the State and Input values; this is not normally allowed in C or other programming languages. But that can be easily resolved by replacing the SWITCH structure with a series of IF and ELSE IF statements such as:

IF(State==A .AND. INPUT==4)    

and so on; or a function could be created that returns some combined value for State and Input .

The latter code results in a more reliable and maintainable module, not just because of the fewer number of “defect opportunities” (in other words, lines of code), but mainly because of the less complex single-level SWITCH structure. Also, should changes in the design at a later time require additional states or inputs, the source can be easily edited by inserting more cases with all the new combinations of states and inputs just above the Default statement.

The fifth line of the source code includes the statement IF(Debug) write Input, State that creates a trace of states and inputs on hard copy or in a file when the Debug flag is set. That sequence of states and inputs reveals a great deal about what happens in the code and should confirm the earlier claim that the FSM paradigm can incorporate an effective debugging tool by just adding that single line of code.

The debugging facility could be improved by also listing the last output. In the case of a hard real-time or time-critical application where writing to a printer or a file would unacceptably disturb the timing, one could push the state and input variables into a memory buffer for postmortem viewing. Both improvements will require a bit of additional code that most readers will be able to figure out.

A few final points about the overall design process need to be added. It was indicated earlier that ideally each state transition and associated actions need to take place instantaneously. That means that the state transition and actions have to be atomic, so that no input could occur before the transition to the next state is stable and the output activities have completed. Otherwise one could end up with unplanned transitions, race conditions, and unexpected behavior.

However, in the real world some actions may take a significant amount of time or result in asynchronous events with unpredictable timing (just think of a communication system waiting for a response). Here is where the designer needs to apply some careful analysis and possibly consider inserting some transitional states in order to avoid these potential problems and creating an unstable system.

These can be complex issues that are intrinsic and specific to each project and beyond the scope of this article; just let the reader be forewarned.

The initial sales pitch indicated that the FSM design method lends itself to group design. If one congregates a team of programmers who have a good understanding of the task at hand, it's possible to brainstorm a state transition table quite effectively using a whiteboard or a computer with a projector and a spreadsheet program.

The design process would start by listing the system's inputs along the left edge and drawing one column for the initial state. The table would be gradually expanded by identifying the various states and adding the corresponding columns until the STT is completed and the system is fully described. The checks and balances provided by several pairs of eyes could ensure a robust design and even contribute to the team's group spirit and cooperation.

Most programmers are familiar with state diagrams or charts, where states are represented by bubbles and transitions are free-form arrows connecting the bubbles. State diagrams are used quite commonly and there are convenient software tools that can expedite their creation.

While a picture is supposed to be worth “a thousand words” and intuitively appealing, I try to avoid using state diagrams and stick with transition tables. Here's why.

Any chart containing more than a few states and transitions can quickly become overly complex and confusing. This is particularly true if a diagram needs to span over several pages or screenshots.

There is no standard drawing order or pattern; some designers start drawing the charts from left to right and top to bottom; others start from the center of the page and fan out in all directions, making it often difficult to find the thread in the logic.

Diagrams may not have a consistent look on different computers because of the dissimilar tools or screen settings used to view them.

Graphics are more difficult to edit and maintain than tables, so state diagrams may often fail to keep up with design or code changes throughout the lifecycle of the project and can eventually become useless as either documentation or maintenance tools.

The connection between a state diagram and the corresponding code is not always obvious, whereas a state transition table seems to map directly into the structure of the code, as this paper has attempted to show.

I hope that this article will motivate you to use the FSM design method in your next software project.

Ted Carmely is a senior engineer affiliated with the Aerospace Corporation in Southern California. He has over 40 years of experience in designing software for real-time applications and has earned M.S. degrees in math and computer science. In his spare time he plays clarinet and sax in a Jazz band.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.