Extended finite-state machine

This article needs more citations. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Extended finite-state machine" – news · newspapers · books · scholar · JSTOR (February 2013) (Learn how and when to remove this message)

Classes of automata

(Clicking on each layer links to the article on that subject.)

In a conventional finite-state machine, the transition is associated with a set of input Boolean conditions and a set of output Boolean functions. In an extended finite-state machine (EFSM) model, the transition can be expressed by an “if statement” consisting of a set of trigger conditions. If trigger conditions are all satisfied, the transition is fired, bringing the machine from the current state to the next state and performing the specified data operations.

Definition

An EFSM is defined as a 7-tuple ${\displaystyle M=(I,O,S,D,F,U,T)}$ where

• S is a set of symbolic states,
• I is a set of input symbols,
• O is a set of output symbols,
• D is an n-dimensional linear space ${\displaystyle D_{1}\times \ldots \times D_{n}}$,
• F is a set of enabling functions ${\displaystyle f_{i}:D\rightarrow \{0,1\}}$,
• U is a set of update functions ${\displaystyle u_{i}:D\rightarrow D}$,
• T is a transition relation, ${\displaystyle T:S\times F\times I\rightarrow S\times U\times O}$

Intuitively, the state machine represents the possible states of a system, and how the system transitions from one state to another

• S represents the possible states, parametrized by D
• I represents input from the outside world,
• O represents output to the outside world,
• F models what is forbidden / allowed. These functions are run as part of T to determine whether the state transition will happen,
• U models how the state parameters evolve,
• T models the transitions. It is saying: if we're in a given state, and an input arrives from the outside world, and if f ∈ F is "guarding" this transition, and if f returns true, then this will take us to another state, with a new set of parameters (obtained via the update function). Along the way a certain output will be sent to the outside world.

Structure

EFSM Architecture: An EFSM model consists of the following three major combinational blocks (and a few registers).

• FSM-block: A conventional finite-state machine realizing the state transition graphs of the EFSM model.
• A-block: an arithmetic block for performing the data operation associated with each transition. The operation of this block is regulated by the output signals of the FSM block.
• E-block: A block for evaluating the trigger conditions associated with each transition. The input signals to this block are the data variables, while the output is a set of binary signals taken for input by the FSM-block. Information about redundant computation is extracted by analyzing the interactions among the three basic blocks. Using this information, certain input operands of the arithmetic block and evaluation block can be frozen through input gating under specific run time conditions to reduce the unnecessary switching in the design. At the architecture level, if each trigger evaluation & data operation is regarded as an atomic action, then the EFSM implies an almost lowest-power implementation.

The cycle behavior of an EFSM can be divided into three steps:

1. In E-block, evaluate all trigger conditions.
2. In FSM-block, compute the next state & the signals controlling A-block.
3. In A-block, perform the necessary data operations and data movements.

See also

• Abstract state machine

References