Diseño combinacional

01 · Punto de partida

Un método de seis pasos

Tomemos un problema chico: «una votación de tres personas se aprueba con exactamente dos votos a favor» (no uno solo, ni los tres: es una regla de votación calificada). ¿Cómo se pasa de esa frase a un circuito? Hay un camino que siempre funciona, y es el que usa cualquier ingeniero, aunque la herramienta cambie.

• ¿Cómo se escribe una especificación que no tenga huecos?
• ¿Cómo se diseña un circuito con varias salidas y cuándo se comparten términos?
• ¿Cómo se pasa de una expresión mínima a una lista de chips?
• ¿Cómo se estima el retardo y qué se verifica antes de energizar?
• ¿Qué hacer con las combinaciones de entrada imposibles?

02 · Paso 1

Especificar sin huecos

Una especificación completa nombra las entradas, nombra las salidas, define qué significa cada valor (¿1 es «pulsado» o «suelto»?) y dice, para cada una de las 2^N combinaciones, qué hace cada salida. Si la frase en castellano admite dos lecturas, la especificación todavía no está terminada.

Con tres entradas las lecturas «al menos dos» y «mayoría estricta» coinciden; con cuatro no (el empate de 2 contra 2 las separa). La especificación tiene que decidirlo.

Nombres y polaridades

«A = 1 cuando el pulsador está presionado» es una definición. «A es el botón» no. Con entradas activas en bajo (Tema 7), escribí el nombre que describe la acción (~ARRANQUE) y la tabla en términos de nivel eléctrico.

Los casos borde, por escrito

«¿Qué pasa con 000?» y «¿qué pasa con 111?» son las dos preguntas que más errores previenen. Casi todos los bugs de lógica viven en los extremos.

Combinaciones imposibles

Marcalas explícitamente como X, con la razón («el flotador alto no puede estar mojado si el bajo está seco»). Una X sin justificación suele ser una fila que nadie pensó.

Formatos válidos de especificación

Una tabla de verdad, una lista de minterms Σm, o ecuaciones. Lo importante es que sea inequívoca y se pueda comprobar mecánicamente.

03 · Pasos 2 y 3

Tabla de verdad y minterms

Con la especificación en mano, la tabla se arma sin pensar: 2^N filas en orden binario, una columna por salida. Para «exactamente dos de tres votos»:

Los minterms son Σm(3, 5, 6). Con varias salidas, la tabla simplemente tiene más columnas, y cada una tiene su propia lista de minterms (y, si las hay, sus X). Las X de una salida pueden ser unos o ceros en otra: cada columna es una función distinta con sus propias libertades.

04 · Paso 4

Minimizar e implementar

Para cada salida se aplica lo aprendido en los Temas 15 y 16: mapa de Karnaugh (o Quine-McCluskey), grupos lo más grandes posible, aprovechando las X. Pero con varias salidas aparece una decisión nueva: los términos pueden compartirse.

Términos compartidos

Si dos salidas usan el mismo producto (por ejemplo A·B), se cablea una sola puerta AND y su salida se reparte. Cada término compartido ahorra una puerta. A veces conviene elegir, entre dos grupos igual de buenos para una salida, el que ya existe en otra.

El mínimo por salida no es el mínimo del conjunto

Minimizar cada salida por separado es un buen comienzo, pero el diseño óptimo del conjunto puede usar un grupo no mínimo para una salida si lo comparte con otra. Las herramientas profesionales optimizan todas juntas.

Los inversores también se comparten

Si ~A aparece en tres términos, se usa un solo inversor para A.

Una sola forma no siempre alcanza: el caso de «exactamente dos»

Σm(3, 5, 6) no tiene minterms adyacentes (cada par difiere en dos bits), así que la suma de productos mínima es la directa. Cuesta 3 AND de tres entradas, 1 OR de tres entradas y 3 inversores: 7 puertas. Pero hay otras formas con más niveles:

La segunda forma sale de razonar sobre el problema («al menos dos, pero no los tres») y no de aplicar el método mecánicamente. Tiene una puerta menos y ningún inversor. La moraleja: el mínimo de dos niveles no siempre es el más barato, y entender qué hace la función abre alternativas que el método no ve.

05 · Paso 5

Chips, retardo y lista de materiales

La expresión mínima se traduce a puertas y las puertas a chips. En la serie 74HC (Temas 8, 9 y 12) cada chip trae varias puertas del mismo tipo, así que lo que cuenta es la cantidad de chips, no solo de puertas.

Lista de materiales (BOM)

La lista de chips y componentes del circuito, con cantidades: por ejemplo «74HC04 ×1, 74HC11 ×1, 74HC4075 ×1, condensadores de 100 nF ×3». Es el entregable del paso 5, junto con el esquema.

Puertas sobrantes

Un chip de cuatro puertas usado a medias tiene puertas libres: sus entradas se atan (Tema 12). A veces conviene ajustar el diseño para llenar chips: cambiar un AND de tres entradas por dos de dos puede ahorrar un chip de otro tipo.

Retardo estimado

Cada nivel de puertas suma un retardo de propagación (del orden de 10 ns en HC). El camino crítico es la ruta de entrada a salida con más niveles: define cuánto hay que esperar antes de que la salida sea válida. Un circuito de tres niveles responde en unos 30 ns.

Carga y alimentación

Revisá el fan-out (cuántas entradas cuelgan de cada salida), las corrientes de las salidas que manejan LED o cargas externas (Tema 12) y que cada chip tenga su capacitor de 100 nF.

06 · Paso 6

Verificar: las 2^N filas

Un circuito combinacional con N entradas tiene 2^N casos. Con N = 3 son 8; con N = 10, 1024. A diferencia del software, se pueden probar todos (si N es chico), y eso es exactamente lo que hay que hacer: ninguna otra técnica da la misma garantía.

1. 1
   Antes de cablear: verificar el diseño en papel o en código.

   Evaluar la expresión minimizada en las 2^N filas y compararla con la especificación (Paso 3 del Python). Es lo que hace el simulador de este tema.

2. 2
   Antes de energizar: lista de chequeo.

   Alimentación, desacople, entradas atadas, salidas sin enfrentarse, chips bien orientados.

3. 3
   En la mesa: recorrer las filas.

   Con interruptores en las entradas y LED en las salidas, ir por las 2^N combinaciones y anotar. Son minutos y dan la certeza.

4. 4
   Mirar los bordes dos veces.

   000 y 111, y las filas con una sola entrada distinta. Es donde casi siempre se esconde el error.

Hay una razón más para insistir con el recorrido completo: un diseño con 100 % de la tabla verificada es casi imposible que falle por lógica. Los fallos que quedan son físicos (contactos, alimentación, glitches) y se buscan con otros métodos. Verificar todo separa los dos tipos de problemas.

07 · Ejemplo completo

El nivel de un tanque

Un tanque tiene tres flotadores: A (bajo), B (medio) y C (alto). Cada uno vale 1 si está mojado. Hay que generar el nivel como un número de 2 bits (0 a 3) para un display, y una señal de VACÍO. Aplicamos los seis pasos.

Paso 1: especificación

• Entradas: A, B, C (flotadores bajo, medio y alto; 1 = mojado).
• Salidas: N1 y N0 (nivel en binario) y VACÍO (activa en alto).
• Física del problema: si el flotador alto está mojado, el medio y el bajo también lo están, y si el medio está mojado, el bajo también. Las combinaciones válidas son 000, 100, 110 y 111.
• Combinaciones imposibles: 001, 010, 011 y 101 (un flotador mojado por encima de uno seco).

Pasos 2 y 3: tabla y minterms

Minterms: N1 = Σm(6, 7) + d(1, 2, 3, 5); N0 = Σm(4, 7) + d(1, 2, 3, 5); VACÍO = Σm(0) + d(1, 2, 3, 5).

Paso 4: minimización con las X

Las X convirtieron un problema de tres salidas en un cable (N1 = B), un inversor (VACÍO = ~A) y una función de tres literales (N0). Sin las X, N1 sería A·B + ... y todo costaría el triple.

Paso 5: puertas, chips y retardo

Total: 1 NOT + 1 NOR + 1 OR = 3 puertas, repartidas en tres chips (74HC04, 74HC02 y 74HC32), con dos niveles de retardo (unos 20 ns). El truco del NOR: A·~B = ~(~A + B), y ~A ya existe. Una puerta dedicada que se evita comparte un inversor.

Paso 6: verificación y una advertencia de diseño

Se recorren las cuatro filas válidas (las X no se prueban). Pero antes de dar por cerrado el diseño, una pregunta de ingeniero: ¿qué pasa si un flotador se traba y aparece una de las combinaciones «imposibles»? El circuito dará algún nivel inventado (por ejemplo, 010 da N1 = 1, N0 = 0: «nivel 2»), y el display mostrará un valor falso sin avisar.

La salida FALLA vale 1 exactamente en las filas 1, 2, 3 y 5; se obtiene con un mapa de esas cuatro celdas (dos grupos de dos: ~A·B y ~B·C). Para un tanque de agua potable, quizá sobre. Para uno de combustible, es la diferencia entre un diseño robusto y uno frágil. Las X son una decisión de ingeniería, no un regalo.

08 · Simulador

Laboratorio: de la tabla a los chips

El simulador recorre el método con una tabla de verdad de tres entradas y hasta tres salidas. Cargá un caso (o tocá las celdas de salida para editar la tabla: 0 → 1 → X) y el programa minimiza cada salida, comparte los términos repetidos, cuenta las puertas y los chips, estima el retardo y verifica el circuito contra la tabla fila por fila.

• Tabla: las tres primeras columnas son las entradas A, B, C; las siguientes, las salidas Y1, Y2, Y3. Las celdas amarillas valen 1, las naranjas son X.
• Marca final de cada fila: ✓ si el circuito minimizado coincide con la especificación en esa fila (las X siempre se aceptan).
• Panel de la derecha: las expresiones mínimas con los términos compartidos marcados con ◆, y la lista de puertas y chips.

Recorrido guiado (8 minutos)

1. 1
   Mirá «Exactamente dos» (estado inicial).

   Tres términos de tres literales cada uno, sin posibilidad de fusión. Siete puertas (3 AND de tres entradas, 1 OR de tres y 3 inversores) en tres chips: 74HC11, 74HC4075 y 74HC04. Las ocho filas verifican.

2. 2
   Apretá «Tanque (con X)».

   Las celdas naranjas son las combinaciones imposibles. Las tres salidas colapsan: N1 = B (un cable), N0 = C + A·~B y VACÍO = ~A. Cuatro puertas en esta forma (el simulador no aplica el truco del NOR).

3. 3
   Apretá «Tanque con FALLA».

   La tercera salida ahora vale 1 en las filas imposibles. Fijate en la expresión mínima: ~A·B + ~B·C, cuatro literales. Es el costo de detectar averías.

4. 4
   Apretá «Alarma (término compartido)».

   La sirena (Y1 = A·B + A·C) y la sirena de puerta (Y2 = A·B) comparten el término A·B, marcado con ◆. La cuenta de «términos distintos» baja y se ahorra una puerta AND.

5. 5
   Apretá «Gray → binario».

   Y1 = A es solo un cable; Y2 = A⊕B se expande a dos términos; Y3 = A⊕B⊕C es la paridad, que no se simplifica en AND-OR (cuatro términos de tres literales). Las puertas XOR (Tema 10) serían mucho más baratas.

6. 6
   Apretá «Sumador completo».

   Y1 (acarreo) es la mayoría; Y2 (suma) es la paridad. Es el circuito del Tema 23, que se construye con XOR y AND en lugar de esta forma.

7. 7
   Editá una celda a mano.

   Cambiá una celda de la salida Y1 en «Exactamente dos» (por ejemplo la fila 7 a 1): la función pasa a ser «al menos dos» y la expresión se achica a tres términos de dos literales. Un solo bit de la tabla cambia por completo el circuito.

8. 8
   Convertí una fila válida en X.

   En el tanque, poné una X en una fila válida (por ejemplo la 4). Las expresiones se achican todavía más, pero el circuito dejó de garantizar el nivel 1: la verificación sigue marcando ✓ porque esa fila ya no es una exigencia. Ese es el riesgo de las X.

Preguntas para pensar

1. En «Exactamente dos», ¿por qué no hay ninguna simplificación posible en dos niveles?
2. En el tanque, ¿qué diferencia hay entre Y3 = VACÍO y Y3 = FALLA en las filas imposibles?
3. En la alarma, ¿qué ahorra el término compartido y cuándo no se puede compartir?
4. ¿Por qué una tabla verificada 8/8 no garantiza que el circuito físico no tenga glitches?

09 · El método en código

Del enunciado a la lista de chips

Estos bloques automatizan el método: convierten distintas lecturas de una especificación en tablas, minimizan varias salidas con términos compartidos y generan la lista de chips, simulan el circuito como una red de puertas y lo comparan con la especificación, calculan el camino crítico y miden la calidad de la prueba con mutantes.

Paso 1: una frase, varias tablas

def sigma(f, n):
    return [i for i in range(2 ** n) if f(bin(i).count("1"))]


for n in (3, 4):
    LECTURAS = {
        "al menos 2":         lambda k: k >= 2,
        "exactamente 2":      lambda k: k == 2,
        "más de la mitad":    lambda k: k > n / 2,
        "la mitad o más":     lambda k: k >= n / 2,
        "cantidad par":       lambda k: k % 2 == 0,
    }
    print(f"{n} votantes")
    for nombre, f in LECTURAS.items():
        print(f"   {nombre:<18} Σm{tuple(sigma(f, n))}")

Con 3 votantes «más de la mitad» y «al menos 2» coinciden; con 4 se separan: «más de la mitad» exige 3 o más y «la mitad o más» acepta el empate de 2. La frase en castellano no alcanza: hay que elegir una tabla.

Paso 2: minimización multisalida, términos compartidos y chips

from itertools import combinations
from math import ceil


def primos(unos, dcs, n):
    actual = {format(m, f"0{n}b") for m in set(unos) | set(dcs)}
    res = set()
    while actual:
        sig, usados = set(), set()
        for a, b in combinations(sorted(actual), 2):
            d = [i for i in range(n) if a[i] != b[i]]
            if len(d) == 1 and "-" not in (a[d[0]], b[d[0]]):
                i = d[0]
                sig.add(a[:i] + "-" + a[i + 1:])
                usados.update((a, b))
        res |= actual - usados
        actual = sig
    return sorted(res)


def cubre(p, m, n):
    b = format(m, f"0{n}b")
    return all(x in ("-", y) for x, y in zip(p, b))


def minima(unos, dcs, n):
    if not unos:
        return []
    ps = primos(unos, dcs, n)
    esc = set()
    for m in unos:
        c = [p for p in ps if cubre(p, m, n)]
        if len(c) == 1:
            esc.add(c[0])
    resto = [m for m in unos if not any(cubre(p, m, n) for p in esc)]
    libres = [p for p in ps if p not in esc]
    for k in range(len(libres) + 1):
        sol = [c for c in combinations(libres, k) if all(any(cubre(p, m, n) for p in c) for m in resto)]
        if sol:
            return sorted(esc | set(min(sol, key=lambda c: sum(x != "-" for p in c for x in p))))
    return sorted(esc)


def termino(p, vs="ABC"):
    return "·".join(v if x == "1" else "~" + v for v, x in zip(vs, p) if x != "-") or "1"


def lits(p):
    return sum(x != "-" for x in p)


def arbol_or(k):
    tam = []
    while k > 1:
        t = min(4, k)
        tam.append(t)
        k = k - t + 1
    return tam


CHIP = {("not", 1): ("74HC04", 6), ("and", 2): ("74HC08", 4), ("and", 3): ("74HC11", 3),
        ("or", 2): ("74HC32", 4), ("or", 3): ("74HC4075", 3), ("or", 4): ("74HC4072", 2)}


def disenar(nombre, n, salidas):
    elegidas = {s: minima(u, d, n) for s, (u, d) in salidas.items()}
    unicos = {p for ps in elegidas.values() for p in ps}
    usos = {p: [s for s, ps in elegidas.items() if p in ps] for p in unicos}
    gates = {}
    for p in unicos:
        if lits(p) >= 2:
            gates[("and", lits(p))] = gates.get(("and", lits(p)), 0) + 1
    for ps in elegidas.values():
        for t in arbol_or(len(ps)):
            gates[("or", t)] = gates.get(("or", t), 0) + 1
    neg = {i for p in unicos for i, x in enumerate(p) if x == "0"}
    if neg:
        gates[("not", 1)] = len(neg)
    print(nombre)
    for s, ps in elegidas.items():
        marca = lambda p: termino(p) + (" ◆" if len(usos[p]) > 1 else "")
        print(f"   {s} = {' + '.join(marca(p) for p in ps) or '0'}")
    total = sum(gates.values())
    chips = {CHIP[g][0]: ceil(c / CHIP[g][1]) for g, c in gates.items()}
    bruto = sum(len(ps) for ps in elegidas.values())
    print(f"   términos: {bruto} -> {len(unicos)} distintos | {total} puertas | chips: {chips}")
    return elegidas


A = {"exactamente dos": (3, {"Y": ([3, 5, 6], [])}),
     "tanque": (3, {"N1": ([6, 7], [1, 2, 3, 5]), "N0": ([4, 7], [1, 2, 3, 5]), "VACÍO": ([0], [1, 2, 3, 5])}),
     "alarma": (3, {"sirena": ([5, 6, 7], []), "puerta": ([6, 7], [])}),
     "gray a binario": (3, {"B2": ([4, 5, 6, 7], []), "B1": ([2, 3, 4, 5], []), "B0": ([1, 2, 4, 7], [])})}
for nombre, (n, sal) in A.items():
    disenar(nombre, n, sal)

El tanque queda en N1 = B, N0 = C + A·~B y VACÍO = ~A. En la alarma, A·B (◆) se comparte y se cuenta una sola vez. La paridad de Gray a binario no se achica: son cuatro términos de tres literales.

Paso 3: simular el circuito como una red de puertas y compararlo con la especificación

from itertools import combinations


def primos(unos, dcs, n):
    actual = {format(m, f"0{n}b") for m in set(unos) | set(dcs)}
    res = set()
    while actual:
        sig, usados = set(), set()
        for a, b in combinations(sorted(actual), 2):
            d = [i for i in range(n) if a[i] != b[i]]
            if len(d) == 1 and "-" not in (a[d[0]], b[d[0]]):
                i = d[0]
                sig.add(a[:i] + "-" + a[i + 1:])
                usados.update((a, b))
        res |= actual - usados
        actual = sig
    return sorted(res)


def cubre(p, m, n):
    b = format(m, f"0{n}b")
    return all(x in ("-", y) for x, y in zip(p, b))


def minima(unos, dcs, n):
    if not unos:
        return []
    ps = primos(unos, dcs, n)
    esc = set()
    for m in unos:
        c = [p for p in ps if cubre(p, m, n)]
        if len(c) == 1:
            esc.add(c[0])
    resto = [m for m in unos if not any(cubre(p, m, n) for p in esc)]
    libres = [p for p in ps if p not in esc]
    for k in range(len(libres) + 1):
        sol = [c for c in combinations(libres, k) if all(any(cubre(p, m, n) for p in c) for m in resto)]
        if sol:
            return sorted(esc | set(min(sol, key=lambda c: sum(x != "-" for p in c for x in p))))
    return sorted(esc)


def red(salidas, n):
    # lista de puertas (nombre, tipo, entradas) en orden topológico
    vs = "ABC"[:n]
    nodos = [(v, "in", ()) for v in vs]
    hechos = set(vs)
    elegidas = {s: minima(u, d, n) for s, (u, d) in salidas.items()}

    def literal(i, x):
        if x == "1":
            return vs[i]
        nombre = "~" + vs[i]
        if nombre not in hechos:
            nodos.append((nombre, "not", (vs[i],)))
            hechos.add(nombre)
        return nombre

    for s, ps in elegidas.items():
        terminos = []
        for p in ps:
            ls = tuple(literal(i, x) for i, x in enumerate(p) if x != "-")
            if len(ls) == 1:
                terminos.append(ls[0])
            else:
                nombre = "&".join(ls)
                if nombre not in hechos:
                    nodos.append((nombre, "and", ls))
                    hechos.add(nombre)
                terminos.append(nombre)
        if len(terminos) == 1:
            nodos.append((s, "buf", (terminos[0],)))
        elif not terminos:
            nodos.append((s, "const0", ()))
        else:
            nodos.append((s, "or", tuple(terminos)))
    return nodos


def simular(nodos, entradas):
    v = dict(entradas)
    for nombre, tipo, ins in nodos:
        if tipo == "in":
            continue
        a = [v[i] for i in ins]
        v[nombre] = (1 - a[0]) if tipo == "not" else int(all(a)) if tipo == "and" else int(any(a)) if tipo == "or" else a[0] if tipo == "buf" else 0
    return v


def verificar(nombre, n, salidas):
    nodos = red(salidas, n)
    malas = []
    for i in range(2 ** n):
        ent = {"ABC"[k]: (i >> (n - 1 - k)) & 1 for k in range(n)}
        v = simular(nodos, ent)
        for s, (unos, dcs) in salidas.items():
            if i in dcs:
                continue
            if v[s] != int(i in unos):
                malas.append((i, s, v[s]))
    print(f"{nombre:<18} {len(nodos) - n} nodos, {2 ** n} filas: {'TODAS ok' if not malas else 'FALLAS ' + str(malas)}")


verificar("exactamente dos", 3, {"Y": ([3, 5, 6], [])})
verificar("tanque", 3, {"N1": ([6, 7], [1, 2, 3, 5]), "N0": ([4, 7], [1, 2, 3, 5]), "VACÍO": ([0], [1, 2, 3, 5])})
verificar("sumador completo", 3, {"Cout": ([3, 5, 6, 7], []), "Suma": ([1, 2, 4, 7], [])})

La red generada se simula puerta por puerta, sin usar las expresiones minimizadas, y se compara con la tabla. Las filas X se saltan; todas las demás deben coincidir. Si alguna no coincidiera, el programa la nombra.

Paso 4: camino crítico y retardo

RETARDO = {"not": 8, "nor": 9, "and": 10, "or": 10, "buf": 0, "in": 0, "const0": 0}   # ns, valores supuestos
EXTRA = {3: 2, 4: 4}                                                            # puertas de más entradas son más lentas


def camino_critico(nodos):
    llegada = {}
    for nombre, tipo, ins in nodos:
        base = max((llegada[i] for i in ins), default=0)
        extra = EXTRA.get(len(ins), 0) if tipo in ("and", "or") else 0
        llegada[nombre] = base + RETARDO[tipo] + extra
    return llegada


# red a mano del tanque (dos formas)
suma_productos = [("A", "in", ()), ("B", "in", ()), ("C", "in", ()),
                  ("~A", "not", ("A",)), ("~B", "not", ("B",)),
                  ("A&~B", "and", ("A", "~B")), ("N0", "or", ("C", "A&~B")),
                  ("N1", "buf", ("B",)), ("VACIO", "buf", ("~A",))]
truco_nor = [("A", "in", ()), ("B", "in", ()), ("C", "in", ()),
             ("~A", "not", ("A",)), ("A&~B", "nor", ("~A", "B")),   # A·~B = NOR(~A, B), reutiliza el ~A
             ("N0", "or", ("C", "A&~B")), ("N1", "buf", ("B",)), ("VACIO", "buf", ("~A",))]

for nombre, red in (("suma de productos", suma_productos), ("con ~A compartido", truco_nor)):
    t = camino_critico(red)
    print(f"{nombre:<20} N1={t['N1']} ns  N0={t['N0']} ns  VACIO={t['VACIO']} ns  peor={max(t['N1'], t['N0'], t['VACIO'])} ns")

# el efecto de los niveles
for niveles in (1, 2, 3, 4, 6):
    print(f"{niveles} niveles de puertas de 2 entradas: ≈ {niveles * 10} ns -> frecuencia máxima de entrada ≈ {1000 / (niveles * 10):.0f} MHz")

Los tiempos son supuestos: lo que importa es el procedimiento (llegada = el más lento de las entradas + retardo de la puerta). N1 es un cable (0 ns), VACÍO es un inversor (8 ns) y N0 es el camino crítico. Cada nivel extra suma unos 10 ns.

Paso 5: ¿qué tan buena es la prueba? Mutantes

from itertools import combinations


def primos(unos, dcs, n):
    actual = {format(m, f"0{n}b") for m in set(unos) | set(dcs)}
    res = set()
    while actual:
        sig, usados = set(), set()
        for a, b in combinations(sorted(actual), 2):
            d = [i for i in range(n) if a[i] != b[i]]
            if len(d) == 1 and "-" not in (a[d[0]], b[d[0]]):
                i = d[0]
                sig.add(a[:i] + "-" + a[i + 1:])
                usados.update((a, b))
        res |= actual - usados
        actual = sig
    return sorted(res)


def cubre(p, m, n):
    b = format(m, f"0{n}b")
    return all(x in ("-", y) for x, y in zip(p, b))


def minima(unos, dcs, n):
    ps = primos(unos, dcs, n)
    esc = set()
    for m in unos:
        c = [p for p in ps if cubre(p, m, n)]
        if len(c) == 1:
            esc.add(c[0])
    resto = [m for m in unos if not any(cubre(p, m, n) for p in esc)]
    libres = [p for p in ps if p not in esc]
    for k in range(len(libres) + 1):
        sol = [c for c in combinations(libres, k) if all(any(cubre(p, m, n) for p in c) for m in resto)]
        if sol:
            return sorted(esc | set(min(sol, key=lambda c: sum(x != "-" for p in c for x in p))))
    return sorted(esc)


def pasa(patrones, unos, dcs, n):
    for m in range(2 ** n):
        if m in dcs:
            continue
        if any(cubre(p, m, n) for p in patrones) != (m in unos):
            return False
    return True


def mutantes(patrones):
    out = []
    for k, p in enumerate(patrones):
        resto = patrones[:k] + patrones[k + 1:]
        out.append(("quitar término " + p, resto))
        for i, x in enumerate(p):
            if x == "-":
                for v in "01":
                    out.append((f"agregar literal {v} en {i} de {p}", patrones[:k] + [p[:i] + v + p[i + 1:]] + patrones[k + 1:]))
                continue
            inv = "1" if x == "0" else "0"
            out.append((f"invertir literal {i} de {p}", patrones[:k] + [p[:i] + inv + p[i + 1:]] + patrones[k + 1:]))
            out.append((f"quitar literal {i} de {p}", patrones[:k] + [p[:i] + "-" + p[i + 1:]] + patrones[k + 1:]))
    return out


CASOS = {
    "exactamente dos (sin X)": ([3, 5, 6], [], 3),
    "N0 del tanque (con X)":   ([4, 7], [1, 2, 3, 5], 3),
    "mayoría de 3":            ([3, 5, 6, 7], [], 3),
}
for nombre, (unos, dcs, n) in CASOS.items():
    base = minima(unos, dcs, n)
    ms = mutantes(base)
    vivos = [d for d, ps in ms if pasa(ps, unos, dcs, n)]
    print(f"{nombre}: {len(ms)} mutantes, {len(ms) - len(vivos)} detectados por la tabla, {len(vivos)} sobreviven")
    for d in vivos:
        print("     sobrevive:", d)

En «exactamente dos» (sin X y sin términos solapados) la prueba exhaustiva detecta todos los mutantes. En el tanque y en la mayoría sobreviven algunos: cambios que solo tocan filas «no importa» o celdas que otro término ya cubre. Son los lugares donde la tabla no puede protegerte: las X dan libertad, pero también agujeros en la prueba.

10 · Analogía de programador

TDD en silicio

1. 1
   Spec = requerimiento.

   Escrito antes de diseñar. «Exactamente dos» sin dobles lecturas, con el caso 111 resuelto.

2. 2
   Tabla = tests.

   Ocho casos exhaustivos: cobertura del 100 % antes de soldar. En software eso casi nunca se logra; en lógica combinacional, sí.

3. 3
   Minimizar = refactor.

   Mismo verde, menos código. A veces el diseño directo ya es mínimo: no se refactoriza por deporte.

Una diferencia con el software: acá desplegar es soldar, y corregir un error cuesta herramientas, tiempo y componentes. Por eso la disciplina del método (especificar, verificar en papel, recorrer la tabla en la mesa) no es burocracia: es la manera de que el primer prototipo sea el último.

11 · Comprensión

Confusiones frecuentes

12 · Práctica guiada

Ejercicios de método

Ejercicio 1: «al menos uno»

Especificación, minterms y mínimo de Y = 1 si alguna de las tres entradas es 1. ¿Cuántas puertas y qué chip?

Ejercicio 2: detector de «101»

Y = 1 solo con A = 1, B = 0, C = 1. Minterms, mínimo y chips. ¿Se simplifica?

Ejercicio 3: «exactamente dos» multinivel

Verificá por tabla que Y = (A·B + A·C + B·C)·~(A·B·C) es «exactamente dos». Contá las puertas y comparalas con la suma de productos directa.

Ejercicio 4: el tanque con falla

Para el tanque, obtené la salida FALLA (1 en las combinaciones imposibles) con un mapa, y explicá cómo se combina con las otras salidas en el panel de un operario.

Ejercicio 5: una especificación ambigua

Cuatro personas votan y «se aprueba por mayoría». Escribí dos lecturas distintas, sus minterms, y decidí cuál conviene si un empate debe repetir la votación.

Ejercicio 6: el sumador completo y la lista de materiales

El sumador completo tiene dos salidas: acarreo = Σm(3, 5, 6, 7) y suma = Σm(1, 2, 4, 7). Obtené la lista de chips con la suma de productos, y compará con una versión que comparte A⊕B.

13 · Síntesis

Ideas para recordar

¿Listo para el Tema 18?

Podés avanzar si sos capaz de responder esto sin mirar:

• Nombrar los seis pasos del método y qué documento produce cada uno.
• Escribir las Σm de «exactamente dos» y de «al menos dos» de tres entradas.
• Explicar por qué hay que verificar todas las filas y cuáles mirar primero.
• Contar los chips necesarios para una expresión dada.
• Decidir si conviene o no marcar una combinación como X.
• Dar un ejemplo de término compartido entre dos salidas.

Con el método completo ya podés diseñar casi cualquier circuito combinacional chico. Falta conocer los bloques que ahorran trabajo, porque muchas funciones ya existen en un solo chip: en el próximo tema, multiplexores.