Software design of state machines
The following is an adaptation of hardware design with the achievable goal of short/routine development, and efficient code. It also results in easy checkout, and accountability for all conditionals. It requires figures and tables in the documentation and a decision table in the code. The examples include illustrations in assembly language. The first is also illustrated in C.
State machines have been the focus of design for many years in the hardware arena , but they are relatively new in the software arena . Much work is still being done to model state machines . There are software packages to help automate development , as well as detailed training . However, in software there is still difficulty in covering all of the conditionals. The goal of this paper is to apply long-established principles, add some original detail, and thus allow individuals to routinely design their own state machines in software with no missed conditionals.
II. DESIGN OVERVIEW
In layman’s terms a state machine is a logic array with inputs and outputs, such that the outputs depend not only on the present inputs, but also on a past history of inputs and outputs. The inputs and outputs are single bit binary variables consisting of either a logic one, a logic zero, or a directive to execute or not execute. These variables may go to or from other logic arrays; to and from a hardware interface; or control the transition to another state. Memory of the past is captured with a state number. The external inputs and the state number are the inputs to the machine’s logic, which determine a unique set of outputs. Fig. 1 is the generic block diagram.
Fig. 1. Block Diagram (Source: Author)
The design is started with a specification. The description from the specification is recorded in a state diagram. See Fig. 4. The design phase continues with minimization techniques (discussed in the example), which includes assigning the state numbers. The results allow all of the information to be organized into a truth table. From the truth table a software decision table is formed. The decision table includes a list of direct jump statements to routines which generate the outputs. To create a decision table, the inputs from the truth table becomes the data pointer to an indirect jump instruction, ultimately invoking the output routines. The decision table is a selector switch. The result is the execution of one from the list of the direct jump statements to the output routines. Those which cause a transition to another state, do so by manipulating the state number. The state number can be manipulated by executing one of the following equivalent operations: Increment, Decrement, And, Or, Set, Clear, Complement, Load, and Rotate. Note that since the entire next state logic is coded into the jump table and that the jump table is complete, all conditional logic is accommodated. Nothing is left to chance. Fig. 2 is the Top-Level Flow Diagram. The best way to explain the complete process is to discuss it with an example.
Fig. 2. Top-Level Flow Diagram (Source: Author)