Maquina de estados

Prévia do material em texto

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/0
1/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; 
 
 
 
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;
1/0
 Sinic
0/0
1/0
0/0
0/0
1/0
0/0
1/1
 S1
 S11
 S110
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/0
1/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;
 
 
 
MÁQUINA DE MEALY
1/0
 Sinic
0/0
1/0
0/0
0/0
1/0
0/0
1/1
 S1
 S11
 S110
Descrição VHDL – Exemplo 3
1/0
 Sinic
0/0
1/0
0/0
0/0
1/0
0/0
1/1
 S1
 S11
 S110
Descrição VHDL – Exemplo 3
 0 1 1 0 1 1 1 0 1
PADRÃO 
1/0
 Sinic
0/0
1/0
0/0
0/0
1/0
0/0
1/1
 S1
 S11
 S110