EFSM

From Wikipedia, the free encyclopedia

In a conventional finite state machine, the transition is associated with a set of input Boolean conditions & 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 if trigger conditions are all satisfied, the transition is fired , bringing the machine from the current state to the next state & performing the specified data operations.^[1]

[edit] Structure

EFSM Architecture: An EFSM model consists of three major combinational blocks & 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 & 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 & data movements.

[edit] See also

Abstract state machine

[edit] References

1. ^ Computer Programming Software Terms, Glossary and Dictionary - EFSM: Extended Finite State Machine Model (Web). Network Dictionary.com. Retrieved on December 13, 2006.