Máquina de Estados

• Uma máquina de estados finitos ou autômato finito é uma

modelagem de um comportamento composto por estados,

transições e ações

• Um estado armazena informações sobre o passado

• Uma transição indica uma mudança de estado e é descrita por uma condição que precisa ser realizada para que a transição ocorra

• Uma ação é a descrição de uma atividade que deve ser realizada em determinado momento

Máquina de Estados

• Uma máquina de estados é um sistema seqüencial

• O número de estados são finitos

• As entrada e saídas são consideradas em instantes de tempo discretos que são definidos por pulsos de um sinal de sincronização chamado relógio (clock)

Máquina de Estados

• Representação de máquinas de estados

1. Tabela de Transição

EA – Estado Atual

PE – Próximo Estado

Máquina de Estados

• Representação de máquinas de estados

1. Diagrama de Estados

Máquina de Estados

• Exemplo 1:

Máquina de Estados

• Exemplo 1:

Máquina de Estados

• Exemplo 2:

• Considere um sistema seqüencial descrito abaixo:

Entrada : x(t ) ∋ {a, b, c}

Saída : z(t) ∋ {0, 1} Estado : s(t) ∋ {S0 , S1 , S2 , S3 }

Estado Inicial: s(0) = S0

Funções : As funções de transição e de saída são:

EA – Estado Atual

PE – Próximo Estado

TABELA DE TRANSIÇÃO ESTADOS

Máquina de Estados

• Representação de máquinas de estados

1. Diagrama de Estados da máquina do Exemplo 2

TABELA DE TRANSIÇÃO ESTADOS

DIAGRAMA DE ESTADOS

Máquina de Estados

• As máquinas de estados são classificados de acordo com o tipo de função de saída, em dois tipos:

Máquina de Mealy e Máquina de Moore

• A máquina de Mealy é um sistema seqüencial cuja saída no tempo t depende do estado e da entrada no tempo t, ou seja:

z(t) = H(s(t), x(t))

• A máquina de Moore é um sistema seqüencial cuja saída no tempo t depende somente do estado no tempo t, ou seja:

z(t) = H(s(t))

Máquina de Estados

• Exemplo 1:

Máquina de Mealy

z(t) = H(s(t), x(t))

Máquina de Estados

• Representação de máquinas de estados

1. Diagrama de Estados da máquina do Exemplo 2

TABELA DE TRANSIÇÃO ESTADOS

DIAGRAMA DE ESTADOS

Máquina de Moore

z(t) = H(s(t))

Máquina de Estados

• Descrição de máquinas de estados usando VHDL

1. Os dois componentes do sistema seqüencial , ou seja, a função

de transição de estado e a função de saída são descritas como

processos (process) separados.

2. O primeiro processo descreve a função de transição de

estado e é ativado sempre que há um evento no sinal de

relógio (clock).

3. O segundo processo descreve a função de saída e é ativado

sempre que há uma transição de estado ou um evento nos

sinais de entrada

Máquina de Estados

• Descrição de máquinas de estados usando VHDL

Exemplo 3 :

Faça uma descrição VHDL da máquina de estados especificada pelo diagrama

de estados abaixo:

1/0 Sinic

0/01/0

0/0

0/0

1/0

0/0

1/1

S1 S11 S110

Descrição VHDL – Exemplo 3

library IEEE;use ieee.std_logic_1164.all;

use ieee.std_logic_unsigned.all;

ENTITY detetor_de_padroes IS

PORT

( x : IN STD_LOGIC;

y : OUT STD_LOGIC;

clk : IN STD_LOGIC

);

END detetor_de_padroes;

1/0 Sinic

0/01/0

0/0

0/0

1/0

0/0

1/1

S1 S11 S110

ARCHITECTURE comportamental OF detetor_de_padroes IS TYPE estados IS (Sinic, S1, S11, S110); -- tipo define os estados SIGNAL estado_atual: estados; -- sinal do tipo estados SIGNAL estado_anterior: estados; -- sinal do tipo estados BEGIN PROCESS (clk) BEGIN IF RISING_EDGE (clk) THEN – mudança de estado CASE estado_atual IS WHEN Sinic => IF x = '0' THEN estado_atual <= Sinic; ELSE estado_atual <= S1; estado_anterior <= Sinic; END IF; WHEN S1 => IF x = '0' THEN estado_atual <= Sinic; estado_anterior <= S1; ELSE estado_atual <= S11; estado_anterior <= S1; END IF; WHEN S11 => IF x = '0' THEN estado_atual <= S110; estado_anterior <= S11; ELSE estado_atual <= S11; estado_anterior <= S11; END IF; WHEN S110 => IF x = '0' THEN estado_atual <= Sinic; estado_anterior <= S110; ELSE estado_atual <= S1; estado_anterior <= S110; END IF; END CASE; END IF; END PROCESS;

Descrição VHDL – Exemplo 3

PROCESS (estado_atual, estado_anterior, x) -- processo responsável BEGIN -- pela função de saída

CASE estado_atual IS WHEN Sinic => y <= '0'; WHEN S1 => IF estado_anterior = S110 THEN y <= '1'; ELSE y <= '0'; END IF; WHEN S11 => y <= '0';

WHEN S110 => y <= '0'; END CASE; END PROCESS; END comportamental;

1/0 Sinic

0/01/0

0/0

0/0

1/0

0/0

1/1

S1 S11 S110

Descrição VHDL – Exemplo 3

library IEEE;use ieee.std_logic_1164.all; PROCESS (estado_atual, estado_anterior, x) -- processo responsável

use ieee.std_logic_unsigned.all; BEGIN -- pela função de saída

ENTITY detetor_de_padroes IS CASE estado_atual IS PORT WHEN Sinic => y <= '0'; ( x : IN STD_LOGIC; WHEN S1 => IF estado_anterior = S110 THEN y <= '1'; y : OUT STD_LOGIC; ELSE y <= '0'; clk : IN STD_LOGIC END IF; ); WHEN S11 => y <= '0';

END detetor_de_padroes; WHEN S110 => y <= '0';ARCHITECTURE comportamental OF detetor_de_padroes IS END CASE; TYPE estados IS (Sinic, S1, S11, S110); -- tipo define os estados END PROCESS;

SIGNAL estado_atual: estados; -- sinal do tipo estados END comportamental;

SIGNAL estado_anterior: estados; -- sinal do tipo estados BEGIN PROCESS (clk) BEGIN IF RISING_EDGE (clk) THEN – processo responsável pela mudança de estado CASE estado_atual IS WHEN Sinic => IF x = '0' THEN estado_atual <= Sinic; ELSE estado_atual <= S1; estado_anterior <= Sinic; END IF; WHEN S1 => IF x = '0' THEN estado_atual <= Sinic; estado_anterior <= S1; ELSE estado_atual <= S11; estado_anterior <= S1; END IF; WHEN S11 => IF x = '0' THEN estado_atual <= S110; estado_anterior <= S11; ELSE estado_atual <= S11; estado_anterior <= S11; END IF; WHEN S110 => IF x = '0' THEN estado_atual <= Sinic; estado_anterior <= S110; ELSE estado_atual <= S1; estado_anterior <= S110; END IF; END CASE; END IF; END PROCESS;

1/0 Sinic

0/01/0

0/0

0/0

1/0

0/0

1/1

S1 S11 S110

MÁQUINA DE MEALY

Descrição VHDL – Exemplo 3

1/0 Sinic

0/01/0

0/0

0/0

1/0

0/0

1/1

S1 S11 S110

Descrição VHDL – Exemplo 3

1/0 Sinic

0/01/0

0/0

0/0

1/0

0/0

1/1

S1 S11 S110

0 1 1 0 1 1 1 0 1

PADRÃO