Application of state machine in single chip microcomputer programming

The concept of state machine

State machine is an important concept in software programming. More important than this concept is its flexible application. In a clear and efficient program, there must be a state machine.

For example, a key command parsing program can be considered a state machine: originally in state A, it switches to state B after a key is triggered; it switches to state C after another key is triggered, or returns to state A. This is the simplest example of a key state machine. The actual key parsing program will be more complicated than this, but this does not affect our understanding of the state machine.

Furthermore, the keystroke itself can be considered a state machine. A small keystroke includes the following states: release, jitter, close, jitter, and re-release.

Similarly, the timing of a serial communication (regardless of the protocol it follows, whether it is a standard serial port or I2C; regardless of whether it is wired, infrared, or wireless) can also be viewed as consisting of a series of finite states.

The display scanning program is also a state machine; the communication command parsing program is also a state machine; even the relay's energizing/releasing control and the light-emitting diode (LED)'s on/off control are also state machines.

When we open our minds and introduce the state machine as a thought into the program, we will find an effective shortcut to solve the problem. Sometimes it may be more effective to think about what the program should do with the state machine thinking rather than thinking with the control flow thinking. In this way, the state machine has a more practical function.

A program is actually a state machine.

Maybe you still don’t understand the above sentence. Think about it, isn’t the computer edifice built on the foundation of the two basic states of “0” and “1”?

Elements of a state machine

The state machine can be summarized into four elements, namely, current state, condition, action, and next state. This summary is mainly due to the consideration of the internal cause and effect relationship of the state machine. "Current state" and "condition" are causes, and "action" and "next state" are effects. The detailed explanation is as follows:

① Current state: refers to the current state.

②Condition: Also known as "event". When a condition is met, an action will be triggered or a state transition will be performed.

③Action: The action executed after the condition is met. After the action is executed, you can migrate to a new state or keep the original state. The action is not required. When the condition is met, you can also migrate to the new state directly without executing any action.

④ Sub-state: The new state to be moved to after the conditions are met. "Sub-state" is relative to "current state". Once the "sub-state" is activated, it will transform into the new "current state".

If we further summarize, unify the "current state" and "next state", and ignore (downgrade) the "action", then only two most critical elements remain, namely: state and migration conditions.

There are many ways to represent a state machine. We can use text, graphics or tables to represent a state machine.

Purely describing it with words is very inefficient, so I won't introduce it. Next, I will introduce the graphical method.

State Transition Diagram (STD)

A state transition diagram (STD) is a graphical way to describe the states of a system and their transformation relationships. There are many ways to draw a state transition diagram, but they are generally similar. Let's use an example to illustrate how to draw it, as shown in Figure 1.

Figure 1 State transition diagram

① Status box: Use a box to represent the status, including the so-called "current state" and "next state".

②Conditions and transition arrows: Use arrows to indicate the direction of state transition, and mark the triggering conditions on the arrows.

③Node circle: When multiple arrows point to one state, they can be connected and summarized using a node symbol (small circle).

④Action box: represented by an elliptical box.

⑤ Additional condition judgment box: represented by a hexagonal diamond box.

The state transition diagram is essentially different from the common flowchart. Specifically, in the flowchart, the arrow represents the jump of the program PC pointer; while in the state transition diagram, the arrow represents the change of state.

We will find that this state transition diagram is more concise, intuitive and easy to understand than the ordinary program flow chart. This is exactly what we need to achieve.

State transition table

In addition to the state transition diagram, we can also use a table to represent the relationship between states. This table is generally called a state transition table.

Table 1 is another description of the state transition diagram introduced earlier.

Table 1 State transition table

① Using a table to describe the state machine has the advantage of being able to accommodate more textual information. For example, we can not only describe the state transition relationship in the state transition table, but also include the characteristic description of each state.

② If the table has too much content and is too bulky to read, we can also split the state transition table. The name of the split table will also change according to its specific content.

③For example, we can list the state characteristics and transition relations separately. The table that describes the state characteristics separately can also be called a "state truth table". Among them, the more common is to list the display content of each state separately. This table that describes the display content of each state is called a "display truth table". Similarly, we call the state transition table based on buttons separately a "button function truth table". In addition, if each state contains too much information, we can also list each state separately.

④It can be seen that the state transition table is a useful supplement to the state transition diagram, and its expression form is flexible.

⑤ The advantage of the state transition table is that it covers a wide range of information, but its disadvantage is that it is not visually intuitive, so it cannot replace the state transition diagram. It is more ideal to combine graphics and tables. Use graphics to show the macro and use tables to explain the details. The two refer to each other and complement each other.

Using state machine ideas to implement a clock program [page]

Next, I will give a practical example of the application of state machines, combining flowcharts, state transition diagrams, and state transitions. The following figure is a state transition diagram of a clock program, as shown in Figure 2.

Figure 2 Clock program state transition diagram

By summarizing this picture a little bit, we can get another form of its expression - the state transition table, as shown in Table 2.

Table 2 Clock program state transition table

Notes on state machine applications

The difficulty in applying the program scheduling mechanism based on the state machine does not lie in the understanding of the concept of the state machine, but in the reasonable division of the system working state.

Beginners often treat a certain "program action" as a "state". I call it a "pseudo-state". So how to distinguish "action" from "state". My experience is to look at the essence of the two: "action" is unstable, even if there is no triggering condition, "action" is over once it is executed; while "state" is relatively stable, if there is no external triggering condition, a state will continue.

Another fatal mistake of beginners is to miss some states when dividing the states. I call it "leaky states".

The existence of these two errors, "pseudo-state" and "leakage state", will lead to the loosening of program structure. Therefore, special care should be taken to avoid them.

More complex state machines

The previous introduction is a simple state structure. It has only one level and one dimension, as shown in Figure 3.

Figure 3 Linear state machine structure

If necessary, we can build more complex state machine models.

1 Multi-level state structure

State machines can be multi-level. In a hierarchical multi-level state machine system, a "parent state" can be divided into multiple "sub-states". These sub-states share some commonalities with the parent state, while each has its own personality.

In some states, sub-states can be further divided. For example, we can modify the previous clock example as follows:
merge all states related to the clock function into one first-level state. In this state, three second-level sub-states can be divided, namely display time, set hours, and set minutes;

Similarly, we can combine all the states related to the alarm function into one primary state. In this state, there are four secondary sub-states, namely display alarm, set "hour", set "minute", and set beep time.

We need another state variable (register) to represent these sub-states.

Of course, there can be lower-level grandchildren states under the sub-states (and the descendants are endless), thus turning the entire state system into a tree-like multi-level state structure, as shown in Figure 4.

Figure 4 Tree-like multi-level state structure

2 Multidimensional state structure

The state structure can also be multi-dimensional. The system is divided into states from different perspectives, and some characteristics of these states are intertwined. For example, while the states are divided according to buttons and displays, another state division is made according to the system's working process. These two state divisions exist at the same time and intersect with each other, thus forming a two-dimensional state structure space.

Take an example in this regard, such as an air conditioner remote controller, as shown in FIG5 .

Figure 5 Multidimensional state machine structure

Similarly, we can also construct three-dimensional, four-dimensional or even more-dimensional state structures. Each dimension of the state needs to be represented by a state variable (register).

No matter how attractive the multi-level state structure and multi-dimensional state structure look, the craftsman's advice is: we still need to simplify the state structure as much as possible. If we can use a single-level, single-dimensional structure, we should not make trouble for ourselves by playing with that nightmarishly complex structure.

Simple is the most effective.

Conclusion

Understanding state machines requires a gradual process of deepening. This process should be combined with practical applications and specific case studies. When a good idea becomes a design habit, it will bring rewards to the designer. I hope that the state machine-based programming ideas introduced in this note can bring some inspiration to novices and help everyone find the feeling of "programming".