Extended finite-state machine

Definition

• 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,
• F is a set of enabling functions,
• U is a set of update functions,
• T is a transition relation,

  Structure

• 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.

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.