Introducción a las Máquinas de Estados

Una máquina de estados finitos (FSM) es un sistema digital que puede estar en uno de un número finito de estados en cualquier momento. Transiciona entre estados basándose en entradas y una señal de reloj, y produce salidas basadas en el estado actual (y posiblemente en las entradas). Las FSMs son la clave para diseñar cualquier sistema digital con comportamiento de secuenciación, desde semáforos hasta unidades de control de CPU.

Objectives

• Definir estados, transiciones, entradas y salidas en una FSM
• Dibujar e interpretar diagramas de estado
• Comprender la estructura general de una FSM: lógica combinacional + registro de estado
• Distinguir entre máquinas Moore y Mealy (introducción)
• Diseñar FSMs simples para problemas del mundo real

Key Takeaways

• FSM = estados + transiciones + entradas + salidas, sincronizados por un reloj
• Los diagramas de estado usan círculos (estados) y flechas (transiciones)
• Hardware: registro de estado (flip-flops) + lógica de estado siguiente + lógica de salida
• Número de flip-flops: ceil(log₂(número de estados))
• Las FSMs son la base de todo el diseño de controladores digitales

Applications

• Controladores de Protocolo: USB, Ethernet, SPI todos usan FSMs para el manejo de protocolos.
• Máquinas Expendedoras: Aceptan monedas, rastrean el total, dispensan producto.
• Semáforos: Secuenciación a través de verde-amarillo-rojo con solicitudes de peatones.
• Unidades de Control de CPU: El ciclo buscar-decodificar-ejecutar es una FSM.

Practice Problems

Problem 1: Un semáforo cicla Verde→Amarillo→Rojo→Verde. ¿Cuántos estados tiene esta FSM?

Problem 2: Dibuja un diagrama de estado para un torniquete con moneda (estados: Bloqueado, Desbloqueado).

Problem 3: ¿Cuántos flip-flops se necesitan para codificar 5 estados?

Problem 4: ¿Cuál es la diferencia entre la lógica de estado siguiente y la lógica de salida en una FSM?