Máquina de Estado Algorítmica ASM

Se recomienda inicialmente consultar: http://es.wikipedia.org/wiki/M%C3%A1quina_de_estados_algor%C3%ADtmica

Un algoritmo es una secuencia de pasos bien definida que produce una secuencia deseada de acciones en respuesta a una secuencia dada de entradas.

Un diagrama ASM (Algorithmic State Machine) es una herramienta conveniente para expresar los algoritmos que serán realizados por circuitos lógicos secuenciales.

Se emplean tres elementos para construir diagramas ASM:

  * Caja de estado: RECTÁNGULO: Representa un estado del circuito y equivale a un nodo del diagrama de estados. En la caja se etiqueta el nombre del estado.

  * Caja de decisión: ROMBO: Representa una decisión de transición de estado con base en una prueba de una entrada del circuito. Una caja de decisión tiene un único punto de entrada y dos puntos de salida.

  * Caja de salida condicional: OVALADA: Por lo general se ubican en la ruta entre una caja de decisión y una caja de estado. Tiene una única entrada y un punto de salida.

En las Máquinas de Estado Algorítmicas existen dos grandes bloques: La UNIDAD DE CONTROL y la UNIDAD DE PROCESO, conocida también como el PROCESADOR DE DATOS.

EJERCICIO: Se requiere implementar una máquina ASM que realice lo siguiente:

1. Al activar un PULSADOR se dá una señal de START (Inicio) que hace que un contador 74190 cuente ascendentemente desde el 0 hasta el 9, cada segundo.Antes de dar el START el contador estaba bloqueado en 0.
2. Cuando el contador llega al 9, automáticamente sigue contando luego descendentemente, hasta llegar nuevamente al 0.
3. El conteo ascendente y descendente lo tiene que hacer 5 veces, cuenta que realiza un segundo contador 74190.
4. Al final de los 5 ciclos, ambos contadores 74190, se bloquean en 0, hasta tanto no se de un nuevo pulso de START para repetir la operación.
5. Mientras están los contadores bloqueados se enciende un LED AMARILLO:
6. Al estar el primer 74190 en conteo ASCENDENTE enciende un LED VERDE.
7. Al estar el primer 74190 en conteo DESCENDENTE enciende un LED ROJ0.

SOLUCIÖN:

En el procesador de datos disponemos de 2 contadores 74190 y 3 flip-flops J-K así:

•  C1 (74190): cuenta ascendente y descendente (0...9,  9...0)
•  C2 (74190): cuenta los ciclos (0...5)
• F1: Enciende o apaga el LED AMARILLO
• F2: Enciende o apaga el LED VERDE
• F3: Enciende o apaga el LED ROJO

La Unidad de control va a disponer de MULTIPLEXOR , Flip-Flops D y DECODIFICADOR.

Paso 1:  DIAGRAMA ASM.

Para analizar el diagrama lo hacemos por bloques  ASM.  El bloque ASM se inicia con una casilla de estados. Nuestro diagrama está constituido por 3 bloques ASM debido a sus 3 casillas de estado S0,S1,S2.

• BLOQUE S0: La máquina ASM inicia con el flip-flop F1 en nivel alto, para que el Led Amarillo esté encendido, los contadores deben estar reseteados. Esta situación se mantiene si no se acciona el pulsador de arranque (START). Al oprimir el pulsador se coloca F1 en 0 para apagar el Led amarillo y se fija el Flip-flop F2 en alto para encender el led Verde.

• BLOQUE S1: Un periodo de reloj después de haber accionado el pulsador se incrementa el contador C1. Mientras no llegue al 8, estando el detector D1 en 0, sigue incrementando cada vez que llegue el flanco de subida del reloj. Al llegar al 8, D1 = 1, incrementa por última vez, llegando al 9, y simultáneamente F2 =0, F3 =1, apagándose el Led Verde y encendiéndose el led Rojo.

• BLOQUE S2:Un periodo de reloj después de haber llegado C1 al 9, decrementa pasando al 8, y lo sigue haciendo mientras D2 =0, al no detectarse que el contador C1 ha llegado al 1. Cuando D1 = 1, es porque el contador ha llegado al 1, y en esta ocasión en el siguiente pulso de reloj, la casilla de estados S2 le ordena a C1 que vuelva a decrementar, pasando a 0, y simultáneamente, debido a que la casilla condicional que lo ordena está en el mismo bloque ASM, los flip-flops F2 y F3 se colocan en 1 y 0 respectivamente, con lo cual se enciende el led Verde nuevamente y se apaga el Led rojo, indicando que se terminó el conteo descendente y vuelve C1 a contar ascendentemente.Cuando C1 ha terminado de contar en forma descendente, se incrementa el contador C2, el cual lleva la cuenta del número de ciclos.Mientras el detector D3 = 0, C1 sigue incrementando de 0 a 9, y decrementando enseguida de 9 a 0. Cuando D3 = 1, ello quiere decir que si C2=5, ya se han realizado los 5 ciclos, F3=0, se apaga el led Rojo, y al volver al bloque S0, se enciende el Led amarillo, quedando los 2 contadores reseteados, esperando que se dé un nuevo pulso de START para repetir la operación.

Paso 2: Tomamos la UNIDAD DE CONTROL como una caja negra, cuyas entradas las dan las casillas de decisión y las salidas las casillas de estados, e implementamos el PROCESADOR DE DATOS compuesto por los 2 contadores 74190 y los 3 flip-flops J-K. Primero implementamos los contadores y luego los flip-flops:

CONTADOR C1: 

• La unidad de control inicia con S0=1, S1=0,S2=0, indicando que la máquina ASM está ubicada en el bloque S0. Como S0 = 1, el inversor coloca la entrada LOAD del 74190 en nivel bajo, y como las entradas D,C,B,A están todas a tierra, C1 se coloca en 0, tal como lo exige la primera casilla de estados S0 (C1<--0). Así permanece mientras la señal de START sea Cero. 

• Al accionar el pulsador del  START la unidad de control pasa a S0=0,S1=1,S2=0, pues se va al bloque S1. Al llegar la máquina ASM al bloque S1, como la entrada DOWNUP =0, porque está conectada a la salida S2 de la unidad de control, como la entrada Enable G del contador está a tierra, y LOAD = 1 (S0 invertida), entonces se dan las condiciones para que C1 incremente mientras esté en el bloque S1.

• Al llegar al Bloque S2 (S0=0, S1=0, S2=1), lo cual hace que LOAD =1, G=0, DOWNUP=1, y por consiguiente en este bloque C1 tiene que contar en forma descendente.

CONTADOR C2: 

• En el bloque S0 debe estar reseteado (C2<--0), lo cual lo hace el inversor que maneja la entrada de carga del 74190.

• En el bloque S1, C2 debe estar bloqueado en 0. Para ello enviamos el 1 de S1 a través de una compuerta OR a la entrada G de enable del contador.

• En el bloque S2, C2 está bloqueado mientras que el detector D2 =0, por esta razón, al invertir D2 y enviarla al enable G de C2 a través de la otra entrada de la compuerta OR inhibimos el conteo. Estando en el estado S2 (S2=1), y D2=1, la compuerta NAND al tener dos niveles altos en sus entradas, coloca un 0 en su salida, y como la NAND va a la entrada DOWNUP, DOWNUP=0, G=0, LOAD=1, y C2 incrementa sólamente cuando se presenten estas condiciones.  Al terminar su conteo, y volver al bloque S0 (C2<--0), y cambia el 5 por el 0.

DETECTORES:

La unidad de control avanza de bloque en bloque de acuerdo a sus entradas START, y los detectores D1,D2,D3.

• D1: Como D1 está ubicado en el bloque S1 donde C1 incrementa desde 0, cuando C1 llega al 8=(1000)2, QD=1, por consiguiente la salida QD de C1 es igual a D1.

                                  QD QC QB QA

                                   0     0    0     0

                                   0     0    0     1

                                   0     0    1     0

                                   0     0    1     1

                                   0     1    0     0 

                                   0     1    0     1

                                   0     1    1     0

                                   0     1    1     1
                                  1     0    0     0

• D2: Como es el detector en el bloque S2 donde C1 decrementa debe analizarse el conteo descendente:

                                  QD   QC   QB   QA

                                   1       0       0       1

                                   1       0       0       0  

                                   0       1       1       1

                                   0       1       1       0

                                   0       1       0       1

                                   0       1       0       0

                                   0       0       1       1

                                   0       0       1       0

                                   0       0       0       1  

     

La compuerta NOR con las 3 entradas QD,QC,QB produce salida en nivel alto al detectar el 1 decimal en conteo descendente.

• D3: la detección de cuando C2 ha llegado al 5 al contar ascendentemente se hace a través de una compuerta AND de entradas QC y QA.

                                QD  QC   QB   QA

                                  0     0       0       0  

                                  0     0       0       1

                                  0     0       1       0

                                  0     0       1       1

                                  0     1       0       0

                                  0     1       0       1    

Pasamos ahora a mirar como implementamos los 3 flip-flops que manejan los Leds, para lo cual tomamos nuevamente la UNIDAD de CONTROL como una caja negra y 3 flip-flops J-K de salidas F1,F2 y F3:

FLIP-FLOP F1 (Led amarillo): De acuerdo al diagrama ASM, F1<--1, cuando está en la casilla de estado S0, y se coloca en 0 en el mismo bloque cuando START = 1. Por consiguiente si la entrada J = S0, y la entrada K está a una compuerta AND con S2 y START como entradas, ello hace que F1 sea 1 al iniciarse la máquina y se apague el led amarillo cuando K=1, estando J = 1, por la conmutación del flip-flop.

FLIP-FLOP F2 (Led verde): Hay 2 posibilidades para que el led verde se encienda (F2<--1), o sea para que J(F2) = 1 1, cuando S0=1, Start =1,  o, cuando S2=1,D3=0, por ello J(F2)= S0.S + S2.D3'.  Como el led verde se apaga (f2<--0) solo cuando S1=1,D1=1, entonces K(F2) = S1 D1.

FLIP-FLOP F3 (Led rojo): J(F3)= S1 D1 (El led rojo enciende cuando se apaga el verde). El led rojo se aapaga en dos ocasiones, luego:. K(F3) = S2 D3 + S2 D3'.

Paso 3: DISEÑO DE LA UNIDAD DE CONTROL.

Se ván a utilizar 2 Multiplexores de 4 entradas/1 salida, 2 flip-flops D y un decodificador de 2 entradas/3 salidas. 

Observe en el esquemático las siguientes consideraciones:

• La entrada INH del multiplexor es un Enable, que debe estar a tierra para que el multiplexor quede habilitada.
• Las entradas de selección S1 y S0  de los multiplexores son las salidas Q1 y Q0 de los flip-flops D.
• El decodificador de 2 entradas/3 salidas fue implementado en discreto con compuertas AND e Inversores; las entradas del decodificador son las salidas de los Flip-Flops D y las salidas del decodificador son las salidas de la unidad de control.
• Las entradas de los multiplexores responden a una lógica de acuerdo al diagrama ASM en sus casillas de decisión donde están presentes las entradas de la unidad de control: el pulso de Start y los detectores D1,D2,D3.
• La entrada de datos D3 de los multiplexores no es requerida,por consiguiente no se utiliza.

Veamos en detalle como se conectan las entradas de la Unidad de Control a las entradas de los Multiplexores, para lo cual es indispensable que el lector tenga a la mano el Diagrama ASM de la máquina:

• Por Reset-Power-On los flip-flops inician reseteados, de tal manera que Q1=0,Q0=0. Esto hace que S1=S0=0,  y en cada multiplexor la entrada de datos D0 se conecte a la salida del mismo.Como la entrada D0 de MUX1 está a tierra, y la del MUX2 está a la entrada S(Start), entonces si S=0, en el siguiente flanco de reloj, las entradas de los flip-flops van a ser 00, y los flip-flops dejen pasar estos datos, de tal manera que en la salida del decodificador vá a estar S0=1, S0=0,S2=0. Si S=1, el estado siguiente de los flip-flops será 01, y el decodificador tendrá: S0=0,S1=1,S2=0, indicativo que la máquina avanzó del bloque S0 al S1, tal como lo exige el diagrama ASM.

• Al estar la máquina en el bloque S1,  Q1=0,Q0=1, lo cual hace que los multiplexores conecten sus entradas de datos D1 a sus salidas.La entrada D1 de MUX1  va al detector D1, y la de MUX2 va a D1´ .  Esto hace que si el detector D1 = 0, Q1 y Q0 siguen en 01, pero si el detector D1=1, Q1Q0 cambian a 10, y el docodificador saca a su salida S0=0, S1=0, S2=1, indicando que ha habido transición del bloque S1 a S2.

• Al llegar Q1=1, Q0 = 0, (Bloque S2), el diagrama ASM nos indica lo siguiente:

1. Si  D2 = 0, el estado siguiente de los flip-flops es Q1=1,Q0=0 (Permanece en el bloque S2)
2. Si D2 =1, D3 = 0,  el estado siguiente de los flip-flops es Q1=0,Q0=1 (Cambia al bloque S1)
3. Si D2 =1, D3 = 1,  el estado siguiente de los flip-flops es Q1=0,Q0=0 (Cambia al bloque S0)

Si la anterior información  la organizamos en una tabla nos queda así:

                       ESTADO SIGUIENTE         CONDICIÓN DE 

                                   Q1  Q0                    LOS DETECTORES        

                                     0    0                              D2  D3

                                     0    1                              D2  D3'

                                     1    0                              D2' 

Inspeccionando la tabla deducimos que la entrada de datos D2 de MUX1, asociada a Q1,  debe estar conectada al detector D2  con un inversor:  D2´

Así mismo la entrada de datos D0 de MUX2, que es la que está asociada con Q0, debe ser D2.D3´.

SIMULACIÖN DE LA UNIDAD DE CONTROL EN ALTERA:

UNIDAD DE CONTROL EN ispLEVER CON ABEL (Máquina de Moore)

Tenemos que elaborar el diagrama de estados de la UNIDAD de CONTROL:

El programa en ABEL es el siguiente:

Al efectuar su simulación en ispLEVER se comprueba su correcto funcionamiento:

EJERCICIO: Simular en Altera el correcto funcionamiento de la Máquina ASM descrita en el presente documento.