Máquinas de Estados Finitos
Vídeo da aula estará disponível em breve
O que é uma Máquina de Estados Finitos
Uma Máquina de Estados Finitos (FSM — Finite State Machine) é um modelo matemático de um sistema sequencial com um número finito de estados. A cada pulso de clock, a máquina pode transitar de um estado para outro, dependendo das entradas e do estado atual. FSMs são o modelo central para projetar qualquer circuito sequencial.
Definição formal
Uma FSM é definida por 5 elementos:
M = (S, I, O, δ, λ)
S = conjunto finito de estados
I = conjunto finito de entradas
O = conjunto finito de saídas
δ = função de transição: S × I → S (próximo estado)
λ = função de saída (difere entre Moore e Mealy)Moore vs. Mealy
Existem dois tipos de FSM, que diferem em como a saída é determinada:
Moore vs. Mealy
MOORE: saída depende APENAS do estado atual
λ: S → O
A saída é associada ao estado (dentro do círculo)
Estrutura:
Entradas → Lógica de → Registrador → Lógica de → Saídas
próximo estado de estado saída
(combinacional) (sequencial) (combinacional)
MEALY: saída depende do estado atual E das entradas
λ: S × I → O
A saída é associada à transição (na seta)
Estrutura:
Entradas → Lógica de → Registrador → Saídas
│ próximo estado de estado ↑
│ (combinacional) (sequencial) │
└──────────────────────────────────┘
Lógica de saída
Diferenças práticas:
Moore: saídas mudam apenas com o clock (mais estável)
Mealy: saídas podem mudar assincronamente com entradas
Mealy: geralmente precisa de menos estados
Moore: mais fácil de depurarDiagramas de estado
FSMs são representadas visualmente com diagramas de estado, onde círculos são estados e setas são transições:
Notação
MOORE:
┌──────┐
│ S0 │ Estado com saída dentro
│ Y=01 │ (nome do estado / saída)
└──┬───┘
│ X=1 Transição com condição de entrada
▼
┌──────┐
│ S1 │
│ Y=10 │
└──────┘
MEALY:
┌────┐
│ S0 │ Estado (sem saída)
└─┬──┘
│ X=1/Y=10 Transição com entrada/saída
▼
┌────┐
│ S1 │
└────┘Exemplo completo: controlador de semáforo
Vamos projetar um controlador de semáforo simples com dois sinais (Norte-Sul e Leste-Oeste). Usaremos uma FSM Moore com 4 estados.
Passo 1: Definir estados e saídas
Definição dos estados
Estados:
S0: NS=Verde, EW=Vermelho (tráfego Norte-Sul)
S1: NS=Amarelo, EW=Vermelho (transição)
S2: NS=Vermelho, EW=Verde (tráfego Leste-Oeste)
S3: NS=Vermelho, EW=Amarelo (transição)
Entrada:
T = sinal do temporizador (1 quando tempo esgotou)
Saídas (6 bits: NS[2:0], EW[2:0]):
Verde = 001
Amarelo = 010
Vermelho = 100
Estado │ NS │ EW │ Saída (6 bits)
───────┼───────┼────────┼───────────────
S0 │ Verde │ Verm │ 001_100
S1 │ Amar │ Verm │ 010_100
S2 │ Verm │ Verde │ 100_001
S3 │ Verm │ Amar │ 100_010Passo 2: Diagrama de estados (Moore)
Diagrama de estados
T=0 (espera)
┌──┐
│ ▼
┌──────┐ T=1 ┌──────┐
┌───→│ S0 │────────→│ S1 │───┐
│ │001100│ │010100│ │
│ └──────┘ └──────┘ │
│ T=1 │
│ T=1 ▼ │
│ ┌──────┐ ┌──────┐ │
└────│ S3 │←────────│ S2 │←──┘
│100010│ T=1 │100001│
└──────┘ └──────┘
▲ │ ▲ │
└──┘ └──┘
T=0 T=0
Ciclo: S0 → S1 → S2 → S3 → S0 → ...
Cada estado espera T=1 para avançar.Passo 3: Tabela de estados
Tabela de transição de estados
Codificação dos estados (2 bits: Q₁Q₀):
S0 = 00, S1 = 01, S2 = 10, S3 = 11
Estado atual │ T │ Próximo estado │ Saídas
Q₁ Q₀ │ │ Q₁⁺ Q₀⁺ │ NS[2:0] EW[2:0]
─────────────┼───┼───────────────┼─────────────────
0 0 │ 0 │ 0 0 │ 001 100
0 0 │ 1 │ 0 1 │ 001 100
0 1 │ 0 │ 0 1 │ 010 100
0 1 │ 1 │ 1 0 │ 010 100
1 0 │ 0 │ 1 0 │ 100 001
1 0 │ 1 │ 1 1 │ 100 001
1 1 │ 0 │ 1 1 │ 100 010
1 1 │ 1 │ 0 0 │ 100 010Passo 4: Lógica de próximo estado e saída
Expressões booleanas
Próximo estado (por K-map ou inspeção):
Q₁⁺ = Q₁ ⊕ (Q₀ · T)
= Q₁·(Q₀·T)̅ + Q̅₁·Q₀·T
= Q₁·Q̅₀ + Q₁·T̅ + Q̅₁·Q₀·T
Q₀⁺ = Q₀ ⊕ T
= Q₀·T̅ + Q̅₀·T
(Observação: isso é um contador de 2 bits que
incrementa quando T=1!)
Saídas (Moore — dependem apenas do estado):
NS_Verde = Q̅₁ · Q̅₀ (S0)
NS_Amarelo = Q̅₁ · Q₀ (S1)
NS_Vermelho = Q₁ (S2 ou S3)
EW_Verde = Q₁ · Q̅₀ (S2)
EW_Amarelo = Q₁ · Q₀ (S3)
EW_Vermelho = Q̅₁ (S0 ou S1)
Circuito final:
2 flip-flops D (para Q₁, Q₀)
+ lógica combinacional para próximo estado
+ lógica combinacional para saídas
+ clock e temporizador
Metodologia de projeto de FSM
- Definir estados, entradas e saídas
- Desenhar diagrama de estados
- Criar tabela de transição de estados
- Escolher codificação dos estados (binária, one-hot, Gray)
- Derivar expressões de próximo estado (K-maps)
- Derivar expressões de saída
- Implementar com flip-flops + lógica combinacional
Codificação de estados
Estratégias de codificação
BINÁRIA (mínimo de flip-flops):
S0=00, S1=01, S2=10, S3=11
4 estados → 2 FFs
Lógica de saída mais complexa
ONE-HOT (um FF por estado):
S0=0001, S1=0010, S2=0100, S3=1000
4 estados → 4 FFs
Lógica de saída trivial (cada FF = um estado)
Preferida em FPGAs (FFs são abundantes, lógica é cara)
GRAY (estados adjacentes diferem em 1 bit):
S0=00, S1=01, S2=11, S3=10
Reduz glitches nas transições (apenas 1 bit muda)
Exemplo one-hot para o semáforo:
NS_Verde = FF₀ (Q do flip-flop 0)
NS_Amarelo = FF₁
EW_Verde = FF₂
EW_Amarelo = FF₃
Decodificação zero! Cada FF é diretamente uma saída.FSM em Verilog
Verilog
module semaforo(
input wire clk, reset, timer_done,
output reg [2:0] ns_light, ew_light
);
// Definição dos estados
localparam S0 = 2'b00, // NS verde
S1 = 2'b01, // NS amarelo
S2 = 2'b10, // EW verde
S3 = 2'b11; // EW amarelo
localparam VERDE = 3'b001,
AMARELO = 3'b010,
VERMELHO = 3'b100;
reg [1:0] state, next_state;
// Registrador de estado (sequencial)
always @(posedge clk or posedge reset) begin
if (reset)
state <= S0;
else
state <= next_state;
end
// Lógica de próximo estado (combinacional)
always @(*) begin
case (state)
S0: next_state = timer_done ? S1 : S0;
S1: next_state = timer_done ? S2 : S1;
S2: next_state = timer_done ? S3 : S2;
S3: next_state = timer_done ? S0 : S3;
default: next_state = S0;
endcase
end
// Lógica de saída Moore (combinacional)
always @(*) begin
case (state)
S0: begin ns_light = VERDE; ew_light = VERMELHO; end
S1: begin ns_light = AMARELO; ew_light = VERMELHO; end
S2: begin ns_light = VERMELHO; ew_light = VERDE; end
S3: begin ns_light = VERMELHO; ew_light = AMARELO; end
default: begin ns_light = VERMELHO; ew_light = VERMELHO; end
endcase
end
endmoduleFSMs em software
FSMs não existem apenas em hardware. São um dos padrões de projeto mais usados em software:
Python — FSM para parser
# FSM simples: detectar a sequência "101" em um fluxo de bits
class DetectorFSM:
def __init__(self):
self.state = "S0" # estado inicial
def process(self, bit):
# Tabela de transição
transitions = {
"S0": {0: "S0", 1: "S1"}, # esperando primeiro 1
"S1": {0: "S2", 1: "S1"}, # viu 1, esperando 0
"S2": {0: "S0", 1: "S3"}, # viu 10, esperando 1
"S3": {0: "S2", 1: "S1"}, # detectou 101!
}
detected = self.state == "S3"
self.state = transitions[self.state][bit]
return detected
# Uso
fsm = DetectorFSM()
stream = [1,0,1,1,0,1,0,1]
for bit in stream:
if fsm.process(bit):
print("Sequência 101 detectada!")No harness.os
Máquinas de estados finitos são possivelmente o conceito de sistemas digitais mais diretamente aplicável ao harness.os:
- Estado de sessão — cada sessão do harness transita por estados (started → active → completed). As transições são disparadas por eventos (início de trabalho, end_session). Isso é literalmente uma FSM Moore: a saída (comportamento permitido) depende apenas do estado atual.
- Estado de projeto — projetos transitam entre fases (discovery → development → testing → production). Cada fase habilita diferentes workflows e regras. A tabela de transição define quais transições são válidas.
- Workflows como FSMs — cada workflow no harness (QA gate, deployment pipeline, feature flag lifecycle) é uma FSM com estados, transições e condições de guarda. O template de workflow é o diagrama de estados; a execução é a instância da FSM.
- Moore vs. Mealy no harness — regras que dependem apenas do estado do projeto (Moore: "em produção, exija revisão de segurança") vs. regras que dependem do estado + entrada (Mealy: "em desenvolvimento, se o commit tocar em auth, exija revisão de segurança"). O harness suporta ambos os modelos.
- Codificação one-hot em flags — representar estados como flags booleanas independentes (is_active, is_testing, is_production) é codificação one-hot. Cada flag é um "flip-flop" conceitual. A alternativa binária seria um campo enum com valor numérico.
Exercícios
- Detector de sequência: Projete uma FSM Moore que detecta a sequência "110" em um fluxo serial de bits. Desenhe o diagrama de estados, crie a tabela de transição e derive as expressões de próximo estado usando flip-flops D. A saída deve ser 1 apenas no clock em que o último bit da sequência é recebido.
- Semáforo com pedestre: Modifique o controlador de semáforo para incluir um botão de pedestre (P). Quando P=1 durante o estado NS verde, o semáforo deve completar o ciclo normal. Mas se P=1 durante EW verde, deve transitar para EW amarelo imediatamente. Desenhe o diagrama de estados Mealy.
- Vending machine: Projete uma FSM para uma máquina de venda que aceita moedas de 5 e 10 centavos. O produto custa 15 centavos. A máquina deve dar troco se necessário. Defina os estados, desenhe o diagrama, e escreva a tabela de transição completa.
Resumo
Verifique seu entendimento
Qual é a diferença entre uma FSM Moore e uma FSM Mealy?
- FSM = estados finitos + entradas + saídas + transições + função de saída
- Moore: saída depende apenas do estado (mais estável, mais estados)
- Mealy: saída depende do estado + entradas (menos estados, saídas assíncronas)
- Metodologia: diagrama → tabela → codificação → K-maps → circuito
- Codificação binária minimiza flip-flops; one-hot simplifica a lógica de saída
- FSMs aparecem em hardware (controladores, protocolos) e software (parsers, workflows)
- Verilog estrutura FSMs em 3 blocos: registrador, próximo estado, saída