Slide Máquina de estados - Circuitos Lógicos UFPB

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)
Diagrama Tradicional de uma Máquina de Estados
Lógica Combinacional
Lógica Sequencial
saída
entrada
próximo 
estado
Estado 
atual
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 
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))
Diagrama Tradicional de uma Máquina de Estados
Lógica Combinacional
Lógica Sequencial
saída
entrada
próximo 
estado
Estado 
atual
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)
FSM – Finite State Machine
clock
início
cheio
tempo
secar
válvula_água
modo_agitar
modo_girar
FSM
reset_n
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) 
Espera
início = 1
Encher Agitar Girar
início = 0 cheio = 0
cheio = 1
tempo = 0
tempo = 1
secar = 1
secar = 0
válvula_água = 0 
modo_agitar = 0
modo_girar = 0
válvula_água = 1 
modo_agitar = 0
modo_girar = 0
válvula_água = 0 
modo_agitar = 1
modo_girar = 0
válvula_água = 0 
modo_agitar = 0
modo_girar = 1
reset_n
Máquina de Estados
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
Descrição Verilog
Simulação
clock
início
cheio
tempo
secar
válvula_água
modo_agitar
modo_girar
Máquina de Lavar
reset_n
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:
1/0
Sinic
0/0
1/0
0/0
0/0
1/0
0/0
1/1
S1 S11 S110
Descrição Verilog – Exemplo 4
1/0
Sinic
0/0
1/0
0/0
0/0
1/0
0/0
1/1
S1 S11 S110
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 
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 
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
Sinic
0/0
1/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