Máquina de estados finitos estendida

Numa máquina de estados finitos convencional, uma transição é associada a um conjunto de entrada de condições booleanas e um conjunto de saída de funções booleanas. Num modelo de máquina de estados finitos estendida (EFSM, do inglês extended finite state machine model), a transição pode ser expressa por uma “estrutura de seleção” consistindo de um conjunto de condições de disparo. Se as condições de disparo forem todas satisfeitas, a transição é disparada, levando a máquina do estado atual para o próximo estado e realizando a operação de dados especificada.

Definição

Uma EFSM é definida^[1] como uma 7-tupla ${\displaystyle M=(I,O,S,D,F,U,T)}$ onde

• S é o conjunto de estados simbólicos,
• I é o conjunto de símbolos de entrada,
• O é o conjunto de símbolos de saída,
• D é um espaço linear  n-dimensional ${\displaystyle D_{1}\times \ldots \times D_{n}}$,
• F é um conjunto de funções de ativação ${\displaystyle f_{i}:D\rightarrow \{0,1\}}$,
• U é um conjunto de funções de atualização ${\displaystyle u_{i}:D\rightarrow D}$,
• T é uma relação de transição, ${\displaystyle T:S\times F\times I\rightarrow S\times U\times O}$

Estrutura

Arquitetura EFSM: Um modelo EFSM consiste dos seguintes três grandes blocos combinatórios (e alguns registradores).

• Bloco FSM: Uma máquina de estados finitos convencional realizando os grafos de transição de estados do modelo EFSM.

• Bloco A: um bloco aritmético para realizar operações de dados associados com cada transição. A operação deste bloco é regulada pelo sinal de saída do bloco FSM.

• Bloco E: Um bloco para avaliar as condições de disparo associadas com cada transição. Os sinais de entrada para este bloco são as variáveis de dados, enquanto que os sinais de saída são formados pelo conjunto de sinais binários recebidos na entrada pelo Bloco FSM. Informação sobre computação redundante é extraída analisando as interações dos três blocos básicos. Usando esta informação, certos operadores de entrada do bloco aritmético e bloco de avaliação podem ser congelados através de input gating sob condições específicas em tempo de execução para reduzir a codificação de comutação desnecessário no projeto. Ao nível de arquitetura, se cada gatilho de avaliação e operação de dados é dito ser uma ação atômica, então o EFSM implica uma implementação praticamente do menor nível de consumo energético.

O ciclo de comportamento de uma EFSM pode ser dividido em três etapas:

1. Em Bloco E, avaliar todas as condições de disparo.
2. Em Bloco FSM, computar o próximo estado & os sinais de controle do Bloco A.
3. Em A-block, realizar as operações de dados necessárias e a movimentação de dados.
   

Veja também

Máquina de estados abstrata

Referências

1. Cheng, K-T; Krishnakumar, A.S. (1993). «Automatic Functional Test Generation Using The Extended Finite State Machine Model». International Design Automation Conference (DAC). ACM. pp. 86–91