Finite State Machines
Sistemas Embutidos – Versão Modificada
1.1
Máquinas de Estados Finitos e Autômatos
 São uma Forma Muito Usada para Representar Sistemas que
Possuem Memorização de Estados, não sendo Portanto Meramente
Combinacionais. Podem ser usados para Representar:
•
•
•
•

Protocolos em Redes
Comportamento de Circuitos Eletrônicos
Comportamento de Programas de Computador
Comportamento de um Processo de Fabricação
O Contrôle de Um Processo Físico Analógico de Uma forma Geral:
Entrada
Analógica
Num Sistema Analógico a
Somador/
Comparador
Saída
Analógica
PROCESSO
Realimentação
Sistemas Embutidos – Versão Modificada
Relação entre Saída e Entrada
Pode Ser Representada por
Equações Diferenciais e Integrais
Variáveis Assumem Valôres
Contínuos no Tempo
1.2
Lógica Combinacional e Lógica Sequencial
 Lógica Combinacional
• A saída depende apenas de uma combinação
lógica dos valores de entrada. A saída não
precisa esperar nenhum “clock” para ser
gerada. Saídas são geradas um tempo
pequeno (atraso da lógica) após as entradas
mudarem.
A
S
B
T
C
U
D
 Lógica Sequencial
• É a que faz uso de registros (memória)
• A saída pode depender apenas dos estados
dos flip-flops ou da combinação dos estados
e das entradas.
• Denomina-se “ESTADO” da lógica
sequencial ao conjunto de “1s” e “0s”
armazenados nos flip-flops (memória) da
lógica
• O relógio demarca o momento em que os
estados mudam.
Sistemas Embutidos – Versão Modificada
A
D
B
Q
S
Q
T
C
C
D
D
C
CK
1.3
Autômatos – Variáveis Assumem Valores Discretos no Tempo
Representação:
Reset
11/0
10/0
10/1
E3
10/0
Estado
00/0
A- Tabela de Transição
E0
E1
E2
E3
E4
01/1
E4
00/1
PRÓXIMO ESTADO
ENTRADAS
SAÍDAS (z)
ENTRADAS
x, y
00
E0
E3
E2
E3
E4
00/0
E2
11/0
E1
Entradas(x, y)
01/0
E0
11/1
01/0
Saída (z)
ESTADO
ATUAL
00/0
10/0
A- Diagrama de Transição
01
E2
E1
E2
E3
E0
Sistemas Embutidos – Versão Modificada
x, y
10
E0
E1
E2
E4
E2
11
E1
E2
E3
E3
E4
00
0
1
0
0
?
01
0
0
?
?
1
10
0
0
?
0
1
11
1
0
0
?
?
1.4
Autômatos Determinísticos e Não Determinísticos
 Autômato Finito Determinístico (AFD)
•
•
•
•
•
Um Conjunto Q de Elementos Denominados Estados
Um conjunto finito I denominado alfabeto de entrada
Uma função F de mapeamento de Q X I em Q
Um estado inicial q0 em Q
Um Conjunto (não vazio) de Estados Terminais Z
 Autômato Finito Não Determinístico (AFND)
•
•
•
•
•
Um Conjunto Q de Elementos Determinados Estados
Um Conjunto finito I denominado alfabeto de entrada
Uma função F de mapeamento de Q x I em subconjuntos de Q
Um conjunto de estados iniciais em Q
Um conjunto (não vazio) de estados terminais Z contido em Q
 NOTA: Um AFND pode estar em vários estados simultaneamente
(paralelismo – vários caminhos podem ser percorridos ao mesmo
tempo para chegar ao resultado final)
Sistemas Embutidos – Versão Modificada
1.5
Mealy and Moore Machines
Mealy Machine
Inputs
Next State
Combinatorial
Logic
Flip
Flops
Output
Combinatorial
Logic
Flip
Flops
Output
Combinatorial
Logic
Outputs
Clock
Moore Machine
Inputs
Next State
Combinatorial
Logic
Outputs
Clock
Sistemas Embutidos – Versão Modificada
1.6
Mealy Machine and “C” Encoding
I
Inputs
Next State
Logic
Flip
Flops
Outputs
Out1, Out2
Output
Logic
Q
Ck
Inputs
A, B
CK
State 0
State 1
A
B
OUT2
Sistemas Embutidos – Versão Modificada
State 2
State = Initial_State;
While (1) {
// Loop forever
Switch (State) {
case 0:
// Initial_State = 0
{
if (A==0 && B==1) {
State = 3;
Out2 = 1; // depends on inputs &
// present state
}
else
{
State = 4;
Out2 = 0;
}
break;
}
case 1:
// Second State
{
----------------}
1.7
Moore Machine and “C” Encoding
I
Inputs
Next State
Logic
Inputs
A, B
Flip
Flops
Outputs
Out1, Out2
Output
Logic
Q
Ck
CK
State 0
State 1
A
B
OUT2
Sistemas Embutidos – Versão Modificada
State 2
State = Initial_State;
While (1) {
// Loop forever
Switch (State) {
case 0:
// Initial_State = 0
{
Out1 = 0; // depends on state only
Out2 = 1; // depends on state only
if (A==0 && B==1) {
State = 3;
}
else
{
State = 4;
}
break;
}
case 1:
// Second State
{
Out2 = 0;
Out1 = 1;
--------}
1.8
Mealy Finite State Machine
Mealy and Moore
Representation for VHDL
Description
0/0
reset
1/1
1/0
S0/0
1/0
0/0
S1/0
1/0
S2/1
0/0
Sistemas Embutidos – Versão Modificada
1.9
VHDL Description of a FSM
entity sm is
std_logic;
port ( clk, In, reset : in
Mealy : out std_logic; Moore : out
std_logic );
end sm;
architecture behavior of sm is
states is (S0,S1,S2);
type
signal present_state, next_state :
states;begin state_register: process
(clk)
begin
if (clk'event and clk='1') then
if (reset = '1') then
present_state <= S1;
else
present_state <= next_state;
end if;
end if;
end process;
Sistemas Embutidos – Versão Modificada
next_state_transition: process (present_state, In)
begin
next_state <= present_state;
Mealy <= '0';
// JUST A SIGNAL NAME
Moore <= '0';
// JUST A SIGNAL NAME
case (present_state) is
when S0 =>
if (In='1') then
next_state <= S1;
else
next_state <= S0;
end if;
when S1 =>
if (In='0') then
next_state <= S2;
else
Mealy <= '1';
next_state <= S1;
end if;
when S2 =>
Moore <= '1';
if (In='1') then
next_state <= S2;
else
next_state <= S0;
end if;
end case;
end process;
1.10
Máquina de Mealy
Reset
A- Exemplo:
0/1
1/0
E0
1/1
1/0
0/0
1/0
E1
0/0
0/1
B- Tabela de Transição
Est.
E2
0/1
E4
E3
1/0
Próx. Estado/Saída
Atual
Entrada (x)
E
x=0
x=1
E0
E0/1
E2/0
E1
E3/1
E1/1
E2
E1/0
E4/1
E3
E0/0
E2/0
E4
E1/1
E3/0
Sistemas Embutidos – Versão Modificada
1.11
Máquina de Moore
Reset
1
A- Exemplo:
0
E0/1
1
0
0
E3/0
1
E4/0
0
B- Tabela de Transição
Est.
E2/1
Próx. Estado
Saída (y)
Atual
Entrada (x)
E
x=0
x=1
E0
E0
E2
1
E1
E3
E1
0
E2
E1
E4
1
E3
E0
E2
0
E4
E1
E3
0
Sistemas Embutidos – Versão Modificada
1
0
1
E1/0
y = F (E)
1.12
Algumas Características de Máquinas Não Determinísticas
(simplificando inicialmente)
 Os estados são equivalentes a variáveis booleanas em
um programa
 Sua construção é mais intuitiva que a determinística
 A atribuição de estados é simples, normalmente
associados com as saídas. Normalmente não se usa
codificação de estados.
 As equações são extraídas diretamente do diagrama,
sem tabelas ou mapas
 Máquinas não determinísticas são ineficientes para
sequências de contagem pois usam mais flip-flops que
máquinas determinísticas com codificação de estados.
Sistemas Embutidos – Versão Modificada
1.13
Geração das Equações de Estado
 Em Máquinas Determinísticas
• Atribui-se a Codificação dos Estados
• Mapeiam-se os Estados e Eventos em uma Tabela Verdade
• Simplifica-se com o Mapa de Karnaugh (ou programa específico)
 Em Máquinas Não Determinísticas:
•
•
•
•
Cada estado é representado por um bit (“One Hot Encoding”)
Cada termo produto é o produto do evento com o estado origem
O estado é ativado pelo “ou” dos produtos que chegam a ele
O estado é desativado pelos produtos que efetivamente o
abandonam. Na verdade, um estado é desativado pela ativação
de um estado gerado a partir dele. Portanto, não é necessário
especificar as equações para desativar estados.
Sistemas Embutidos – Versão Modificada
1.14
Mealy x Moore
Mealy Machine:
• Output is specified based on transitions, that is, this type of machine
model should be used when the output signals must change almost
simultaneously (combinational delay logic only) with the input signals
and not only with state transitions. The designer has to recognize the
need for this type of behavior.
• There can be “glitches” on output signals because input signals are
allowed to change at any time.
• Mealy machines typically have fewer states. Because it can associate
outputs with transitions, a Mealy machine can often generate the same
output sequence in fewer states than a Moore machine.
Moore Machine: output is specified based on states only. This
means that output signals will vary only just after clock
transitions and not at any moment. This minimizes the
possibilities of glitches on output signals.
The two are equivalent, one can be constructed from the other
Sistemas Embutidos – Versão Modificada
1.15
Moore/Mealy
 More States in Moore Than in Behavioral
Equivalent Mealy
 Mealy
• Usually pulse output (during transition)
 Moore
• Usually level output (during state)
Sistemas Embutidos – Versão Modificada
1.16
State Encoding
 Binary Coded State
•
•
•
•
n flip-flops used to store 2n states
Most efficient
Need to account for unused states
The number of flip-flops is reduced by
enconding states (e.g: 3 flip-flops -> 8
states)
3 bits – 8 states
000 – S0
001 – S1
010 – S2
011 – S3
100 – S4
101 – S5
110 – S6
111 – S7
 “One-Hot” Encoding
• Requires one flip-flop (one bit) for each
state (uses more flip-flops than the
minimum required)
• There is no need for state decoding logic
• The flip-flop that stores the state can also
be used as an output signal.
• Very good encoding for simple FSMs.
• Maps well to FPGAs since each CLB
contains a FF
Sistemas Embutidos – Versão Modificada
One bit for each
state
001 – state 1
010 – state 2
100 – state 3
1.17
Washing Machine Control Panel
LIGADA
Molho 10
Enxaguar
RESET
OPERANDO
INICIAR
AG
AA
EA
TA
Entradas (de Sensores e Botões de Contrôle):
MC
Sinais de Saída :
RESET – Botão Reset – Reinicia Programa
LED Ligada
M10 – Especifica Molho 10 minutos
LED Operando
INIC – Botão Iniciar após escolher Molho
ou Enxaguar
LED M10 – Molho 10
LED - Enxaguando
LED AG - Agitando
ENX – Enxaguar
LED AA – Abre_Água
TA – Tampa_Aberta
LED EA – Esvazia_Água
CC – Cesto_Cheio
LED TA – Tampa_Aberta
CV – Cesto_Vazio
LED MC – Motor_Centrifugar
Sistemas Embutidos – Versão Modificada
1.18