bitGateLab Digital · Aprende
Abrir el simulador
Aprende › Tema 11
Máquinas de estados Moore y Mealy: diseño completo
Lectura de 7 min · Equipo bitGateLab
Una máquina de estados finitos (FSM) es un circuito secuencial que "recuerda" en qué paso de un proceso va. Semáforos, cerraduras con clave, controladores de elevador y receptores de comunicación serie son máquinas de estados. Aquí vas a ver los dos modelos clásicos, Moore y Mealy, y vas a seguir un diseño completo desde la descripción en palabras hasta las ecuaciones de los flip-flops, con un detector de la secuencia 101.
Partes de una máquina de estados
Toda FSM síncrona tiene tres bloques:
- Registro de estado: n flip-flops (casi siempre tipo D) que guardan el estado actual; alcanzan para hasta 2n estados.
- Lógica de estado siguiente: combinacional; calcula el próximo estado a partir del estado actual y las entradas.
- Lógica de salida: combinacional; calcula las salidas.
La diferencia entre los dos modelos está en el último bloque:
- Moore: las salidas dependen solo del estado actual. Se escriben dentro del círculo de cada estado (por ejemplo S3/1).
- Mealy: las salidas dependen del estado y de las entradas. Se escriben sobre las flechas (entrada/salida, por ejemplo 1/1).
El problema: detector de la secuencia 101
Una entrada serie X llega sincronizada con el reloj, un bit por ciclo. La salida Z debe valer 1 cada vez que los últimos tres bits recibidos sean 1, 0, 1. Se permite traslape: en la cadena 10101 hay dos detecciones, porque el último 1 de la primera secuencia es el primero de la siguiente.
El primer paso es decidir qué debe recordar la máquina. Cada estado representa "cuánto de la secuencia llevo":
- S0: no llevo nada útil.
- S1: el último bit fue 1.
- S2: los últimos bits fueron 1, 0.
- S3: acabo de recibir 1, 0, 1 (Z = 1).
Diagrama y tabla de estados (Moore)
Para cada estado y cada valor de X pregúntate: con este nuevo bit, ¿cuál es el sufijo más largo que coincide con el inicio de 101? Ese sufijo define el estado siguiente.
| Estado actual | X = 0 | X = 1 | Z |
|---|---|---|---|
| S0 | S0 | S1 | 0 |
| S1 | S2 | S1 | 0 |
| S2 | S0 | S3 | 0 |
| S3 | S2 | S1 | 1 |
Fíjate en dos transiciones que se equivocan con frecuencia. En S1 llega otro 1: la cadena termina en 11, y el último 1 sigue sirviendo como inicio, así que la máquina se queda en S1. En S3 llega un 0: la cadena termina en 1010, cuyo sufijo 10 coincide con el inicio de 101, así que va a S2 y no a S0. Eso es lo que permite el traslape.
Asignación de estados y ecuaciones
Con 4 estados bastan 2 flip-flops D (Q1 Q0). La asignación más directa es la binaria: S0 = 00, S1 = 01, S2 = 10, S3 = 11. Con flip-flops D la tabla de excitación es trivial, porque D = Q+.
| Q1 | Q0 | X | Q1+ = D1 | Q0+ = D0 |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 | 1 |
Simplificación:
- D0 vale 1 exactamente en las filas con X = 1, así que D0 = X. Tiene sentido: en esta asignación Q0 = 1 significa "el último bit fue 1".
- D1 = Σm(2, 5, 6) con las variables en el orden Q1 Q0 X. Los minitérminos 2 (010) y 6 (110) son adyacentes y forman Q0·X. El 5 (101) no tiene vecinos en 1 y queda solo: Q1·Q0·X. D1 = Q0·X + Q1·Q0·X.
- La salida de Moore solo depende del estado: Z = Q1·Q0.
El circuito queda con 2 flip-flops D, una AND de 2 entradas para Z, y para D1 una AND de 2, una AND de 3 y una OR de 2 (más los inversores de Q0 y X).
Verificación con una secuencia de prueba
Entrada X = 1 0 1 0 1 1 0 1, partiendo de S0. Estado después de cada flanco:
| Flanco | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| X | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 1 |
| Estado | S1 | S2 | S3 | S2 | S3 | S1 | S2 | S3 |
| Z | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 |
Hay tres detecciones: en los bits 1 a 3, 3 a 5 (traslape) y 6 a 8. Comprueba el flanco 4 con las ecuaciones: estado S3 = 11 y X = 0, D1 = 1·1 + 1·0·0 = 1 y D0 = 0, estado siguiente 10 = S2. Coincide.
La versión Mealy
En Mealy la salida va en la transición, así que el estado S3 sobra: la detección ocurre "al llegar el 1 estando en S2". Con tres estados A (nada), B (último bit 1) y C (últimos bits 1, 0):
| Estado | X = 0 | X = 1 |
|---|---|---|
| A | A / 0 | B / 0 |
| B | C / 0 | B / 0 |
| C | A / 0 | B / 1 |
Siguen haciendo falta 2 flip-flops, pero la salida Z = 1 aparece en el mismo ciclo en que llega el último 1, un ciclo antes que en la versión Moore.
Errores comunes
- Mandar a S0 todas las transiciones que "fallan", sin revisar qué parte de la secuencia todavía sirve; así se pierden detecciones con traslape.
- Escribir salidas sobre las flechas en una máquina Moore o dentro de los estados en una Mealy.
- Olvidar las combinaciones de flip-flops no usadas (por ejemplo, el código 11 en la versión Mealy): hay que decidir a dónde van o marcarlas como X y verificar que la máquina regrese a la secuencia.
- Leer la salida de una Mealy en cualquier momento: debe muestrearse justo antes del flanco, cuando la entrada ya es estable.
- Cambiar la entrada X justo en el flanco del reloj al probar la máquina.
Pruébalo en el simulador
Una vez que tienes las ecuaciones, armar el detector toma pocos minutos y el cronograma te deja comprobar cada transición.
- Coloca dos flip-flops D con el mismo reloj; nombra sus salidas Q1 y Q0.
- Conecta la entrada X directamente a D0.
- Arma D1 = Q0·X + Q1·Q0·X con dos inversores, dos AND y una OR, y conéctalo a D1.
- Conecta una AND de Q1 y Q0 a un indicador para Z.
- Cambia X antes de cada flanco siguiendo la secuencia 1 0 1 0 1 1 0 1 y observa en el cronograma que Z se enciende después de los flancos 3, 5 y 8.
Ejercicios
- Con traslape, ¿cuántas veces detecta 101 la máquina en la cadena 1010101?
Respuesta
Tres veces: en los bits 1 a 3, 3 a 5 y 5 a 7.
- Rehaz la tabla Moore del detector de 101 sin traslape (después de una detección se empieza de cero).
Respuesta
Solo cambia la fila S3: con X = 0 va a S0 y con X = 1 va a S1. Las demás filas quedan igual.
- Con la asignación de la versión Mealy A = 00, B = 01, C = 10, obtén Z.
Respuesta
Z = 1 solo en el estado C con X = 1: Z = Q1·Q0·X. Si el código 11 nunca aparece se puede marcar como X y queda Z = Q1·X.
- ¿Cuántos flip-flops necesita como mínimo una máquina de 9 estados?
Respuesta
4, porque 23 = 8 no alcanza y 24 = 16 sí.
Para repasar los flip-flops que forman el registro de estado consulta latches y flip-flops.