Diseño de una máquina de estados

01 · Punto de partida

El camino de la especificación al circuito

Diseñar una máquina de estados es traducir una descripción de comportamiento a un conjunto de ecuaciones booleanas y flip-flops. El proceso es siempre el mismo, y conviene recorrerlo en orden porque cada paso prepara el siguiente:

Los pasos 1 y 2 ya los dominás. Este tema cubre del 3 al 8. Todo el recorrido se hace con el mismo ejemplo, para que se vea cómo una decisión (por ejemplo, la codificación) cambia los pasos siguientes.

02 · Un ejemplo

Un ejemplo: la puerta automática

Enunciado: una puerta de comercio se abre cuando un sensor detecta a alguien (S = 1) y se cierra cuando deja de detectar. Para no cortar el paso al que justo se movió, la puerta espera un ciclo de reloj más con el motor energizado antes de cerrarse. La salida M = 1 energiza el motor de apertura.

• Entrada: S (sensor, sincronizado con el reloj).
• Salida: M (motor), de modelo Moore: depende solo de la fase.
• Qué recordar: cerrada (C), abierta con alguien presente (A), y en espera tras dejar de detectar (W). Tres estados.

Verificación rápida (tema 22): la tabla es completa (3 × 2 = 6 filas), determinista, todos los estados son alcanzables desde C y ningún par de estados es equivalente (A y W tienen la misma salida pero distinto destino con S = 0). Se puede pasar a codificar.

03 · Asignación de estados

Codificar los estados

Los flip-flops guardan bits, no nombres. Hay que decidir qué combinación de bits representa a cada estado, y esa decisión se llama asignación de estados. Con S estados hace falta, como mínimo, ⌈log₂ S⌉ flip-flops, pero no es obligatorio usar el mínimo.

• Binaria: la menor cantidad de flip-flops. Las ecuaciones son funciones de varios bits y suelen ser más complejas. Hay que decodificar el estado para saber en cuál está.
• One-hot: un flip-flop por estado, con exactamente un 1. Las ecuaciones salen casi por inspección (cada flip-flop se activa por las transiciones que llegan a ese estado), no hace falta decodificar y es rápido. Usa más flip-flops y deja muchísimas combinaciones sin usar (2ⁿ − n). Es la elección habitual en FPGA, donde los flip-flops abundan.
• Gray o de pocos cambios: estados vecinos difieren en un bit. Reduce glitches y consumo en secuencias lineales. No siempre es posible: aquí W → C cambiaría dos bits en la asignación de la tabla (11 → 00).

Para el resto del tema usamos la codificación binaria con C = 00, A = 01 y W = 10, y al final comparamos con one-hot.

04 · Tabla en binario y ecuaciones

Tabla en binario y ecuaciones

Se reescribe la tabla con los bits de los estados. Las columnas del estado actual (Q1 Q0) y la entrada (S) son las variables; las columnas del próximo estado (D1 D0, si se usan flip-flops D) y de la salida M son las funciones a obtener. Las combinaciones que corresponden a estados no usados llevan una X («no importa»): no están en la especificación, así que se puede elegir lo que mejor simplifique.

Mapas de Karnaugh

Cada columna de resultado se vuelca en un mapa (filas Q1 Q0 en orden Gray, columnas S) y se agrupan los unos, usando las X cuando ayudan a hacer grupos más grandes:

• D1: el único 1 está en (Q1 Q0 = 01, S = 0). Su vecino en el mapa, (11, 0), es una X: se la toma como 1 y el grupo de dos da D1 = Q0 · ~S. Sin la X habría hecho falta ~Q1 · Q0 · ~S.
• D0: los unos ocupan toda la columna S = 1 (las X completan la fila 11). El grupo de cuatro da D0 = S: no hay compuerta, es un cable.
• M: vale 1 en 01 y 10, 0 en 00 y X en 11. Los dos unos con la X forman grupos que dan M = Q1 + Q0.

Con un total de 5 literales (Q0, ~S, S, Q1, Q0) el circuito es muy chico. Para más variables se usa el método de Quine-McCluskey, que es el mismo agrupamiento hecho por algoritmo y que se implementa en el código de este tema.

05 · Elegir el flip-flop

Elegir el flip-flop: D, T o JK

Hasta ahora usamos flip-flops D, para los que la entrada es directamente el próximo estado. Con T o JK las ecuaciones cambian, porque sus entradas dicen qué hacer (conmutar, poner a 0, poner a 1) en lugar de qué valor tomar. La tabla de excitación da, para cada transición Q → Q⁺ de un bit, qué debe valer la entrada:

Aplicando esa tabla a las seis transiciones válidas de la puerta se obtienen las entradas de cada tipo:

Minimizando cada columna (con las X de los estados no usados y las de la propia tabla de excitación) resultan estas ecuaciones:

Para este tipo de máquina, el D gana: las ecuaciones son las más cortas y el 74HC74 (tema 12) es el flip-flop de uso general. T y JK convienen en contadores, donde «conmutar» describe naturalmente lo que hace cada bit (tema 18). En general: D para máquinas de control, T o JK para contadores.

06 · Combinaciones que sobran

Estados no usados

Con S estados y n flip-flops quedan 2ⁿ − S combinaciones fuera de la especificación. El circuito puede caer en una de ellas al encender, por ruido o por una falla. Hay que decidir qué ocurre entonces, y la decisión se toma al elegir qué hacer con las X.

1. Usar las X para simplificar y verificar después. Es lo más barato: se minimiza libremente y luego se calcula adónde va cada estado no usado.
2. Definir una salida segura. Se asigna a cada estado no usado un próximo estado válido (normalmente el inicial) y se acepta una lógica algo mayor.
3. Un reset de encendido que lleva al estado inicial, y no se espera que el circuito vuelva solo.

En la puerta, con la ecuación minimizada (D1 = Q0·~S, D0 = S), el estado no usado 11 se comporta así:

El 11 se recupera en un solo ciclo. Fue una suerte del diseño, no una garantía: siempre hay que comprobarlo. Un peligro típico es el estado sumidero: una combinación no usada de la que no se sale (tema 22). El caso clásico es el estado 000 en un one-hot: si las ecuaciones se escriben «literalmente», mirando solo las transiciones válidas, el 000 se queda en 000 para siempre.

07 · Implementación

El circuito con chips 74HC

Con las ecuaciones D1 = Q0·~S, D0 = S y M = Q1 + Q0, el circuito necesita dos flip-flops D (un 74HC74), un inversor, una AND y una OR:

La salida M debería pasar por un transistor o relé para mover el motor, no ir directo. Y la entrada S, que viene de un sensor, debe pasar antes por un flip-flop sincronizador (tema 11) y, si es un contacto mecánico, por un antirrebote (tema 7). Si M se usa como señal para otro circuito, al ser de Moore ya es limpia (tema 23).

Probar el diseño

• Secuencia esperada: con S = 0 desde C, queda en C (M = 0). S = 1: pasa a A (M = 1). S = 0: pasa a W (M = 1) y un ciclo después a C (M = 0).
• Reabrir en la espera: en W, S = 1 devuelve a A sin pasar por C.
• Encendido: repetir diez veces; con el reset, siempre arranca en C.
• Estado no usado: si hay forma de forzar 11 (precargando los flip-flops), comprobar que cae en un estado válido en un flanco.

08 · El diseño en código

Minimizar, verificar y comparar

Los bloques automatizan lo que se hizo a mano: obtienen las ecuaciones por Quine-McCluskey, verifican el circuito contra la especificación, comparan la versión binaria con la one-hot (incluyendo los estados atrapados) y calculan las entradas de los tres tipos de flip-flop.

Paso 1: de la tabla a las ecuaciones

def primos(minterms, dontcares):
    grupos = {(m, 0) for m in set(minterms) | set(dontcares)}      # (valor, máscara de bits eliminados)
    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:             # difieren en un solo bit
                    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:
        # primero los esenciales (cubren un minterm que nadie más cubre); si no hay, el que más cubre
        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))


# Especificación (Moore): estado, S -> próximo
ESPEC = {
    ("C", 0): "C", ("C", 1): "A",
    ("A", 1): "A", ("A", 0): "W",
    ("W", 1): "A", ("W", 0): "C",
}
COD = {"C": (0, 0), "A": (0, 1), "W": (1, 0)}                  # (Q1, Q0)
inv = {v: k for k, v in COD.items()}

m1, m0, dc = [], [], []
print("Q1 Q0 S | D1 D0")
for q1 in (0, 1):
    for q0 in (0, 1):
        for s in (0, 1):
            idx = q1 * 4 + q0 * 2 + s
            if (q1, q0) not in inv:
                dc.append(idx)
                print(f"{q1}  {q0}  {s} | X  X   (estado no usado)")
                continue
            n1, n0 = COD[ESPEC[(inv[(q1, q0)], s)]]
            if n1: m1.append(idx)
            if n0: m0.append(idx)
            print(f"{q1}  {q0}  {s} | {n1}  {n0}")
print()
print("D1 =", minimizar(m1, dc, ["Q1", "Q0", "S"]))
print("D0 =", minimizar(m0, dc, ["Q1", "Q0", "S"]))
print("M  =", minimizar([1, 2], [3], ["Q1", "Q0"]))

La tabla en binario coincide con la de la sección 4, con X en las dos filas del estado 11. El algoritmo devuelve D1 = Q0·~S, D0 = S y M = Q0 + Q1, las mismas ecuaciones que salieron del mapa de Karnaugh. Probá cambiar la codificación (por ejemplo, C = 00, A = 10, W = 01) y mirar cómo cambian las ecuaciones.

Paso 2: el circuito contra la especificación

import random

ESPEC = {("C", 0): "C", ("C", 1): "A", ("A", 1): "A", ("A", 0): "W", ("W", 1): "A", ("W", 0): "C"}
SALIDA = {"C": 0, "A": 1, "W": 1}
COD = {"C": (0, 0), "A": (0, 1), "W": (1, 0)}
inv = {v: k for k, v in COD.items()}


def circuito(q1, q0, s):                       # las ecuaciones que obtuvo la minimización
    d1 = q0 & (1 - s)
    d0 = s
    m = q1 | q0
    return d1, d0, m


rnd = random.Random(8)
estado, q = "C", (0, 0)
errores = 0
for _ in range(1000):
    s = rnd.randint(0, 1)
    d1, d0, m = circuito(*q, s)
    if m != SALIDA[estado]:
        errores += 1
    estado = ESPEC[(estado, s)]
    q = (d1, d0)
    if inv[q] != estado:
        errores += 1
print("1000 ciclos con entrada al azar: discrepancias entre el circuito y la especificación =", errores)

print()
print("estado no usado Q1Q0 = 11:")
for s in (0, 1):
    d1, d0, m = circuito(1, 1, s)
    print(f"  S={s}: próximo estado {d1}{d0} ({inv[(d1, d0)]}), salida M = {m}")
print("-> desde el estado no usado se cae en un estado válido en un ciclo (no hay estado sumidero)")

En 1000 ciclos de entrada aleatoria, el circuito sintetizado y la especificación coinciden en cada estado y cada salida: cero discrepancias. Desde el estado no usado 11, con S = 0 pasa a 10 (W) y con S = 1 a 01 (A), siempre con M = 1. Probá a cambiar una ecuación (por ejemplo, D0 = S · Q0) y mirar cuántas discrepancias aparecen.

Paso 3: one-hot y estados atrapados

from itertools import product

# One-hot: estados C=100, A=010, W=001 (Qc, Qa, Qw).  Entrada S.
VALIDOS = {(1, 0, 0): "C", (0, 1, 0): "A", (0, 0, 1): "W"}


def minimizadas(q, s):          # lo que sale de aprovechar los "no importa" de los 5 estados no usados
    qc, qa, qw = q
    return ((1 - qa) & (1 - s), s, qa & (1 - s))


def literales(q, s):            # lo que se escribe mirando la tabla, sin aprovechar los "no importa"
    qc, qa, qw = q
    return ((1 - s) & (qc | qw), s & (qc | qa | qw), qa & (1 - s))


def analizar(f, nombre):
    print(f"--- {nombre} ---")
    no_usados = [q for q in product((0, 1), repeat=3) if q not in VALIDOS]
    atrapados = []
    for q in no_usados:
        # ¿desde q se puede llegar a un estado válido con alguna secuencia de entradas?
        vistos, pendientes, sale = {q}, [q], False
        while pendientes and not sale:
            x = pendientes.pop()
            for s in (0, 1):
                y = f(x, s)
                if y in VALIDOS:
                    sale = True
                    break
                if y not in vistos:
                    vistos.add(y)
                    pendientes.append(y)
        if not sale:
            atrapados.append(q)
        destinos = [f"S={s}->{''.join(map(str, f(q, s)))}{'*' if f(q, s) in VALIDOS else ''}" for s in (0, 1)]
        print(f"  {''.join(map(str, q))}: {'   '.join(destinos)}")
    print("  estados que quedan atrapados:", [''.join(map(str, q)) for q in atrapados] or "ninguno")
    print("  (* = cae en un estado válido)")


analizar(minimizadas, "ecuaciones minimizadas: Qc+ = ~Qa·~S, Qa+ = S, Qw+ = Qa·~S")
analizar(literales, "ecuaciones 'literales': Qc+ = ~S·(Qc+Qw), Qa+ = S·(Qc+Qa+Qw), Qw+ = Qa·~S")

Con las ecuaciones minimizadas, los cinco estados no usados caen en un estado válido en un ciclo (el asterisco marca el destino válido). Con las ecuaciones «literales», el 000 se queda en 000 con cualquier entrada: es un estado sumidero, y el controlador no responde nunca más hasta un reset. El resto sí se recupera, a veces pasando por otro estado no usado (011 con S = 0 va a 101, y de ahí a C). Es la misma máquina con dos escrituras distintas.

Paso 4: las entradas de D, T y JK

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))


# Transiciones de la puerta automática con codificación binaria: (Q1Q0, S) -> Q1+Q0+
filas = [((0, 0), 0, (0, 0)), ((0, 0), 1, (0, 1)), ((0, 1), 0, (1, 0)), ((0, 1), 1, (0, 1)), ((1, 0), 0, (0, 0)), ((1, 0), 1, (0, 1))]
dc = [6, 7]


def excitacion(qa, qn, tipo):
    if tipo == "D":
        return {"D": qn}
    if tipo == "T":
        return {"T": qa ^ qn}
    return {(0, 0): {"J": 0, "K": "X"}, (0, 1): {"J": 1, "K": "X"}, (1, 0): {"J": "X", "K": 1}, (1, 1): {"J": "X", "K": 0}}[(qa, qn)]


print("entradas de los flip-flops FF1 y FF0 por fila (Q1Q0 S):")
for (q, s, n) in filas:
    d1, d0 = excitacion(q[0], n[0], "D")["D"], excitacion(q[1], n[1], "D")["D"]
    t1, t0 = excitacion(q[0], n[0], "T")["T"], excitacion(q[1], n[1], "T")["T"]
    j1, j0 = excitacion(q[0], n[0], "JK"), excitacion(q[1], n[1], "JK")
    print(f"  {q[0]}{q[1]} {s}:  D1D0={d1}{d0}   T1T0={t1}{t0}   J1K1={j1['J']}{j1['K']}  J0K0={j0['J']}{j0['K']}")


def eq(bit_pos, tipo, campo):
    minterms, dcs = [], list(dc)
    for q, s, n in filas:
        valor = excitacion(q[bit_pos], n[bit_pos], tipo)[campo]
        i = q[0] * 4 + q[1] * 2 + s
        if valor == "X":
            dcs.append(i)
        elif valor == 1:
            minterms.append(i)
    return minimizar(minterms, dcs, ["Q1", "Q0", "S"])


print()
resultados = {
    "D": [eq(0, "D", "D"), eq(1, "D", "D")],
    "T": [eq(0, "T", "T"), eq(1, "T", "T")],
    "JK": [eq(0, "JK", "J"), eq(0, "JK", "K"), eq(1, "JK", "J"), eq(1, "JK", "K")],
}
for tipo, es in resultados.items():
    lits = sum(e.count("Q") + e.count("S") for e in es)
    print(f"{tipo:2s}: " + " | ".join(es) + f"   -> {lits} literales")

La tabla muestra, fila por fila, qué debe valer la entrada de cada tipo de flip-flop. Minimizando: D necesita 3 literales (D1 = Q0·~S, D0 = S); JK, 4 (J1 = Q0·~S, K1 = 1, J0 = S, K0 = ~S); T, 7. Para una máquina de control como esta, D es la opción más corta, y es el flip-flop que ofrece el 74HC74. Para un contador, donde «conmutar» describe cada bit, T o JK salen mejor.

Los cuatro bloques cubren el método completo: tabla, ecuaciones, verificación, estados no usados y elección de flip-flop. Con esas piezas se puede diseñar cualquier máquina chica a mano y cualquier otra con herramientas.

09 · Exploración interactiva

El laboratorio: comparar diseños

El simulador implementa la puerta automática en cuatro variantes: codificación binaria u one-hot, con ecuaciones que aprovechan los «no importa» o que no lo hacen. Para cada variante muestra las ecuaciones, la cantidad de flip-flops y de literales, y los estados que quedan atrapados. Podés dar flancos con S = 0 o 1, o forzar un estado no usado para ver si el circuito se recupera.

Recorrido guiado

1. Con binaria y «no importa» marcado, S = 1 y un flanco: la puerta pasa de C (00) a A (01) y M = 1. Con S = 0 y un flanco pasa a W (10), con M = 1 todavía. Otro flanco con S = 0: C, con M = 0. Es la espera de un ciclo.
2. Desde W, poné S = 1 y dale un flanco: vuelve a A sin pasar por C. El motor nunca se apagó.
3. Mirá los literales: la versión binaria con «no importa» tiene 5. Desmarcá «no importa» (ecuaciones literales) y vuelve a mirar: sube a 11. La misma máquina, más lógica.
4. Con binaria, forzá el estado no usado 11: con S = 0, el siguiente flanco lo lleva a 10 (W); con S = 1, a 01 (A). «Estados atrapados» dice ninguno. Probalo también sin «no importa»: el 11 va a 00.
5. Pasá a one-hot con «no importa»: 3 flip-flops y 7 literales. Forzá cada uno de los cinco estados no usados: todos se recuperan en un flanco y «atrapados» sigue en ninguno.
6. Desmarcá «no importa» en one-hot (ecuaciones literales): aparece 000 como atrapado. Forzalo y dá flancos con S = 0 y con S = 1: no sale nunca. Es el sumidero de la sección 6.
7. Reiniciá con «Reset al estado inicial»: el reset es la única salida del 000 en esa versión.
8. Comparalas: binaria usa menos flip-flops y menos literales; one-hot tiene ecuaciones más directas y salida casi gratis, pero deja cinco combinaciones por controlar.

10 · Comprensión

Confusiones frecuentes

11 · Práctica guiada

Predecí antes de simular

1. Flip-flops y combinaciones libres

Una máquina tiene 5 estados. ¿Cuántos flip-flops usa en codificación binaria y cuántas combinaciones quedan sin usar? ¿Y en one-hot?

2. Leer una ecuación

En la puerta, D0 = S. ¿Qué significa en términos de comportamiento? ¿Qué estado tiene la puerta después de cualquier flanco con S = 1?

3. Un contador módulo 3

Diseñá un contador que recorra 00 → 01 → 10 → 00 con flip-flops D (sin entradas). Obtené D1 y D0 aprovechando el estado no usado 11. ¿Adónde va el 11?

4. Excitación

Un bit pasa de 1 a 0. ¿Cuánto vale la entrada de un flip-flop D, de un T y de un JK?

5. Cuatro estados

A la puerta se le agrega una segunda espera W2, quedando C, A, W y W2. ¿Cuántos flip-flops usa ahora la binaria y cuántas combinaciones quedan sin usar?

6. Diagnóstico

Un controlador one-hot de 4 estados funciona perfecto en el banco, pero en la placa a veces no hace nada tras encender, hasta que se lo reinicia. Todas sus salidas valen 0. ¿Qué pasó y cómo se evita?

12 · Síntesis

Ideas para recordar

¿Listo para el tema 25?

Antes de avanzar, recorré de memoria los pasos del diseño, explicá qué hacer con las combinaciones no usadas y justificá por qué conviene un reset. Si podés responder las tres, ya podés aplicar el método a un problema nuevo.

En el próximo tema armaremos el taller del detector de secuencia: una máquina que reconoce un patrón de bits en una entrada serie, desde la especificación hasta las transiciones verificadas.