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)
Diagrama Tradicional de uma Máquina de Estados
entrada
saída
Lógica Combinacional
Estado
atual
próximo
estado
Lógica Sequencial
clock
reset
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
Diagrama Tradicional de uma Máquina de Estados
entrada
saída
Lógica Combinacional
Estado
atual
próximo
estado
Lógica Sequencial
clock
reset
Máquina de Estados
•
Descrição de máquinas de estados usando Verilog
1. Os dois componentes da máquina, ou seja, a função
de transição de estado e a função de saída são descritas em
blocos always separados.
2. Um dos blocos always descreve a função de transição de
estado e é ativado sempre que há um evento no sinal de
relógio (clock) e representa a parte sequencial da máquina
3. O segundo bloco always descreve a função de saída e é ativado
sempre que há uma transição de estado ou um evento nos sinais
de entrada e representa a parte combinacional da máquina
Máquina de Estados
Exemplo 3: Máquina de estados simples (Máquina de lavar)
• O diagrama de blocos abaixo representa uma máquina de estados com 5
entradas (ínicio, cheio, tempo, secar, reset_n) e o clock
• A máquina possui 3 saídas (válvula_água, modo_agitar e modo_girar)
início
válvula_água
cheio
tempo
FSM
secar
reset_n
clock
FSM – Finite State Machine
modo_agitar
modo_girar
Máquina de Estados
O diagrama de estados abaixo especifica a máquina:
• Os sinais: válvula_água, modo_agitar e modo_girar são os sinais de saída
• A máquina possui 4 estados (Espera, Encher, Agitar e Girar)
início = 0
cheio = 0
início = 1
reset_n
Espera
válvula_água = 0
modo_agitar = 0
modo_girar = 0
cheio = 1
Encher
válvula_água = 1
modo_agitar = 0
modo_girar = 0
secar = 0
tempo = 0
Agitar
secar = 1
tempo = 1
válvula_água = 0
modo_agitar = 1
modo_girar = 0
Girar
válvula_água = 0
modo_agitar = 0
modo_girar = 1
Máquina de Estados
Descrição Verilog
module maquina_de_lavar
(output reg valvula_agua, modo_agitar, modo_girar,
input clock, reset_n, inicio, tempo, cheio, secar);
reg [1:0] estado_atual;
parameter espera = 0, encher =1, agitar = 2, girar = 3;
always @ (*) begin // parte combinacional
case (estado_atual)
espera: begin
valvula_agua =0; modo_agitar=0; modo_girar=0;
end
encher: begin
valvula_agua=1; modo_agitar=0; modo_girar=0;
end
agitar: begin
valvula_agua=0; modo_agitar=1; modo_girar=0;
end
girar: begin
valvula_agua =0; modo_agitar=0; modo_girar=1;
end
endcase
end
always @ (posedge clock, negedge reset_n) // parte sequencial
if (~reset_n)
estado_atual <= espera;
else
case (estado_atual)
espera: if (inicio == 1)
estado_atual <= encher;
encher: if (cheio == 1)
estado_atual <= agitar;
agitar: if (tempo == 1)
estado_atual <= girar;
girar: if (secar == 0)
estado_atual <= espera;
endcase
endmodule
início
válvula_água
cheio
tempo
secar
reset_n
clock
Simulação
Máquina de Lavar
modo_agitar
modo_girar
Máquina de Estados
•
Descrição de máquinas de estados usando Verilog
Exemplo 4 :
Faça uma descrição Verilog 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 Verilog – Exemplo 4
module maquina_de_estados_detetor_de_padroes_2
(output reg y,
input clock, x, reset);
reg [1:0] estado_atual, estado_anterior;
parameter Sinic = 0, S1 =1, S11 = 2, S110 = 3;
always @ (*) begin // parte combinacional
case (estado_atual)
Sinic: y = 0;
S1: begin
if (estado_anterior == S110 )
y = 1;
else y = 0;
end
S11: y = 0;
S110: y = 0;
endcase
end
1/0
0/0
Sinic
S1
1/0
0/0
1/0
S11
1/1
0/0
0/0
always @ (posedge clock, negedge reset) // parte sequencial
if (~reset)
estado_atual <= Sinic;
else
case (estado_atual)
Sinic: begin
if (x == 0)
estado_atual <= Sinic;
else begin
estado_atual <= S1; estado_anterior <= Sinic; end
end
S1: begin
if (x == 0) begin
estado_atual <= Sinic; estado_anterior <= S1; end
else begin
estado_atual <= S11; estado_anterior <= S1; end
end
S11: begin
if (x == 0) begin
estado_atual <= S110; estado_anterior <= S11; end
else begin
estado_atual <= S11; estado_anterior <= S11; end
end
S110: begin
if (x == 0) begin
S110
estado_atual <= Sinic; estado_anterior <= S110; end
else begin
estado_atual <= S1; estado_anterior <= S110; end
end
endcase
endmodule
Descrição Verilog – Exemplo 4
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