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
DIAGRAMA DE ESTADOS
TABELA DE TRANSIÇÃO 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
Máquina de
Moore
z(t) = H(s(t))
1. Diagrama de Estados da máquina do Exemplo 2
DIAGRAMA DE ESTADOS
TABELA DE TRANSIÇÃO ESTADOS
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:
0/0
1/0
Sinic
1/0
S1
1/0
0/0
S11
1/1
0/0
0/0
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;
0/0
1/0
Sinic
1/0
S1
1/0
0/0
S11
1/1
0/0
0/0
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;
0/0
1/0
Sinic
1/0
S1
1/0
0/0
S11
1/1
0/0
0/0
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 – 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;
0/0
estado_anterior <= S1;
ELSE estado_atual <= S11;
estado_anterior <= S1;
END IF;
WHEN S11 => IF x = '0' THEN estado_atual <= S110;
estado_anterior <= S11;
Sinic
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;
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;
MÁQUINA DE MEALY
1/0
1/0
S1
1/0
0/0
S11
1/1
0/0
0/0
S110
Descrição VHDL – Exemplo 3
0/0
1/0
Sinic
1/0
S1
1/0
0/0
S11
1/1
0/0
0/0
S110
Descrição VHDL – Exemplo 3
1/0
0/0
1/0
Sinic
S1
S11
1/0
0/0
1/1
0/0
0
1
1
0
1
PADRÃO
1
1
0
1
0/0
S110