Digital Adder Design: Half/Full Adders and Ripple Carry Adder Delay

Chapter 2 Adder Overview

The adder is the foundation of all arithmetic and the core of a processor datapath. These notes start with the half adder and full adder and go through high-speed adder structures such as the carry chain, carry lookahead, and carry select.

Half Adder

Two 1-bit inputs A, B → sum S and carry C:

• $S = A \oplus B$
• $C = A \cdot B$

Full Adder

Three 1-bit inputs A, B, Cin → S, Cout:

• $S = A \oplus B \oplus C_{in}$
• $C_{out} = AB + (A \oplus B) \cdot C_{in} = AB + AC_{in} + BC_{in}$

Propagate & Generate

The basic concepts behind carry lookahead:

• Generate: $G = A \cdot B$ (always produces a carry)
• Propagate: $P = A \oplus B$ (passes the carry through)
• Cout = $G + P \cdot C_{in}$

Full Adder Design — Transistor Level

• Cout: $(A+B) \cdot C_{in} + A \cdot B$ → a 5–6 transistor structure
• S: XOR-based → 10–12 transistors
• Inverting logic: use only NAND/NOR to optimize area and delay

Ripple Carry Adder (RCA)

n full adders connected in sequence:

  A0,B0      A1,B1      A2,B2
    │          │          │
 [FA0]─C1→[FA1]─C2→[FA2]─C3→
    │          │          │
   S0         S1         S2

Delay

• Carry propagation: passes through all $n$ bits → O(n) delay
• Worst case: $t = n \times t_{FA}$ → very slow at 32 bits

Carry Lookahead Adder (CLA)

Precomputes the carry of every bit in parallel:

Expanded:

→ Each carry can be computed with O(log n) delay.

Block Carry Lookahead

Groups the CLA into 4-bit blocks and computes the carries between blocks with lookahead as well. A hierarchical CLA.

• Hierarchy of 4-bit groups → 16-bit CLA → 64-bit CLA
• Log time at each level → $O(\log n)$ overall

Manchester Carry Chain

Implements the carry chain with CMOS pass transistors:

• Propagate passes the carry along through a pass transistor
• Generate creates it directly through a pull-down

Carry Skip Adder

Splits the RCA into k-bit blocks; if every bit in a block has propagate=1, the carry skips (bypasses) the whole block:

• Within a block: ripple
• At block boundaries: skip through a MUX

Performance: $O(\sqrt{n})$ delay, area-efficient.

Carry Select Adder

Computes each block for both Cin=0 and Cin=1 at the same time → when the actual Cin arrives, a MUX selects the result.

• ↑ area, but ↓ delay
• Common in 32-bit adders

Conditional Sum Adder

A recursive version of carry select. Upper blocks are also selected recursively. Delay $O(\log n)$.

Brent-Kung / Kogge-Stone Prefix Adder

Uses a prefix tree to compute all carries in parallel. A parallel prefix adder.

• Brent-Kung: depth = 2log n, small area
• Kogge-Stone: depth = log n, large area, fastest
• Ladner-Fischer, Han-Carlson: intermediate tradeoffs

Most high-performance datapath adders in CPUs are Kogge-Stone or a variant.

Pipelined Adder

Pipelines a long n-bit adder over several stages. ↑ throughput, ↑ latency.

Subtraction (Two's Complement)

$A - B = A + \bar{B} + 1$ (two's complement). Implemented with an adder + XOR gates + Cin=1.

Multi-Operand Addition

Adding three or more numbers: a CSA (carry save adder) tree reduces the partial sums at each bit position, followed by a final CPA.

Saturation Arithmetic

On overflow, the result saturates: it is clamped to the MAX or MIN value. Important in DSP/multimedia.

Floating-Point Adder

• Align exponents (shift to match the larger value)
• Add mantissas
• Normalize the result (shift, adjust exponent)
• Round

Each stage is complex, so a pipelined FP adder is a must.

Summary

The adder's delay determines the datapath performance of a processor. Most ALUs in modern CPUs use a parallel prefix adder (a Kogge-Stone variant) + pipelining.