Máquinas de Estados
Máquinas de Estados Finitos (FSM)
Circuitos combinacionais dependem apenas das entradas atuais. Já os circuitos sequenciais possuem memória: suas saídas dependem das entradas atuais e de toda a história passada do sistema, resumida no conceito de Estado.
Fundamentos de Circuitos Sequenciais
Como é impossível construir um circuito com memória infinita para guardar todas as entradas passadas, compactamos o histórico relevante em um número finito de combinações binárias chamadas Estados Internos.
Estímulo vindo do mundo externo (sensores, botões ou barramento de dados) que provoca mudanças na máquina.
Valor binário armazenado nos Flip-Flops no ciclo de clock atual. Representa o resumo do passado do circuito.
O novo estado para o qual a máquina irá avançar assim que ocorrer a próxima borda ativa do sinal de clock.
As Duas Equações Gerais de uma FSM
O próximo estado sempre depende do estado atual e da entrada atual.
Define se a saída depende só do estado ou também da entrada imediata.
Arquitetura: Moore vs. Mealy
Saída depende exclusivamente do Estado Atual ($Q$)
| Critério | Máquina de Moore | Máquina de Mealy |
|---|---|---|
| Dependência da Saída | Apenas do Estado Atual: $Z = g(Q)$ | Estado Atual e Entrada: $Z = g(Q, X)$ |
| Representação no Grafo |
Dentro do círculo do estado:
Estado / Z
|
Nas setas de transição:
X / Z
|
| Quantidade de Estados | Maior (ex: 4 estados para detector "01") | Menor (ex: 2 estados para detector "01") |
| Velocidade de Resposta | Síncrona (aguarda a borda do clock) | Mais rápida (reage imediatamente a $X$) |
| Sensibilidade a Ruídos | Alta imunidade (saída filtrada pelos FFs) | Sujeita a glitches se $X$ oscilar |
Roteiro de Projeto em 6 Passos
Todo projeto de circuito sequencial síncrono em PCS3115 segue uma receita estruturada que transforma um problema em palavras em portas lógicas e Flip-Flops reais:
Diagrama de Estados
Traduzir o enunciado verbal para um grafo visual com nós (estados) e setas (transições guiadas pelas entradas).
Tabela de Estados
Tabular todas as transições: linhas representam o estado atual e colunas mostram o próximo estado e a saída para cada entrada.
Minimização de Estados
Identificar e fundir estados equivalentes para reduzir o número de Flip-Flops necessários na implementação física.
Designação de Estados
Atribuir códigos binários ($y_1, y_0$) para cada estado simbólico ($A, B, C...$). O uso de código Gray vizinho ajuda a simplificar mapas.
Mapas de Karnaugh
Escolher o tipo de Flip-Flop (geralmente Tipo D, onde $D = Y$) e extrair as equações booleanas mínimas para cada bit de estado e saída.
Esquemático Final
Desenhar ou simular o circuito lógico conectando as portas AND, OR e NOT às entradas dos Flip-Flops sincronizados pelo clock.
Laboratório Interativo: Detector de Sequência "01"
Vamos comparar na prática como as máquinas de Moore (4 estados) e Mealy (2 estados) reagem exatamente à mesma sequência de bits. Envie bits de entrada ($x = 0$ ou $x = 1$) abaixo ou clique diretamente nos estados dos diagramas para inspecionar seu significado.
Saída dentro do Estado
Saída nas Transições ($x/z$)
Diagrama de Formas de Onda (Timing Diagram)
Visualização temporal síncrona dos sinais e comparação de glitches entre Moore e Mealy
Síntese Lógica e Mapas de Karnaugh
Tabela de Transição Codificada & Mapas de Karnaugh
| Estado | $y_1 y_0$ | $Y_1 Y_0$ ($x=0$) | $Y_1 Y_0$ ($x=1$) | Saída $z$ |
|---|---|---|---|---|
| A | 0 0 | 0 1 (B) | 0 0 (A) | 0 |
| B | 0 1 | 0 1 (B) | 1 1 (C) | 0 |
| C | 1 1 | 0 1 (B) | 1 0 (D) | 1 |
| D | 1 0 | 0 1 (B) | 1 0 (D) | 0 |
Economia Extrema de Hardware com Mealy
| Estado Atual (y) | Próx. Y (x=0) | Próx. Y (x=1) | Saída z (x=0) | Saída z (x=1) |
|---|---|---|---|---|
| A (y = 0) | 1 (B) | 0 (A) | 0 | 0 |
| B (y = 1) | 1 (B) | 0 (A) | 0 | 1 |
Observe a coluna de Próximo Estado ($Y$): ela vale $1$ sempre que $x = 0$ e vale $0$ sempre que $x = 1$, independentemente de $y$!
Já a saída $z$ só é ativada na combinação única onde estamos no estado $B$ ($y=1$) e chega a entrada $x=1$:
Autoavaliação Rápida para a Prova
Por que o modelo de Mealy costuma exigir menos estados que o modelo de Moore para resolver o mesmo problema?
Se uma máquina possui 5 estados distintos após a etapa de minimização, qual é o número mínimo de Flip-Flops necessários?