Máquina de estado finito

La retroalimentación es un principio de ingeniería fascinante. Puede convertir un dispositivo o proceso bastante simple en algo sustancialmente más complejo. Hemos visto los efectos de la retroalimentación integrada intencionalmente en los diseños de circuitos con algunos efectos asombrosos:

• Comparador + retroalimentación negativa —————-> amplificador de ganancia controlable
• Comparador + retroalimentación positiva —————-> comparador con histéresis
• Lógica combinacional + retroalimentación positiva—> multivibrador

En el campo de la instrumentación de procesos, la retroalimentación se utiliza para transformar un sistema de medición simple en algo capaz de controlar:

• Sistema de medición + retroalimentación negativa —-> sistema de control de circuito cerrado

La retroalimentación, tanto positiva como negativa, tiende a agregar una dinámica completamente nueva al funcionamiento de un dispositivo o sistema. A veces, estas nuevas dinámicas encuentran una aplicación útil, mientras que otras veces son simplemente interesantes.

Con tablas de búsqueda programadas en dispositivos de memoria, la retroalimentación de las salidas de datos a las entradas de dirección crea un tipo de dispositivo completamente nuevo:la Máquina de estado finito o FSM :

El circuito anterior ilustra la idea básica:los datos almacenados en cada dirección se convierten en la siguiente ubicación de almacenamiento a la que se dirige la ROM. El resultado es una secuencia específica de números binarios (siguiendo la secuencia programada en la ROM) en la salida, a lo largo del tiempo.

Sin embargo, para evitar problemas de sincronización de la señal, debemos conectar las salidas de datos a las entradas de dirección a través de un flip-flop tipo D de 4 bits, de modo que la secuencia se lleve a cabo paso a paso al ritmo de un pulso de reloj controlado:

Una analogía para el funcionamiento de tal dispositivo podría ser una serie de apartados de correos, cada uno con un número de identificación en la puerta (la dirección), y cada uno contiene una hoja de papel con la dirección de otro P.O. cuadro escrito en él (los datos). Una persona, abriendo el primer P.O. casilla, encontraría en ella la dirección del próximo P.O. caja para abrir.

Al almacenar un patrón particular de direcciones en el P.O. cajas, podemos dictar la secuencia en la que se abre cada caja y, por lo tanto, la secuencia de qué papel se lee.

Al tener 16 ubicaciones de memoria direccionables en la ROM, esta máquina de estado finito tendría 16 "estados" estables diferentes en los que podría engancharse. En cada uno de esos estados, la identidad del siguiente estado se programaría en la ROM, esperando que la señal del siguiente pulso de reloj se devuelva a la ROM como una dirección.

Una aplicación útil de tal FSM sería generar una secuencia de conteo arbitraria, como Gray Code:

 Dirección -----> Secuencia de recuento del código gris de datos: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 

Intente seguir la secuencia de conteo del Código Gray como lo haría el FSM:comenzando en 0000, siga los datos almacenados en esa dirección (0001) hasta la siguiente dirección, y así sucesivamente (0011), y así sucesivamente (0010), y así en (0110), etc. El resultado, para la tabla de programas que se muestra, es que la secuencia de direccionamiento salta de una dirección a otra en lo que parece una forma desordenada, pero cuando verifica cada dirección a la que se accede, encontrará que sigue el orden correcto para el código Gray de 4 bits.

Cuando el FSM llega a su último estado programado (dirección 1000), los datos almacenados allí son 0000, que comienza de nuevo la secuencia completa en la dirección 0000 en el paso con el siguiente pulso de reloj.

Podríamos ampliar las capacidades del circuito anterior usando una ROM con más líneas de dirección y agregando más datos de programación:

Ahora, al igual que el circuito sumador de la tabla de búsqueda que convertimos en una Unidad Aritmética Lógica (+, -, x, / funciones) utilizando más líneas de dirección como entradas de "control de función", este contador FSM se puede usar para generar más de una secuencia de conteo, una secuencia diferente programada para los cuatro bits de retroalimentación (A0 a A3) para cada una de las dos combinaciones de entrada de línea de control de función (A4 =0 o 1).

 Dirección -----> Dirección de datos -----> Datos 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 

Si A4 es 0, el FSM cuenta en binario; si A4 es 1, el FSM cuenta en Gray Code. En cualquier caso, la secuencia de conteo es arbitraria:determinada por el capricho del programador. De hecho, la secuencia de conteo ni siquiera tiene que tener 16 pasos, ya que el programador puede decidir que la secuencia se recicle a 0000 en cualquiera de los pasos. Es un dispositivo de conteo completamente flexible, cuyo comportamiento está estrictamente determinado por el software (programación) en la ROM.

Podemos ampliar las capacidades del FSM aún más utilizando un chip ROM con líneas adicionales de entrada de dirección y salida de datos. Tome el siguiente circuito, por ejemplo:

Aquí, las salidas de datos D0 a D3 se utilizan exclusivamente para retroalimentación a las líneas de dirección A0 a A3. Las líneas de salida de fecha D4 a D7 se pueden programar para generar algo diferente al valor de "estado" del FSM. Dado que cuatro bits de salida de datos se retroalimentan a cuatro bits de dirección, este sigue siendo un dispositivo de 16 estados.

Sin embargo, el hecho de que los datos de salida provengan de otras líneas de salida de datos le da al programador más libertad para configurar funciones que antes. En otras palabras, ¡este dispositivo puede hacer mucho más que contar! La salida programada de este FSM depende no solo del estado de las líneas de dirección de retroalimentación (A0 a A3), sino también del estado de las líneas de entrada (A4 a A7).

La entrada de señal de reloj del flip / flop tipo D tampoco tiene que provenir de un generador de pulsos. Para hacer las cosas más interesantes, el flip / flop podría conectarse para sincronizar algún evento externo, de modo que el FSM pase al siguiente estado solo cuando una señal de entrada lo indique.

Ahora tenemos un dispositivo que cumple mejor con el significado de la palabra "programable". Los datos escritos en la ROM son un programa en el sentido más verdadero:las salidas siguen un orden preestablecido basado en las entradas al dispositivo y en qué "paso" se encuentra el dispositivo en su secuencia.

Esto está muy cerca del diseño operativo de la Máquina de Turing , un dispositivo informático teórico inventado por Alan Turing, que se ha demostrado matemáticamente que es capaz de resolver cualquier problema aritmético conocido, dada la capacidad de memoria suficiente.