Do diagrama de estados à tabela e às equações dos flip-flops, com um detetor de sequência
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.
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 | Mealy | |
|---|---|---|
| A saída depende | Só do estado | Do estado e das entradas |
| Onde se desenha a saída | Dentro de cada estado | Em cada seta, «entrada/saída» |
| Número de estados | Costuma precisar de mais algum | Costuma precisar de menos |
| Resposta | A saída muda no flanco de relógio seguinte | A saída muda logo que muda a entrada |
| Saída | Estável durante todo o ciclo, sem glitches | Pode 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.
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.
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.
| Estado | Luzes automóveis | Luzes peões | Passa ao seguinte quando |
|---|---|---|---|
| S0 Verde | Verde | Vermelho | Um peão carregou e passou o tempo mínimo de verde |
| S1 Amarelo | Amarelo | Vermelho | Tempo de amarelo cumprido |
| S2 Vermelho | Vermelho | Verde | Tempo de travessia dos peões cumprido |
| S3 Desobstrução | Vermelho | Verde intermitente | Tempo 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.