16.3: 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 bastante 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, tiene la tendencia a agregar dinámicas completamente nuevas al funcionamiento de un dispositivo o sistema. En ocasiones, estas nuevas dinámicas encuentran aplicación útil, mientras que otras veces son meramente interesantes. Con las tablas de consulta 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 señal, necesitamos conectar las salidas de datos a las entradas de dirección a través de un flip-flop tipo D de 4 bits, para que la secuencia tenga lugar paso a paso al ritmo de un pulso de reloj controlado:

Una analogía para el funcionamiento de dicho dispositivo podría ser una matriz de cajas de correos, cada una con un número de identificación en la puerta (la dirección), y cada una conteniendo una hoja de papel con la dirección de otra casilla de correos escrita en ella (los datos). Una persona, abriendo el primer apartado de correos, encontraría en él la dirección del siguiente apartado de correos para abrir. Al almacenar un patrón particular de direcciones en las casillas de correos, podemos dictar la secuencia en la que se abre cada caja y, por lo tanto, la secuencia de la cual se lee el papel.

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 enclavarse. 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 sea realimentada a la ROM como dirección. Una aplicación útil de dicho FSM sería generar una secuencia de conteo arbitraria, como Gray Code:

Trate de seguir la secuencia de conteo del Código Gris como lo haría el FSM: comenzando en 0000, siga los datos almacenados en esa dirección (0001) a la siguiente dirección, y así sucesivamente (0011), y así sucesivamente (0010), y así sucesivamente (0110), etc. El resultado, para la tabla de programas mostrada, es que la secuencia de direccionamiento salta desde la dirección para abordar en lo que parece una manera fortuita, pero cuando compruebes cada dirección a la que se accede, encontrarás 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 inicia de nuevo toda la secuencia en la dirección 0000 en 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 tabla de búsqueda que convertimos en una Unidad Lógica Aritmética (+, -, x,/funciones) al utilizar 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).

Si A4 es 0, el FSM cuenta en binario; si A4 es 1, el FSM cuenta en Código Gris. En cualquier caso, la secuencia de conteo es arbitraria: determinada por el capricho del programador. Para el caso, 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 en absoluto. Se trata de un dispositivo de conteo completamente flexible, el comportamiento estrictamente determinado por el software (programación) en la ROM.

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

Aquí, las salidas de datos D0 a D3 se utilizan exclusivamente para la 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 emitir algo que no sea el valor de “estado” del FSM. Siendo que cuatro bits de salida de datos se están realimentando a cuatro bits de dirección, este sigue siendo un dispositivo de 16 estados. Sin embargo, tener los datos de salida procedentes 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 solo 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 de los estados 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 estar conectado al reloj en algún evento externo, de modo que el FSM pase al siguiente estado solo cuando una señal de entrada le indique que lo haga.

Ahora tenemos un dispositivo que mejor cumple 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” está encendido el dispositivo en su secuencia. Esto está muy cerca del diseño operativo de la Máquina Turing, un dispositivo informático teórico inventado por Alan Turing, matemáticamente probado que es capaz de resolver cualquier problema aritmético conocido, dada la suficiente capacidad de memoria.