11.5: Máquinas de Estado Finito

Hasta ahora, cada circuito que se presentó era un circuito combinatorio. Eso quiere decir que su salida es dependiente sólo por sus entradas de corriente. Las entradas anteriores para ese tipo de circuitos no tienen efecto en la salida.

Sin embargo, hay muchas aplicaciones donde existe la necesidad de que nuestros circuitos tengan “memoria”; recordar entradas anteriores y calcular sus salidas de acuerdo a ellas. Un circuito cuya salida depende no solo de la entrada actual sino también de la historia de la entrada se denomina circuito secuencial.

En esta sección aprenderemos a diseñar y construir tales circuitos secuenciales. Para ver cómo funciona este procedimiento, usaremos un ejemplo, sobre el cual estudiaremos nuestro tema.

Entonces, supongamos que tenemos un juego de preguntas digitales que funciona en un reloj y lee una entrada de un botón manual. Sin embargo, queremos que el conmutador transmita solo un pulso ALTO al circuito. Si enganchamos el botón directamente en el circuito del juego transmitirá ALTO por tan pocos ciclos de reloj como nuestro dedo pueda lograr. En una frecuencia de reloj común nuestro dedo nunca puede ser lo suficientemente rápido.

El procedimiento de diseño tiene pasos específicos que deben seguirse para poder realizar el trabajo:

Paso 1

El primer paso del procedimiento de diseño es definir con palabras simples pero claras lo que queremos que haga nuestro circuito:
“Nuestra misión es diseñar un circuito secundario que transmita un pulso ALTO con duración de solo un ciclo cuando se presione el botón manual, y no transmita otro pulso hasta que se presione el botón y se vuelva a presionar”. Paso 2

El siguiente paso es diseñar un Diagrama de Estado. Se trata de un diagrama que está hecho de círculos y flechas y describe visualmente el funcionamiento de nuestro circuito. En términos matemáticos, este diagrama que describe el funcionamiento de nuestro circuito secuencial es una Máquina de Estado Finito.

Toma nota de que se trata de una Máquina de Estado Finito Moore. Su salida es función únicamente de su estado actual, no de su entrada. Eso contrasta con la Máquina de Estado Finito Harinoso, donde la entrada afecta a la salida. En este tutorial, solo se examinará la Máquina de Estado Finito Moore.

El Diagrama de Estado de nuestro circuito es el siguiente: (Figura abajo)

Un diagrama de estado

Cada círculo representa un “estado”, una condición bien definida en la que se puede encontrar nuestra máquina.
En la mitad superior del círculo describimos esa condición. La descripción nos ayuda a recordar lo que se supone que debe hacer nuestro circuito en esa condición.

• El primer círculo es la condición “stand-by”. Aquí es de donde parte nuestro circuito y donde espera otra pulsación de botón.
• El segundo círculo es la condición en la que el botón acaba de ser presionado y nuestro circuito necesita transmitir un pulso ALTO.
• El tercer círculo es la condición en la que nuestro circuito espera a que se suelte el botón antes de que vuelva a la condición de “stand-by”.

En la parte inferior del círculo está la salida de nuestro circuito. Si queremos que nuestro circuito transmita un ALTO en un estado específico, ponemos un 1 en ese estado. De lo contrario ponemos un 0.

Cada flecha representa una “transición” de un estado a otro. Una transición ocurre una vez cada ciclo de reloj. Dependiendo de la entrada actual, podemos ir a un estado diferente cada vez. Observe el número en el centro de cada flecha. Esta es la entrada de corriente.
Por ejemplo, cuando estamos en el estado “Inicial-Stand by” y “leemos” un 1, el diagrama nos dice que tenemos que ir al estado “Activar Pulso”. Si leemos un 0 debemos quedarnos en el estado “Inicial-Stand by”.

Entonces, ¿qué hace exactamente nuestra “Máquina”? Comienza desde el estado “Inicial - Stand by” y espera hasta que se lea un 1 en la Entrada. Después pasa al estado “Activar Pulso” y transmite un pulso ALTO en su salida. Si el botón sigue siendo presionado, el circuito pasa al tercer estado, el “Bucle de Espera”. Allí espera hasta que se suelte el botón (Entrada va 0) mientras transmite un BAJO en la salida. ¡Entonces todo ha terminado otra vez!

Esta es posiblemente la parte más difícil del procedimiento de diseño, ya que no se puede describir con simples pasos. Se necesita expreriencia y un poco de pensamiento agudo para establecer un Diagrama de Estado, pero el resto es solo un conjunto de pasos predeterminados.

Paso 3

A continuación, reemplazamos las palabras que describen los diferentes estados del diagrama por números binarios. Comenzamos la enumeración desde 0 que se asigna en el estado inicial. Luego continuamos la enumeración con cualquier estado que nos guste, hasta que todos los estados tengan su número. El resultado se ve algo así: (Figura abajo)

Un diagrama de estados con estados codificados

Paso 4

Después, llenamos la Mesa Estatal. Esta tabla tiene una forma muy específica. Daré la tabla de nuestro ejemplo y la utilizaré para explicar cómo rellenarla. (Figura abajo)

Una tabla de estados

Las primeras columnas son tantos como los bits del número más alto que asignamos al Diagrama de Estado. Si tuviéramos 5 estados, habríamos usado hasta el número 100, lo que significa que usaríamos 3 columnas. Para nuestro ejemplo, usamos hasta el número 10, por lo que solo se necesitarán 2 columnas. Estas columnas describen el Estado Actual de nuestro circuito.
A la derecha de las columnas Estado Actual escribimos las Columnas de Entrada. Estas serán tantas como nuestras variables de entrada. Nuestro ejemplo solo tiene una entrada.
A continuación, escribimos las Columnas del Estado Siguiente. Estas son tantas como las columnas Estado Actual.
Por último, escribimos las Columnas de Salidas. Estas son tantas como nuestras salidas. Nuestro ejemplo solo tiene una salida. Como hemos construido una Máquina de Estado Más Finito, la salida depende solo de los estados de entrada actuales. Esta es la razón por la que la columna de salidas tiene dos 1: para dar como resultado una función booleana de salida que es independiente de la entrada I. Sigue leyendo para más detalles.

Las columnas Estado Actual y Entrada son las Entradas de nuestra tabla. Los rellenamos con todos los números binarios de 0 a

Es más sencillo de lo que suena afortunadamente. Por lo general, habrá más filas que los Estados reales que hemos creado en el Diagrama de Estado, pero eso está bien.

Cada fila de las columnas Estado Siguiente se rellena de la siguiente manera: La rellenamos con el estado que alcanzamos cuando, en el Diagrama de Estado, desde el Estado Actual de la misma fila seguimos la Entrada de la misma fila. Si hay que rellenar una fila cuyo número de Estado Actual no corresponda a ningún Estado real en el Diagrama del Estado lo rellenamos con términos de No importa (X). Después de todo, no nos importa a dónde podamos ir desde un Estado que no existe. ¡No estaríamos ahí en primer lugar! Nuevamente es más sencillo de lo que parece.

La columna de salidas es llenada por la salida del Estado Actual correspondiente en el Diagrama de Estado.

¡La Mesa Estatal está completa! Describe el comportamiento de nuestro circuito tan completamente como lo hace el Diagrama de Estado.

Paso 5a

El siguiente paso es tomar esa “Máquina” teórica e implementarla en un circuito. La mayoría de las veces, esta implementación involucra Flip Flops. Esta guía está dedicada a este tipo de implementación y describirá el procedimiento tanto para D - Flip Flops como para JK - Flip Flops. T - Las chanclas no se incluirán ya que son demasiado similares a los dos casos anteriores. La selección del Flip Flop a usar es arbitraria y generalmente está determinada por factores de costo. La mejor opción es realizar tanto análisis como decidir qué tipo de Flip Flop da como resultado un número mínimo de puertas lógicas y menor costo.

Primero examinaremos cómo implementamos nuestra “Máquina” con D-Flip Flops.

Vamos a necesitar tantas D - Chanclas como las columnas Estado, 2 en nuestro ejemplo. Por cada Flip Flop agregaremos una columna más en nuestra tabla de Estados (Figura abajo) con el nombre de la entrada del Flip Flop, “D” para este caso. La columna que corresponde a cada Flip Flop describe qué entrada debemos darle al Flip Flop para pasar del Estado Actual al Estado Siguiente. Para el D - Flip Flop esto es fácil: La entrada necesaria es igual al Estado Siguiente. En las filas que contienen X's también rellenamos X's en esta columna.

Una Tabla de Estados con D - Excitaciones Flip Flop

Paso 5b

Podemos hacer los mismos pasos con JK - Chanclas. Sin embargo, existen algunas diferencias. Un JK - Flip Flop tiene dos entradas, por lo tanto necesitamos agregar dos columnas para cada Flip Flop. El contenido de cada celda viene dictado por la tabla de excitación de JK:

(Figura abajo) JK - Tabla de Excitación Flip Flop:

Esta tabla dice que si queremos pasar de Estado Q a Estado Q a _{continuación}, necesitamos usar la entrada específica para cada terminal. Por ejemplo, para pasar de 0 a 1, necesitamos alimentar a J con 1 y no nos importa qué entrada alimentamos a la terminal K.

Una Tabla de Estados con JK - Excitaciones Flip Flop

Paso 6

Estamos en la etapa final de nuestro procedimiento. Lo que queda, es determinar las funciones booleanas que producen las entradas de nuestros Flip Flops y el Output. Extraeremos una función booleana por cada entrada de Flip Flop que tengamos. Esto se puede hacer con un Mapa de Karnaugh. Las variables de entrada de este mapa son las variables Estado Actual así como las Inputs.

Dicho esto, las funciones de entrada para nuestras D - Flip Flops son las siguientes: (Figura abajo)

Mapas de Karnaugh para la D - Entradas Flip Flop

Si optamos por usar JK - Flip Flops nuestras funciones serían las siguientes: (Figura abajo)

Mapa de Karnaugh para el JK - Entrada Flip Flop

También se utilizará un Mapa de Karnaugh para determinar la función de la Salida: (Figura abajo)

Mapa de Karnaugh para la variable de salida Y

Paso 7

Diseñamos nuestro circuito. Colocamos los Flip Flops y usamos puertas lógicas para formar las funciones booleanas que calculamos. Las puertas toman entrada de la salida de los Flip Flops y la Entrada del circuito. ¡No olvides conectar el reloj a las Chanclas!

La versión D - Flip Flop: (Figura abajo)

El circuito secuencial completo D - Flip Flop

La versión JK - Flip Flop: (Figura abajo)

El circuito secuencial JK - Flip Flop completado

¡Esto es! Hemos diseñado y construido exitosamente un Circuito Secuencial. Al principio puede parecer una tarea desalentadora, pero después de la práctica y la repetición el procedimiento se volverá trivial. Los circuitos secuenciales pueden ser útiles como partes de control de circuitos más grandes y pueden realizar cualquier tarea lógica secuencial que se nos ocurra. ¡El cielo es el límite! (o la placa de circuito, al menos)

Revisar

• Una función Lógica Secuencial tiene una función de “memoria” y toma en cuenta entradas pasadas para decidir sobre la salida.
• La Máquina de Estado Finito es un modelo matemático abstracto de una función lógica secuencial. Cuenta con entradas finitas, salidas y número de estados.
• Los FSM se implementan en circuitos de la vida real mediante el uso de Flip Flops
• El procedimiento de implementación necesita un orden específico de pasos (algoritmo), para poder llevarse a cabo.