Taller: detector de secuencia

01 · Punto de partida

Tres detectores para el mismo patrón

La entrada x llega un bit por flanco de reloj. La salida y debe valer 1 cuando los últimos cuatro bits recibidos son 1, 0, 1, 1 (en ese orden, el 1 más antiguo primero). Los patrones pueden solaparse: en la entrada 1011011 el patrón termina dos veces, porque el último 1 de la primera aparición es el primer 1 de la segunda. Vamos a resolverlo de tres maneras, para ver qué diferencia hay entre pensar en estados y pensar en ventanas:

Como en los talleres anteriores, no hace falta tener los materiales: el código construye y verifica la máquina, y el laboratorio permite probar otros patrones.

02 · Preparación

Materiales y herramientas

Con un reloj manual todo ocurre despacio, y alcanza con los LED y el multímetro. Antes de armar, anotá la tabla de estados en papel: los errores de este taller casi siempre están en la tabla, no en los cables.

Antes de dar tensión

• 100 nF por chip; ninguna entrada al aire, incluidas las compuertas y los flip-flops sin usar.
• PRE̅ de los flip-flops en +5 V; CLR̅ conectado a la red de reset (los dos flip-flops de estado deben arrancar en 00).
• La entrada x puede cambiar en cualquier momento de la mano, pero solo se la muestrea en el flanco del reloj manual.

03 · Del patrón a la máquina

De un patrón a una máquina de estados

La idea para no equivocarse es dar a cada estado un significado preciso: «los últimos k bits recibidos coinciden con los primeros k bits del patrón», tomando el k más grande posible (el sufijo más largo que es prefijo del patrón). Para el patrón 1011:

Cada transición se calcula con una pregunta: «agrego el bit x a lo que ya tengo; ¿cuál es el sufijo más largo del resultado que es un prefijo del patrón?». Así salen todas las flechas, incluidas las de retroceso:

Dos observaciones: ningún estado se «cuelga» (cada uno tiene una flecha por cada valor de x, por lo que la tabla es completa), y las flechas de retroceso (S1 con 1, S2 con 0, S3 con 0) son las que más se olvidan: llevan a un estado intermedio, no al inicial. Sin solapamiento, S3 con x = 1 volvería a S0.

04 · Montaje 1

El detector de Mealy

Con 4 estados alcanzan 2 flip-flops. La asignación de códigos importa: con la «natural» (S0 = 00, S1 = 01, S2 = 10, S3 = 11) salen 9 literales; probando las 24 asignaciones posibles, la mejor da solo 7:

Minimizando (los cuatro estados usan las cuatro combinaciones: no hay estados sin usar ni «no importa»):

D1 = x significa que el flip-flop Q1 simplemente guarda el último bit recibido, y el término ~Q0 · x aparece en D0 y en y: se calcula una vez y se reutiliza.

Pruebas

Con el interruptor de x puesto, el LED de y se enciende antes del flanco del pulso 4 (en cuanto x = 1 con el circuito en S3): es una salida de Mealy y depende de la entrada del mismo ciclo. Si movés x con el reloj quieto, el LED sigue a x.

05 · Montaje 2

Salida registrada (Moore)

Si la salida y va a alimentar otro circuito, conviene que no cambie fuera del flanco (tema 23). La solución es pasarla por un flip-flop: y_reg se carga con el valor de y en cada flanco. El conjunto se comporta como una máquina de Moore: la detección aparece un ciclo después del último bit.

Pruebas

• Misma secuencia 1 0 1 1 0 1 1: y (Mealy) se enciende antes del flanco de los pulsos 4 y 7; y_reg se enciende después de esos flancos y dura hasta el siguiente.
• Mover x con el reloj quieto: y (Mealy) cambia; y_reg no se mueve.
• Fidelidad: con cualquier secuencia, y_reg es y desplazada exactamente un ciclo.

06 · Montaje 3

Ventana de desplazamiento

La otra forma de pensarlo es mucho más directa: guardar los últimos 4 bits en un registro de desplazamiento y comparar el contenido con 1011. No hay estados que diseñar, ni tabla, ni retrocesos que olvidar: el registro ya es la memoria. El 74HC164 (tema 14) recibe x en DSA, desplaza en cada flanco y entrega los bits en Q0 (el más nuevo) a Q3 (el más viejo). Para 1011 (el 1 más viejo en Q3):

Pruebas y comparación

• Reset y 1 0 1 1: con cuatro flancos, los LED de Q3..Q0 muestran 1011 y y se enciende, durante el ciclo posterior al cuarto flanco.
• Solapamiento: con 1 0 1 1 0 1 1, detecta las dos apariciones; el registro lo hace natural, porque siempre mira la ventana completa.
• Mismo comportamiento que el montaje 2: y_ventana coincide cuadro por cuadro con y_reg.
• Costo: 4 flip-flops y un comparador de 4 bits, contra 2 flip-flops y 5 compuertas de la máquina de estados. Para un patrón de 16 bits: 16 flip-flops contra 4.

07 · Cuando no funciona

Verificación, fallas y método

La mejor forma de verificar un detector es compararlo con una referencia sencilla: una búsqueda directa del patrón en la entrada completa. Si ambos coinciden sobre miles de bits aleatorios, la tabla es correcta, y los casos de borde (patrón solapado, comienzo de la entrada, ceros largos) quedan cubiertos casi gratis. El código de la sección siguiente lo hace.

Método de armado por etapas

1. La tabla primero: escribirla y recorrerla con 3 o 4 secuencias antes de tocar el protoboard.
2. El reloj manual y los flip-flops con las entradas fijas, antes de la lógica.
3. La lógica de próximo estado y los LED de los dos bits de estado, probando la secuencia de la sección 4.
4. La salida y al final, comprobándola con los casos de solapamiento.
5. Después, el flip-flop de salida y por último la ventana, comparando las tres salidas con la misma entrada.

08 · El taller en código

Construir, verificar, sintetizar y comparar

Los bloques generan el autómata de cualquier patrón, lo comparan con una búsqueda directa, buscan la mejor asignación de estados para el patrón 1011 y miden la equivalencia entre la máquina de estados y la ventana de desplazamiento.

Paso 1: el autómata a partir del patrón

def construir(patron, solapado=True):
    """Autómata de Mealy: el estado k significa 'los últimos k bits coinciden con el comienzo del patrón'."""
    L = len(patron)

    def mayor_prefijo(texto):
        for j in range(min(L, len(texto)), -1, -1):
            if texto.endswith(patron[:j]):
                return j

    borde = mayor_prefijo(patron[1:]) if solapado else 0          # cuánto del final de un acierto se reutiliza
    tabla = {}
    for k in range(L):
        for c in "01":
            j = mayor_prefijo(patron[:k] + c)
            if j == L:
                tabla[(k, c)] = (borde, 1)
            else:
                tabla[(k, c)] = (j, 0)
    return tabla


patron = "1011"
tabla = construir(patron)
print(f"patrón {patron}, con solapamiento: {len(tabla) // 2} estados (S0..S{len(tabla) // 2 - 1})")
print("estado  x=0           x=1")
for k in range(len(patron)):
    f0, f1 = tabla[(k, "0")], tabla[(k, "1")]
    print(f"  S{k}    S{f0[0]} / {f0[1]}         S{f1[0]} / {f1[1]}")
print()
for k in range(len(patron)):
    print(f"S{k} = últimos bits '{patron[:k]}' (coinciden con el comienzo del patrón)")
print()
sin = construir(patron, solapado=False)
print("sin solapamiento, el estado S3 con x=1 va a:", sin[(3, "1")], "(vuelve a S0)")
print("con solapamiento, el estado S3 con x=1 va a:", tabla[(3, "1")], "(el último 1 ya es el comienzo del siguiente)")

La tabla generada coincide con la que dedujimos a mano: S0 va a S0 con 0 y a S1 con 1; S1, a S2 con 0 y a sí mismo con 1; S2, a S0 con 0 y a S3 con 1; y S3, a S2 con 0 y, con 1, a S1 con salida 1. Con solapamiento, el acierto vuelve a S1 (el último 1 sirve de inicio); sin solapamiento volvería a S0. Probá con otros patrones, como «110» o «10010».

Paso 2: contra una búsqueda directa

import random


def construir(patron, solapado=True):
    L = len(patron)

    def mayor_prefijo(texto):
        for j in range(min(L, len(texto)), -1, -1):
            if texto.endswith(patron[:j]):
                return j

    borde = mayor_prefijo(patron[1:]) if solapado else 0
    tabla = {}
    for k in range(L):
        for c in "01":
            j = mayor_prefijo(patron[:k] + c)
            tabla[(k, c)] = (borde, 1) if j == L else (j, 0)
    return tabla


def detectar(tabla, bits):
    k, salidas = 0, []
    for b in bits:
        k, y = tabla[(k, b)]
        salidas.append(y)
    return salidas


def buscar(patron, bits, solapado=True):
    """Referencia: búsqueda directa de las posiciones donde TERMINA el patrón."""
    L, fin, i, res = len(patron), -1, 0, []
    while i + L <= len(bits):
        if bits[i:i + L] == patron:
            res.append(i + L - 1)
            i += 1 if solapado else L
        else:
            i += 1
    return res


rnd = random.Random(25)
bits = "".join(rnd.choice("01") for _ in range(2000))
for solapado in (True, False):
    t = construir("1011", solapado)
    y = detectar(t, bits)
    pos_fsm = [i for i, v in enumerate(y) if v]
    pos_ref = buscar("1011", bits, solapado)
    print(f"solapado={solapado}: FSM {len(pos_fsm)} detecciones, referencia {len(pos_ref)}, coinciden: {pos_fsm == pos_ref}")
muestra = "0010110110011011"
y = detectar(construir("1011"), muestra)
print()
print("entrada :", muestra)
print("salida y:", "".join(str(v) for v in y))
print("el patrón termina en las posiciones:", [i for i, v in enumerate(y) if v])

Sobre 2000 bits aleatorios, la máquina detecta 115 apariciones con solapamiento, las mismas posiciones que la búsqueda directa; sin solapamiento son 105, también coincidentes. En la muestra de 16 bits el patrón termina en las posiciones 5, 8 y 15 (contando desde 0): 001011 | 011 | 0011011, con la segunda aparición solapada con la primera. Una discrepancia con la referencia sería la señal de que la tabla tiene un error.

Paso 3: la mejor asignación de estados

def primos(minterms, dontcares):
    grupos = {(m, 0) for m in set(minterms) | set(dontcares)}
    primos = set()
    while grupos:
        siguientes, usados = set(), set()
        lista = list(grupos)
        for i in range(len(lista)):
            for j in range(i + 1, len(lista)):
                (v1, m1), (v2, m2) = lista[i], lista[j]
                d = v1 ^ v2
                if m1 == m2 and d and d & (d - 1) == 0:
                    siguientes.add((v1 & ~d, m1 | d))
                    usados.update((lista[i], lista[j]))
        primos |= grupos - usados
        grupos = siguientes
    return primos


def cubre(p, m):
    v, mask = p
    return (m & ~mask) == v


def minimizar(minterms, dontcares, nombres):
    n = len(nombres)
    if not minterms:
        return "0"
    ps = primos(minterms, dontcares)
    faltan, elegidos = set(minterms), []
    while faltan:
        esencial = next((p for m in sorted(faltan) for p in [[q for q in ps if cubre(q, m)]] if len(p) == 1), None)
        mejor = esencial[0] if esencial else max(ps, key=lambda p: sum(cubre(p, m) for m in faltan))
        elegidos.append(mejor)
        faltan -= {m for m in faltan if cubre(mejor, m)}
    terminos = []
    for v, mask in elegidos:
        lits = []
        for i in range(n - 1, -1, -1):
            if not (mask >> i) & 1:
                lits.append(nombres[n - 1 - i] if (v >> i) & 1 else "~" + nombres[n - 1 - i])
        terminos.append("·".join(lits) if lits else "1")
    return " + ".join(sorted(terminos))


from itertools import permutations

# Mealy del detector 1011 con solapamiento (estados S0..S3), entrada x.
TABLA = {
    (0, 0): (0, 0), (0, 1): (1, 0),
    (1, 0): (2, 0), (1, 1): (1, 0),
    (2, 0): (0, 0), (2, 1): (3, 0),
    (3, 0): (2, 0), (3, 1): (1, 1),
}
NOMBRES = ["Q1", "Q0", "x"]


def ecuaciones(cod):
    d1, d0, y = [], [], []
    for (s, x), (prox, sal) in TABLA.items():
        idx = cod[s] * 2 + x
        if cod[prox] >> 1: d1.append(idx)
        if cod[prox] & 1: d0.append(idx)
        if sal: y.append(idx)
    return [minimizar(d1, [], NOMBRES), minimizar(d0, [], NOMBRES), minimizar(y, [], NOMBRES)]


def literales(eqs):
    return sum(e.count("Q") + e.count("x") for e in eqs)


natural = {0: 0, 1: 1, 2: 2, 3: 3}
eq_nat = ecuaciones(natural)
print("asignación natural S0=00 S1=01 S2=10 S3=11:")
for n, e in zip(("D1", "D0", "y "), eq_nat):
    print(f"  {n} = {e}")
print(f"  literales: {literales(eq_nat)}")

resultados = []
for perm in permutations(range(4)):
    cod = dict(enumerate(perm))
    eqs = ecuaciones(cod)
    resultados.append((literales(eqs), perm, eqs))
resultados.sort()
mejor_l, mejor_p, mejor_eq = resultados[0]
print()
print("de las 24 asignaciones posibles, la mejor:")
print("  códigos:", {f"S{s}": format(c, "02b") for s, c in enumerate(mejor_p)})
for n, e in zip(("D1", "D0", "y "), mejor_eq):
    print(f"  {n} = {e}")
print(f"  literales: {mejor_l}   (peor asignación: {resultados[-1][0]})")

# Verificación del circuito contra la tabla (con los códigos ganadores)
cod = dict(enumerate(mejor_p))
inv = {v: k for k, v in cod.items()}


def circuito(q1, q0, x):                       # D1 = x, D0 = Q1 + ~Q0·x, y = Q1·~Q0·x
    return x, q1 | ((1 - q0) & x), q1 & (1 - q0) & x


ok = True
for (s, x), (prox, sal) in TABLA.items():
    q1, q0 = cod[s] >> 1, cod[s] & 1
    d1, d0, y = circuito(q1, q0, x)
    ok &= (d1 * 2 + d0 == cod[prox]) and (y == sal)
print()
print("el circuito de 7 literales reproduce las 8 filas de la tabla:", ok)

Con los códigos «naturales» salen D1 = Q0·~x + Q1·~Q0·x, D0 = x e y = Q1·Q0·x, 9 literales. De las 24 asignaciones posibles, la mejor (S0 = 00, S1 = 11, S2 = 01, S3 = 10) da D1 = x, D0 = Q1 + ~Q0·x e y = Q1·~Q0·x, 7 literales; la peor llega a 18. El circuito resultante reproduce las 8 filas de la tabla. La asignación cambia el costo del circuito por un factor de más de dos, sin cambiar su comportamiento.

Paso 4: la ventana frente a la máquina de estados

import random


def construir(patron):
    L = len(patron)

    def mayor_prefijo(texto):
        for j in range(min(L, len(texto)), -1, -1):
            if texto.endswith(patron[:j]):
                return j

    borde = mayor_prefijo(patron[1:])
    return {(k, c): ((borde, 1) if mayor_prefijo(patron[:k] + c) == L else (mayor_prefijo(patron[:k] + c), 0)) for k in range(L) for c in "01"}


def fsm_mealy(patron, bits):
    t, k, ys = construir(patron), 0, []
    for b in bits:
        k, y = t[(k, b)]
        ys.append(y)
    return ys


def ventana(patron, bits):
    """Registro de desplazamiento con L etapas y un comparador: la salida depende solo del contenido del registro."""
    L, reg, ys = len(patron), "0" * len(patron), []
    for b in bits:
        ys.append(int(reg == patron))      # lo que ve el comparador durante este ciclo (antes de que entre b)
        reg = reg[1:] + b                  # flanco: el bit nuevo entra y el más viejo sale
    return ys


rnd = random.Random(31)
for patron in ("1011", "110", "10010"):
    bits = "".join(rnd.choice("01") for _ in range(3000))
    ym, yv = fsm_mealy(patron, bits), ventana(patron, bits)
    desfasada = ym[:-1] == yv[1:]
    print(f"patrón {patron:6s}: Mealy {sum(ym):3d} detecciones | ventana {sum(yv):3d} | ventana == Mealy retrasada 1 ciclo: {desfasada}")
print()
print("recursos para un patrón de L bits:")
for L in (4, 8, 16):
    print(f"  L = {L:2d}: FSM con solapamiento {L} estados -> {max(1, (L - 1).bit_length())} flip-flops (+ lógica que cambia con el patrón)"
          f" | ventana {L} flip-flops + comparador de {L} bits (el patrón se cambia recableando)")

Para tres patrones distintos y 3000 bits aleatorios cada uno, la ventana detecta exactamente las mismas apariciones que la máquina de Mealy, pero con un ciclo de retraso: la salida de la ventana depende del registro, no de la entrada actual. Es la relación Moore = Mealy retrasada de los temas 23 y 24. En recursos, la máquina de estados crece de forma logarítmica (2, 3 y 4 flip-flops para 4, 8 y 16 bits) y la ventana de forma lineal (4, 8 y 16), pero la ventana no necesita recalcular ninguna tabla.

Los cuatro bloques cubren el ciclo completo: construir la máquina, verificarla contra una referencia, optimizarla y compararla con otra arquitectura. Es el mismo ciclo con que se verifica software.

09 · Exploración interactiva

El banco de pruebas

El simulador construye el detector para el patrón que escribas (de 2 a 6 bits) y lo ejecuta en tres versiones: Mealy, Moore y ventana de desplazamiento. Podés enviar bits de a uno o aplicar una secuencia entera, y activar o no el solapamiento. La fila de abajo muestra las entradas, marca con un borde los lugares donde el patrón termina de verdad y con un triángulo los ciclos en que la salida vale 1: comparando ambos se ve la diferencia de tiempo entre los modelos.

Recorrido guiado

1. Con Mealy y solapamiento, enviá 1, 0, 1, 1 con los botones: el estado recorre S1, S2, S3 y vuelve a S1; la salida y vale 1 en el cuarto bit, en el mismo ciclo.
2. Enviá la secuencia de ejemplo 0010110110011011: la salida vale 1 en tres ciclos (posiciones 5, 8 y 15) y coincide con las «ocurrencias reales».
3. Cambiá a Moore (se reinicia) y repetí: aparece un estado más (S4, «patrón completo») y las ▲ quedan un ciclo después de los bordes de la entrada. Las detecciones totales son iguales, pero la última puede quedar pendiente si la secuencia termina justo en el patrón.
4. Cambiá a «Ventana de desplazamiento»: aparece el registro de 4 bits con cada bit comparado con el patrón; las ▲ coinciden con las de Moore.
5. Desmarcá «Con solapamiento» (en Mealy o Moore) y enviá 1011011: sólo detecta la primera aparición, porque tras ella se vuelve a empezar de cero. La ventana siempre solapa.
6. Probá el patrón 110 y la secuencia 1110110: observá cómo el estado S2 se queda en sí mismo mientras siguen llegando unos (S2 con x = 1 → S2).
7. Probá un patrón de 6 bits como 101101: son 6 estados en Mealy (3 flip-flops) y 7 en Moore (3 flip-flops), contra 6 flip-flops de la ventana.
8. Probá 000: la ventana, que arranca en 000, ya cumple el patrón en el primer ciclo sin que haya llegado ningún bit útil; la máquina de estados no. Es un caso de borde del reset.

10 · Comprensión

Confusiones frecuentes

11 · Práctica guiada

Predecí antes de simular

1. Tabla de un patrón nuevo

Construí a mano la tabla del detector (Mealy, con solapamiento) del patrón 110.

2. Seguir el detector

El detector de 1011 (Mealy, con solapamiento) parte de S0 y recibe 0 1 1 0 1 1 1 0 1 1. ¿En qué ciclos vale y = 1?

3. Cantidad de flip-flops

Un detector Mealy de un patrón de 12 bits, ¿cuántos estados y flip-flops usa? ¿Y en Moore? ¿Y una ventana?

4. Orden del patrón

En el montaje de la ventana con el 74HC164, ¿qué ecuación de y detecta el patrón 1101 (el 1 más viejo primero)?

5. El borde de un patrón

¿Cuánto solapamiento admiten los patrones 1011, 1010 y 1000? Escribí el estado al que va el último acierto en cada caso.

6. Diagnóstico

Un detector de 1011 reconoce bien la entrada 1 0 1 1 aislada, pero no detecta nada en 1 0 1 0 1 1, donde el patrón aparece terminando en el último bit. ¿Qué transición está mal?

12 · Síntesis

Ideas para recordar

¿Listo para el tema 26?

Antes de avanzar, construí a mano la tabla del detector de otro patrón de tres o cuatro bits, indicá cuántos flip-flops necesita en Mealy y en Moore y explicá por qué una salida registrada llega un ciclo tarde. Si podés justificar las tres respuestas, ya cerraste la parte de máquinas de estados.

En el próximo tema empieza el bloque de memorias: organización y buses, es decir cómo se direccionan palabras, cuál es la capacidad de una memoria y cómo se leen y escriben datos.