Somadores e ULA

Módulo 2 · Aula 2 ~22 min de leitura Nível: Intermediário

Vídeo da aula estará disponível em breve

Meio-somador (Half Adder)

O meio-somador é o circuito aritmético mais simples: soma dois bits e produz um bit de soma (S) e um bit de carry (C). Não aceita carry de entrada — por isso é "meio".

Half Adder

Tabela-verdade:
  A  B │ S  C
  ─────┼──────
  0  0 │ 0  0
  0  1 │ 1  0
  1  0 │ 1  0
  1  1 │ 0  1

Expressões:
  S = A ⊕ B    (XOR — soma sem carry)
  C = A · B    (AND — carry)

Circuito:
  A──┤XOR├── S
  B──┘
  A──┤AND├── C
  B──┘

Total: 1 porta XOR + 1 porta AND

Somador completo (Full Adder)

O somador completo aceita um carry de entrada (Cᵢₙ), permitindo que vários somadores sejam encadeados para somar números de múltiplos bits.

Full Adder

Tabela-verdade:
  A  B  Cᵢₙ │ S  Cₒᵤₜ
  ───────────┼─────────
  0  0   0   │ 0   0
  0  0   1   │ 1   0
  0  1   0   │ 1   0
  0  1   1   │ 0   1
  1  0   0   │ 1   0
  1  0   1   │ 0   1
  1  1   0   │ 0   1
  1  1   1   │ 1   1

Expressões (por K-map ou álgebra):
  S    = A ⊕ B ⊕ Cᵢₙ
  Cₒᵤₜ = A·B + Cᵢₙ·(A ⊕ B)

Implementação com dois half adders:
  HA1: A, B  → S₁ = A⊕B,  C₁ = A·B
  HA2: S₁, Cᵢₙ → S = S₁⊕Cᵢₙ, C₂ = S₁·Cᵢₙ
  Cₒᵤₜ = C₁ + C₂ = A·B + (A⊕B)·Cᵢₙ

Diagrama:
  A──┤HA1├─S₁──┤HA2├── S
  B──┘    └─C₁  Cᵢₙ──┘  └─C₂
              └──┤OR├──────── Cₒᵤₜ
                 C₂──┘

Somador Ripple-Carry (RCA)

Para somar números de n bits, encadeamos n somadores completos. O carry de saída de cada bit alimenta o carry de entrada do próximo. Chamamos de ripple-carry porque o carry "propaga" sequencialmente.

Somador Ripple-Carry de 4 bits

       A₃ B₃    A₂ B₂    A₁ B₁    A₀ B₀
        │  │     │  │     │  │     │  │
  Cₒᵤₜ←┤FA₃├─C₃←┤FA₂├─C₂←┤FA₁├─C₁←┤FA₀├←Cᵢₙ(=0)
        │       │       │       │
        S₃      S₂      S₁      S₀

Exemplo: 0101 + 0011 (5 + 3)
  Bit 0: 1+1+0 = S₀=0, C₁=1
  Bit 1: 0+1+1 = S₁=0, C₂=1
  Bit 2: 1+0+1 = S₂=0, C₃=1
  Bit 3: 0+0+1 = S₃=1, Cₒᵤₜ=0

  Resultado: 1000 = 8 ✓

O problema do Ripple-Carry O RCA é simples mas lento. O carry precisa propagar por todos os n estágios sequencialmente. Para n bits, o atraso total é O(n) — proporcional ao número de bits. Em um processador de 64 bits, isso é inaceitável. A solução é o Carry-Lookahead Adder.

Carry-Lookahead Adder (CLA) — conceito

O CLA elimina a propagação sequencial do carry calculando todos os carries em paralelo. Definimos dois sinais para cada posição de bit:

Carry-Lookahead

Gᵢ = Aᵢ · Bᵢ     (Generate: gera carry independente do carry anterior)
Pᵢ = Aᵢ ⊕ Bᵢ     (Propagate: propaga carry se houver carry anterior)

Carries calculados diretamente:
  C₁ = G₀ + P₀·C₀
  C₂ = G₁ + P₁·G₀ + P₁·P₀·C₀
  C₃ = G₂ + P₂·G₁ + P₂·P₁·G₀ + P₂·P₁·P₀·C₀
  C₄ = G₃ + P₃·G₂ + P₃·P₂·G₁ + P₃·P₂·P₁·G₀ + P₃·P₂·P₁·P₀·C₀

Atraso: O(1) para gerar G,P + O(1) para calcular carries
= O(1) total! (constante, independente de n)

Custo: mais portas lógicas e fios mais longos.
Trade-off clássico: velocidade vs. área/complexidade.

Subtrator e somador/subtrator

Graças ao complemento de 2, subtrair é somar com o complemento. Um circuito somador/subtrator usa um sinal de controle SUB:

Somador/Subtrator de 4 bits

Sinal SUB: 0 = soma, 1 = subtração

Para cada bit Bᵢ:
  Bᵢ' = Bᵢ ⊕ SUB
  (quando SUB=0: Bᵢ'=Bᵢ, quando SUB=1: Bᵢ'=B̅ᵢ)

Carry de entrada: Cᵢₙ = SUB
  (quando SUB=1: inversão + soma de 1 = complemento de 2!)

       A₃  B₃⊕SUB   A₂  B₂⊕SUB   A₁  B₁⊕SUB   A₀  B₀⊕SUB
        │    │        │    │        │    │        │    │
  Cₒᵤₜ←┤FA₃├──C₃←───┤FA₂├──C₂←───┤FA₁├──C₁←───┤FA₀├←SUB
        │             │             │             │
        S₃            S₂            S₁            S₀

Quando SUB=1: calcula A + (~B) + 1 = A + (-B) = A - B

Unidade Lógico-Aritmética (ULA/ALU)

A ULA é o coração computacional de um processador. Combina operações aritméticas (soma, subtração) e lógicas (AND, OR, XOR, NOT) em um único circuito, selecionadas por um código de operação.

ULA simplificada de 1 bit

Operações controladas por ALUop (2 bits):

  ALUop │ Operação │ Resultado
  ──────┼──────────┼──────────────
   00   │ AND      │ A · B
   01   │ OR       │ A + B
   10   │ ADD      │ A + B (aritmético)
   11   │ SUB      │ A - B

Estrutura interna (1 bit):
                    ┌── AND(A,B)
                    ├── OR(A,B)
  A,B ──→ funções ──┤                ──→ MUX 4:1 ──→ Resultado
                    ├── FA(A,B,Cᵢₙ)
                    └── FA(A,B̅,Cᵢₙ)
                                          ▲
                                        ALUop

Flags de status (geradas pela ULA):
  Zero (Z)     — resultado é 0 (NOR de todos os bits)
  Negative (N) — bit mais significativo do resultado
  Carry (C)    — carry out do último somador
  Overflow (V) — erro de complemento de 2

ULA de 4 bits — estrutura

Entradas: A[3:0], B[3:0], ALUop[1:0]
Saídas: Result[3:0], Zero, Negative, Carry, Overflow

  A₃ B₃     A₂ B₂     A₁ B₁     A₀ B₀
   │  │      │  │      │  │      │  │
  ┤ALU₃├────┤ALU₂├────┤ALU₁├────┤ALU₀├
   │          │          │          │
   R₃         R₂         R₁        R₀

  Zero     = ~(R₃ | R₂ | R₁ | R₀)
  Negative = R₃
  Carry    = Cₒᵤₜ do ALU₃
  Overflow = Cᵢₙ₃ ⊕ Cₒᵤₜ₃

O processador MIPS usa esta ULA. A instrução ADD aciona
ALUop=10; BEQ (branch if equal) usa SUB e testa flag Zero.

ULA no processador real No MIPS (estudado em Arquitetura de Computadores), a ULA é controlada por um sinal de 4 bits que seleciona entre AND, OR, ADD, SUB, SLT (set on less than), e NOR. Cada instrução assembly é decodificada pelo controle em um código de operação da ULA. Uma instrução como add $t0, $t1, $t2 resulta em ALUop = "add" e os registradores são conectados às entradas A e B da ULA.

No harness.os

A ULA e os somadores refletem conceitos presentes no harness:

Operações aritméticas em queries — todo SELECT count(*), SUM(), AVG() no banco de dados do harness é, em última instância, executado por ULAs no processador. Entender a ULA é entender o custo real de uma query.
Trade-off velocidade vs. complexidade — o dilema Ripple-Carry vs. CLA é o mesmo dilema que aparece em software: O(n) simples vs. O(1) com mais complexidade. No harness, escolher entre uma consulta sequencial simples e uma estrutura de cache paralela envolve o mesmo tipo de trade-off.
Flags como status — a flag Zero da ULA é equivalente a um status check: "o resultado deu zero?". No harness, verificações como "a lista de erros está vazia?" são a mesma lógica, apenas em nível de software.
Composição modular — a ULA é construída com half adders → full adders → somador → somador/subtrator → ULA completa. O harness segue o mesmo princípio: primitivas simples compostas em módulos mais complexos.

Exercícios

Aritmética: Calcule 0110 - 1001 (6 - 9) usando um somador de 4 bits com complemento de 2. Mostre todos os carries e identifique se há overflow.
CLA: Para A = 1010 e B = 0111 com C₀ = 0, calcule G₀, P₀, G₁, P₁, G₂, P₂, G₃, P₃. Em seguida, calcule C₁, C₂, C₃ e C₄ usando as fórmulas do Carry-Lookahead. Verifique que o resultado da soma está correto.
ULA: Projete uma ULA de 1 bit que suporte 4 operações: AND, OR, ADD, XOR. Use um MUX 4:1 para selecionar a operação. Desenhe o circuito completo com portas lógicas.

Resumo

Verifique seu entendimento

Por que o somador Ripple-Carry é considerado lento para processadores modernos?

Porque usa muitas portas XOR
Porque não suporta números negativos
Porque o carry precisa propagar sequencialmente por todos os bits
Porque consome muita energia

Half adder: soma 2 bits sem carry de entrada (S = A⊕B, C = A·B)
Full adder: soma 2 bits + carry de entrada, pode ser encadeado
Ripple-carry: simples mas O(n) de atraso; CLA: rápido O(1) mas mais complexo
Subtração via complemento de 2: inverter B e somar 1 (XOR + carry in)
ULA combina operações aritméticas e lógicas, selecionadas por ALUop
Flags (Zero, Negative, Carry, Overflow) informam o resultado para desvios

Aula anterior 2.1 Multiplexadores e Demultiplexadores Próxima aula 2.3 Circuitos Combinacionais na Prática