- Extended finite state machine
In a conventional
finite state machine , the transition is associated with a set of inputBoolean 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 oftrigger condition s. If trigger conditions are all satisfied, the transition is fired, bringing the machine from the current state to the next state and performing the specifieddata operation s. [cite web
title = Computer Programming Software Terms, Glossary and Dictionary - EFSM: Extended Finite State Machine Model
work =
publisher = Network Dictionary.com
date =
url = http://www.networkdictionary.com/software/e.php?PHPSESSID=9926acc9b2e4f8f05ced05a620abcfe9
format = Web
doi =
accessdate = 2006-12-13]Definition
An EFSM is defined [cite conference
first = K-T
last = Cheng
coauthors = Krishnakumar, A.S.
title = Automatic Functional Test Generation Using The Extended Finite State Machine Model
booktitle = International Design Automation Conference (DAC)
publisher = ACM
pages = 86-91
year = 1993 ] as a 7-tuple 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 D_1 imes ldots imes D_n,
* F is a set of "enabling functions" f_i : D ightarrow {0,1},
* U is a set of "update functions" u_i : D ightarrow D,
* T is a transition relation, T : S imes D imes I ightarrow S imes D imes Otructure
EFSM Architecture: An EFSM model consists of three major combinational blocks and a few registers.
FSM-block: A conventional finite state machine that realizes 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 of evaluating the trigger conditions associated with each transition. The input signals of this block are the data variables, while the output is a set of binary signals taken as the inputs by the FSM-block. The information of redundant computation is extracted by analyzing the interactions among the three basic blocks. Using this information, certain input operands of the
arithmetic block andevaluation block can be frozen throughinput 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:
# In E-block, evaluate all trigger conditions.
# In FSM-block, compute the next state & the signals controlling A-block.
# In A-block, perform the necessary data operations & data movements.ee also
Abstract state machine References
Wikimedia Foundation. 2010.