Locally connected space: Difference between revisions
Jump to navigation
Jump to search
alter reference |
en>Austinmohr m Minor edit for readability |
||
| Line 1: | Line 1: | ||
{{multiple issues| | |||
{{cleanup|reason=article should take [[Finite-state machine]] as its base for an article, featuring a more cohesive lead, feature an example, concept and vocabulary...|date=February 2013}} | |||
{{ref improve|date=February 2013}} | |||
{{technical|date=February 2013}} | |||
}} | |||
In a conventional [[finite state machine]], the transition is associated with a set of input [[Boolean logic|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 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 specified [[data operation]]s.<ref> | |||
{{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}} | |||
</ref> | |||
==Definition== | |||
An EFSM is defined<ref> | |||
{{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 }} | |||
</ref> as a 7-tuple <math>M=(I,O,S,D,F,U,T)</math> 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 [[Vector space|linear space]] <math>D_1 \times \ldots \times D_n</math>, | |||
* F is a set of ''enabling functions'' <math>f_i : D \rightarrow \{0,1\}</math>, | |||
* U is a set of ''update functions'' <math>u_i : D \rightarrow D</math>, | |||
* T is a transition relation, <math>T : S \times F \times I \rightarrow S \times U \times O</math> | |||
==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 numeral system|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: | |||
# In E-block, evaluate all trigger conditions. | |||
# In FSM-block, compute the next state & the signals controlling A-block. | |||
==See also== | |||
[[Abstract state machine]] | |||
Extended finite state machines | |||
==References== | |||
<references/> | |||
[[Category:Models of computation]] | |||
[[Category:Formal methods]] | |||
[[Category:Theory of computation]] | |||
Revision as of 21:37, 1 December 2013
Template:Multiple issues 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.[1]
Definition
An EFSM is defined[2] as a 7-tuple 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 ,
- F is a set of enabling functions ,
- U is a set of update functions ,
- T is a transition relation,
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:
- In E-block, evaluate all trigger conditions.
- In FSM-block, compute the next state & the signals controlling A-block.
See also
Abstract state machine Extended finite state machines
References
- ↑ Template:Cite web
- ↑
55 years old Systems Administrator Antony from Clarence Creek, really loves learning, PC Software and aerobics. Likes to travel and was inspired after making a journey to Historic Ensemble of the Potala Palace.
You can view that web-site... ccleaner free download