Máquina de estado finito

O feedback é um princípio de engenharia fascinante. Ele pode transformar um dispositivo ou processo bastante simples em algo substancialmente mais complexo. Vimos os efeitos do feedback intencionalmente integrado aos projetos de circuito com alguns efeitos bastante surpreendentes:

• Comparador + feedback negativo —————-> amplificador de ganho controlável
• Comparador + feedback positivo —————-> comparador com histerese
• Lógica combinacional + feedback positivo—> multivibrador

No campo da instrumentação de processos, o feedback é usado para transformar um sistema de medição simples em algo capaz de controle:

• Sistema de medição + feedback negativo —-> sistema de controle de malha fechada

O feedback, tanto positivo quanto negativo, tende a adicionar uma dinâmica totalmente nova à operação de um dispositivo ou sistema. Às vezes, essas novas dinâmicas encontram uma aplicação útil, enquanto outras vezes são meramente interessantes.

Com tabelas de pesquisa programadas em dispositivos de memória, o feedback das saídas de dados de volta para as entradas de endereço cria um tipo totalmente novo de dispositivo:a Máquina de Estados Finitos ou FSM :







O circuito acima ilustra a ideia básica:os dados armazenados em cada endereço se tornam o próximo local de armazenamento para o qual a ROM é endereçada. O resultado é uma seqüência específica de números binários (seguindo a seqüência programada na ROM) na saída, ao longo do tempo.

Para evitar problemas de tempo de sinal, no entanto, precisamos conectar as saídas de dados de volta às entradas de endereço por meio de um flip-flop tipo D de 4 bits, de modo que a sequência ocorra passo a passo na batida de um pulso de clock controlado:









Uma analogia para o funcionamento de tal dispositivo pode ser um conjunto de caixas postais, cada uma com um número de identificação na porta (o endereço), e cada uma contendo um pedaço de papel com o endereço de outro posto de correio. caixa escrita nele (os dados). Uma pessoa, abrindo o primeiro P.O. caixa, encontraria nela o endereço do próximo P.O. caixa para abrir.

Ao armazenar um determinado padrão de endereços na caixa postal caixas, podemos ditar a sequência em que cada caixa é aberta e, portanto, a sequência em que o papel é lido.



Tendo 16 locais de memória endereçáveis ​​na ROM, esta máquina de estados finitos teria 16 diferentes “estados” estáveis ​​nos quais poderia travar. Em cada um desses estados, a identidade do próximo estado seria programada na ROM, aguardando que o sinal do próximo pulso de clock fosse retornado à ROM como um endereço.

Uma aplicação útil de tal FSM seria gerar uma sequência de contagem arbitrária, como Gray Code:

 Endereço -----> Sequência de contagem do código cinza de dados:0000 -------> 0001 0 0000 0001 -------> 0011 1 0001 0010 -------> 0110 2 0011 0011 -------> 0010 3 0010 0100 -------> 1100 4 0110 0101 -------> 0100 5 0111 0110 -------> 0111 6 0101 0111 -------> 0101 7 0100 1000 -------> 0000 8 1100 1001 -------> 1000 9 1101 1010 -------> 1011 10 1111 1011 -------> 1001 11 1110 1100 -------> 1101 12 1010 1101 -------> 1111 13 1011 1110 -------> 1010 14 1001 1111 -------> 1110 15 1000 

Tente seguir a sequência de contagem do Gray Code como o FSM faria:começando em 0000, siga os dados armazenados nesse endereço (0001) para o próximo endereço e assim por diante (0011), e assim por diante (0010), e assim por diante em (0110), etc. O resultado, para a tabela de programa mostrada, é que a sequência de endereçamento salta de endereço em endereço no que parece de forma aleatória, mas quando você verifica cada endereço que é acessado, você descobrirá que ele segue a ordem correta para o código Gray de 4 bits.

Quando o FSM chega ao seu último estado programado (endereço 1000), os dados armazenados lá são 0000, que inicia toda a sequência novamente no endereço 0000 em etapa com o próximo pulso de clock.

Poderíamos expandir as capacidades do circuito acima usando um ROM com mais linhas de endereço e adicionando mais dados de programação:







Agora, assim como o circuito somador de tabela de consulta que transformamos em uma Unidade Lógica Aritmética (+, -, x, / funções), utilizando mais linhas de endereço como entradas de "controle de função", este contador FSM pode ser usado para gerar mais de uma sequência de contagem, uma sequência diferente programada para os quatro bits de feedback (A0 a A3) para cada uma das duas combinações de entrada de linha de controle de função (A4 =0 ou 1).

 Endereço -----> Endereço de dados -----> Dados 00000 -------> 0001 10000 -------> 0001 00001 -------> 0010 10001 -------> 0011 00010 -------> 0011 10010 -------> 0110 00011 -------> 0100 10011 -------> 0010 00100 -------> 0101 10100 -------> 1100 00101 -------> 0110 10101 -------> 0100 00110 -------> 0111 10110 -------> 0111 00111 -------> 1000 10111 -------> 0101 01000 -------> 1001 11000 -------> 0000 01001 -------> 1010 11001 -------> 1000 01010 -------> 1011 11010 -------> 1011 01011 -------> 1100 11011 -------> 1001 01100 -------> 1101 11100 -------> 1101 01101 -------> 1110 11101 -------> 1111 01110 -------> 1111 11110 -------> 1010 01111 -------> 0000 11111 -------> 1110 

Se A4 for 0, o FSM conta em binário; se A4 for 1, o FSM conta em Gray Code. Em qualquer dos casos, a sequência de contagem é arbitrária:determinada pelo capricho do programador. Por falar nisso, a sequência de contagem nem mesmo precisa ter 16 etapas, pois o programador pode decidir que a sequência seja reciclada para 0000 em qualquer uma das etapas. É um dispositivo de contagem totalmente flexível, cujo comportamento é estritamente determinado pelo software (programação) na ROM.

Podemos expandir ainda mais as capacidades do FSM utilizando um chip ROM com entrada de endereço adicional e linhas de saída de dados. Pegue o seguinte circuito, por exemplo:





Aqui, as saídas de dados D0 a D3 são usadas exclusivamente para feedback para as linhas de endereço A0 a A3. As linhas de saída de data D4 a D7 podem ser programadas para produzir algo diferente do valor de "estado" do FSM. Sendo que quatro bits de saída de dados estão sendo realimentados para quatro bits de endereço, este ainda é um dispositivo de 16 estados.

No entanto, ter os dados de saída vindo de outras linhas de saída de dados dá ao programador mais liberdade para configurar funções do que antes. Em outras palavras, este dispositivo pode fazer muito mais do que apenas contar! A saída programada deste FSM depende não apenas do estado das linhas de endereço de feedback (A0 a A3), mas também dos estados das linhas de entrada (A4 a A7).

A entrada do sinal de relógio do flip / flop tipo D também não precisa vir de um gerador de pulso. Para tornar as coisas mais interessantes, o flip / flop pode ser conectado para fazer o clock em algum evento externo, de modo que o FSM vá para o próximo estado apenas quando um sinal de entrada o instruir.



Agora temos um dispositivo que preenche melhor o significado da palavra “programável”. Os dados gravados na ROM são um programa no sentido mais verdadeiro:as saídas seguem uma ordem pré-estabelecida com base nas entradas para o dispositivo e em qual “passo” o dispositivo está em sua sequência.

Isso está muito próximo do projeto operacional da Máquina de Turing , um dispositivo de computação teórico inventado por Alan Turing, matematicamente comprovado como sendo capaz de resolver qualquer problema aritmético conhecido, dada a capacidade de memória suficiente.