PT

Máquinas de estados (Moore e Mealy)

Do diagrama de estados à tabela e às equações dos flip-flops, com um detetor de sequência

Projetista de detetor de sequência

Máquina

Diagrama de estados

Cada seta leva o valor da entrada x que a provoca; em Mealy, também a saída produzida («entrada/saída»). Em Moore a saída vai dentro do estado, e os estados com círculo duplo são os que dão z = 1.

Tabela de estados

Equações com flip-flops D

Simulação

Entrada

O que é uma máquina de estados

Uma máquina de estados finitos é um circuito sequencial que, em cada momento, está num de um número limitado de estados. O estado resume tudo o que importa do passado. A cada flanco de relógio passa a um novo estado, que depende do estado atual e das entradas. Constrói-se com um registo de flip-flops, que guarda o estado, e dois blocos de lógica combinatória: um calcula o estado seguinte e outro as saídas.

É a forma ordenada de projetar qualquer automatismo sequencial: um semáforo, o controlo de uma porta automática, uma máquina de venda, o protocolo de uma porta série ou as etapas de um ciclo de lavagem. Num PLC programa-se da mesma forma com GRAFCET ou com passos em ladder, e num microcontrolador com um switch sobre uma variável de estado.

Moore e Mealy

MooreMealy
A saída dependeSó do estadoDo estado e das entradas
Onde se desenha a saídaDentro de cada estadoEm cada seta, «entrada/saída»
Número de estadosCostuma precisar de mais algumCostuma precisar de menos
RespostaA saída muda no flanco de relógio seguinteA saída muda logo que muda a entrada
SaídaEstável durante todo o ciclo, sem glitchesPode ter glitches se a entrada os tiver

Compare os dois tipos no simulador com a mesma sequência: o detetor de Mealy dá z = 1 no mesmo ciclo em que chega o último bit, e o de Moore um ciclo depois, quando já entrou no estado final. Se a saída de um Mealy for levada a outro circuito síncrono, esse atraso aparece de qualquer modo ao registá-la.

Passos do projeto

  1. Diagrama de estados. Descreve-se o comportamento: que estados há, para qual se passa com cada entrada e que saída se produz. Num detetor de sequência, cada estado significa «já recebi os primeiros k bits da sequência».
  2. Tabela de estados. O mesmo que o diagrama, em forma de tabela: estado atual e entrada à esquerda, estado seguinte e saída à direita.
  3. Codificação. Atribui-se um código binário a cada estado. Com S estados são precisos ⌈log₂ S⌉ flip-flops. A codificação binária usa o mínimo de flip-flops; a «one-hot» (um flip-flop por estado) gasta mais flip-flops mas simplifica muito as equações, e é habitual em FPGA.
  4. Equações. Com flip-flops D, a entrada D de cada um é diretamente o bit correspondente do estado seguinte. Os códigos não usados são indiferentes e ajudam a simplificar no mapa de Karnaugh. Com flip-flops JK usa-se a tabela de excitação em vez de copiar o estado seguinte.
  5. Estados que sobram. É preciso verificar para onde vai a máquina se arrancar num código não usado, por um ruído ou ao ligar, e prever um reset que a leve ao estado inicial.

Sobreposição

Com sobreposição, os últimos bits de uma sequência detetada podem ser o início da seguinte: procurando 1011 em 1011011, deteta-se duas vezes. Sem sobreposição, após cada deteção a máquina recomeça e só encontra uma. Para decidir a que estado voltar quando chega um bit que não encaixa, procura-se a parte mais longa do que foi recebido que coincide com o início da sequência; é a mesma ideia usada pelo algoritmo de pesquisa de texto KMP.

Exemplo: um semáforo

Um semáforo para automóveis com botão para peões é uma máquina de Moore: as luzes dependem só do estado. Um temporizador dá o sinal de «tempo cumprido» e o botão fica memorizado até ser atendido.

EstadoLuzes automóveisLuzes peõesPassa ao seguinte quando
S0 VerdeVerdeVermelhoUm peão carregou e passou o tempo mínimo de verde
S1 AmareloAmareloVermelhoTempo de amarelo cumprido
S2 VermelhoVermelhoVerdeTempo de travessia dos peões cumprido
S3 DesobstruçãoVermelhoVerde intermitenteTempo de desobstrução cumprido; volta a S0

Quatro estados codificam-se com dois flip-flops. As saídas são funções de Q1 e Q0, por exemplo verde dos automóveis = Q1'·Q0' e vermelho dos peões = Q1'.

Relacionado: latches e flip-flops, mapa de Karnaugh, simulador de portas lógicas e simulador ladder.