Binary Addition Circuits
A half adder and full adder are the fundamental building blocks for performing binary addition in hardware. Every arithmetic operation in a CPU ultimately reduces to chains of these circuits.
Half Adder
A half adder takes two single-bit inputs (A and B) and produces:
- Sum = A XOR B -- the least significant bit of the addition
- Carry = A AND B -- the carry-out to the next position
| A | B | Sum | Carry |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
The half adder is called "half" because it has no carry input -- it cannot be chained to handle multi-bit addition on its own.
Full Adder
A full adder extends the half adder by accepting a carry-in (Cin) from a previous stage:
- Sum = A XOR B XOR Cin
- Cout = (A AND B) OR (Cin AND (A XOR B))
This three-input, two-output circuit is the workhorse of binary addition. A full adder can be built from two half adders and an OR gate.
Ripple-Carry Adder
To add N-bit numbers, chain N full adders together. The carry-out of bit position i feeds the carry-in of bit position i+1. The first stage uses Cin=0 (or a subtraction borrow). This is called a ripple-carry adder because the carry signal "ripples" through each stage sequentially.
Carry Propagation Delay
The critical weakness of ripple-carry is propagation delay. The final sum bit cannot be computed until the carry has propagated through all N stages. For an N-bit adder, the worst-case delay is O(N) gate delays. In a 64-bit adder, this could mean the carry passes through 64 stages before the result is valid.
Carry-Lookahead Concept
Carry-lookahead adders (CLA) solve this by precomputing carries in parallel using generate and propagate signals:
- Generate: Gi = Ai AND Bi (this bit position produces a carry regardless of Cin)
- Propagate: Pi = Ai XOR Bi (this bit position passes an incoming carry through)
Using these signals, each carry can be computed directly: Ci+1 = Gi OR (Pi AND Ci). By expanding this recursively, all carries are computed in O(log N) time, dramatically improving speed at the cost of more complex hardware.
Real-Life: Odometer and Carry Chains
A car's mechanical odometer works exactly like a ripple-carry adder. Each digit wheel represents one decimal place. When a wheel rolls from 9 to 0, it physically nudges the next wheel to increment by one -- this is the carry propagating. If the number is 099999, adding 1 causes a carry to ripple through all six wheels, which takes noticeably more time (mechanical delay) than incrementing 000001.
Other real-world applications:
- ALU arithmetic: Every CPU's ALU uses full adders (usually carry-lookahead or carry-select variants) for ADD, SUB (via two's complement), and address calculation.
- Subtraction via adder: To compute A - B, a full adder chain adds A + NOT(B) + 1 (two's complement negation). The same hardware does both addition and subtraction by toggling an invert input and setting Cin=1.
- Address calculation: When computing memory addresses (base + offset), the CPU uses an adder circuit. Array indexing like
arr[i]translates to base_address + i * element_size, requiring addition. - Floating-point mantissa addition: Even floating-point units use integer adders internally to add the mantissa (significand) portions after aligning exponents.