Máquinas de estados e controladores

Uma máquina de estados finita, FSM, guarda apenas a parte do passado necessária para decidir o comportamento seguinte. Para reconhecer se um número binário é múltiplo de 3, não precisamos de guardar todos os bits recebidos: chega guardar o resto da divisão por 3, porque o próximo resto depende só do resto atual e do bit que chega.

Moore e Mealy

Numa Moore, a saída depende só do estado atual. Numa Mealy, pode depender também das entradas atuais. O próximo estado depende sempre do estado e das entradas.

Num diagrama Moore, escreve a saída dentro do estado e a condição na seta. Num Mealy, escreve condição/saída na seta. Uma saída Mealy pode mudar entre flancos se a entrada mudar; não a trates como um valor sempre registado.

Resto de uma sequência binária

Se o prefixo lido vale $v$ e chega um bit $b$, o novo valor é $2v+b$. Para o resto $r$ módulo 3, com

$$r^+=(2r+b)\bmod3.$$

Usamos estados R0, R1, R2 e saída $z=1$ em R0. O reset põe a máquina em R0. Aqui o prefixo vazio é interpretado como zero; se a especificação exigir pelo menos um bit, é preciso guardar também essa informação.

Estado	$b=0$	$b=1$	$z$
R0	R0	R1	1
R1	R2	R0	0
R2	R1	R2	0

Diagrama da Moore

Ao ler 110, passamos R0 → R1 → R0 → R0, e o número é 6, múltiplo de 3. Ao ler 101, passamos R0 → R1 → R2 → R2: 5 deixa resto 2; a saída observada depois de cada flanco corresponde ao prefixo já recebido.

Laboratório de máquinas

No laboratório, cada passo corresponde a um flanco com o bit indicado. A saída de R0 antes de receber bits aparece no passo 0. Altera a saída de R0 para 0 e executa a entrada vazia: o erro já é observável antes do primeiro bit. Repõe o exemplo e segue 110; o percurso R0,R1,R0,R0 deve produzir 1,0,1,1, incluindo a saída inicial.

Em Resolver exercício, recebe uma máquina com um erro. Corrige-a ou usa Construir do zero para criar a tua solução. Verificar máquina compara as saídas para todas as entradas: explora os pares de estados alcançáveis com a referência e mostra uma palavra testemunha se encontrar uma diferença. Os exemplos apresentados ajudam a localizar o erro; são a exploração completa dos pares, e não esses exemplos isolados, que decide a equivalência. Esta comparação é entre máquinas do mesmo modelo e alfabeto, não entre Moore e Mealy.

O seletor inclui também os exercícios do resto módulo 5 e da deteção Mealy de 11. Para o resto módulo 5, escolhe essa máquina e usa Resolver exercício seguido de Construir do zero. O estado após cada prefixo deve representar o seu resto. Com 1010, que representa 10, visita R1,R2,R0,R0 depois dos flancos; as saídas são 0,0,1,1, além do 1 inicial. A prática do capítulo pede a tabela e a justificação desse significado.

Síntese com flip-flops D

Codifica R0=00, R1=01, R2=10. São necessários dois flip-flops, porque $\lceil\log_2 3\rceil=2$. Escolhe recuperação de 11 para 00, com saída 0.

A tabela anterior, expandida para bits $q_1,q_0,b$ com próximo estado $n_1n_0$, dá o seguinte, onde cada linha com próximo bit 1 gera um termo do produto:

$q_1q_0$	$b=0\to n_1n_0$	$b=1\to n_1n_0$
00 pronto R0	00	01
01 pronto R1	10	00
10 pronto R2	01	10
11 inválido	00	00

$$D_1=\overline q_1q_0\overline b+q_1\overline q_0b,$$ $$D_0=\overline q_1\overline q_0b+q_1\overline q_0\overline b,$$ $$z=\overline q_1\overline q_0.$$

Cada termo de D vem de uma linha cuja próxima saída do flip-flop é 1. As equações dão 00 para o estado inválido, como escolhido. O circuito tem lógica combinatória para D e dois flip-flops que atualizam juntos.

Em one-hot usamos um bit por estado: $h_0,h_1,h_2$ representam R0,R1,R2, com exatamente um bit a 1. A escrita h0 h1 h2 dá R0=100, R1=010, R2=001. Para obter o próximo bit de cada estado, reúne as setas que chegam a esse estado:

$$normal_0=h_0\overline b+h_1b,$$ $$normal_1=h_0b+h_2\overline b,$$ $$normal_2=h_1\overline b+h_2b.$$

Por exemplo, R0 recebe uma seta de R0 com b=0 e outra de R1 com b=1. São os dois produtos de $normal_0$. Cada equação é uma OR de duas AND de duas entradas.

Estas equações só garantem a máquina pretendida nos códigos válidos. O código 000 ficaria em 000, porque todos os produtos valem 0. O reset estabelece 100; só a partir de um código válido é que as transições seguem a tabela. Se exigirmos recuperação de qualquer código inválido, precisamos também de verificar o invariante:

$$val=h_0\overline h_1\overline h_2+\overline h_0h_1\overline h_2+\overline h_0\overline h_1h_2.$$

Com $inv=\overline{val}$, escolhemos

$$h_0^+=normal_0+inv,$$ $$h_1^+=normal_1\,val,$$ $$h_2^+=normal_2\,val.$$

Se val=1, conservamos as transições normais. Se val=0, os próximos bits são 100, mesmo num código com vários bits a 1. O custo desta recuperação é adicional ao das três equações base; one-hot não elimina estados inválidos.

Reconhecer padrões e produzir um impulso

Para detetar 101 com sobreposição, os estados distinguem os prefixos já reconhecidos: nenhum, 1, 10 e deteção 101. Depois de detetar, o último 1 já pode iniciar outra ocorrência, por isso em 10101 há duas deteções; voltar incondicionalmente ao estado inicial perderia a segunda.

Uma Moore completa para esse caso tem esta tabela, onde a saída indicada é a do estado atual e só D deteta o padrão:

Estado	Prefixo útil	Saída	Próximo com 0	Próximo com 1
A	Nenhum	0	A	B
B	1	0	C	B
C	10	0	A	D
D	Deteção 101, termina em 1	1	C	B

Partindo de A, 10101 dá B,C,D,C,D. Observamos 0,0,1,0,1 depois dos flancos; em D, um novo 0 já completa o prefixo 10, por isso a transição vai para C. É esta informação conservada que permite a sobreposição.

Para produzir um impulso de um ciclo quando um botão fica 1, usa estados Espera, Impulso e Libertação. Espera entra em Impulso quando x=1; Impulso passa a Libertação se x ainda for 1, ou Espera se já for 0; Libertação conserva enquanto x=1. A saída só é 1 em Impulso. Sem Libertação, uma entrada longa pode provocar vários impulsos.

Mealy e sobreposição

Para detetar 11, basta recordar se o bit anterior era 1. Usa A para bit anterior 0, incluindo o reset, e B para bit anterior 1; a saída é 1 só quando o estado anterior é B e a entrada atual é 1:

Estado anterior	Entrada 0, destino/saída	Entrada 1, destino/saída
A	A/0	B/0
B	A/0	B/1

Em B, um novo 1 deteta um par e conserva B. Por isso, 111 produz 0,1,1: o segundo bit completa o primeiro par e o terceiro completa outro par com o segundo. Se a deteção voltasse a A, a segunda ocorrência perder-se-ia.

No laboratório, escolhe Mealy: detetar 11 e segue 111011. Antes dos flancos, os estados são A,B,B,B,A,B; as saídas da amostra são 0,1,1,0,0,1. O estado indicado na linha de cada passo é o destino da transição, mas a saída usa o estado anterior e o bit dessa linha. Não uses o novo estado B para atribuir 1 ao primeiro bit: ainda não havia um 1 anterior.

Com um flip-flop q que guarda esse bit anterior, as equações são $q^+=b$ e $z=qb$. A entrada b pode mudar z entre flancos. O simulador mostra amostras de entradas estáveis; não modela atrasos, glitches nem metastabilidade. Uma saída registada depois do flanco exigiria um registo de saída e uma especificação temporal própria.

Controlar uma soma em memória

Um controlador pode coordenar um contador de endereços e um acumulador sem executar instruções. Considera uma memória de 64 words com sinal de 32 bits, leitura combinatória e dados que não mudam durante o cálculo. Queremos somar os módulos dos 64 valores. Supomos que cada leitura, cálculo do módulo e soma estabilizam antes do flanco seguinte.

Usa um contador i de 6 bits para endereçar a memória. Se o bit de sinal do dado for 0, conserva-o; se for 1, calcula o complemento para dois. Interpreta a saída deste bloco como magnitude sem sinal: para 0x80000000, o módulo é $2^{31}$ e continua a ter o padrão 0x80000000. Não cabe como inteiro positivo com sinal de 32 bits, mas cabe numa magnitude sem sinal de 32 bits.

Antes de somar ao acumulador, alarga a magnitude com zeros. O pior caso são 64 valores iguais a $-2^{31}$:

$$S_{max}=64\times2^{31}=2^{37}.$$

Um acumulador sem sinal de 37 bits só chega a $2^{37}-1$. São necessários 38 bits para garantir o resultado exato. O somador e o registo do acumulador têm essa largura; os endereços continuam a ter 6 bits.

Uma Moore com Espera, Soma e Concluído controla o percurso:

Estado	Ação no flanco seguinte	Próximo estado
Espera, start=0	S←0, i←0	Espera
Espera, start=1	S←0, i←0	Soma
Soma, i diferente de 63	S←S+módulo(Mem[i]), i←i+1	Soma
Soma, i=63	Acrescenta o último módulo; contador volta a 0	Concluído
Concluído	Conserva o resultado	Concluído

done=1 só em Concluído; o reset coloca o controlador em Espera. Neste contrato, reset prepara uma nova operação. Não o confundas com um controlador que aceite start novamente em Concluído.

Os controlos da Moore dependem só do estado: Espera inicializa os registos em cada flanco; Soma habilita a soma e o contador; Concluído conserva. start e a comparação i=63 só decidem o próximo estado.

O flanco de arranque inicializa, mas ainda não soma. Os 64 flancos seguintes somam as posições 0 a 63. No último, soma-se o dado do endereço antigo 63, o contador volta a 0 e entra-se em Concluído; a habilitação da soma desliga-se nesse novo estado. Se o contador voltasse a 0 com a soma ainda habilitada, os mesmos dados seriam somados de novo.

Com memória síncrona de latência de um ciclo, este traço deixa de servir: seria preciso lançar o endereço num ciclo e usar o dado no seguinte, com registos e estados adicionais. A largura da memória, a capacidade, a latência de leitura e a largura do resultado são decisões distintas.

Minimização e comunicação

Para minimizar uma Moore, agrupa primeiro estados com a mesma saída. Divide um grupo quando dois dos seus estados, para a mesma entrada, transitam para grupos diferentes. Repete até estabilizar. Só estados que continuam indistinguíveis podem ser fundidos; ter a mesma saída hoje não chega.

Exemplo de partição

Considera esta Moore, com estado inicial A:

Estado	Saída	Próximo com 0	Próximo com 1
A	0	B	D
B	0	C	D
C	0	C	C
D	1	E	D
E	1	D	E

Começamos com $\{A,B,C\}$ e $\{D,E\}$. A entrada 1 separa C de A,B, pois C permanece no grupo de saída 0 enquanto A,B vão para saída 1. Ficamos com $\{A,B\},\{C\},\{D,E\}$. A entrada 0 separa agora A de B: A vai para o grupo A,B, mas B para C. A partição final é $\{A\},\{B\},\{C\},\{D,E\}$. D e E continuam juntos porque ambas as suas transições ficam no seu próprio grupo.

A máquina reduzida tem quatro estados: A, B, C e H, que representa D/E. A vai para B/H, B para C/H, C para C/C e H para H/H, respetivamente com 0/1. Conserva as saídas 0,0,0,1. Não conseguimos fundir A e B, apesar da mesma saída inicial: a sequência 01 termina em saída 1 a partir de A e 0 a partir de B.

Duas máquinas podem coordenar-se por handshake de quatro fases, com dados, valid e ack no tempo, segundo a tabela seguinte:

Passo	Dados	valid	ack	Regra
1	emissor fixa D	0	0	D estabiliza antes de valid
2	D estável	1	0	emissor pede aceitação
3	D estável	1	1	recetor aceitou D
4	D estável	0	1	emissor fecha pedido
5	livre	0	0	recetor fecha confirmação

Neste protocolo conservamos D até ao fim da confirmação. O emissor baixa valid depois de ver ack=1; o recetor baixa ack depois de ver valid=0. Só então se prepara a transferência seguinte. Mudar D logo após pôr valid=1 pode fazer o recetor aceitar outra palavra. A confirmação também permite esperar pelo recetor: um impulso de um ciclo sem confirmação pode ser perdido se ele não o observar.

Entre relógios diferentes, entradas podem violar setup/hold e provocar metastabilidade. O modelo de FSM assume entradas amostradas válidas. A implementação exige sincronização apropriada; sincronizar bits independentes não garante uma palavra de dados coerente.