Máquinas de estados finitos: um circuito que lembra em que passo está

Máquinas de estados finitos: um circuito que lembra em que passo está

Imagine um cofre de brinquedo que só abre quando você digita 1, 0, 1 nessa ordem, e que não se importa com o que veio antes. Se você digitar 1, 1, 0, 1, ele ainda assim abre, porque os três últimos dígitos formam a sequência certa. O cofre não guarda a sequência inteira que você digitou. Ele guarda só o pedaço do que digitou que ainda pode virar a senha, e esse pedaço muda a cada dígito. Essa é a ideia de uma máquina de estados finitos: um circuito que decide o que fazer olhando para a entrada do momento e para um pequeno número de situações possíveis em que ele pode estar, chamadas estados.

A analogia tem um limite claro. O cofre de brinquedo é uma máquina de estados de verdade, mas um cofre real guarda a senha inteira em algum lugar, e a máquina de estados guarda apenas o estado atual. Quem projeta um circuito precisa decidir quais situações distinguir, e a qualidade do projeto depende dessa escolha.

A aula Circuitos sequenciais mostrou como um flip-flop guarda um bit, e a aula Clock e sincronização mostrou quando esses bits podem mudar. Esta aula junta as duas peças. Um registrador de poucos flip-flops guarda o estado, portas lógicas calculam o próximo estado e a saída, e o clock decide quando o estado avança. É a estrutura mais comum de controle digital, e é também a forma que a unidade de controle de uma CPU tem por dentro, o que liga esta aula à fase 3 da Trilha de Hardware.

Mapa da aula

As figuras de circuito, como a 06, têm fundo escuro embutido, como nas aulas anteriores da fase. Os valores de tempo dos diagramas são de exemplo, e a seção de fontes diz o que foi conferido.

1. O que é uma máquina de estados

Uma máquina de estados finitos, sigla FSM em inglês (finite state machine), é um circuito cuja saída depende da entrada atual e do estado em que ele se encontra. O estado é um conjunto finito de situações possíveis. “Finito” quer dizer que a lista de situações tem tamanho fixo e conhecido de antemão, e isso é o que permite desenhar o circuito.

A máquina tem quatro peças. Os estados são as situações em que ela pode estar. As entradas são os sinais que chegam a cada ciclo de clock. As saídas são os sinais que ela produz. As transições são as regras que dizem, para cada estado e cada entrada, qual é o próximo estado. Existe ainda o estado inicial, que é o estado em que a máquina começa depois do reset.

Um semáforo de cruzamento é a máquina de estados mais fácil de ver. Ele está em verde, amarelo ou vermelho, e troca de estado quando o temporizador esgota. A figura 01 mostra o desenho. O círculo cheio à esquerda marca o estado inicial, cada caixa é um estado, e cada seta é uma transição com o motivo que a dispara. Note que o semáforo não guarda o tempo que já passou no verde. Essa contagem fica num temporizador separado, e a máquina só recebe um sinal dizendo que o tempo acabou. Essa separação aparece de novo mais adiante, quando o circuito de um contador é ligado a uma máquina de estados.

A figura mostra três estados e três transições, todas com a mesma condição, “t = 1”, que significa que o temporizador esgotou. Não há setas de volta no mesmo estado, porque o semáforo espera sem fazer nada enquanto t vale 0. O ArchFlow não desenha esses laços, e a legenda dos próximos diagramas repete essa informação quando for o caso.

Esse desenho se chama diagrama de estados. Ele é ótimo para entender uma máquina e ruim para executá-la. Para virar circuito, o diagrama vira uma tabela, e a tabela vira equações. As seções seguintes fazem essa passagem com um exemplo completo.

2. Para que serve

Um circuito puramente combinacional, como o somador da aula Circuitos combinacionais, não lembra nada. Ele responde a cada entrada como se fosse a primeira. Isso basta para somar, mas não basta para uma tarefa que depende da ordem dos acontecimentos. Um controle de elevador precisa lembrar se a porta já está aberta. Um leitor de código de barras precisa lembrar se já viu o início de uma sequência. Um protocolo de comunicação precisa lembrar em que etapa do envio está. Em todos esses casos a resposta depende do que aconteceu antes, e não só do que chegou agora.

Sem uma máquina de estados, o projetista teria duas saídas, e as duas são ruins. A primeira é guardar o histórico inteiro das entradas, o que cresce sem limite. A segunda é espalhar a lógica de controle em contadores e registradores soltos, sem uma regra clara sobre o que cada combinação significa. Quem já viu um circuito desses sabe que o comportamento só se entende lendo o fio com um lápis na mão. A máquina de estados coloca a lógica numa forma que se pode desenhar, conferir e testar antes de montar qualquer coisa.

Há uma razão adicional, que aparece na aula Clock e sincronização. A seção 4.9 de Clock e sincronização diz que um laço de realimentação sem registrador no meio torna o caminho crítico o laço inteiro, e cita esse caso como assunto desta aula. Numa máquina bem projetada, o estado sempre passa por flip-flops. O laço existe, mas corta-se a cada borda de clock, e o caminho crítico é o que vai de um registrador ao seguinte, passando pela lógica de próximo estado.

3. Exemplos em contextos diferentes

O primeiro exemplo é o semáforo da seção 1, que já vimos. Ele mostra o caso mais simples, com um único sinal de entrada e três estados sem nenhuma ambiguidade.

O segundo é a máquina de venda automática. Ela começa em zero, e cada moeda aumenta o crédito. Quando o crédito alcança o preço, a máquina libera o produto e volta ao zero, ou devolve o troco, conforme o modelo. O estado é o valor acumulado, e a entrada é a moeda. Uma máquina real tem muitos estados de crédito, mas o raciocínio é o mesmo do semáforo: a saída, liberar o produto, depende do estado e da entrada no momento em que a moeda chega.

O terceiro é o receptor de uma porta serial UART. Em termos gerais, a linha fica em nível alto quando está ociosa. Quando o receptor vê o bit de início, passa a ler os bits de dados um a um, e depois confere o bit de parada. Cada uma dessas etapas é um estado, e a máquina só avança quando o tempo de cada bit chega. Os tempos exatos e a configuração de bits do protocolo não foram conferidos em fonte nesta aula, então ficam para a seção de limitações.

O quarto é o decodificador de UTF-8 da aula Texto, ASCII, Unicode e UTF-8. Ele lê bytes um a um. Quando o byte inicial diz que o caractere ocupa mais de um byte, a máquina passa a esperar os bytes de continuação e só emite o caractere quando todos chegaram. A figura 08 mostra um recorte disso, com um estado para cada quantidade de bytes de continuação que ainda faltam.

A figura mostra só o recorte. Os estados Falta 1, Falta 2 e Falta 3 são o que a máquina precisa lembrar entre dois bytes, e o caractere só sai quando o último byte de continuação chega. Não há contador nem memória de bytes, só esses estados, e é isso que faz do decodificador uma máquina de estados e não uma sequência de somas.

O quinto é o reconhecimento de expressões regulares. Uma expressão regular simples, sem recursos como referências a grupos anteriores, descreve exatamente o que um autômato finito reconhece. O resultado clássico que liga as duas coisas não foi consultado nesta aula, mas a ideia prática é fácil de ver: um motor de busca por padrão lê o texto caractere a caractere e mantém a posição atual no padrão.

Os cinco exemplos têm a mesma forma. Uma sequência de entradas chega, a máquina mantém um estado pequeno que resume o que importa para o futuro, e a saída depende desse resumo. A próxima seção mostra como esse resumo vira hardware.

4. Como funciona

4.1 A estrutura em hardware

Uma máquina de estados síncrona tem três blocos, e a figura 02 mostra como eles se ligam. O primeiro é o registrador de estado, um conjunto de flip-flops que guarda o estado atual. Ele é o mesmo registrador da aula Circuitos sequenciais, com um clock comum a todos os bits. O segundo é a lógica de próximo estado, um circuito combinacional que recebe o estado atual e a entrada e calcula em que estado a máquina vai estar depois da próxima borda. O terceiro é a lógica de saída, que calcula o que a máquina produz.

A ordem em que os blocos trabalham é o que dá o comportamento. Entre duas bordas de clock, o registrador segura o estado atual. A lógica de próximo estado calcula o próximo, e a lógica de saída calcula a saída. Na borda seguinte, o registrador copia o próximo estado para dentro de si, e o ciclo recomeça. Por isso o caminho crítico vai do registrador, passa pela lógica de próximo estado e volta ao registrador, com o setup e o clock para Q das aulas Circuitos sequenciais e Clock e sincronização somados ao caminho de lógica.

A figura 02 é o desenho que resume a seção. A entrada x chega à lógica de próximo estado, que recebe também o estado atual do registrador e entrega o próximo estado de volta ao registrador. O registrador alimenta a lógica de saída, que produz z. O clock aparece entrando no registrador, e a linha pontilhada marca que ele só copia na borda. Um detalhe de leitura: a caixa da lógica de próximo estado tem uma linha de clock passando por baixo dela, por limitação do traçado automático, e essa linha só leva o sinal de clock até o registrador.

Repare que a lógica de saída lê o estado e não o próximo estado. Essa escolha é que define o tipo da máquina, Moore ou Mealy, e é o assunto da seção seguinte.

4.2 Moore e Mealy

Existem duas formas clássicas de ligar a lógica de saída, e elas recebem o nome dos autores que as descreveram. Na máquina de Moore, a saída depende só do estado atual. Na máquina de Mealy, a saída depende do estado atual e da entrada do momento. George H. Mealy publicou o método de síntese com essa forma em 1955, no Bell System Technical Journal, e Edward F. Moore publicou a sua em 1956, no volume Automata Studies. Os dois nomes e as datas foram conferidos em registros bibliográficos, mas nenhum dos dois artigos foi lido integralmente para esta aula.

A diferença prática é o atraso de uma saída. Numa máquina de Mealy, a saída pode mudar logo que a entrada muda, antes da próxima borda, e por isso ela aparece no mesmo ciclo em que o bit chega. Numa máquina de Moore, a saída só muda quando o estado muda, e o estado só muda na borda. Logo, a saída de Moore aparece um ciclo depois da de Mealy para o mesmo evento. A figura 04 mostra isso com uma entrada real, e o programa da seção 7 confirma os valores.

Vale uma analogia, com limite declarado. Pense em um cronômetro de cozinha, que toca quando o tempo acaba, e num garçom que avisa enquanto você ainda está mastigando. O cronômetro é Moore: ele toca depois que o estado mudou. O garçom é Mealy: ele reage ao que você fez no mesmo instante. A analogia falha porque o garçom pode errar a hora, e o circuito não erra, já que a saída é só uma função lógica das entradas e do estado.

Para comparar as duas, o exemplo que usamos daqui em diante é o detector da sequência 101 com sobreposição. A máquina recebe um bit por ciclo e deve sinalizar toda vez que os últimos três bits recebidos forem 1, 0, 1. Com sobreposição, a sequência 10101 conta duas vezes: a primeira vez nos bits 1 a 3 e a segunda nos bits 3 a 5, porque o 1 do meio é compartilhado. Sem sobreposição, a máquina precisaria esquecer o que viu depois de cada detecção, e essa é uma escolha de projeto que muda a tabela.

A figura 03 coloca as duas máquinas lado a lado. A versão de Moore tem quatro estados, porque precisa de um estado próprio, o S3, para representar “acabei de ver 101”, já que a saída precisa estar ligada ao estado. A versão de Mealy tem três, porque a saída pode depender da transição que chega ao estado S2 com a entrada 1.

Leia a figura de cima para baixo, começando pela versão de Moore. S0 é o estado sem prefixo útil, S1 significa que o último bit foi 1, S2 que os dois últimos foram 1 e 0, e S3 que os três últimos foram 1, 0, 1. Como a saída é z = 1 só em S3, a máquina mostra a detecção assim que entra nesse estado. A versão de Mealy, embaixo, tem a saída escrita em cada transição, depois da barra. O único lugar em que z vale 1 é a transição de S2 com entrada 1, ou seja, a transição que completa 101. A legenda da figura não mostra as transições que voltam ao próprio estado, porque o ArchFlow não as desenha, e elas estão na tabela da seção 4.3.

A figura 04 mostra o efeito do atraso com a entrada de teste 101101010, que é a mesma usada no programa. A linha de cima é o clock, e cada subida é o começo de um ciclo. A linha de x traz os bits que chegam. A linha azul, z Mealy, sobe no ciclo 3, quando o terceiro bit chega, e volta a zero no ciclo 4. A linha rosa, z Moore, sobe no ciclo 4, um ciclo depois. Ela também desce depois da azul. Os tempos de 0,1 e 0,6 unidades depois da borda são valores de exemplo para deixar a diferença visível, e a forma dos degraus segue a convenção do gráfico, não uma medida de circuito.

Depois da entrada, as duas curvas continuam para os ciclos 9 e 10, e o gráfico só mostra as duas detecções da entrada, a do ciclo 3 e a do ciclo 6. A linha rosa repete as mesmas detecções, mas um ciclo depois, porque é isso que o atraso de Moore significa. O valor é o mesmo, e a diferença está só no ciclo em que ele aparece.

Qual das duas usar? Mealy responde mais cedo e usa menos estados, mas a saída depende da entrada, e uma entrada que vem de fora de forma assíncrona pode fazer a saída oscilar antes da borda. Moore é mais previsível, porque a saída muda só na borda, e isso costuma facilitar a depuração e a análise de tempo. A escolha é de engenharia, e nenhuma das duas é mais correta.

4.3 Do enunciado à tabela de estados

O projeto de uma máquina segue sempre a mesma ordem. Primeiro escreve-se o enunciado de forma precisa, depois o diagrama de estados, depois a tabela de estados, depois a codificação, e só então as equações e o circuito. Pular etapas é o caminho mais curto para um circuito que funciona em quase todos os casos e falha no caso que ninguém testou.

O enunciado do detector é: a cada bit recebido, a saída z vale 1 se e só se os três últimos bits recebidos são 1, 0, 1, com sobreposição. A partir dele, a pergunta que guia o diagrama é: o que a máquina precisa lembrar do passado para responder certo no próximo bit? A resposta são os prefixos da sequência 101 que ainda podem virar a sequência completa. Esses prefixos são “vazio”, “1”, “10” e “101”. O prefixo “101” é o que completa a sequência, e por isso ele ganha um estado próprio em Moore.

Com os quatro prefixos, a tabela de estados se escreve com calma. Para cada estado e cada entrada, pergunta-se qual é o maior prefixo que ainda faz sentido depois do novo bit. Se o estado é “10” e chega 1, a sequência virou “101”, e o estado é S3. Se o estado é “10” e chega 0, a sequência virou “100”, e nenhum prefixo útil termina ali, porque o último 0 não serve para começar 101, então o estado volta a S0. Se o estado é “101” e chega 0, a sequência virou “1010”, e o sufixo “10” ainda é prefixo, então o estado é S2. Esse último caso é a sobreposição: o 1 de “101” continua valendo para formar “10”.

A tabela de estados da versão de Moore fica assim, com a entrada x e o estado atual:

Na versão de Mealy, a tabela tem a saída dentro da célula da transição, e os estados são os mesmos três de antes, com o S3 fundido ao S2. A tabela fica assim, com o formato próximo estado / saída:

Note que as duas tabelas dizem a mesma coisa sobre a sequência de entrada. Na de Moore, a saída z = 1 aparece no estado S3. Na de Mealy, aparece na transição que sai de S2 com x = 1. O programa da seção 7 verifica isso por força bruta, em todas as entradas de 1 a 16 bits.

4.4 Codificação: binária, one-hot e Gray

Uma máquina com quatro estados precisa de flip-flops para guardá-los, e a regra de como nomear os estados com bits se chama codificação. A escolha parece cosmética, mas muda o tamanho do registrador, a quantidade de portas e o comportamento em caso de falha.

A codificação binária é a mais econômica em flip-flops. Com dois bits, cabem quatro estados: S0 = 00, S1 = 01, S2 = 10 e S3 = 11. Ela usa o menor número possível de flip-flops, porque o número de bits é o logaritmo na base 2 do número de estados arredondado para cima. O custo aparece na lógica, porque cada bit de estado mistura informação de vários estados, e as equações ficam mais difíceis de ler.

A codificação one-hot usa um flip-flop por estado, e exatamente um deles fica em 1 em cada momento. Com quatro estados, são quatro flip-flops: S0 = 1000, S1 = 0100, S2 = 0010 e S3 = 0001. Ela gasta mais flip-flops, mas cada equação fica simples. A equação de um estado depende só dos estados que chegam até ele, e não é preciso decodificar nada para saber em que estado a máquina está, porque basta olhar um bit. O custo é o número de flip-flops, que cresce com o número de estados.

A codificação Gray organiza os estados de forma que, entre dois estados vizinhos, muda só um bit. Com dois bits, a sequência é 00, 01, 11, 10. Ela não reduz o número de flip-flops, que continua sendo dois, mas reduz o número de bits que mudam em cada transição. Isso importa quando a máquina precisa de transições suaves, porque menos bits mudando ao mesmo tempo deixam menos chance de um valor intermediário errado aparecer. A figura 05 mostra os três códigos dos quatro estados do detector.

A figura 05 tem três grupos, um por codificação. Em cada um, as quatro caixas são os estados, com o código de bits no título e a descrição do significado embaixo. A diferença visual é o número de caixas com bits e a forma dos códigos: binário e Gray usam dois bits, e one-hot usa quatro com apenas um aceso. Os códigos de Gray e binário são diferentes só na ordem em que os estados S2 e S3 aparecem, o que muda as equações.

4.5 Equações de próximo estado e de saída

Com a codificação escolhida, cada bit do próximo estado e a saída viram funções lógicas dos bits atuais e da entrada. Esse é o passo em que a máquina deixa de ser desenho e vira circuito. Vamos resolver a codificação binária à mão, com Karnaugh, e depois mostrar as outras duas.

Na codificação binária, o estado é o par (q1, q0), e a entrada é x. A tabela de estados vira uma tabela de oito linhas, uma para cada combinação de q1, q0 e x. Para cada linha, escreve-se o próximo estado. O bit q0’ (o próximo valor de q0) vale 1 quando o próximo estado é 01 ou 11, e isso acontece exatamente quando a entrada é 1. Olhe a tabela: quando x = 1, o próximo estado é S1 (01) ou S3 (11), e as duas têm q0’ = 1. Quando x = 0, o próximo estado é S0 (00) ou S2 (10), e as duas têm q0’ = 0. Logo, q0’ = x. Esse resultado tem uma leitura bonita: o bit de menor peso do estado é o último bit recebido.

O bit q1’ vale 1 quando o próximo estado é 10 ou 11, ou seja, quando a sequência acabou de ganhar um 0 depois de um 1 (indo para S2), ou um 1 depois de “10” (indo para S3). Na tabela, isso dá três linhas com q1’ = 1: (q1, q0, x) = (0, 1, 0), que é S1 com x = 0; (1, 0, 1), que é S2 com x = 1; e (1, 1, 0), que é S3 com x = 0. Para minimizar, desenha-se o mapa de Karnaugh com as linhas em Gray (00, 01, 11, 10) e as colunas em x:

As duas células com 1 na coluna x = 0 estão nas linhas 01 e 11, e ficam juntas porque q0 vale 1 nas duas. Isso forma o termo q0 x̄. A célula com 1 na linha 10 e coluna x = 1 não se junta com nenhuma outra, e dá o termo q1 q̄0 x. Logo:

q1’ = q0 x̄ + q1 q̄0 x

A saída de Moore é z = q1 q0, porque S3 é o único estado com os dois bits em 1. Com isso, o projeto da versão de Moore com codificação binária fica completo: q0’ = x, q1’ = q0 x̄ + q1 q̄0 x e z = q1 q0.

Para a versão de Mealy, a tabela tem só os estados S0, S1 e S2, com códigos 00, 01 e 10. O código 11 não aparece em lugar nenhum, e a seção 4.6 trata dele. As equações saem da mesma forma. A saída z vale 1 só na transição de S2 com x = 1, o que dá z = q1 q̄0 x. O próximo estado do bit de menor peso é de novo x, porque chegar em S1 (01) acontece com qualquer entrada 1. O bit de maior peso vale 1 só para ir de S1 com x = 0 até S2, e isso dá q1’ = q0 x̄. Logo, a versão de Mealy com codificação binária tem q1’ = q0 x̄, q0’ = x e z = q1 q̄0 x. Ela usa as mesmas duas flip-flops de Moore, mas com equações mais curtas, porque tem um estado a menos.

Na codificação one-hot da versão de Moore, cada estado tem seu bit, e cada próximo estado é uma soma das transições que chegam nele. S0 é alcançado de S0 e S2 com x = 0. S1 é alcançado de S0, S1 e S3 com x = 1. S2 é alcançado de S1 e S3 com x = 0. S3 é alcançado só de S2 com x = 1. Então:

S0’ = x̄ (S0 + S2) S1’ = x (S0 + S1 + S3) S2’ = x̄ (S1 + S3) S3’ = x S2 z = S3

Na codificação de Gray, a versão de Moore com S0 = 00, S1 = 01, S2 = 11 e S3 = 10 fica com estas equações, obtidas pela mesma tabela:

q1’ = q̄1 q0 x̄ + q1 q̄0 x̄ + q1 q0 x q0’ = q̄1 (q0 + x) + q1 q̄0 z = q1 q̄0

Essas equações foram conferidas pelo programa da seção 7, que checa, para cada estado e cada entrada, se o próximo estado e a saída das equações batem com a tabela. Nenhuma das seis conferências de equações apresentou falha. Repare que as equações de Gray são mais longas que as binárias, e esse é o preço de transições com menos bits mudando.

4.6 Estados inalcançáveis

Com dois bits, há quatro códigos possíveis, e a versão de Mealy usa só três deles. O código 11 é inalcançável, no sentido de que nenhuma sequência de entradas a partir do reset leva a ele. O programa da seção 7 confirma isso por busca em largura: partindo de 00, os códigos alcançáveis são 00, 01 e 10.

Um código que ninguém alcança parece inofensivo, mas ele aparece em dois momentos. O primeiro é no projeto, porque a tabela não diz o que fazer com 11, e o projetista tem de escolher. O segundo é na prática, porque uma radiação, um ruído ou um defeito de fabricação pode colocar o circuito em 11 mesmo assim. Por isso a escolha importa.

Há duas políticas. Na primeira, trata-se 11 como “não importa” (don’t care) e deixa-se a equação simplificar como quiser. Essa é a política da versão de Mealy desta aula: as equações q1’ = q0 x̄ e q0’ = x não dizem nada sobre 11, e o programa mostra que a máquina sai de 11 sozinha, indo para 10 com x = 0 e para 01 com x = 1. Ou seja, mesmo se o circuito cair em 11, ele volta aos estados válidos no ciclo seguinte. Essa propriedade não foi garantida por projeto, e sim verificada para essas equações específicas.

A segunda política força o código inalcançável para um estado seguro, como o reset. É a escolha certa quando a máquina controla algo perigoso. O semáforo com dois flip-flops, na figura 09, faz isso: os códigos são V = 00, A = 01 e R = 10, e o código 11 é forçado para o verde. As equações forçadas ficam q1’ = q̄1 q0 t + q1 q̄0 t̄ e q0’ = q̄1 (q0 ⊕ t), e o programa confere que, com 11 como entrada, ambas dão 00, que é V.

A figura 09 mostra o código 11 numa caixa com borda tracejada, sem nenhuma seta chegando a ele, e uma seta pontilhada saindo para o verde. A ausência de seta chegando é exatamente o que o ArchFlow avisa como “nada leva a este estado”, e é esse aviso que queremos ver: é um sinal de que o estado é inalcançável por projeto. Os laços de t = 0 foram omitidos, porque o diagrama não os desenha. O rótulo “forçado para verde” descreve a política, e não uma transição que chegue de fora. Para o semáforo, o custo da política é pouco: um pouco de lógica a mais para tratar um caso que não acontece.

4.7 Reset

Todo flip-flop de uma máquina começa com um valor que o projeto não controla, a não ser que haja um reset. O reset é um sinal que força o registrador ao estado inicial, e ele é o que garante que a máquina começa do mesmo lugar sempre. Sem reset, a primeira sequência de entradas depende do estado em que o circuito acordou, e isso torna o comportamento difícil de reproduzir.

O reset não aparece nas equações desta aula, porque ele é um caso à parte: ele força o próximo estado para o estado inicial, independentemente da entrada. Na prática, cada bit de estado ganha uma porta a mais, que zera o bit quando o reset está ativo. Em Moore com codificação binária, isso significa que q1’ e q0’ passam a valer 0 enquanto reset estiver em 1. Essa mudança não altera a tabela, e por isso não foi escrita nas equações.

A decisão de projeto é se o reset é síncrono, que atua só na borda, ou assíncrono, que atua a qualquer momento. O reset síncrono é mais seguro para a análise de tempo, porque o sinal passa pela mesma lógica de qualquer outra entrada, e o reset assíncrono zera o estado na hora. Qual usar depende do projeto, e nenhuma das duas formas foi medida nesta aula.

4.8 Passo a passo com a entrada de teste

Para fechar o projeto, vamos seguir a entrada de teste 101101010 pelas equações da versão binária de Moore. O estado começa em S0, que é 00. Em cada passo, calcula-se q1’, q0’ e z com as equações, e o novo estado vira o atual.

No passo 1, x = 1 e o estado é 00. q1’ = q0 x̄ + q1 q̄0 x = 0·0 + 0·1·1 = 0. q0’ = x = 1. Logo o próximo estado é 01 (S1), e z = q1 q0 = 0.

No passo 2, x = 0 e o estado é 01. q1’ = q0 x̄ + q1 q̄0 x = 1·1 + 0 = 1. q0’ = 0. Próximo estado: 10 (S2), e z = 0.

No passo 3, x = 1 e o estado é 10. q1’ = q0 x̄ + q1 q̄0 x = 0 + 1·1·1 = 1. q0’ = 1. Próximo estado: 11 (S3), e z = q1 q0 = 1·0 = 0 ainda, porque z é calculado com o estado atual, que é 10.

Essa última linha merece atenção, porque ela tem o atraso de Moore. A detecção acontece quando o registrador chega a 11, que é depois da borda do passo 3. A saída z = 1 aparece, portanto, durante o ciclo seguinte, no passo 4. Esse é exatamente o atraso mostrado na figura 04.

No passo 4, x = 1 e o estado é 11. q1’ = q0 x̄ + q1 q̄0 x = 1·0 + 1·0·1 = 0. q0’ = 1. Próximo estado: 01 (S1), e z = 1·1 = 1, que é a detecção do bit 3 aparecendo no ciclo seguinte.

Os demais passos seguem o mesmo método, e o programa da seção 7 imprime a sequência completa: S0, S1, S2, S3, S1, S2, S3, S2, S3, S2, com as saídas de Moore nos ciclos seguintes à detecção. Fazer isso à mão uma vez é o melhor jeito de ganhar confiança na tabela, e as equações já estão conferidas pelo programa.

4.9 Circuito do detector

Com as equações prontas, o circuito sai quase sozinho. A figura 06 mostra a versão binária de Moore com dois flip-flops, e ela é feita de seis portas e dois flip-flops, mais as ligações. A entrada x sai de uma caixa de entrada com três saídas, porque x vai a três lugares: ao inversor, à porta de três entradas e ao flip-flop de menor peso.

A figura 06 é um instantâneo, e não uma animação do circuito. Ela mostra o momento em que a máquina está no estado S2, que é 10 (q1 = 1 e q0 = 0), e a entrada x vale 1. Cada fio traz o nível que tem nesse instante, escrito no rótulo, e é fácil conferir a conta: x̄ = 0 e q̄0 = 1. A porta E3 recebe q1 = 1, q̄0 = 1 e x = 1, e sai 1. A porta E de q0 e x̄ recebe 0 e 0, e sai 0. A porta OU entrega 1 para D1, então q1’ = 1. D0 recebe x = 1, então q0’ = 1. O próximo estado é 11, que é S3, e a saída z = q1 q0 = 1·0 = 0, porque z ainda é calculado com o estado atual. Na borda seguinte, o registrador vai para 11, e z passa a valer 1 no ciclo seguinte, como na seção 4.8.

As marcas de fan-out, que são as bolinhas onde um fio se divide, aparecem como avisos no checador do ArchFlow, porque uma saída de flip-flop alimenta mais de uma porta. Num circuito real, isso é normal, e a figura não quebra por causa disso. Os dois flip-flops ficam no lado direito, com as saídas q voltando para a esquerda, e por isso alguns fios atravessam o diagrama. Nenhum fio passa por dentro de uma caixa.

4.10 One-hot contra binário

A escolha entre binário e one-hot se resume a um troca: menos flip-flops contra equações mais simples. Para o semáforo, que tem três estados, a comparação fica nítida. Em binário, são dois flip-flops, com q1’ = q̄1 q0 t + q1 q̄0 t̄ e q0’ = q̄1 (q0 ⊕ t). Em one-hot, são três flip-flops, com V’ = t̄ V + t R, A’ = t V + t̄ A e R’ = t A + t̄ R. A figura 10 mostra as duas codificações lado a lado.

Leia as caixas de cima, em binário: três estados com códigos de dois bits, e uma caixa com as equações. A caixa de baixo, em one-hot, tem três estados com um bit aceso cada, e as equações mais curtas. O número de flip-flops cresce com o número de estados, no one-hot, e a conta de portas segue o caminho contrário, porque cada equação one-hot depende de poucos bits. Não há uma regra universal, e o projeto de cada caso decide.

Repare que a versão one-hot tem um número grande de códigos não usados. Com três flip-flops há oito códigos, e só três são válidos. Com quatro, como no detector, são dezesseis, e só quatro são válidos. Os códigos não usados são inalcançáveis, e a seção 4.6 mostra as duas políticas para tratá-los. Em one-hot, a política mais comum é verificar que a máquina tem exatamente um bit aceso, e levar a um estado de erro quando não tem.

4.11 Projeto em cinco perguntas

Para resumir o método, vale uma lista curta de perguntas que o projetista repete ao começar qualquer máquina. Ela não substitui a explicação acima, mas ajuda a não esquecer etapas.

Qual é a sequência de entradas que a máquina precisa reconhecer ou controlar, e o que deve acontecer em cada caso? Quais prefixos ou situações precisam de estado próprio para responder certo no futuro? A saída depende só do estado (Moore) ou também da entrada (Mealy)? Quantos bits de estado a codificação escolhida exige, e o que fazer com os códigos que sobram? As equações de próximo estado e de saída batem com a tabela em todos os casos, incluindo os inalcançáveis?

4.12 A unidade de controle da CPU

A unidade de controle de uma CPU simples é, em essência, uma máquina de estados. Para cada instrução, ela repete um ciclo de etapas: busca a instrução apontada pelo contador de programa, decodifica os campos da instrução e executa a operação, e então escreve o resultado e atualiza o contador. A aula Como a CPU executa instruções descreveu esse ciclo em visão geral, e aqui ele aparece como estados e transições, com o clock avançando de uma etapa para a seguinte.

A figura 07 mostra a versão didática, com quatro estados e um estado final que a instrução HALT alcança. Cada seta é uma transição guiada pelo clock. A figura não mostra os estados extras que uma instrução de acesso à memória exige, nem o fato de que uma instrução pode levar vários ciclos em cada etapa.

O desenho é um recorte simplificado. Num processador real, cada estado da unidade de controle liga um conjunto de sinais, e a lista desses sinais por estado é a microprogramação, uma tabela de palavras de controle guardada numa memória interna. Cada palavra diz quais registradores são lidos, qual operação a ULA executa e para onde vai o resultado. Esse é o sentido do microcódigo citado na aula Como a CPU executa instruções. Os detalhes desses sinais, dos registradores, da ULA e do ciclo de instrução completo ficam para a fase 3 da Trilha de Hardware, e não são tratados aqui.

Essa ponte tem um limite. A figura mostra a etapa do ciclo, mas o próximo estado de uma CPU real também depende da instrução decodificada. Um salto condicional, por exemplo, pode ir a dois lugares diferentes conforme a flag de resultado. Quando a fase 3 começar, a ULA, os registradores e o contador de programa vão entrar nesse desenho como os blocos de dados que a máquina controla. A máquina desta aula é o esqueleto desse ciclo, e a fase 3 coloca a carne em cima dele.

5. Detalhes e bordas

O primeiro detalhe é o limite do número de estados. Com n flip-flops, uma máquina tem no máximo 2^n estados em binário, e um contador de 0 a 999 precisa de 1000 estados, ou seja, dez bits em binário. Uma máquina que conta até 999 não é uma máquina de estados desenhada à mão, e tenta-se resolver a contagem com um contador de dez bits, e não com 1000 caixas no diagrama. Quando há vários contadores ou memória, o número de estados explode e o diagrama vira ilegível. A regra prática é separar: o contador cuida da contagem, e a máquina cuida das decisões.

O segundo detalhe é a memória. Um controle que precisa lembrar de uma quantidade grande de dados não cabe numa máquina de estados, porque cada dado diferente seria um estado. Nesse caso, a máquina controla o fluxo, e os dados ficam num registrador ou numa memória, como acontece na CPU. A seção 4.12 mostra isso com a unidade de controle.

O terceiro detalhe é o caminho crítico. A máquina de estados tem um caminho que vai do registrador, passa pela lógica de próximo estado e volta ao registrador. O período mínimo do clock é esse caminho mais o clock para Q e o setup, como na aula Clock e sincronização. Uma máquina com muitos estados tem lógica de próximo estado mais profunda, e o caminho cresce.

O quarto detalhe é a saída de Mealy com entrada assíncrona. Se a entrada vem de um botão ou de outro domínio de clock, a saída de Mealy depende de uma entrada que pode mudar no meio do ciclo, e por isso pode oscilar. A aula Clock e sincronização mostrou o sincronizador de dois estágios para entradas assim. Antes de usar a saída de Mealy em algo sensível, convém passar a entrada por um sincronizador.

O quinto detalhe é a comparação com as alternativas. Uma máquina de estados é a forma natural de projetar controle, mas não é a única. Um microcontrolador pode fazer o mesmo com software, e um circuito combinacional com contadores também pode servir. O critério é a clareza: quando a lógica depende de uma sequência de passos com poucos estados, a máquina é a forma mais legível de descrevê-la.

6. Erros comuns e boas práticas

O erro mais frequente é esquecer o estado inicial e o reset. Quem monta a tabela começando do estado S0 imagina que a máquina sempre começa em S0, e descobre no laboratório que ela começa em qualquer código, porque os flip-flops acordam com valores indefinidos. Todo mundo esquece o reset uma vez, e quem diz que nunca esqueceu ainda não viu um circuito ligar com a saída presa. A boa prática é desenhar o estado inicial no diagrama e garantir, nas equações ou no hardware, que o reset o força.

O segundo erro é confundir o atraso de Moore com um defeito. Quando a saída de Moore aparece um ciclo depois da de Mealy, quem olha a forma de onda pensa que a máquina está atrasada. Ela está fazendo exatamente o que o projeto de Moore define. A boa prática é escolher o tipo de máquina sabendo que ela custa um ciclo de latência, e documentar essa escolha no diagrama.

O terceiro erro é deixar estados sem transição. Um estado sem saída para uma das entradas faz a máquina travar, porque não há próximo estado definido. O ArchFlow avisa quando um estado não tem entrada, e é bom tratar o aviso como erro de projeto. A boa prática é preencher toda a tabela, com as duas entradas em cada estado, mesmo que a resposta seja “fica onde está”.

O quarto erro é ignorar a sobreposição. Um detector de 101 sem sobreposição não detecta a sequência 10101 duas vezes, e quem testa só com a sequência isolada não percebe a diferença. A boa prática é escrever, no enunciado, o que acontece com sobreposição, e testar com uma entrada que tenha sobreposição de propósito. A entrada 101101010 da seção 7 serve para isso.

O quinto erro é desenhar a tabela sem decidir a codificação, e depois descobrir que a lógica ficou feia. A boa prática é escolher a codificação antes de escrever as equações, e quando a lógica ficar difícil de ler, testar outra codificação. Um projeto com one-hot pode ser mais simples do que parece à primeira vista.

O sexto erro é achar que a máquina cabe em qualquer tarefa com contagem. Um contador de mil ciclos em forma de máquina tem mil caixas, e o diagrama vira um emaranhado. A boa prática é usar um contador para a contagem e a máquina apenas para as decisões, como na seção 5.

7. O programa que simula

O programa abaixo implementa o detector de 101 nas duas versões, Moore e Mealy, a partir das tabelas de estados. Ele roda uma entrada de teste, imprime a sequência de estados e as saídas, e depois faz uma verificação por força bruta: testa todas as entradas de 1 a 16 bits, que somam 131070 entradas, e confere se as duas versões dão a mesma sequência de detecções, e se essa sequência bate com um gabarito calculado direto na string. A parte 3 confere as equações de cada codificação contra a tabela de estados, e a parte 4 faz a busca de estados alcançáveis e mostra o que acontece com o código 11. O semáforo entra como segundo exemplo, com suas equações binárias e one-hot.

O programa foi executado com Python 3.12.8, no modo isolado, com o comando python3 -I detector101.py. A saída abaixo é a real, copiada do terminal sem edição.

# Detector da sequência 101 com sobreposição: máquina de Moore contra máquina de Mealy.
# As partes 3 e 4 conferem as equações de cada codificação contra a tabela de estados.
from itertools import product

# Moore: a saída depende só do estado atual.
MOORE_PROX = {
    ("S0", 0): "S0", ("S0", 1): "S1",
    ("S1", 0): "S2", ("S1", 1): "S1",
    ("S2", 0): "S0", ("S2", 1): "S3",
    ("S3", 0): "S2", ("S3", 1): "S1",
}
MOORE_SAIDA = {"S0": 0, "S1": 0, "S2": 0, "S3": 1}

# Mealy: a saída depende do estado atual e da entrada.
MEALY_PROX = {
    ("S0", 0): ("S0", 0), ("S0", 1): ("S1", 0),
    ("S1", 0): ("S2", 0), ("S1", 1): ("S1", 0),
    ("S2", 0): ("S0", 0), ("S2", 1): ("S1", 1),
}

# Semáforo: a entrada t vale 1 quando o temporizador esgota.
SEM_PROX = {
    ("V", 0): "V", ("V", 1): "A",
    ("A", 0): "A", ("A", 1): "R",
    ("R", 0): "R", ("R", 1): "V",
}


def simula_moore(bits):
    estado = "S0"
    estados = [estado]
    saidas = []
    for x in bits:
        estado = MOORE_PROX[(estado, x)]
        estados.append(estado)
        saidas.append(MOORE_SAIDA[estado])
    return estados, saidas


def simula_mealy(bits):
    estado = "S0"
    estados = [estado]
    saidas = []
    for x in bits:
        estado, saida = MEALY_PROX[(estado, x)]
        estados.append(estado)
        saidas.append(saida)
    return estados, saidas


def referencia(bits):
    # Gabarito direto na string: 1 quando os três últimos bits lidos são 1, 0, 1.
    saidas = []
    for k in range(1, len(bits) + 1):
        ultimos = tuple(bits[max(0, k - 3):k])
        saidas.append(1 if ultimos == (1, 0, 1) else 0)
    return saidas


TESTE = (1, 0, 1, 1, 0, 1, 0, 1, 0)

print("== 1. entrada de teste: 101101010 ==")
est_m, sai_m = simula_moore(TESTE)
est_l, sai_l = simula_mealy(TESTE)
print("k  x | Moore: estado apos  saida | Mealy: estado antes  saida  estado apos")
for k, x in enumerate(TESTE, start=1):
    print("%d  %d | %-16s %5d | %-19s %5d  %s" % (
        k, x, est_m[k], sai_m[k - 1], est_l[k - 1], sai_l[k - 1], est_l[k]))
print("estados Moore:", " -> ".join(est_m))
print("estados Mealy:", " -> ".join(est_l))
print("ciclo:  ", " ".join("%2d" % c for c in range(1, len(TESTE) + 2)))
print("entrada:", " ".join("%2d" % x for x in TESTE), "  -")
print("Mealy:  ", " ".join("%2d" % v for v in sai_l), " -")
print("Moore:  ", " ".join("%2d" % v for v in [0] + sai_m))

print("== 2. força bruta: todas as entradas de 1 a 16 bits ==")
total = 0
deteccoes = 0
divergencias = 0
for n in range(1, 17):
    for bits in product((0, 1), repeat=n):
        total += 1
        _, sm = simula_moore(bits)
        _, sl = simula_mealy(bits)
        ref = referencia(bits)
        deteccoes += sum(sl)
        if sm != sl or sl != ref:
            divergencias += 1
print("entradas testadas:", total)
print("deteccoes (Mealy, somadas):", deteccoes)
print("Moore e Mealy com a mesma sequencia de deteccoes e referencia:", divergencias == 0)
print("entradas com divergencia:", divergencias)


def decodifica(codigos):
    return {bits: nome for nome, bits in codigos.items()}


def verifica(rotulo, codigos, equacoes, esperado):
    # Confere cada estado com cada entrada: próximo estado e saída das equações contra a tabela.
    decode = decodifica(codigos)
    falhas = 0
    for nome, bits in codigos.items():
        for x in (0, 1):
            prox_bits, z = equacoes(bits, x)
            prox_nome, z_esperado = esperado(nome, x)
            if decode.get(tuple(prox_bits)) != prox_nome or z != z_esperado:
                falhas += 1
    print("%-34s falhas: %d de %d combinacoes" % (rotulo, falhas, len(codigos) * 2))


def esperado_moore(nome, x):
    return MOORE_PROX[(nome, x)], MOORE_SAIDA[nome]


def esperado_mealy(nome, x):
    return MEALY_PROX[(nome, x)]


def esperado_sem(nome, t):
    return SEM_PROX[(nome, t)], 0


# Equações: cada função recebe os bits do estado atual e a entrada, e devolve (bits do próximo, saída).
def eq_moore_bin(b, x):
    q1, q0 = b
    return ((q0 & (1 - x)) | (q1 & (1 - q0) & x), x), q1 & q0


def eq_moore_onehot(b, x):
    s0, s1, s2, s3 = b
    nx = 1 - x
    return ((nx & (s0 | s2), x & (s0 | s1 | s3), nx & (s1 | s3), x & s2), s3)


def eq_moore_gray(b, x):
    q1, q0 = b
    n1, n0, nx = 1 - q1, 1 - q0, 1 - x
    prox1 = (n1 & q0 & nx) | (q1 & n0 & nx) | (q1 & q0 & x)
    prox0 = (n1 & (q0 | x)) | (q1 & n0)
    return (prox1, prox0), q1 & n0


def eq_mealy_bin(b, x):
    q1, q0 = b
    return (q0 & (1 - x), x), q1 & (1 - q0) & x


def eq_sem_bin(b, t):
    q1, q0 = b
    nq1, nt = 1 - q1, 1 - t
    return ((nq1 & q0 & t) | (q1 & (1 - q0) & nt), nq1 & (q0 ^ t)), 0


def eq_sem_onehot(b, t):
    v, a, r = b
    nt = 1 - t
    return ((nt & v) | (t & r), (t & v) | (nt & a), (t & a) | (nt & r)), 0


print("== 3. equações de próximo estado e de saída, contra a tabela ==")
BIN_MOORE = {"S0": (0, 0), "S1": (0, 1), "S2": (1, 0), "S3": (1, 1)}
ONEHOT_MOORE = {"S0": (1, 0, 0, 0), "S1": (0, 1, 0, 0), "S2": (0, 0, 1, 0), "S3": (0, 0, 0, 1)}
GRAY_MOORE = {"S0": (0, 0), "S1": (0, 1), "S2": (1, 1), "S3": (1, 0)}
BIN_MEALY = {"S0": (0, 0), "S1": (0, 1), "S2": (1, 0)}
BIN_SEM = {"V": (0, 0), "A": (0, 1), "R": (1, 0)}
ONEHOT_SEM = {"V": (1, 0, 0), "A": (0, 1, 0), "R": (0, 0, 1)}

verifica("Moore, binario (2 FF)", BIN_MOORE, eq_moore_bin, esperado_moore)
verifica("Moore, one-hot (4 FF)", ONEHOT_MOORE, eq_moore_onehot, esperado_moore)
verifica("Moore, Gray (2 FF)", GRAY_MOORE, eq_moore_gray, esperado_moore)
verifica("Mealy, binario (2 FF)", BIN_MEALY, eq_mealy_bin, esperado_mealy)
verifica("Semaforo, binario (2 FF)", BIN_SEM, eq_sem_bin, esperado_sem)
verifica("Semaforo, one-hot (3 FF)", ONEHOT_SEM, eq_sem_onehot, esperado_sem)

print("== 4. estados inalcançáveis ==")
alcancaveis = {(0, 0)}
fila = [(0, 0)]
while fila:
    b = fila.pop()
    for x in (0, 1):
        prox, _ = eq_mealy_bin(b, x)
        prox = tuple(prox)
        if prox not in alcancaveis:
            alcancaveis.add(prox)
            fila.append(prox)
print("codigos alcancaveis no Mealy binario:", sorted(alcancaveis))
print("codigo 11 com x=0 e x=1 vai para:", [eq_mealy_bin((1, 1), x)[0] for x in (0, 1)])
print("semaforo: codigo 11 com t=0 e t=1 vai para:",
      [eq_sem_bin((1, 1), t)[0] for t in (0, 1)], "(V = 00)")

Saída real do programa, com Python 3.12.8:

== 1. entrada de teste: 101101010 ==
k  x | Moore: estado apos  saida | Mealy: estado antes  saida  estado apos
1  1 | S1                   0 | S0                      0  S1
2  0 | S2                   0 | S1                      0  S2
3  1 | S3                   1 | S2                      1  S1
4  1 | S1                   0 | S1                      0  S1
5  0 | S2                   0 | S1                      0  S2
6  1 | S3                   1 | S2                      1  S1
7  0 | S2                   0 | S1                      0  S2
8  1 | S3                   1 | S2                      1  S1
9  0 | S2                   0 | S1                      0  S2
estados Moore: S0 -> S1 -> S2 -> S3 -> S1 -> S2 -> S3 -> S2 -> S3 -> S2
estados Mealy: S0 -> S1 -> S2 -> S1 -> S1 -> S2 -> S1 -> S2 -> S1 -> S2
ciclo:    1  2  3  4  5  6  7  8  9 10
entrada:  1  0  1  1  0  1  0  1  0   -
Mealy:    0  0  1  0  0  1  0  1  0  -
Moore:    0  0  0  1  0  0  1  0  1  0
== 2. força bruta: todas as entradas de 1 a 16 bits ==
entradas testadas: 131070
deteccoes (Mealy, somadas): 212993
Moore e Mealy com a mesma sequencia de deteccoes e referencia: True
entradas com divergencia: 0
== 3. equações de próximo estado e de saída, contra a tabela ==
Moore, binario (2 FF)              falhas: 0 de 8 combinacoes
Moore, one-hot (4 FF)              falhas: 0 de 8 combinacoes
Moore, Gray (2 FF)                 falhas: 0 de 8 combinacoes
Mealy, binario (2 FF)              falhas: 0 de 6 combinacoes
Semaforo, binario (2 FF)           falhas: 0 de 6 combinacoes
Semaforo, one-hot (3 FF)           falhas: 0 de 6 combinacoes
== 4. estados inalcançáveis ==
codigos alcancaveis no Mealy binario: [(0, 0), (0, 1), (1, 0)]
codigo 11 com x=0 e x=1 vai para: [(1, 0), (0, 1)]
semaforo: codigo 11 com t=0 e t=1 vai para: [(0, 0), (0, 0)] (V = 00)

Leia a saída de cima para baixo. A tabela da parte 1 mostra o que vimos à mão: a saída de Mealy vale 1 no ciclo 3 e no ciclo 6, e a de Moore aparece nos ciclos 4 e 7, um ciclo depois. A linha de estados Moore passa por S3 nos mesmos instantes em que a saída vale 1. A parte 2 testou 131070 entradas e não encontrou nenhuma divergência entre as duas versões nem contra o gabarito. A parte 3 confere, para cada codificação, todos os estados e as duas entradas, e nenhuma falha aparece.

A última linha da parte 4 confirma a política de forçar o código 11 para o verde no semáforo: com t = 0 e com t = 1, o código 11 vai para 00, que é V. As equações da seção 4.6 e o programa dizem a mesma coisa.

8. Exercícios

1. Na versão de Moore desta aula, a máquina está em S2 (viu 10) e recebe x = 0. Qual é o próximo estado, e qual é a saída no ciclo seguinte?

Resposta: o próximo estado é S0, porque “100” não tem nenhum prefixo útil de 101 no fim. A saída no ciclo seguinte é 0, porque S0 tem saída 0.

2. Mesma máquina de Mealy, começando em S0, com a entrada 1101. Qual é a sequência de saídas, bit a bit?

Resposta: S0 com x = 1 vai a S1 com z = 0. S1 com x = 1 fica em S1 com z = 0. S1 com x = 0 vai a S2 com z = 0. S2 com x = 1 vai a S1 com z = 1, porque os três últimos bits 1, 0, 1 foram completados. A sequência é 0, 0, 0, 1.

3. Na codificação binária de Moore, o estado atual é 01 (S1) e x = 0. Use as equações da seção 4.5 para achar o próximo estado e a saída.

Resposta: q1’ = q0 x̄ + q1 q̄0 x = 1·1 + 0 = 1, e q0’ = x = 0. O próximo estado é 10, que é S2. A saída z = q1 q0 = 0·1 = 0. O resultado coincide com a tabela da seção 4.3.

4. No semáforo binário da seção 4.6, o estado é 01 (amarelo) e t = 1. Use q1’ = q̄1 q0 t + q1 q̄0 t̄ para achar o próximo bit de maior peso. Em qual estado a máquina cai?

Resposta: q1’ = q̄1 q0 t = 1·1·1 = 1, porque q̄1 = 1, q0 = 1 e t = 1. O segundo termo vale 0, porque q1 = 0. Como q0’ = q̄1 (q0 ⊕ t) = 1·(1 ⊕ 1) = 0, o próximo estado é 10, que é o vermelho. Isso confirma que amarelo com t = 1 vai para vermelho.

5. Quantos códigos não usados existem numa máquina de quatro estados em one-hot com quatro flip-flops? E em binário com dois flip-flops?

Resposta: em one-hot há 2^4 = 16 códigos, e 4 são válidos, então 12 não são usados. Em binário com dois flip-flops há 2^2 = 4 códigos, e todos são usados na versão de Moore. Na versão de Mealy, que tem três estados, sobra um código, o 11.

6. Um contador precisa contar de 0 a 99 e depois emitir um pulso. Quantos estados uma máquina de estados pura teria, e quantos flip-flops seriam necessários em binário? Por que vale a pena usar um contador?

Resposta: uma máquina pura teria 100 estados, mais o estado de pulso se ele for um estado separado. Em binário, 100 estados pedem 7 flip-flops, porque 2^6 = 64 é pouco e 2^7 = 128 basta. Um contador de sete bits, com a máquina só cuidando do pulso, deixa o diagrama com poucos estados. Essa conta de 7 flip-flops é a mínima pela regra de potência de dois, sem contar a lógica.

9. Glossário

Máquina de estados finitos: circuito cuja saída depende da entrada atual e de um conjunto finito de estados, guardado em flip-flops.

Estado: uma das situações possíveis em que a máquina pode estar, guardada no registrador de estado.

Estado inicial: o estado em que a máquina começa depois do reset.

Entrada: sinal que chega à máquina a cada ciclo de clock.

Saída: sinal que a máquina produz, calculado pela lógica de saída.

Transição: regra que diz, para um estado e uma entrada, qual é o próximo estado.

Diagrama de estados: desenho de estados e transições, usado para entender a máquina antes de projetá-la.

Tabela de estados: tabela que lista, para cada estado e cada entrada, o próximo estado e a saída.

Registrador de estado: conjunto de flip-flops que guarda o estado atual, com um clock comum.

Lógica de próximo estado: circuito combinacional que calcula o próximo estado a partir do atual e da entrada.

Lógica de saída: circuito combinacional que calcula a saída, a partir do estado (Moore) ou do estado e da entrada (Mealy).

Máquina de Moore: máquina cuja saída depende só do estado atual.

Máquina de Mealy: máquina cuja saída depende do estado atual e da entrada.

Sobreposição: situação em que a sequência detectada pode começar antes do fim da anterior, como em 10101, que contém duas vezes 101.

Codificação: regra que associa cada estado a um código de bits.

Binária: codificação com o menor número de flip-flops, em que o código é o número do estado escrito em base 2.

One-hot: codificação com um flip-flop por estado, e exatamente um aceso em cada momento.

Gray: codificação em que dois estados vizinhos diferem em um só bit.

Estado inalcançável: código que nenhuma sequência de entradas a partir do reset consegue produzir.

Don’t care: valor que o projetista pode escolher livremente, porque o caso nunca acontece.

Reset: sinal que força a máquina ao estado inicial.

Karnaugh: mapa que ajuda a simplificar uma função lógica agrupando células vizinhas com valor 1.

Fan-out: número de entradas que uma mesma saída alimenta.

O que não foi confirmado ou medido

Os nomes e as datas dos artigos de Mealy (1955) e de Moore (1956) foram conferidos em registros bibliográficos de busca, com o volume e as páginas do artigo de Mealy e o volume Automata Studies com as páginas de Moore. Nenhum dos dois artigos foi lido integralmente para esta aula, e a descrição do conteúdo de cada um é a que aparece nos registros, não a do texto original.

O resultado clássico que liga expressões regulares e autômatos finitos não foi consultado. A seção 3 o cita sem data e sem autor, e a afirmação é a que a teoria usual faz, não algo conferido nesta aula.

O protocolo UART da seção 3 foi descrito em termos gerais, com bit de início, bits de dados e bit de parada. Não consultei especificação de UART nesta aula, então a configuração de bits, o tempo de cada bit e as variações do protocolo não foram conferidos.

Os valores de tempo dos diagramas, como o atraso de 0,1 e de 0,6 unidades após a borda na figura 04, são de exemplo, escolhidos para tornar a diferença entre Moore e Mealy visível. Não foram medidos em nenhum circuito.

A regra de que um flip-flop começa com valor indefinido sem reset é uma afirmação geral do projeto digital. Não consultei a folha de dados de nenhum componente específico para confirmar o comportamento no power-up.

A codificação de UTF-8 da figura 08 usa os padrões de bytes como aparecem na aula Texto, ASCII, Unicode e UTF-8. Não consultei a RFC 3629 nesta aula. O recorte da figura deixa de fora a validação de sequências superlongas, da faixa de surrogates e do limite do código, e as transições de erro dos estados de continuação não estão desenhadas.

O checador do ArchFlow avisa que algumas saídas de flip-flop têm mais de uma conexão (fan-out) e que um rótulo de fio cobre uma caixa vizinha em duas figuras de estados. Esses avisos foram aceitos, porque as figuras foram conferidas na prévia e não há texto cortado nem caixa sobreposta.

Fontes

Consultadas em 1 de novembro de 2026.

• George H. Mealy, “A Method for Synthesizing Sequential Circuits”, Bell System Technical Journal, volume 34, número 5, páginas 1045 a 1079, 1955, DOI 10.1002/j.1538-7305.1955.tb03788.x. Registro bibliográfico obtido na busca, sem leitura integral: https://nokia.com/bell-labs/publications-and-media/publications/a-method-for-synthesizing-sequential-circuits
• Edward F. Moore, “Gedanken-experiments on Sequential Machines”, em Automata Studies, Annals of Mathematics Studies número 34, Princeton University Press, páginas 129 a 153, 1956, editado por C. E. Shannon e J. McCarthy. Cópia do artigo hospedada pela Carnegie Mellon, sem leitura integral nesta aula: https://www.cs.cmu.edu/~cdm/resources/Moore1956-gedanken-experiments.pdf
• Aulas anteriores da trilha: Circuitos sequenciais (definições de latch, flip-flop, setup e hold, com as notas da University of Maryland e da UCSB) e Clock e sincronização (caminho crítico e sincronizador), das quais esta aula reaproveita definições e não as repete.

Relacionados

• Trilha de Hardware
• CPU
• Circuitos sequenciais
• Clock e sincronização
• Circuitos combinacionais
• Transistor como chave
• Bits e binário