Modelos de Moore y Mealy

01 · Punto de partida

Dos formas de decidir una salida

Una máquina de estados tiene dos funciones combinacionales: la que calcula el próximo estado y la que calcula la salida. Del próximo estado ya hablamos: depende del estado actual y de las entradas, y se captura en el flanco. De la salida hay dos versiones, que dan nombre a los dos modelos clásicos:

La expendedora y el torniquete del tema 22 eran máquinas de Mealy: «ENTREGA» o «destraba» aparecían en las flechas, porque dependían del par (estado, moneda). Si la salida fuera una luz que indica «puerta abierta», que solo depende de en qué estado está el sistema, sería Moore.

02 · Moore

Modelo de Moore

En una máquina de Moore la salida es una función únicamente del estado. En el diagrama, cada círculo lleva su salida escrita adentro, y las flechas llevan solo la entrada que las dispara. Como el estado vive en los flip-flops, la salida cambia sólo cuando el estado cambia, es decir, un pequeño tiempo de propagación después de cada flanco de reloj.

Consecuencias directas:

• Salidas estables durante todo el ciclo. Entre dos flancos el estado es constante; por lo tanto, la salida también. Las entradas pueden variar, ensuciarse o rebotar sin afectarla.
• Latencia de un ciclo como mínimo. Una entrada que llega en el ciclo k hace cambiar el estado en el flanco siguiente, y la salida refleja ese nuevo estado en el ciclo k + 1. La máquina nunca reacciona «en el acto».
• Más estados. Si dos situaciones iguales deben producir salidas distintas, necesitan estados distintos; por eso una máquina de Moore suele tener más estados que su equivalente de Mealy.
• Salida fácil de usar. Es una señal limpia, apta para controlar cargas, habilitar otros circuitos o servir de reloj de otro bloque.

Los contadores del curso son máquinas de Moore: la cuenta es el estado, y la salida es el estado mismo. También lo es el semáforo: las luces dependen de en qué paso del ciclo está, no de lo que pase en las entradas en ese instante.

03 · Mealy

Modelo de Mealy

En una máquina de Mealy la salida depende del estado y de las entradas. En el diagrama, cada flecha lleva entrada / salida. Como la salida es un circuito combinacional de las entradas y del estado, cambia cuando cambia cualquiera de los dos, y las entradas pueden moverse en cualquier momento del ciclo.

• Reacciona en el mismo ciclo. Una entrada nueva puede cambiar la salida de inmediato, sin esperar al flanco. Es la respuesta más rápida que permite una máquina síncrona.
• Menos estados. La salida adicional que aporta la entrada evita duplicar estados. Muchas especificaciones salen con la mitad de estados que en Moore.
• Salida no siempre estable. Mientras la entrada es estable, la salida también lo es; pero si la entrada rebota, es asíncrona o llega con retardos distintos, la salida se mueve con ella. Puede tener pulsos cortos fuera del reloj (glitches).
• Caminos de entrada a salida. Una cadena de máquinas de Mealy forma un camino combinacional que atraviesa varias de ellas, lo que complica el análisis de tiempos (tema 11).

04 · Comparación

Un mismo problema, dos máquinas

Un caso ideal para compararlos es el detector de flanco ascendente: una entrada x pasa de 0 a 1 y la salida y debe valer 1 durante un ciclo. Es lo que necesita, por ejemplo, un pulsador que debe contar una sola vez por pulsación (tema 20) aunque se lo mantenga apretado.

Versión Mealy: dos estados

Basta recordar el valor anterior de x. El estado A significa «la entrada anterior fue 0» y B «fue 1». La salida es 1 cuando, estando en A, llega x = 1:

Versión Moore: tres estados

La salida ya no puede depender de x, así que hace falta un estado que signifique «acaba de detectarse un flanco». S0: la entrada está en 0. S1: detectado, salida 1. S2: la entrada sigue en 1 y ya se avisó.

Y en el tiempo

La entrada pasa a 1 en el ciclo 2. La versión Mealy produce su pulso en ese mismo ciclo (la salida depende de x); la versión Moore, un ciclo más tarde, cuando el estado ya cambió a S1. El pulso es igual de largo en las dos; lo único distinto es el desfase. Y la versión Moore necesitó un estado más: 3 estados (2 flip-flops) contra 2 (1 flip-flop).

05 · Pulsos indeseados

Pulsos indeseados y cómo evitarlos

Una salida «combinacional» es una compuerta, y las compuertas no distinguen entre una entrada que cambia por una razón válida y una que tiene un pico. En una máquina de Mealy, si x tiene un pico de un instante entre dos flancos (ruido, rebote, un cambio asíncrono), la salida lo copia: aparece un pulso que ningún flanco real justifica. Si ese pulso alimenta un contador o un reloj, se cuenta de más.

La técnica universal: registrar la salida

Si se pasa la salida por un flip-flop, el valor que sale cambia solo en los flancos, con un retardo corto y limpio. Se paga un ciclo de latencia: una salida Mealy registrada se comporta como una salida Moore, desfasada un ciclo respecto de la Mealy original. Se pierde la reacción inmediata y se gana una salida sin pulsos extraños.

La regla práctica: las salidas que van afuera del chip o a otros bloques deberían salir de un flip-flop. La lógica combinacional pertenece al interior, entre flip-flops, donde los tiempos se controlan con setup y hold.

06 · Equivalencia

Pasar de un modelo al otro

Cualquier máquina de Mealy tiene un equivalente de Moore y al revés, con una salvedad de tiempo.

De Moore a Mealy

Es directo. La salida de la transición hacia un estado s′ es la salida que tenía s′ en Moore. Se pierde nada y a veces se ahorran estados. La salida Mealy aparece un ciclo antes que la salida Moore original.

De Mealy a Moore

Hay que «partir» estados: si a un mismo estado se llega por transiciones con salidas distintas, cada combinación (estado, salida con la que se llegó) pasa a ser un estado de Moore. En el peor caso, una máquina de Mealy con S estados y O salidas distintas da una de Moore con hasta S · O estados. Después se fusionan los equivalentes. La salida Moore resultante es la salida Mealy retrasada un ciclo:

Resultado: 3 estados una vez fusionados (A, 0), (B, 1) y (B, 0), que son los S0, S1 y S2 de la versión Moore dibujada antes.

07 · Criterios

Cuál elegir

Una buena práctica de diseño es esta: máquina de Mealy por dentro, salida registrada por fuera. Se aprovecha el ahorro de estados y la rapidez para calcular lo que hay que hacer, pero lo que sale de la máquina pasa por un flip-flop. En la práctica, es lo que hace casi todo código HDL moderno.

08 · Moore y Mealy en código

Cronogramas, pulsos espurios y conversión

Los bloques ejecutan las dos versiones del detector, miden los pulsos espurios con una entrada ruidosa, convierten una máquina de Mealy a Moore por división de estados y verifican la relación entre las dos salidas.

Paso 1: el detector de flanco en Mealy y en Moore

# Detector de flanco ascendente: salida = 1 durante un ciclo cuando la entrada pasa de 0 a 1.
MEALY = {                                   # (estado, x) -> (próximo, salida)   estados: A = "x anterior fue 0", B = "x anterior fue 1"
    ("A", 0): ("A", 0), ("A", 1): ("B", 1),
    ("B", 0): ("A", 0), ("B", 1): ("B", 0),
}
MOORE = {                                   # (estado, x) -> próximo; salida = f(estado)
    ("S0", 0): "S0", ("S0", 1): "S1",
    ("S1", 0): "S0", ("S1", 1): "S2",
    ("S2", 0): "S0", ("S2", 1): "S2",
}
SALIDA_MOORE = {"S0": 0, "S1": 1, "S2": 0}

x = [0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0]
sm, so = "A", "S0"
print("ciclo  x   Mealy(estado,salida)   Moore(estado,salida)")
sal_mealy, sal_moore = [], []
for k, xk in enumerate(x):
    # lo que se ve DURANTE el ciclo k (antes del próximo flanco)
    out_mealy = MEALY[(sm, xk)][1]               # depende de x del mismo ciclo
    out_moore = SALIDA_MOORE[so]                 # depende solo del estado
    sal_mealy.append(out_mealy)
    sal_moore.append(out_moore)
    print(f"{k:3d}    {xk}   {sm}, {out_mealy}                  {so}, {out_moore}")
    sm = MEALY[(sm, xk)][0]                      # flanco: se actualiza el estado con x del ciclo k
    so = MOORE[(so, xk)]
print()
print("x     :", *x)
print("Mealy :", *sal_mealy, "  (sube en el mismo ciclo que x)")
print("Moore :", *sal_moore, "  (un ciclo después)")

Con la entrada 0 0 1 1 1 0 1 0 0 1 1 0, hay tres flancos ascendentes (ciclos 2, 6 y 9). La salida Mealy es 1 exactamente en esos ciclos; la Moore es 1 en los ciclos 3, 7 y 10, un ciclo después. Fijate en el ciclo 3: el Mealy ya está en B y su salida volvió a 0 mientras el Moore, en S1, vale 1. Es el mismo evento visto con un ciclo de diferencia.

Paso 2: un pico en la entrada

TICKS = 4                                   # 4 "instantes" por ciclo de reloj; el flanco ocurre entre el tick 3 y el tick 0


def simular(x_ciclos, espurio_en=None):
    """Devuelve las formas de onda (un valor por tick) de la entrada y de las tres implementaciones."""
    x_prev, estado_moore, reg = 0, "S0", 0
    wf = {"x": [], "mealy": [], "moore": [], "mealy_reg": []}
    for xk in x_ciclos:
        for t in range(TICKS):
            xt = 1 - xk if t == espurio_en else xk          # un pico de un tick en la entrada
            wf["x"].append(xt)
            wf["mealy"].append(int(x_prev == 0 and xt == 1))  # combinacional: sigue a la entrada
            wf["moore"].append(int(estado_moore == "S1"))     # solo depende del estado
            wf["mealy_reg"].append(reg)                       # salida pasada por un flip-flop
        # flanco de reloj: se muestrea la entrada al final del ciclo (tick 3)
        reg = int(x_prev == 0 and xk == 1)
        estado_moore = {"S0": {0: "S0", 1: "S1"}, "S1": {0: "S0", 1: "S2"}, "S2": {0: "S0", 1: "S2"}}[estado_moore][xk]
        x_prev = xk
    return wf


def pulsos(onda):
    return sum(1 for a, b in zip([0] + onda[:-1], onda) if a == 0 and b == 1)


x = [0, 0, 1, 1, 0, 0, 1, 0, 0, 0]          # dos flancos ascendentes reales
for titulo, esp in (("entrada limpia", None), ("pico de 1 tick en el tick 2", 2)):
    wf = simular(x, esp)
    print(f"--- {titulo} ---")
    for nombre in ("x", "mealy", "moore", "mealy_reg"):
        print(f"{nombre:10s}", "".join(str(b) for b in wf[nombre]))
    print("pulsos en la salida:  Mealy", pulsos(wf["mealy"]), "| Moore", pulsos(wf["moore"]), "| Mealy registrada", pulsos(wf["mealy_reg"]), "| flancos reales: 2")
    print()

Con la entrada limpia, las tres versiones producen 2 pulsos; la Mealy en el mismo ciclo y las otras dos un ciclo después. Con un pico de un tick en cada ciclo, la salida Mealy combinacional pasa a tener 9 pulsos en lugar de 2: copia cada pico. La Moore y la Mealy registrada siguen en 2, porque solo miran la entrada en el flanco. Cambiá espurio_en a 0, 1 o 3 y compará.

Paso 3: de Mealy a Moore por división de estados

from collections import deque


def mealy_a_moore(tabla, inicial, salida_inicial="-"):
    """Cada estado Moore es un par (estado Mealy, salida con la que se llegó a él)."""
    entradas = sorted({e for _, e in tabla})
    ini = (inicial, salida_inicial)
    estados, cola, nueva = {ini}, deque([ini]), {}
    while cola:
        s, o = cola.popleft()
        for e in entradas:
            prox, sal = tabla[(s, e)]
            destino = (prox, sal)
            nueva[((s, o), e)] = destino
            if destino not in estados:
                estados.add(destino)
                cola.append(destino)
    return estados, nueva


DETECTOR = {("A", 0): ("A", 0), ("A", 1): ("B", 1), ("B", 0): ("A", 0), ("B", 1): ("B", 0)}
EXPENDEDORA = {
    (0, "n"): (0, "-"), (0, "5"): (5, "-"), (0, "10"): (10, "-"),
    (5, "n"): (5, "-"), (5, "5"): (10, "-"), (5, "10"): (0, "E"),
    (10, "n"): (10, "-"), (10, "5"): (0, "E"), (10, "10"): (0, "E"),
}
for nombre, tabla, ini in (("detector de flanco", DETECTOR, "A"), ("expendedora", EXPENDEDORA, 0)):
    estados_mealy = {s for s, _ in tabla}
    st, _ = mealy_a_moore(tabla, ini)
    print(f"{nombre}: {len(estados_mealy)} estados Mealy -> {len(st)} estados Moore")
    print("   estados Moore (estado Mealy, salida):", sorted(st, key=str))

El detector pasa de 2 estados Mealy a 4 de Moore antes de fusionar: (A,'-') y (A,0) son idénticos salvo por el nombre, así que al fusionarlos quedan los 3 de la versión Moore que dibujamos. La expendedora de 3 estados pasa a 4: aparece (0,'E'), el estado «volví a 0 después de entregar», que en Moore tiene que ser distinto de (0,'-') porque su salida es otra. En el peor caso la cantidad se multiplica por el número de salidas distintas.

Paso 4: Moore es Mealy retrasado un ciclo

import random

MEALY = {("A", 0): ("A", 0), ("A", 1): ("B", 1), ("B", 0): ("A", 0), ("B", 1): ("B", 0)}
MOORE = {("S0", 0): "S0", ("S0", 1): "S1", ("S1", 0): "S0", ("S1", 1): "S2", ("S2", 0): "S0", ("S2", 1): "S2"}
SAL = {"S0": 0, "S1": 1, "S2": 0}


def correr(x):
    sm, so, ym, yo = "A", "S0", [], []
    for xk in x:
        ym.append(MEALY[(sm, xk)][1])
        yo.append(SAL[so])
        sm = MEALY[(sm, xk)][0]
        so = MOORE[(so, xk)]
    return ym, yo


rnd = random.Random(12)
malas = 0
for _ in range(200):
    x = [rnd.randint(0, 1) for _ in range(30)]
    ym, yo = correr(x)
    if yo[1:] != ym[:-1]:                    # Moore(k+1) debería ser igual a Mealy(k)
        malas += 1
print("secuencias aleatorias probadas: 200 | secuencias donde Moore(k+1) != Mealy(k):", malas)
x = [0, 1, 1, 0, 1, 0, 0, 1]
ym, yo = correr(x)
print("x    :", *x)
print("Mealy:", *ym)
print("Moore:", *yo, "  -> es la salida Mealy retrasada un ciclo")

En 200 secuencias aleatorias de 30 ciclos, la salida Moore del ciclo k + 1 coincide siempre con la salida Mealy del ciclo k: cero discrepancias. El ejemplo corto lo muestra: la fila de Mealy es 0 1 0 0 1 0 0 1 y la de Moore, la misma desplazada: 0 0 1 0 0 1 0 0. Es la propiedad que justifica convertir de un modelo al otro.

Los cuatro bloques muestran la misma lección: un modelo es una forma de contar el mismo comportamiento, y la elección es una cuestión de tiempo, de estados y de limpieza de la salida.

09 · Exploración interactiva

El laboratorio: tres versiones de un detector

El simulador ejecuta, ciclo a ciclo, el detector de flanco en tres versiones al mismo tiempo: Mealy combinacional, Moore y Mealy con salida registrada. Cada ciclo se divide en cuatro instantes. Elegís el valor de la entrada para el próximo ciclo y, opcionalmente, un pico espurio de un instante en la mitad del ciclo. El cronograma muestra los últimos ocho ciclos y el panel compara los pulsos de cada salida con los flancos reales.

Recorrido guiado

1. Con x desmarcada, dale dos ciclos: las tres salidas siguen en 0000.
2. Marcá «x = 1» y dale un ciclo: la salida Mealy vale 1111 en ese mismo ciclo; la Moore y la registrada, 0000. Los pulsos de Mealy suben a 1; los de las otras dos todavía no.
3. Mantené x = 1 y dale otro ciclo: ahora la Moore y la registrada valen 1111, y la Mealy volvió a 0000 (x sigue en 1, pero ya no es un flanco). Las tres reportan 1 pulso, correcto.
4. Desmarcá x, dale dos ciclos y repetí: el detector no se dispara hasta una nueva subida, tanto en la entrada que se mantiene como con la que baja.
5. Elegí «pico espurio en el instante 2» con x = 0 y dale un ciclo: la salida Mealy muestra 0010, un pulso que nadie pidió. La Moore y la registrada siguen en 0000. En «Pulsos de la salida Mealy» aparece «de más».
6. Con el pico activo, marcá x = 1 en un flanco real: la Mealy pasa de 1111 a 1101, cortada en dos pulsos; cuenta uno de más. Las otras versiones siguen exactas.
7. Probá «8 ciclos al azar» con y sin pico espurio varias veces y comparalas: Moore y la registrada nunca se equivocan; la Mealy sí, si hay picos.
8. Notá que Moore y registrada coinciden siempre en forma de onda: la Mealy registrada es una máquina de Moore con un ciclo de retraso.

10 · Comprensión

Confusiones frecuentes

11 · Práctica guiada

Predecí antes de simular

1. Clasificar

¿Moore o Mealy? (a) Un semáforo cuyas luces dependen únicamente de la fase en que está. (b) Una alarma que suena si el sensor de puerta vale 1 mientras el sistema está armado. (c) Un contador cuya cuenta se muestra directamente.

2. Seguir las dos versiones

La entrada del detector de flanco es 0, 1, 1, 0, 1. Escribí la salida de la versión Mealy y de la versión Moore en cada ciclo.

3. Cuántos estados Moore

Una máquina de Mealy tiene 3 estados y 2 valores distintos de salida. ¿Cuántos estados de Moore puede necesitar, como máximo, y cuántos flip-flops?

4. Flip-flops

¿Cuántos flip-flops necesitan el detector de flanco en Mealy y en Moore? ¿Y la Mealy con salida registrada?

5. Un contador que cuenta de más

La salida de un detector de flanco Mealy se conecta al reloj de un contador, y el contador a veces suma dos o tres por pulsación de un pulsador que rebota. ¿Por qué y cómo se arregla?

6. Latencia

Un sistema debe encender una luz de aviso en el mismo ciclo en que un sensor sincronizado se activa. ¿Qué modelo elegirías y qué riesgo aceptás?

12 · Síntesis

Ideas para recordar

¿Listo para el tema 24?

Antes de avanzar, explicá de memoria en qué se diferencian las salidas de Moore y Mealy, por qué una Mealy puede producir pulsos espurios y cómo se evita. Si podés justificar las tres respuestas, ya podés pasar de la especificación al circuito.

En el próximo tema veremos el diseño de una máquina de estados: cómo codificar los estados, escribir la tabla en binario, obtener las ecuaciones de próximo estado y salida, elegir los flip-flops y tratar los estados no usados.