AESOP home

Publications

Efficient table-driven implementation of the finite state machine

Peter G. Harrison

Journal Article
Journal of Systems and Software
Volume 2
Issue 3
pp.201–211
August, 1981
Elsevier
DOI 10.1016/0164-1212(81)90019-4
Abstract

Many programs model real world systems, communication networks for example, that change status according to input pulses. The finite state machine provides a concise description of such processes and is often defined as a table; the rows correspond to pulses and the columns to current system state. The finite state machine represented in this way yields a compact notation and aids clarity in both problem specification and solution. Implementation may involve translation into explicit code sequences for which various optimizations for run-time processing have been developed. The alternative table driven implementation is highly portable, modifiable, and extensible. This follows since the clarity inherent in a table is preserved. In addition, the table-based system uses much less static code than the corresponding code-based system, a saving often significantly greater than the storage requirement of the table itself. However, the handling of "don't care" input pulse components may considerably degrade performance, execution time especially, and run-time inefficiency has severely limited the use of tablebased systems. We propose a new table-driven implementation to achieve clarity, portability, and modifiability with optimizations yielding performance superior to that of the alternative code-based system in terms of storage, and comparable in execution time. These optimizations result primarily from a transformation of the finite state machine into a decision table, by incorporating the current state into the input pulse and reordering pulse components so that "don't care" components need not always be evaluated at run time. Further substantial enhancement is possible by means of a compile-time row merging operation in situations where an arbitrary sequence of transition, actions, and exit is valid upon inputing pulses, typically specified as "doesn't occur", that are undefined.

Information from pubs.doc.ic.ac.uk/finite-state-machine.