> ## Documentation Index > Fetch the complete documentation index at: https://apuntes.simulab.es/llms.txt > Use this file to discover all available pages before exploring further. # Máquinas de estados finitos: Moore y Mealy, diseño paso a paso > Máquinas de estados finitos (FSM) en electrónica digital: estados, transiciones, diagrama y tabla de estados, máquinas de Moore y de Mealy, codificación de estados, diseño con biestables D paso a paso, detector de secuencias y semáforo, con ejemplos resueltos. Un semáforo, una máquina expendedora, el protocolo de un puerto serie o el control de un ascensor no responden solo a lo que pasa ahora, sino también a **lo que ha pasado antes**. Esa memoria se organiza en **estados**: "verde", "ámbar", "rojo"; "esperando moneda", "dando cambio". Una **máquina de estados finitos** describe un sistema así con un número finito de estados y unas reglas para pasar de uno a otro, y se implementa con [biestables](https://apuntes.simulab.es/electronica/logica-secuencial/biestables.md) y lógica combinacional. ## 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 $n$ biestables se pueden codificar hasta $2^n$. * **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*. En una máquina **síncrona**, el cambio de estado ocurre solo en el flanco del reloj. ### Moore y Mealy | | Moore | Mealy | | - | - | - | | Las salidas dependen de | Solo el estado | El estado **y** las entradas | | En el diagrama | La salida se escribe dentro del estado | La salida se escribe en la flecha: `entrada / salida` | | Respuesta | Un ciclo de reloj más tarde | En el mismo ciclo | | Estados necesarios | Suelen ser más | Suelen ser menos | | Salidas | Estables, sin *glitches* | Pueden cambiar a mitad del ciclo si cambia la entrada | ### Estructura ``` ┌──────────────┐ ┌──────────┐ entradas ──►│ lógica de │────►│ registro │──┐ estado ┌─►│estado siguiente│ │ (bies. D)│ │ actual │ └──────────────┘ └──────────┘ │ └─────────────────────────────────────┤ ▼ ┌──────────────┐ (solo Mealy) ───►│ lógica de │──► salidas │ salida │ └──────────────┘ ``` ### Pasos de diseño 1. **Diagrama de estados** a partir del enunciado. 2. **Tabla de estados**: estado actual, entrada, estado siguiente y salida. 3. **Minimizar** estados, si hay estados equivalentes (mismas salidas y mismos siguientes). 4. **Codificar** cada estado en binario. 5. **Tabla de transición** con los códigos: con biestables D, la entrada $D$ de cada biestable es el bit correspondiente del estado siguiente. 6. **Simplificar** las ecuaciones con [mapas de Karnaugh](https://apuntes.simulab.es/electronica/logica-combinacional/karnaugh.md). 7. Dibujar el circuito. ### Codificación de estados | Codificación | Biestables para $N$ estados | Ventaja | | - | - | - | | Binaria | $\lceil\log_2 N\rceil$ | Mínimo número de biestables | | Gray | $\lceil\log_2 N\rceil$ | Solo cambia un bit entre estados consecutivos | | One-hot | $N$ | Lógica muy simple y rápida; habitual en FPGA | ## Ejemplos resueltos > [accordion] Ejemplo 1 · Detector de la secuencia 11 (Moore) > > Una entrada $x$ en serie; la salida $z = 1$ 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; $z = 1$). > > | Estado | $x = 0$ | $x = 1$ | $z$ | > | - | - | - | - | > | A | A | B | 0 | > | B | A | C | 0 | > | C | A | C | 1 | > > Codificación A = 00, B = 01, C = 10, con biestables $Q_1Q_0$: > > $D_1 = x\,(Q_1 + Q_0)$, $D_0 = x\,\overline{Q_1}\,\overline{Q_0}$, $z = Q_1$. > > (El código 11 no se usa y se puede tomar como indiferente al simplificar.) > [accordion] 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). > > | Estado | $x = 0$ | $x = 1$ | > | - | - | - | > | A | A / 0 | B / 0 | > | B | A / 0 | B / 1 | > > Con A = 0 y B = 1: $D = x$ y $z = x\,Q$. Un solo biestable, y la salida se activa en el mismo ciclo en que llega el segundo 1. > [accordion] Ejemplo 3 · Detector de 101 con solapamiento (Mealy) > > Estados: **S0** (nada útil), **S1** (llegó 1), **S2** (llegó 10). > > | Estado | $x = 0$ | $x = 1$ | > | - | - | - | > | S0 | S0 / 0 | S1 / 0 | > | S1 | S2 / 0 | S1 / 0 | > | S2 | S0 / 0 | S1 / **1** | > > Al detectar 101 vuelve a S1, porque ese último 1 puede ser el principio de otra secuencia: con 10101 da dos detecciones. > [accordion] Ejemplo 4 · Semáforo (Moore) > > Un semáforo con sensor de coches $c$ en la calle secundaria. La principal está en verde hasta que llega un coche. > > | Estado | Principal | Secundaria | Siguiente | > | - | - | - | - | > | S0 | Verde | Rojo | S1 si $c = 1$; si no, S0 | > | S1 | Ámbar | Rojo | S2 | > | S2 | Rojo | Verde | S3 | > | S3 | Rojo | Ámbar | S0 | > > 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](https://apuntes.simulab.es/electronica/logica-secuencial/contadores.md) 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 > [accordion] ¿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`. > [accordion] ¿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 > [card] [Biestables](https://apuntes.simulab.es/electronica/logica-secuencial/biestables.md) > > La memoria de la máquina. > [card] [Contadores y registros](https://apuntes.simulab.es/electronica/logica-secuencial/contadores.md) > > Una máquina de estados especial. > [card] [Mapas de Karnaugh](https://apuntes.simulab.es/electronica/logica-combinacional/karnaugh.md) > > Simplificar las ecuaciones. This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.