Sumador medio y completo

01 · Punto de partida

Como en primaria: llevo 1

Sumar 1 + 1 en binario da 10: se escribe 0 y «se lleva» 1 a la columna siguiente. Es el mismo algoritmo de primaria, con la ventaja de que cada columna solo tiene cuatro casos posibles. Un circuito que resuelve una columna se llama sumador de un bit, y viene en dos versiones:

• El medio sumador (half adder) suma dos bits, A y B. Sirve para la primera columna, donde no llega ningún acarreo.
• El sumador completo (full adder) suma tres: A, B y el acarreo que viene de la columna anterior (Cin). Entrega la suma S y el acarreo de salida Cout, que alimenta la columna siguiente.

• ¿Qué ecuaciones tiene cada sumador?
• ¿Por qué el acarreo es una mayoría y la suma una paridad?
• ¿Cuántas puertas cuesta un sumador completo, y cuántas si solo hay NAND?
• ¿Qué son «generate» y «propagate», y por qué importan para la velocidad?
• ¿Para qué sirve un sumador además de sumar: contar, restar, comprimir?

02 · Medio sumador

Dos bits, sin traer nada

La columna de S es la de un XOR (cero con entradas iguales) y la de Cout es la de un AND (solo 1 + 1 lleva). Un XOR y un AND: dos puertas.

Con puertas NAND

El XOR de cuatro NAND (Tema 9) genera adentro la señal NAND(A, B). Esa misma señal, invertida, es el AND: basta un NAND más usado como inversor. El medio sumador completo cuesta 5 NAND, no 6: el XOR comparte su primer NAND con el acarreo.

Con chips

Un 74HC86 trae cuatro XOR y un 74HC08 cuatro AND, así que un medio sumador usa una puerta de cada uno. Comprobá la distribución de pines en la hoja de datos del fabricante.

Es un contador de unos

El par (Cout S) cuenta cuántas entradas valen 1: dos entradas dan 0, 1 o 2, que en binario es 00, 01 o 10.

03 · Sumador completo

Tres bits, con acarreo

A partir del segundo bit, cada columna recibe el acarreo de la anterior. Las entradas posibles son 2³ = 8, y la suma va de 0 a 3, que entra justo en dos bits.

Mirá las dos columnas de salida:

• S vale 1 con una cantidad impar de unos (filas 1, 2, 4 y 7): es la paridad de tres bits, el XOR de tres entradas (Tema 10).
• Cout vale 1 con dos o más unos (filas 3, 5, 6 y 7): Σm(3, 5, 6, 7), la función mayoría que ya minimizaste con Quine-McCluskey y con mapas de Karnaugh (Temas 15 y 16): AB + ACin + BCin.

Por qué XOR de tres

Sumar módulo 2 es XOR, y el XOR es asociativo: (A⊕B)⊕Cin. Se calcula en dos etapas con dos XOR de dos entradas.

Por qué una mayoría

Hay acarreo cuando la suma llega a 2 o más, es decir, cuando al menos dos de los tres bits valen 1. Eso es, por definición, la mayoría de tres.

La regla de oro

2·Cout + S = A + B + Cin en las ocho filas. Es la mejor forma de verificar un sumador: no importa cómo esté construido por dentro.

04 · Construcciones

Cinco formas de construirlo

Con dos funciones de tres variables ya sabés que hay muchas formas de implementarlas, con costos distintos. Todas calculan lo mismo; cambian las puertas, los chips y los retardos.

La versión de cinco puertas

Reescribir el acarreo en función de P = A⊕B muestra por qué se puede reutilizar el XOR:

• Si A = B = 1, hay acarreo siempre (G = 1).
• Si A ≠ B (P = 1), el acarreo de salida es el de entrada: Cout = Cin.
• Si A = B = 0, no hay acarreo.

Es la forma generate / propagate: G genera un acarreo por sí mismo y P propaga el que llega. Como G = 1 implica P = 0 (A = B = 1 da A⊕B = 0), los dos sumandos nunca valen 1 a la vez, así que el OR final puede ser también un XOR (Ejercicio 3).

Las nueve NAND

Son dos XOR de cuatro NAND que comparten una puerta con la lógica del acarreo: n1 y n5 sirven al XOR y al Cout, y el OR final se resuelve con el último NAND (De Morgan, Tema 14: NAND de dos negados es un OR). El simulador y el Paso 2 de Python la verifican en las ocho filas.

05 · Retardo

Generate, propagate y cuánto tarda un acarreo

Las puertas no responden al instante: cada una tarda un pequeño tiempo (retardo de propagación). En un sumador interesa sobre todo el camino del acarreo, porque la columna siguiente tiene que esperarlo.

Dentro de una columna

P y G salen después de un nivel de puertas; S, tras un segundo XOR; Cout, tras el AND y el OR. El camino Cin → Cout cruza solo dos niveles (AND y OR).

En una cadena de N columnas

El acarreo pasa de una columna a la siguiente: cada una agrega dos niveles. Con el modelo simple de «un nivel por puerta», el acarreo final llega a los 1 + 2N niveles: 9 con 4 bits, 17 con 8 y 65 con 32 (Paso 6 de Python).

La consecuencia

Sumar es lineal en el ancho: duplicar los bits duplica el retardo. Los procesadores resuelven esto adivinando los acarreos con lógica extra (sumador de acarreo anticipado). Ese es el tema de las próximas lecciones.

06 · Usos

Qué se hace con un sumador de un bit

Sumar números de N bits

Se conectan N sumadores completos con Cout de cada columna a Cin de la siguiente. La primera columna puede ser un medio sumador, o un completo con Cin = 0. Es el sumador en cascada del Tema 24.

Incrementar

Sumar 1 a un número: la primera columna recibe un 1 fijo y las demás solo propagan. Alcanza con una cadena de medios sumadores: la entrada «1» entra por el B del primero. Es el corazón de un contador (Paso 5). Con 1111 + 1 el acarreo final sale en 1 y el resultado vuelve a 0000.

Restar

A − B = A + ~B + 1 en complemento a dos (Tema 5). Se invierte cada bit de B y se pone Cin = 1 en el primer sumador. Con 5 − 3 en 4 bits: 0101 + 1100 + 1 = 10010, que da 0010 = 2 y acarreo 1. Ese acarreo no es un error: en una resta sin signo vale 1 cuando A ≥ B (no hizo falta «pedir prestado»).

Contar unos (compresor 3:2)

Un sumador completo convierte tres bits del mismo peso en dos bits (S de peso 1, Cout de peso 2). Armados en árbol, N sumadores cuentan cuántos unos tiene una palabra. Para 7 bits alcanzan 4 sumadores completos; la regla general (cada uno elimina un bit) da N menos la cantidad de bits del resultado. Es la base de los multiplicadores.

Comparar

A − B con acarreo final decide si A ≥ B. El comparador del Tema 10 se puede armar con un sumador (más adelante).

07 · Simulador

Laboratorio: sumar con puertas

El simulador dibuja el sumador y muestra el nivel de cada cable. Tiene tres vistas: el medio sumador (Cin fijo en 0), el sumador completo de cinco puertas (con P, G y P·Cin visibles) y la versión de nueve NAND con el valor de cada nodo. En cualquier vista se verifica la regla 2·Cout + S = A + B + Cin.

• Cables: verde = 1, gris = 0.
• Entradas: A, B y Cin se conmutan con los botones; «Siguiente combinación» recorre las ocho filas en orden binario.
• Resultados: S, Cout, el par en binario, la suma en decimal y la verificación.

Recorrido guiado (8 minutos)

1. 1
   Mirá el estado inicial: 1 + 1 + 0 con el completo.

   P = A⊕B = 0, G = A·B = 1, P·Cin = 0. Entonces S = P⊕Cin = 0 y Cout = G + P·Cin = 1: el resultado es 10, o sea 2.

2. 2
   Apretá «Siguiente combinación» siete veces.

   Pasa por todas las filas de la tabla en orden. Anotá en qué filas se enciende Cout: son 011, 101, 110 y 111 (los minterms 3, 5, 6 y 7).

3. 3
   Poné A = 1, B = 1, Cin = 1.

   Los tres unos dan S = 1 y Cout = 1: 11 en binario, 3. Fijate que P vale 0 y que el acarreo sale de G, no de la entrada.

4. 4
   Poné A = 1, B = 0, Cin = 1.

   Ahora P = 1: el acarreo de entrada se propaga hasta la salida (P·Cin = 1) y G = 0. Cout = 1, pero no lo generó ninguna columna: llegó de afuera.

5. 5
   Pasá a «Medio (Cin = 0)».

   El botón de Cin queda fijo en 0 y sobran dos puertas. S es el XOR y Cout es el AND. Comprobá que da lo mismo que el completo con Cin = 0.

6. 6
   Pasá a «Completo (9 NAND)».

   No hay puertas dibujadas, pero sí los nueve nodos. Recorré las ocho filas: S y Cout valen lo mismo que en la versión de cinco puertas, con una estructura distinta.

7. 7
   Mirá n4 en la versión NAND.

   Siempre vale A⊕B (es P). Y n1 vale 1 salvo con A = B = 1: es NAND(A, B), la señal que comparten el XOR y el acarreo.

8. 8
   Seguí la verificación.

   Para cualquier fila y cualquier versión, 2·Cout + S coincide con A + B + Cin. Si alguna vez no coincidiera, el circuito estaría mal construido.

Preguntas para pensar

1. Con 1 + 1 + 1, ¿cuánto valen S y Cout y de qué puerta sale cada acarreo?
2. Con Cin = 0, ¿en qué se parece el sumador completo al medio?
3. ¿En qué filas es Cout = 1 y qué función conocida resulta?
4. ¿Cuántas de las ocho filas tienen S = 1?

08 · Sumar en código

Medio, completo, cinco construcciones, resta, contar unos y retardos

Los bloques verifican la tabla con la regla 2·Cout + S, comprueban las cinco construcciones contra una referencia, suman y restan palabras de 4 bits encadenando completos, arman un contador de unos con sumadores, un incrementador con medios sumadores y calculan el retardo del acarreo con el modelo de niveles.

Paso 1: medio, completo y la regla de oro

from itertools import product


def medio(a, b):
    return a ^ b, a & b


def completo(a, b, cin):
    s = a ^ b ^ cin
    cout = (a & b) | (a & cin) | (b & cin)
    return s, cout


print("medio sumador:  A B | Cout S")
for a, b in product((0, 1), repeat=2):
    s, c = medio(a, b)
    print(f"                {a} {b} |  {c}    {s}")

print()
print("completo:  A B Cin | Cout S | unos")
ok = True
for a, b, cin in product((0, 1), repeat=3):
    s, c = completo(a, b, cin)
    ok = ok and (2 * c + s == a + b + cin)
    print(f"           {a} {b}  {cin}  |  {c}    {s}  |  {a + b + cin}")
print("2*Cout + S == A + B + Cin en las 8 filas:", ok)

indice = lambda t: 4 * t[0] + 2 * t[1] + t[2]
print("filas con Cout = 1 (minterms):", [indice(t) for t in product((0, 1), repeat=3) if completo(*t)[1]])
print("filas con S = 1:", [indice(t) for t in product((0, 1), repeat=3) if completo(*t)[0]])

La regla vale en las 8 filas. Cout = 1 en los minterms [3, 5, 6, 7] (la mayoría) y S = 1 en [1, 2, 4, 7] (la paridad de tres bits).

Paso 2: cinco construcciones, un mismo resultado

from itertools import product


def nand(a, b):
    return 1 - (a & b)


def fa_sop(a, b, c):
    s = (a & (1 - b) & (1 - c)) | ((1 - a) & b & (1 - c)) | ((1 - a) & (1 - b) & c) | (a & b & c)
    cout = (a & b) | (a & c) | (b & c)
    return s, cout


def fa_dos_medios(a, b, c):
    p, g = a ^ b, a & b
    s, pc = p ^ c, p & c
    return s, g | pc


def fa_mux(a, b, c):
    p = a ^ b
    return p ^ c, (c if p else a)


def fa_nand9(a, b, c):
    n1 = nand(a, b)
    n2 = nand(a, n1)
    n3 = nand(b, n1)
    n4 = nand(n2, n3)
    n5 = nand(n4, c)
    n6 = nand(n4, n5)
    n7 = nand(c, n5)
    return nand(n6, n7), nand(n1, n5)


def fa_xor_final(a, b, c):                  # el OR final cambiado por un XOR
    p, g = a ^ b, a & b
    return p ^ c, g ^ (p & c)


ref = {t: (sum(t) % 2, 1 if sum(t) >= 2 else 0) for t in product((0, 1), repeat=3)}
construcciones = (
    ("SOP directa", fa_sop, "9 puertas + 3 NOT"),
    ("dos medios", fa_dos_medios, "5 puertas"),
    ("XOR + mux", fa_mux, "2 XOR + 1 mux"),
    ("9 NAND", fa_nand9, "9 NAND"),
    ("OR por XOR", fa_xor_final, "5 puertas"),
)
for nombre, f, costo in construcciones:
    bien = all(f(*t) == ref[t] for t in ref)
    print(f"{nombre:<12} coincide en las 8 filas: {bien}   ({costo})")

print("G y P·Cin nunca valen 1 a la vez:",
      all(((a & b) & ((a ^ b) & c)) == 0 for a, b, c in product((0, 1), repeat=3)))

Las cinco versiones dan la misma tabla. Además G y P·Cin son mutuamente excluyentes (si A = B = 1, P vale 0), por eso el OR final puede ser también un XOR.

Paso 3: sumar y restar palabras de 4 bits

def completo(a, b, cin):
    return a ^ b ^ cin, (a & b) | (a & cin) | (b & cin)


def sumar(x, y, n=4, cin=0):
    acarreo, r = cin, 0
    for k in range(n):
        s, acarreo = completo((x >> k) & 1, (y >> k) & 1, acarreo)
        r |= s << k
    return r, acarreo


def restar(x, y, n=4):
    mascara = (1 << n) - 1
    return sumar(x, ~y & mascara, n, cin=1)          # A - B = A + ~B + 1


todo_suma = all(sumar(x, y) == ((x + y) % 16, (x + y) // 16) for x in range(16) for y in range(16))
print("suma de 4 bits con 4 sumadores completos, todas las 256 parejas:", todo_suma)
print("7 + 5 =", sumar(7, 5), "(resultado, acarreo final)")
print("9 + 9 =", sumar(9, 9), "(el acarreo final avisa que no cabe en 4 bits)")

todo_resta = all(restar(x, y) == ((x - y) % 16, 1 if x >= y else 0) for x in range(16) for y in range(16))
print("resta A + ~B + 1, todas las parejas: resultado = (A-B) mod 16 y acarreo = (A >= B):", todo_resta)
print("5 - 3 =", restar(5, 3))
print("3 - 5 =", restar(3, 5), "(14 = -2 en Ca2 y acarreo 0: hizo falta pedir prestado)")

Cuatro completos en cadena suman las 256 parejas. 7 + 5 = 12 sin acarreo; 9 + 9 = 18 da 2 con acarreo 1. La resta A + ~B + 1 da (A − B) mod 16 y el acarreo final vale 1 cuando A ≥ B: 5 − 3 = (2, 1) y 3 − 5 = (14, 0).

Paso 4: un árbol de sumadores que cuenta unos

from itertools import product


def completo(a, b, cin):
    return a ^ b ^ cin, (a & b) | (a & cin) | (b & cin)


def contar7(bits):
    s1, c1 = completo(bits[0], bits[1], bits[2])
    s2, c2 = completo(bits[3], bits[4], bits[5])
    s3, c3 = completo(s1, s2, bits[6])                 # pesos 1
    s4, c4 = completo(c1, c2, c3)                      # pesos 2
    return 4 * c4 + 2 * s4 + s3


ok = all(contar7(b) == sum(b) for b in product((0, 1), repeat=7))
print("contar unos de 7 bits con 4 sumadores completos, las 128 palabras:", ok)
print("1111111 ->", contar7((1,) * 7), "  1010100 ->", contar7((1, 0, 1, 0, 1, 0, 0)))

print()
print("bits  sumadores completos (n - bits del resultado)")
for k in (2, 3, 4, 5):
    n = 2 ** k - 1
    print(f"{n:4d}  {n - k:3d}")

Cuatro sumadores cuentan los unos de cualquier palabra de 7 bits (128 casos). Cada sumador elimina un bit, y para 3, 7, 15 y 31 bits hacen falta 1, 4, 11 y 26.

Paso 5: un incrementador con medios sumadores

def medio(a, b):
    return a ^ b, a & b


def incrementar(x, n=4):
    acarreo, r = 1, 0                                  # el «+1» entra como acarreo inicial
    for k in range(n):
        s, acarreo = medio((x >> k) & 1, acarreo)
        r |= s << k
    return r, acarreo


for x in (0, 5, 7, 14, 15):
    r, c = incrementar(x)
    print(f"{x:2d} ({x:04b}) + 1 = {r:2d} ({r:04b})  acarreo final {c}")

ok = all(incrementar(x) == ((x + 1) % 16, (x + 1) // 16) for x in range(16))
print("coincide con (x + 1) mod 16 en las 16 entradas:", ok)

El acarreo se propaga por los unos consecutivos del final: 7 (0111) + 1 = 8 (1000). Con 15 (1111) el acarreo final sale en 1 y el resultado vuelve a 0000.

Paso 6: generate, propagate y el retardo del acarreo

from itertools import product


def acarreo_gp(a, b, cin):
    g, p = a & b, a ^ b
    return g | (p & cin)


mayoria = lambda a, b, c: 1 if a + b + c >= 2 else 0
print("Cout = G + P·Cin coincide con la mayoría en las 8 filas:",
      all(acarreo_gp(*t) == mayoria(*t) for t in product((0, 1), repeat=3)))


def retardos(n):
    t_c = 0                                            # el acarreo inicial está listo en t = 0
    t_s = 0
    for _ in range(n):
        t_s = max(1, t_c) + 1                          # P listo en 1; S = P xor acarreo
        pc = max(1, t_c) + 1                           # P · acarreo
        t_c = max(1, pc) + 1                           # G listo en 1; Cout = G or (P·acarreo)
    return t_s, t_c


print()
print("bits  niveles hasta el último S  niveles hasta el acarreo final")
for n in (1, 4, 8, 16, 32):
    s, c = retardos(n)
    print(f"{n:4d}  {s:20d}  {c:28d}")

La forma G + P·Cin reproduce la mayoría. Con un nivel por puerta, el acarreo final tarda 1 + 2N niveles (3, 9, 17, 33 y 65 con N = 1, 4, 8, 16 y 32) y el último S sale 2N niveles después. Sumar más bits cuesta tiempo en proporción.

09 · Analogía de programador

divmod en silicio

1. 1
   S = paridad, Cout = mayoría.

   Dos funciones que ya conocías, con trabajo nuevo. Reutilizar vale más que reinventar.

2. 2
   Suma sin acarreo + acarreos.

   El truco clásico de suma por software es a + b == (a ^ b) + ((a & b) << 1), repetido hasta que no queden acarreos. El hardware lo hace de una vez, con puertas.

3. 3
   El medio es el caso base.

   La primera columna no tiene acarreo previo: es el caso base de la recursión. El resto usa el completo.

Una diferencia con el software: en un programa a + b es una instrucción que cuesta un ciclo, sin importar el valor. En el hardware, el costo depende del ancho (más bits, más puertas y más retardo del acarreo) y del tiempo que tarda en estabilizarse la última columna.

10 · Comprensión

Confusiones frecuentes

11 · Práctica guiada

Ejercicios de suma

Ejercicio 1: medio sumador con NAND

Armá S y Cout de un medio sumador solo con NAND de dos entradas, compartiendo señales. ¿Cuántas puertas necesitás y cuántos 74HC00?

Ejercicio 2: 1 + 1 + 1 a mano

Con las ecuaciones, calculá S y Cout para A = B = Cin = 1 y comprobá con la regla 2·Cout + S.

Ejercicio 3: ¿OR o XOR al final?

En Cout = G + P·Cin, ¿por qué se puede reemplazar el OR por un XOR sin cambiar el resultado?

Ejercicio 4: restar con sumar

Calculá 5 − 3 con 4 bits sumando bit a bit: 0101 + 1100 + 1 (Cin = 1). ¿Resultado y acarreo final?

Ejercicio 5: un sumador de 8 bits

Para sumar dos números de 8 bits con una cadena de sumadores completos de cinco puertas, ¿cuántos sumadores y cuántas puertas hacen falta? ¿Y con la versión de 9 NAND, cuántos 74HC00?

Ejercicio 6: contar unos de 15 bits

¿Cuántos sumadores completos hacen falta para contar los unos de una palabra de 15 bits en un árbol? ¿Cuántos bits tiene el resultado?

12 · Síntesis

Ideas para recordar

¿Listo para el Tema 24?

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

• Escribir la tabla del sumador completo y sus dos ecuaciones.
• Explicar por qué S es una paridad y Cout una mayoría.
• Verificar un sumador con la regla 2·Cout + S = A + B + Cin.
• Armar el completo con dos medios sumadores y un OR, y justificar el OR.
• Definir generate y propagate y decir qué camino del sumador es el crítico.
• Restar con un sumador usando complemento a dos.

Un bit está dominado. Ahora, N bits: en el próximo tema, el sumador en cascada, donde se encadenan las columnas y se mide el costo del acarreo.