Aprenda › Tema 11

Máquinas de estados Moore e Mealy: projeto completo

Leitura de 7 min · Equipe bitGateLab

Uma máquina de estados finitos (FSM) é um circuito sequencial que "lembra" em que passo de um processo está. Semáforos, fechaduras com senha, controladores de elevador e receptores de comunicação serial são máquinas de estados. Aqui você vai ver os dois modelos clássicos, Moore e Mealy, e acompanhar um projeto completo, da descrição em palavras até as equações dos flip-flops, com um detector da sequência 101.

Partes de uma máquina de estados

Toda FSM síncrona tem três blocos:

Registrador de estado: n flip-flops (quase sempre do tipo D) que guardam o estado atual; são suficientes para até 2ⁿ estados.
Lógica de próximo estado: combinacional; calcula o próximo estado a partir do estado atual e das entradas.
Lógica de saída: combinacional; calcula as saídas.

A diferença entre os dois modelos está no último bloco:

Moore: as saídas dependem apenas do estado atual. São escritas dentro do círculo de cada estado (por exemplo S3/1).
Mealy: as saídas dependem do estado e das entradas. São escritas sobre as setas (entrada/saída, por exemplo 1/1).

Uma máquina de Mealy costuma precisar de menos estados e responde no mesmo ciclo em que a entrada chega, mas sua saída pode mudar a qualquer momento se a entrada mudar. Uma de Moore responde um ciclo depois, e sua saída só muda logo após a borda do clock, o que a torna mais limpa.

O problema: detector da sequência 101

Uma entrada serial X chega sincronizada com o clock, um bit por ciclo. A saída Z deve valer 1 sempre que os últimos três bits recebidos forem 1, 0, 1. Permite-se sobreposição: na cadeia 10101 há duas detecções, porque o último 1 da primeira sequência é o primeiro da seguinte.

O primeiro passo é decidir o que a máquina deve lembrar. Cada estado representa "quanto da sequência eu já tenho":

S0: ainda não tenho nada útil.
S1: o último bit foi 1.
S2: os últimos bits foram 1, 0.
S3: acabei de receber 1, 0, 1 (Z = 1).

Diagrama e tabela de estados (Moore)

Para cada estado e cada valor de X, pergunte-se: com este novo bit, qual é o sufixo mais longo que coincide com o início de 101? Esse sufixo define o próximo estado.

Detector Moore de 101 com sobreposição. Os números sobre as setas são o valor de X; a saída está dentro de cada estado.

Estado atual	X = 0	X = 1	Z
S0	S0	S1	0
S1	S2	S1	0
S2	S0	S3	0
S3	S2	S1	1

Repare em duas transições em que é comum errar. Em S1 chega outro 1: a cadeia termina em 11, e o último 1 continua servindo como início, de modo que a máquina fica em S1. Em S3 chega um 0: a cadeia termina em 1010, cujo sufixo 10 coincide com o início de 101, de modo que ela vai para S2 e não para S0. É isso que permite a sobreposição.

Atribuição de estados e equações

Com 4 estados bastam 2 flip-flops D (Q1 Q0). A atribuição mais direta é a binária: S0 = 00, S1 = 01, S2 = 10, S3 = 11. Com flip-flops D a tabela de excitação é trivial, porque D = Q⁺.

Q1	Q0	X	Q1⁺ = D1	Q0⁺ = D0
0	0	0	0	0
0	0	1	0	1
0	1	0	1	0
0	1	1	0	1
1	0	0	0	0
1	0	1	1	1
1	1	0	1	0
1	1	1	0	1

Simplificação:

D0 vale 1 exatamente nas linhas com X = 1, portanto D0 = X. Faz sentido: nessa atribuição, Q0 = 1 significa "o último bit foi 1".
D1 = Σm(2, 5, 6) com as variáveis na ordem Q1 Q0 X. Os mintermos 2 (010) e 6 (110) são adjacentes e formam Q0·X. O 5 (101) não tem vizinhos em 1 e fica sozinho: Q1·Q0·X. D1 = Q0·X + Q1·Q0·X.
A saída de Moore depende apenas do estado: Z = Q1·Q0.

O circuito fica com 2 flip-flops D, uma AND de 2 entradas para Z e, para D1, uma AND de 2, uma AND de 3 e uma OR de 2 (mais os inversores de Q0 e X).

Verificação com uma sequência de teste

Entrada X = 1 0 1 0 1 1 0 1, partindo de S0. Estado depois de cada borda:

Borda	1	2	3	4	5	6	7	8
X	1	0	1	0	1	1	0	1
Estado	S1	S2	S3	S2	S3	S1	S2	S3
Z	0	0	1	0	1	0	0	1

Há três detecções: nos bits 1 a 3, 3 a 5 (sobreposição) e 6 a 8. Confira a borda 4 com as equações: estado S3 = 11 e X = 0, D1 = 1·1 + 1·0·0 = 1 e D0 = 0, próximo estado 10 = S2. Confere.

A versão Mealy

Em Mealy a saída fica na transição, de modo que o estado S3 é desnecessário: a detecção ocorre "quando chega o 1 estando em S2". Com três estados A (nada), B (último bit 1) e C (últimos bits 1, 0):

Estado	X = 0	X = 1
A	A / 0	B / 0
B	C / 0	B / 0
C	A / 0	B / 1

Continuam sendo necessários 2 flip-flops, mas a saída Z = 1 aparece no mesmo ciclo em que chega o último 1, um ciclo antes do que na versão Moore.

Erros comuns

Mandar para S0 todas as transições que "falham", sem verificar que parte da sequência ainda serve; assim se perdem detecções com sobreposição.
Escrever saídas sobre as setas em uma máquina de Moore ou dentro dos estados em uma de Mealy.
Esquecer as combinações de flip-flops não usadas (por exemplo, o código 11 na versão Mealy): é preciso decidir para onde elas vão ou marcá-las como X e verificar se a máquina volta à sequência.
Ler a saída de uma Mealy em qualquer momento: ela deve ser amostrada logo antes da borda, quando a entrada já está estável.
Mudar a entrada X exatamente na borda do clock ao testar a máquina.

Experimente no simulador

Com as equações em mãos, montar o detector leva poucos minutos, e o cronograma permite comprovar cada transição.

Coloque dois flip-flops D com o mesmo clock; nomeie as saídas deles como Q1 e Q0.
Conecte a entrada X diretamente a D0.
Monte D1 = Q0·X + Q1·Q0·X com dois inversores, duas AND e uma OR, e conecte-o a D1.
Conecte uma AND de Q1 e Q0 a um indicador para Z.
Mude X antes de cada borda seguindo a sequência 1 0 1 0 1 1 0 1 e observe no cronograma que Z acende depois das bordas 3, 5 e 8.

Exercícios

Com sobreposição, quantas vezes a máquina detecta 101 na cadeia 1010101?
Resposta
Três vezes: nos bits 1 a 3, 3 a 5 e 5 a 7.
Refaça a tabela Moore do detector de 101 sem sobreposição (depois de uma detecção, começa-se do zero).
Resposta
Só muda a linha S3: com X = 0 vai para S0 e com X = 1 vai para S1. As demais linhas ficam iguais.
Com a atribuição da versão Mealy A = 00, B = 01, C = 10, obtenha Z.
Resposta
Z = 1 somente no estado C com X = 1: Z = Q1·Q0·X. Se o código 11 nunca aparece, ele pode ser marcado como X e fica Z = Q1·X.
De quantos flip-flops precisa, no mínimo, uma máquina de 9 estados?
Resposta
4, porque 2³ = 8 não é suficiente e 2⁴ = 16 é.

Para revisar os flip-flops que formam o registrador de estado, consulte latches e flip-flops.