Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

EFFICIENT, MAINTAINABLE IMPLEMENTATION OF STATE MACHINES IN SOFTWARE

IP.com Disclosure Number: IPCOM000007291D
Original Publication Date: 1994-Oct-01
Included in the Prior Art Database: 2002-Mar-12
Document File: 3 page(s) / 147K

Publishing Venue

Motorola

Related People

Tom Ziomek: AUTHOR

Abstract

Real time systems often need to implement state machines in software. Existing implementation meth- ods for software state machines lead to code which is extremely complex, inefficient, error-prone and d&cult to debug. These implementations are diffi- cult to modify because the logic used to reach a given state is scattered around one large fUndion or several separate functions.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 45% of the total text.

Page 1 of 3

MOTOROLA Technical Developments Volume 23 October 1994

EFFICIENT, MAINTAINABLE IMPLEMENTAljON OF

STATE MACHINES IN SOFlWARE

by Tom Ziomek

responds to a state. Inputs to the state machine are events and/or variables vvhich cause a change from one state to another.

  State transition tables are one representation for state machines. Columns are assigned for current state variables, inputs, and next state variables. Each row of the table corresRonds to one specific state transition. A row specifies a current state, values for the inputs which cause one particular transition from that state, and the state jvhich is entered when that combination of current state and input values occurs (the next state). The table must contain a row for every possible combination of a current state and input values. The number of rows can sometimes be reduced by combining rows in which some current state variables and/or innuts are "don't cares?

  This method codes a state transition table as a one dimensional array of records. Each record cor- responds to one row of the state transition table.

The record is coded as a data structure containing fields for each current state variable, input, and next state variable (a columnm the state transition table corresponds to one field in the records).

  A "next state" is found by first determining the values of the "current state" and all state machine inputs. Finding the next state is then a simple and efficient matter of searching the array (state transi-

tion table) for a row which matches the current state and inputs.

  In practice, the search for a matching row (array element) can be optimized by "packing" all of the current state and input fields into one large bit field. A byte-size field with, say, 3 possible values would occupy only two bits when it is packed. The state transition table data structure would be packed once during system initialization. The current state and inputs could be similarly packed whenever it is time to determine a next state. The comparison of the current state and inputs bith a row in the state tran-

0 Motorola. 1°C. 1994

II

INTRODUCTION

  Real time systems often need to implement state machines in software. Existing implementation meth- ods for software state machines lead to code which is extremely complex, inefficient, error-prone and d&cult to debug. These implementations are diffi- cult to modify because the logic used to reach a given state is scattered around one large fUndion or several separate functions.

  A better method is to implement the state tran- sition table representation of the state machine directly to a data structure. A generic "search engine" can then be used to determine the current state, find that state's entry in the state table, and look up the next state for that current state.

ADVANTAGES

   This method results in an efficient implementa- tion which is much easier to document and under- stand than the prior art. All of the "knowledge" embedded in the software st...