Lo que vas a aprender
- Qué es una máquina de estados y cómo se representa.
- La diferencia entre máquinas de Moore y de Mealy.
- Cómo pasar del diagrama a la tabla de estados.
- Cómo codificar los estados y obtener las ecuaciones con biestables D.
- El diseño completo de un detector de secuencia y de un semáforo.
Fundamentos teóricos
Elementos
- Estados: las situaciones posibles del sistema. Con biestables se pueden codificar hasta .
- Entradas y salidas.
- Función de transición: el estado siguiente según el estado actual y las entradas.
- Función de salida: las salidas según el estado (y quizá las entradas).
- Estado inicial, al que se llega con el reset.
Moore y Mealy
Estructura
Pasos de diseño
- Diagrama de estados a partir del enunciado.
- Tabla de estados: estado actual, entrada, estado siguiente y salida.
- Minimizar estados, si hay estados equivalentes (mismas salidas y mismos siguientes).
- Codificar cada estado en binario.
- Tabla de transición con los códigos: con biestables D, la entrada de cada biestable es el bit correspondiente del estado siguiente.
- Simplificar las ecuaciones con mapas de Karnaugh.
- Dibujar el circuito.
Codificación de estados
Ejemplos resueltos
Ejemplo 1 · Detector de la secuencia 11 (Moore)
Ejemplo 1 · Detector de la secuencia 11 (Moore)
Una entrada en serie; la salida cuando se han recibido dos unos seguidos.Estados: A (el último bit no fue 1), B (se ha recibido un 1), C (se han recibido dos o más unos seguidos; ).
Codificación A = 00, B = 01, C = 10, con biestables :, , .(El código 11 no se usa y se puede tomar como indiferente al simplificar.)
Ejemplo 2 · El mismo detector como Mealy
Ejemplo 2 · El mismo detector como Mealy
Solo hacen falta dos estados: A (el último bit fue 0) y B (el último bit fue 1).
Con A = 0 y B = 1: y . Un solo biestable, y la salida se activa en el mismo ciclo en que llega el segundo 1.
Ejemplo 3 · Detector de 101 con solapamiento (Mealy)
Ejemplo 3 · Detector de 101 con solapamiento (Mealy)
Estados: S0 (nada útil), S1 (llegó 1), S2 (llegó 10).
Al detectar 101 vuelve a S1, porque ese último 1 puede ser el principio de otra secuencia: con 10101 da dos detecciones.
Ejemplo 4 · Semáforo (Moore)
Ejemplo 4 · Semáforo (Moore)
Un semáforo con sensor de coches en la calle secundaria. La principal está en verde hasta que llega un coche.
Con codificación Gray (00, 01, 11, 10), cada transición cambia un solo bit. En la práctica, cada estado dura varios ciclos, con un contador que marca el tiempo.
Errores frecuentes
- Olvidar alguna transición. Desde cada estado tiene que haber una flecha para cada combinación de entradas.
- No definir el estado inicial ni el reset. Al encender, los biestables pueden arrancar en cualquier código.
- Dejar códigos sin usar sin pensar adónde van. Si por una interferencia la máquina cae en uno, debe volver a un estado válido.
- Mezclar Moore y Mealy en la misma tabla. Decide al principio dónde van las salidas.
- No contemplar el solapamiento en los detectores de secuencia.
Preguntas frecuentes
¿Cómo se implementan hoy las máquinas de estados?
¿Cómo se implementan hoy las máquinas de estados?
En FPGA y ASIC se describen en un lenguaje de descripción de hardware (VHDL o Verilog) con una sentencia
case sobre el estado, y la herramienta de síntesis elige la codificación y genera la lógica. En un microcontrolador se programan igual, con una variable de estado y un switch.¿Qué relación tienen con los autómatas de informática?
¿Qué relación tienen con los autómatas de informática?
Son la misma idea. En teoría de la computación, un autómata finito reconoce lenguajes regulares (los de las expresiones regulares). Las máquinas de Moore y Mealy son autómatas con salida.
Temas relacionados
Biestables
La memoria de la máquina.
Contadores y registros
Una máquina de estados especial.
Mapas de Karnaugh
Simplificar las ecuaciones.