Los circuitos lógicos secuenciales tratados en el texto principal de este libro son estudiados en cursos universitarios superiores desde un punto de vista un poco más formal, utilizando un lenguaje un poco más elegante. En realidad, se está hablando de lo mismo. No hay introducción de nuevas técnicas de diseño que podamos considerar imprescindibles para lo que podemos lograr con lo que ya hemos cubierto. De cualquier modo, este Suplemento tiene como objetivo cubrir esta perspectiva un poco más formal con la finalidad de hacer este libro lo suficientemente flexible como para que pueda ser utilizado por estudiantes universitarios o por técnicos interesados en proseguir con estudios más formales en la materia de lógica digital.
Recordemos el contador binario de conteo ascendente construído con flip-flops J-K. Supóngase que hemos diseñado un contador binario de conteo ascendente de 4 bits usando cuatro flip-flops J-K, al cual denotaremos aquí como una máquina. En cualquier momento, entre un pulso de la señal de reloj y el pulso que le sigue para llevar de el contador de un estado al siguiente, podemos hablar del estado de la máquina. Si en un momento dado entre un pulso de reloj y el que le sigue nuestro contador binario de 4 bits tiene al primer flip-flop J-K en el estado Q1=1, si el segundo flip-flop está en el estado Q2=0, si el tercer flip-flop J-K está en el estado Q3=0 y si el cuarto flip-flop está en el estado Q4=1, entonces el estado de la máquina es Q1Q2Q3Q4=1001.
Puesto que, por diseño, esta es una máquina sin entradas, el siguiente estado de la máquina será Q1Q2Q3Q4=1010. No puede ser de otra manera, puesto que así se ha diseñado la máquina.
Veamos a continuación una representación para una máquina de estado finito (finite state machine) conocido como diagrama de estados:
Aquí tenemos una máquina que podemos suponer fue construída con dos flip-flops. Cada círculo representa uno de los estados de la máquina, la cual sólo puede estar en un estado en un momento dado. Podemos ver esta representación como un juego en el cual los círculos están dibujados en el suelo y en cualquier momento estamos situados en uno de los círculos. De acuerdo al diagrama, esta máquina puede estar en uno de los siguientes tres estados:
q1q0=00Las flechas exteriores (vértices) a los estados (círculos) que salen o llegan a un estado son la entrada o las entradas puestas en la máquina en un momento dado. En este caso, tenemos una máquina que posee una sola entrada designada como x. Veamos ahora lo que sucede en esta máquina dependiendo del valor de la entrada x y del estado q=q1q0 en el que se encuentre.
q1q0=01
q1q0=10
Si la máquina se encuentra en el estado q1q0=00 y la entrada es x=1, entonces en el siguiente "pulso de reloj" la máquina pasará al estado q1q0=01. Pero si la entrada es x=0 cuando la máquina se encuentra en el estado , entonces en el siguiente "pulso de reloj" pasará al estado q1q0=10.
Por otro lado, si la máquina se encuentra en el estado q1q0=01 y la entrada es x=1, entonces en el siguiente "pulso de reloj" la máquina pasará al estado q1q0=10. Pero si la entrada es x=0 cuando la máquina se encuentra en el estado q1q0=01, entonces en el siguiente "pulso de reloj" la máquina se mantendrá en el mismo estado, como si estuviese "atorada" sin poder salir de allí.
Así, este diagrama de estados describe por completo el comportamiento de la máquina para todos los estados posibles de la máquina.
Podemos clasificar las máquinas usando dos modelos diferentes:
(1) Como máquinas Moore.
(2) Como máquinas Mealy.
A continuación tenemos un ejemplo de una máquina Moore, llamada así en honor del Profesor Edward F. Moore (1925-2003) quien propuso este modelo matemático para el estudio de máquinas secuenciales:
La máquina Moore se distingue por ser una máquina en la cual dentro de cada círculo además de especificarse el estado de la máquina se especifican la salida o las salidas que se producen en dicho estado. Las salidas no son necesariamente iguales al estado de la máquina. Pueden serlo, como en el caso del contador binario de conteo ascendente de 4 bits mencionado previamente. Pero si cada una de las terminales Q del contador binario mencionado es conectada a una red de circuitos lógicos que convierte el conjunto de salidas en un conjunto de salidas distintas, entonces es obvio que las salidas producidas serán diferentes a los estados de la máquina. La notación utilizada dentro de cada círculo tiene una forma como 10/11, en donde la primera palabra binaria (10) nos indica el estado de la máquina y la segunda palabra binaria (11) nos indica la salida de la máquina que denominaremos z.
En el ejemplo mencionado para una máquina Mealy, tenemos una máquina que podemos suponer fue construída con dos flip-flops. De acuerdo al diagrama, esta máquina puede estar en uno de los siguientes tres estados:
q1q0=00 dando una salida de z1z0=01Como en el caso de una máquina de estado finito común y corriente que vimos al principio, las flechas exteriores a los estados (círculos) que salen o llegan a un estado son la entrada o las entradas puestas en la máquina en un momento dado. En este caso, tenemos una máquina Moore que también posee una sola entrada designada como x. El comportamiento de esta máquina dependiendo del valor de la entrada x y del estado q=q1q0 en el que se encuentre la máquina es similar a lo que vimos anteriormente, excepto que si la máquina se encuentra en el estado q1q0=00 tendrá una salida z=z1z0=01.
q1q0=01 dando una salida de z1z0=11
q1q0=10 dando una salida de z1z0=11
A continuación tenemos un ejemplo de una máquina Mealy:
La máquina Mealy se distingue por ser una máquina en la cual si la máquina está en cierto estado, entonces al aplicarle cierta entrada transicionará a otro estado produciendo cierta salida como consecuencia de la transición. La notación utilizada en los vértices tiene una forma como 1/0, en donde la primera palabra binaria (1) nos indica la entrada dada a la máquina y la segunda palabra binaria (0) nos indica la salida producida al llevarse a cabo la transición de un estado al siguiente.
En el ejemplo mencionado para una máquina Mealy, tenemos una máquina que nuevamente podemos suponer que fue construída con dos flip-flops. De acuerdo al diagrama, esta máquina puede estar en uno de los siguientes tres estados:
q1q0=00En este caso, tenemos una máquina Mealy que también posee una sola entrada designada como x. La forma de leer este diagrama de estado es la siguiente: Si la máquina se encuentra en el estado q1q0=00, entonces de acuerdo con la notación en el vértice, 1/1, si se le aplica a la máquina una entrada de 1 entonces en el siguiente "pulso de reloj" transicionará al estado q1q0=01 produciendo una salida de 1. Y por el contrario, si está en ese estado de q1q0=00 y se le aplica a la máquina una entrada de 0, entonces en el siguiente "pulso de reloj" la máquina transicionará al estado q1q0=11 produciendo una salida de 1.
q1q0=01
q1q0=11
Se puede demostrar, con rigor matemático, que toda máquina Moore es equivalente a una máquina Mealy, y viceversa. Con esto queremos decir que dada una máquina Moore podemos producir una máquina Mealy, o dada una máquina Mealy podemos producir una máquina Moore tal que ambas tendrán la misma secuencia de salidas q si ambas son alimentadas la misma secuencia en sus entradas x. La demostración para convertir una máquina Mealy en una máquina Moore requiere aumentar el número de estados.
De interés para nosotros es el hecho de que existen programas de computadora que nos permiten convertir cualquier máquina de estado finito en un circuito lógico formado por funciones lógicas básicas y flip-flops. Sin embargo, esto no se cubrirá en este Suplemento, porque como ya se dijo, constituye materia para un curso más avanzado impartido a nivel universitario, un curso en una materia conocida como Teoría de Autómatas.
Se encuentra disponible en Internet un tutorial que entra en mayores detalles sobre las definiciones formales y las aplicaciones prácticas de las máquinas Moore y las máquinas Mealy, en la siguiente dirección:
http://www.jflap.org/tutorial/
El índice general de este domicilio:
http://www.jflap.org
nos dá el acceso a un interesante programa educativo interactivo, el programa JFLAP, un conjunto de herramientas gráficas para ayudar en el aprendizaje de los conceptos básicos de la teoría de Lenguajes Formales y la Teoría de Autómatas.
