Build arithmetic out of gates: half and full adders, a 4-bit adder whose carry you can watch ripple, subtraction, and magnitude comparison.
The half adder
Chapter 3 did binary addition by hand. Now build it. Start with the smallest job, adding two single bits. The answer needs two bits, a sum and a carry, so write the truth table for each and spot the gates.
a
b
carry
sum
0
0
0
0
0
1
0
1
1
0
0
1
1
1
1
0
The sum column is XOR, and the carry column is AND.
> Loading the circuit…
A half adder. It's called half because it can't accept a carry from a previous column.
Set both inputs to 1. Is the output 10 in binary, the number 2?
The full adder
Every column except the rightmost also has a carry coming in, so it adds three bits. A full adder does this. Sum is 1 when an odd number of inputs are 1, and carry is 1 when at least two are.
sum = a ⊕ b ⊕ cin cout = ab + (a ⊕ b)·cin
> Loading the circuit…
A full adder is two half adders and an OR gate. The first half adds a and b, and the second adds in the carry.
Find the three input patterns where cout is 1 but sum is 0.
Press Slow motion and flip cin. Notice how a change to cin takes a shorter path than a change to a.
Practice
A full adder has inputs 1, 0, 1. What are its outputs?
Chaining them: ripple carry
To add 4-bit numbers, use four full adders, one per column, and connect each carry out to the next carry in. Each column has to wait for the carry from the column before it. Nothing here is clocked: the answer just settles when the carry has rippled through.
> Loading the circuit…
Four full adders in a chain, already in slow motion. Displays are in hex.
Set a to F and b to 0. Now flip cin on, and watch the carry travel through every adder in turn. That's the worst case.
Set a to 3 and b to 5, and flip cin. Much less happens, so it settles sooner.
So the carry sets the speed limit. If one full adder's carry takes t_c and its sum takes t_s, the worst case for an n-bit ripple adder is:
t = (n − 1) × t_c + t_s
Chapter 12 shows how lookahead logic beats this.
Practice
A full adder has a carry delay of 2 ns and a sum delay of 3 ns. What's the worst-case delay of an 8-bit ripple adder?
You already know the trick from Chapter 3: A − B = A + B' + 1, so an adder and a set of XOR gates do the job. Still, it's worth knowing the subtractor's own equations, because exams ask for them.
Circuit
Difference
Borrow out
Half subtractor
a ⊕ b
a'b
Full subtractor
a ⊕ b ⊕ bin
a'b + (a ⊕ b)'·bin
TipThe difference is the same XOR as the sum. Only the borrow differs: it fires when a is smaller, so a appears inverted.
Practice
What are the half subtractor's outputs when a = 0 and b = 1?
Comparators
A magnitude comparator tells you whether A is greater than, less than or equal to B. For single bits, the logic is short.
> Loading the circuit…
A 1-bit comparator. Exactly one light is on at any time.
For wider numbers, you compare the way you'd compare two decimal numbers: from the left, and the first difference decides.
> Loading the animation…
In gates, write eᵢ for "bits i are equal", which is an XNOR. Then for 4 bits:
Exams often ask how to build one block from another. A full adder needs 2 half adders and 1 OR gate, or 9 NAND gates. A full subtractor is a full adder with one input inverted and the outputs adjusted, and it also takes 9 NANDs.
A comparison needs no special hardware either. Subtract: the carry out and the zero flag tell you everything. That's what a processor's compare instruction does.
Practice · GATE-style
How many 2-input NAND gates does a full adder need at minimum?
Practice · GATE-style
In a 4-bit ripple adder with inputs A = 1010 and B = 0101 and cin = 0, flipping cin to 1 makes how many sum bits change?
Practice · GATE-style
A 2-bit magnitude comparator's truth table has how many rows and how many outputs?