Autómatas secuenciales finitos

Ejemplo de un autómata secuencial finito paso a paso

ELECTRÓNICA DIGITAL

Biblioman

2/6/201010 min read

En este artículo vamos a ver como implementar con un ejemplo práctico un autómata secuencial finito paso a paso, empezando por el desarrollo del DTE (Diagrama de Transición de Estados), construcción de la tabla de verdad, simplificación a través de los diagramas de Karnaugh, obtención de las ecuaciones de salida e implementación y simulación del circuito resultante. El desarrollo de circuitos con autómatas secuenciales es una herramienta muy potente y cuya comprensión abre el camino a otras técnicas de desarrollo como son por ejemplo en los Microcontroladores los RTOS (Sistemas Operativos en Tiempo Real).

En el desarrollo de sistemas digitales combinacionales las salidas de nuestro circuito en un momento dado dependen únicamente de los valores de las entradas en ese momento. En un sistema secuencial además del valor de las entradas en un instante dado tenemos que tener en cuenta también el estado anterior por el que ha pasado el sistema, por lo que ha estos circuitos se les suele llamar sistemas con memoria. Para implementar esa memoria se suele utilizar biestables (flip-flop) ó memorias ROM. Pero...

¿A que se le llama un autómata secuencial finito?

Una definición podría ser la siguiente: Un autómata es una máquina secuencial síncrona (controlada por una señal de reloj) que se puede encontrar en uno de entre un número posible de estados, recibe una serie de entradas binarias y en función de estas entradas y del estado particular en el que se encuentra, genera una o varias salidas binarias determinadas. Se le llama finito por que el número de estados en el que puede encontrarse el autómata tiene que quedar perfectamente determinado, de ahí que a estos sistemas se les llame también deterministas.


Siempre que hagamos el diseño de un circuito con autómatas secuenciales finitos podremos diferenciar en él los siguientes elementos:

  • Una memoria que permite almacenar el estado actual del autómata.

  • Dos circuitos combinacionales, uno para calcular el estado siguiente del autómata y el otro para hallar la salida.

Un diagrama de bloques del circuito sería el siguiente:

Básicamente existen dos tipos de autómatas finitos: el autómata de Mealy y el autómata de Moore.

Autómatas de Mealy

En un Autómata de Mealy, tanto la salida del autómata como su estado siguiente, en un instante determinado, depende tanto del estado en el que se encuentra el autómata en ese instante como de la entrada ó entradas binarias introducidas.
Esto implica que un autómata de Mealy, estando en un determinado estado, puede evolucionar hacia estados siguientes distintos y producir salidas distintas si se introduce una ó varias entradas binarias distintas.


Un ejemplo en el que podemos ver los diferentes elementos que componen un diagrama de Transición de Estados de un Autómata de Mealy sería el siguiente:

En el podemos distinguir los siguientes elementos:

  • Estados: que se pueden definir como las posibles situaciones a las que puede llegar el autómata.

  • Transiciones: son los eventos producidos por las entradas y que producirán el cambio de un estado a otro, en el sentido indicado por las flechas.

Un ejemplo de cómo debe leerse el diagrama para su comprensión sería el siguiente: desde el estado Q0, con entradas 11, se pasa al estado Q1 y produce salida 0; desde el estado Q1, con entradas 00 se pasa al estado Q0, y la salida será igual a "1", y así para todas las posibles transiciones.


Para que el autómata sea determinista de cada estado deben de salir 2 elevado a n transiciones donde n es el número de entradas.


Como vemos en el DTE (Diagrama de Transición de Estados), la salida depende del estado en que nos encontremos y del valor de las entradas.

Autómatas de Moore

Son aquellos en los cuales el estado siguiente, en un instante determinado, depende tanto del estado en el que se encuentra el autómata como de la entrada o entradas binarias introducidas, pero la salida en ese mismo instante sólo depende del estado en el que se encuentra el autómata.
Esto implica que un autómata de Moore, estando en un determinado estado, produce siempre la misma salida, independientemente de cuál sea la entrada ó entradas de datos en ese estado.


Un ejemplo de un Diagrama de Estados de un Autómata de Moore sería el siguiente:

Como vemos en el DTE la salida depende del estado en que nos encontremos pero no del valor de la entrada ó entradas de ese estado.

El diagrama debe de interpretarse de la siguiente forma: desde el estado 00 (en el cual siempre se da salida 0) y con entrada E0=1 se pasa al estado 01 (en el que siempre tenemos salida 0), una vez que el sistema a evolucionado a este nuevo estado y con entrada E0=1 se pasa al estado 10 con salida 0), y así para todas las posibles transiciones.


Al igual que el autómata de Mealy de cada estado debe salir 2 elevado a n transiciones donde n es el número de entradas.

¿Pero qué Autómata elegir para mis diseños?

La mayoría de las veces suele ser una cuestión de gustos. Algunos puntos prácticos que diferencian a ambos autómatas son los siguientes:

  • En Mealy la salida es obtenida antes que en Moore.

  • Mealy es más ágil y nervioso que Moore, que es más ordenado y tranquilo.

  • Los diseñadores tienen a Mealy por peligroso, ya que tiene cierto carácter asíncrono.

  • Los estados en Mealy suelen o pueden ser más abstractos que en Moore.

  • Mealy suele o puede tener menos estados que Moore, por tanto su implementación resulta más económica.

  • Suele ser más cómodo obtener el DTE de Moore que el de Mealy, pero como he dicho antes suele ser una cuestión de gustos. En el ejemplo práctico que vamos hacer utilizaremos a Moore.

Tablas de excitación de los biestables

Si utilizamos biestables como dispositivo de memoria para almacenar el estado actual del autómata, estas tablas nos sirven para relacionar el estado actual y el estado siguiente en que se encuentre el autómata con las entradas del biestable. En el ejemplo práctico que vamos hacer veremos cómo utilizarlas para hacer la tabla de verdad de nuestro autómata. Cada biestable tiene su propia tabla de excitación, en la figura de abajo se nuestra la tabla de excitación para cada uno de los biestables existentes.

Ejemplo práctico

Vamos hacer un ejemplo práctico y lo vamos a resolver utilizando el modelo del autómata de Moore.

Se trata de resolver la parte de control de un pequeño robot de juguete que funciona a través de un mando a distancia. La caja de control dispone de dos pulsadores (I1 y I2) como entradas del sistema y de dos salidas S0 y S1.

Se deben de cumplir las siguientes condiciones:

  • En estado de reposo (I1=I2=0) el robot no se moverá.

  • Si se pulsa el pulsador I1 el robot se moverá hacia adelante, continuando el movimiento al dejar de presionar dicho pulsador.

  • Si se pulsan ambos pulsadores I1 y I2 a la vez el robot se moverá hacia atrás, continuando el movimiento al dejar de pulsarlos.

  • Si se pulsa el pulsador I2 el robot se parará.

Las señales de salida en función del movimiento del robot deberán de ser las siguientes:

  • Si el robot está parado S0=S1=0

  • Si el robot se mueve hacia atrás S0=0 y S1=1

  • Y si el robot se mueve hacia adelante S0=1 y S1=0

Resolución del ejemplo

Lo primero y más importante que tenemos que hacer es dibujar nuestro diagrama de estados de transición (DTE), lo podemos dibujar directamente en un papel ó ayudarnos de algún software de los muchos que hay, para la realización de este paso (al final del artículo pondré los enlaces de algunos de ellos). Hay que tener en cuenta, que si nos equivocamos aquí, todo lo que hagamos después no servirá de nada. Una cosa que siempre tenemos que comprobar es que sea un autómata determinista, para ello hay que comprobar que no queden posibles estados sin definir. El DTE del ejemplo es el siguiente:

Como se ve en la figura nuestro DTE tiene tres estados llamados (Para, Adel, Atrás), que definen los tres posibles estados de movimiento en los que se puede encontrar el robot.
Como vemos de cada estado salen 4 transiciones, contándose también las que salen y entran al mismo estado. Como tenemos dos entradas, nuestro autómata es determinista (2 elevado a 2 igual a 4). Vamos a ver un ejemplo de cómo habría que ir construyendo nuestro DTE.

Partimos del estado (Para) con entradas I1=I2=0 donde las salidas son S0=0 y S1=0, si pulsamos I1 (I1=1 , I2=0), se producirá la transición al estado (Adel) y la salida cambiará a S0=1 y S1=0 y el robot se moverá hacia adelante. Si ahora soltamos el pulsador (I1=0, I2=0), vemos que continuamos en el mismo estado y por tanto el robot continuará moviéndose en la misma dirección, que es como se había definido en las condiciones del ejemplo. Pues de esta forma hay que ir comprobando todos los estados que definamos y comprobando todas las posibles transiciones entre ellos.


Una vez dibujado y comprobado nuestro DTE. Debemos de construir la tabla de verdad, que en este ejemplo será la siguiente:

Vamos a ir viendo poco a poco como se ha construido esta tabla. En otros ejemplos los nombres de los campos se mantendrán, aunque el número de columnas dependerá del número de estados que tenga nuestro DTE así como del tipo de biestable que utilicemos.

Lo primero que tenemos que hacer es codificar los estados, resultado de hacer nuestro DTE. Como tenemos tres estados (paro, adel y atrás) necesitaremos 2 bits.

Nos sobra la combinación (1,1), hay que ponerla porque nos servirá para simplificar las funciones de salida.

Las variables Q1 y Q0 necesarias para representar en binario cada uno de los estados, pasaran a formar parte de las entradas de nuestro autómata y forman parte del circuito combinacional que habíamos visto en el diagrama de bloques para determinar el estado siguiente del autómata.


Otro dato a tener en cuenta y que ya podemos deducir con lo que llevamos hecho es que: el número de Biestables necesarios en nuestro circuito depende de los bits en binario necesarios para representar todos los estados. En este ejemplo como el número de estados necesita dos bits para su codificación, necesitaremos dos biestables. También tendremos que decidir ahora el tipo de biestable que deseamos utilizar, yo he utilizado el flip-flop tipo D, luego en el campo flip-Flop de la tabla añadiremos las columnas D0 y D1, que corresponden a las salidas de estos flip-flop y que pasaran a formar parte de las funciones de salida de nuestro autómata.


Para tener los campos de las columnas de la tabla completa, tendremos que añadir como entradas I1 y I2 definidas como variables de entrada en nuestro ejemplo y como variables de salida añadiremos S0 y S1, definidas también en el ejemplo. Añadiremos también las columnas del campo correspondiente al estado siguiente de los flip-flop, que aunque no las he definido ni como entradas ni como salidas son necesarias, para hallar el valor de las entradas de los biestables (veremos un ejemplo de cómo hacer esto).


Pues bien, una vez definidas todas las columnas que tendrá nuestra tabla de verdad, es hora de empezar a insertar filas con datos. Empezaremos con las variables de entrada: como tenemos cuatro (Q1, Q0, I2, I1) necesitaremos 16 combinaciones para poder representar todos sus posibles valores, luego empezaremos a rellenar las filas correspondiente a estas columnas, empezando con el valor (0000) y terminando con (1111).


El siguiente paso es rellenar las filas correspondientes a las columnas del campo estado siguiente.

¿Cómo se hace esto?, pues con ayuda del DTE. Por ejemplo estoy en el estado presente paro (Q1=0, Q1=0) si las variables de entrada son (I1=0, I2=0), miro en el DTE cuál sería el estado siguiente, como la transición sale y entra al mismo estado, en las variables (t+1) de Q1 y Q0 tendré que poner cero en ambas también y así igual para todas las combinaciones posibles de Q1 Q0 correspondientes al estado presente.


Los siguientes campos a rellenar son las entradas de los Flip-Flop en este caso D0 y D1, para ello necesitamos la ayuda de la tabla de excitación del biestable. Mira la figura de abajo, donde se calcula el valor que tiene que tener D1 para una fila en concreto:

Como veis se trata de ir viendo que valores le corresponde a la entrada del flip-flop según los valores Q(t) y Q(t+1) que tengamos en cada fila.

Ya solo queda rellenar los valores del campo variables de salida (S1 y S0). Lo podemos hacer fácilmente mirando el DTE. Y poniendo los valores de la salida en función del estado presente en que nos encontremos.


Nota: en este ejemplo coincide por casualidad la codificación del estado con el valor de las variables de salida, pero es una simple coincidencia.


Pues ya tenemos nuestra tabla de verdad completa. Ahora toca obtener las funciones de salida, previamente es aconsejable obtener las expresiones mínimas por un método de simplificación como los diagramas de Karnaugh.

Una vez obtenida las funciones de salida simplificadas, ha llegado la hora de construir nuestro circuito y simularlo. Lo podemos hacer con Proteus, pero existe otro IDE que es perfecto por su sencillez para este tipo de circuitos. Se trata logisim, que además se puede descargar de forma gratuita desde la página del autor, el circuito terminado sería el siguiente:

Fuentes de información

Autómatas finitos (wikipedia)
IDE BOOLE-DEUSTO
Logisim

Para saber como implementar un autómata secuencial finito en un PIC mirar este artículo.

Un saludo y hasta pronto.