TEORÍA DE MÁQUINAS DE ESTADO (FSM)

La teoría de máquinas de estado es el nombre con el que se conocen los métodos de Análisis y Diseño de Circuitos Secuenciales Sincrónicos. Esta lección constituye una introducción al tema del capítulo, donde se definirá lo que son las máquinas de estado y los conceptos básicos para entender la metodología de Análisis y Diseño de Circuitos Secuenciales.

Las máquinas de estado son circuitos secuenciales que se encuentran constituidos por una etapa combinacional y una etapa de memoria, relacionadas de tal forma que conforman un sistema secuencial para algún propósito especial. Los registros y contadores con entradas asincrónicas son ejemplos de este tipo de sistemas secuenciales.

MÁQUINAS DE ESTADO DE MEALY Y MOORE

Los circuitos secuenciales se clasifican dentro de una categoría conocida como máquinas de estado, de la cual se distinguen comúnmente dos tipos:

• Máquina de Mealy: En esta máquina de estados las salidas se encuentran determinadas por el estado interno del sistema y por las entradas no sincronizadas con el circuito. El diagrama de bloques representativo de esta máquina se muestra en la figura 7.1.1. donde se observa que las salidas del sistema son tanto sincrónicas como asincrónicas.
  
  

Figura 7.1.1. Maquina de estados de Mealy

• Máquina de Moore: Las salidas solo dependen del estado interno y de cualquier entrada sincronizada con el circuito, como se observa en la figura 7.1.2. donde las salidas del sistema son unicamente sincrónicas. Un ejemplo de este tipo de máquinas de estado son los contadores (ver capítulo 6).

Figura 7.1.2. Maquina de estados de Moore

Los circuitos secuenciales se caracterizan por tener una etapa combinacional y otra de memoria conformada por flip-flops. En la figura 7.1.3. se puede observar un ejemplo particular de este tipo de circuitos, el cual corresponde a una Maquina de estado de Mealy. Observe que hay salidas que dependen de la etapa de memoria y hay una salida que depende directamente de la etapa combinatoria.

Figura 7.1.3. Circuito Secuencial de ejemplo

Con base en el circuito de la figura 7.1.3. se dará una descripción de las herramientas básicas que son empleadas para el Análisis y Diseño de Circuitos Secuenciales. Entre estas herramientas se encuentran las ecuaciones lógicas, las los diagramas de estado, las tablas de estado, las tablas de transición y los mapas de Karnaugh.

Ecuaciones Lógicas

Las ecuaciones lógicas son funciones que definen la relación existente entre los estados de entrada y los estados de salida del sistema. Para determinar las ecuaciones lógicas de la máquina de estados de la figura 7.3.1. inicialmente se deben identificar los estados siguientes. Estos estados corresponden a aquellos que ocurren después de una transición en la señal de reloj de los flip-flops. Recuerde que para los flip-flops tipo D el estado siguiente (Q_i+1) es igual al estado de la entrada D. Teniendo en cuenta lo anterior las ecuaciones lógicas para los flip-flops A y B del circuito de la figura 7.1.3 serían las siguientes:

A = D_A = A·X + B·X

B = D_B= A’·X

La salida Y esta dada por:

Y = (A + B)·X’

Observando esta última ecuación se concluye que la salida (Y) es función del estado presente del sistema (A y B) y de la entrada asincrónica (X).

Las ecuaciones lógicas en los circuitos secuenciales tienen una estructura formada por dos clases de estados:

• Los estados siguientes, los cuales se agrupan al lado izquierdo de la expresión y representan las variables dependientes del sistema. El estado de estas variables cambia en el momento que ocurra un transición en la señal de reloj.
• Los estados actuales y entradas del sistema. Agrupados al lado derecho de la exprexión, constituyen las variables inpendientes, las cuales pueden o no cambiar en sincronía con el sistema.

Cuando las ecuaciones de estado contienen varios términos, se pueden simplificar empleando metodologías de reducción de términos como Algebra de Boole, Mapas de Karnaugh, o mediante el Algoritmo de Quine-McCluskey , las cuales fueron presentadas en el Capitulo 2.

Tablas de Estado

Una tabla de estado es un listado que contiene la secuencia de los estados de entradas, estados internos y salidas del sistema, considerando todas las posibles combinaciones de estados actuales y entradas. Las tablas de estado por lo general se divididen en tres partes: estados actuales, estados siguientes y salidas, tal como se muestra en la tabla 7.1.1.

Estados actuales		Entrada	Estados siguientes		Salida
A	B	X	A	B	Y
0	0	0	0	0	0
0	0	1	0	1	0
0	1	0	0	0	0
0	1	1	1	1	1
1	0	0	0	0	0
1	0	1	1	0	1
1	1	0	0	0	0
1	1	1	1	0	1

Tabla 7.1.1. Tabla de estado (circuito Figura 7.1.3)

La tabla de estado para un circuito secuencial con m flip-flops y n entradas tiene 2^m+n filas. El estado siguiente tiene m columnas, y el número de columnas depende del número de salidas.

Existe una forma mas conveniente de organizar la información en la tabla de estado, la cual se muestra en la Tabla 7.1.2, donde los estados se agrupan de tal modo que la tabla se puede traducir a un diagrama de estados. Al igual que la tabla anterior esta tiene tres secciones: estados actuales, estado siguientes y salidas, sin embargo los estados se agrupan dependiendo del valor de las entradas. La sección de estados actuales agrupa los estados que ocurren antes de una transición en la señal de reloj, la sección de estados siguientes lista aquellos que ocurren después de la transición del reloj y la sección de salidas reúne los estados que se dan en el mismo instante de los estados actuales.

Estado Actual	Estado Siguiente		Salida
	X=0	X=1	X=0	X=1
AB	AB	AB	Y	Y
00	00	01	0	0
01	00	11	1	0
10	00	10	1	0
11	00	10	1	0

Tabla 7.1.2. Tabla de estado (forma simplificada)

Haciendo un análisis de la operación del circuito de la figura 7.1.3. se puede observar lo siguiente: Cuando la variable X=0 los estados actuales A y B cambian a 0 después de la transición de reloj , y cuando X=1, los estados de las salidas se comportan tal como se resume en la tabla 7.1.2. Se plantea como ejercicio verificar la información de la tabla.

Diagramas de Estado

Un diagrama de estados es una representación gráfica que indica la secuencia de los estados que se presentan en un circuito secuencial, teniendo en cuenta las entradas y salidas. El diagrama se forma con círculos y líneas. Los circulos representan los estados del circuito secuencial y cada uno de ellos contiene un número que identifica su estado. Las líneas indican las transiciones entre estados y se marcan con dos números separados por un (/), estos dos números corresponden a la entrada y salida presentes antes de la transición. A manera de ejemplo observe la línea que une los estados 00 y 01 en el diagrama de estado de la figura 7.1.4. Esta línea marcada como 1/0 indica que el circuito secuencial se encuentra en el estado 00 mientras la entrada X=0 y la salida Y=0, y que después de que ocurra una transición en la señal de reloj el estado cambia a 01.

Figura 7.1.4. Diagrama de estados correspondiente a la Tabla 7.1.2

Las líneas que salen y regresan al mismo círculo indican que no hay cambio en el estado, cuando se presentan la entrada y salida indicados.

Tablas de Transición de flip-flops

Las tablas de transición se usan en conjunto con las de estado y representan la tabla de verdad de los flip-flops con los cuales se desea implementar el circuito secuencial. La tabla contiene los estados actuales y siguientes según el estado de las entradas de los flip-flops. La tabla 7.1.3 corresponde a la tabla de transición del flip-flop JK.

Transiciones de Salida		Entradas al flip-flop
Qi	Qi+1	J	K
0	0	0	X
0	1	1	X
1	0	X	1
1	1	X	0

Tabla 7.1.3. Tabla de transición del flip-flop JK

En la tabla, Q_i corresponde al estado actual y Q_i+1 al estado siguiente, J y K son las entradas de los flip-flops. La información sombreada en la tabla se interpreta de la siguiente forma: cuando el estado presente de la salida Q=0 y las entradas J=1 y K=X (X indica una condición de no importa, 1 o 0), después de un pulso de reloj en el flip-flop la salida cambia al estado siguiente Q=1.

Mapas de Karnaugh

Generalmente la tablas de estado y de transición de los flip-flops se fusionan en una sola para agrupar la información de tal forma que permitan construir los Mapas de Karnaugh para simplificar las funciones lógicas. La tabla 7.1.4 corresponde a una tabla de estado de un contador de tres bits con flip-flops JK. Observe que esta tabla incluye las entradas J y K para cada una de la transiciones (estado actual a estado siguiente). Las regiones sombreadas en la tabla indican que el estado Q_i cambia estando presentes las entradas J_i y K_icorrespondientes después de una transición del reloj.

Estado Actual			Estado Siguiente			Entradas de los flip-flop
Q2	Q1	Q0	Q2	Q1	Q0	J2	K2	J1	K1	J0	K0
0	0	0	0	0	1	0	X	0	X	1	X
0	0	1	0	1	0	0	X	1	X	X	1
0	1	0	0	1	1	0	X	X	0	1	X
0	1	1	1	0	0	1	X	X	1	X	1
1	0	0	1	0	1	X	0	0	X	1	X
1	0	1	1	1	0	X	0	1	X	X	1
1	1	0	1	1	1	X	0	X	0	1	X
1	1	1	0	0	0	X	1	X	1	X	1

Tabla 7.1.4. Tabla de estado y transición de un contador de 3 bits

Los Mapas de Karnaugh se emplean para definir la lógica de las entradas de los flip-flops y se debe hacer uno para cada una de las entradas. La figura 7.1.5 corresponde al Mapa de karnaugh de la entrada J₁. de la tabla de estado 7.1.4.

Figura 7.1.5. Mapa de Karnaugh para el estado J₁

Observe que cada celda en el mapa representa uno de los estados actuales de la secuencia en la tabla de estado. Una vez asignados todos los estados posibles a cada celda en elMapa de Karnaugh se procede a simplicar y deducir las exprexiones lógicas. En la figura 7.1.5 se observa que la expresión correspondiente a la entrada J₁ es:

J₁ = Q₀

Esta expresión indica que en el circuito lógico la salida Q₀ debe ir conectada a la entrada J₁. En la siguiente lección se explicara de una forma detallada el procedimiento para el Diseno de Circuitos Secuenciales.