You are viewing a free preview of this lesson.
Subscribe to unlock all 10 lessons in this course and every other course on LearningBro.
Adders are the first place in this course where logic gates assemble into something a computer visibly does: arithmetic. Every addition a processor performs — and, through two's complement, every subtraction, and the repeated additions inside multiplication — is carried out by adder circuits at the heart of the arithmetic logic unit. This lesson builds them from the ground up: the half adder that adds two bits, the full adder that also accepts a carry from the column to its right, the ripple-carry adder that chains full adders to add whole binary numbers, and the carry-propagation delay that limits how fast a ripple adder can run. It is the clearest demonstration in 1.4.3 that the abstract Boolean machinery of the earlier lessons has a concrete, performance-critical payoff.
The thread running through the lesson is the carry. Single-column binary addition is trivial — it is just XOR for the sum and AND for the carry — but the moment numbers span more than one bit, each column must accept a carry in from the column on its right and may produce a carry out to the column on its left. The half adder cannot do this (it has no carry-in, which is exactly why it is only "half" an adder); the full adder can, and chaining full adders so each one's carry-out feeds the next one's carry-in builds an adder of any width. Understanding adders is therefore mostly understanding how carry information flows, and the cost of moving it along the chain is the headline limitation you must be able to explain.
Every truth table below is a markdown table, every Boolean expression is in KaTeX, and every circuit is a diagram — never ASCII art.
This lesson covers the adder strand of OCR H446 section 1.4.3 (Boolean algebra and its application), with a direct link to data representation in 1.4.1:
It depends on logic gates, XOR, and the logic-circuits lesson, and it feeds the full circuit-design lesson and the wider study of the ALU and processor.
Binary addition obeys the same column rules as decimal, with only the digits 0 and 1. For a single column of two bits there are four cases:
| A + B | Sum | Carry |
|---|---|---|
| 0 + 0 | 0 | 0 |
| 0 + 1 | 1 | 0 |
| 1 + 0 | 1 | 0 |
| 1 + 1 | 0 | 1 |
The only interesting case is 1+1: the result is two (102), so the column shows a sum of 0 and sends a carry of 1 to the next column left — exactly as 5+5=10 in decimal leaves a 0 and carries a 1. Capturing those two output bits, sum and carry, from the two input bits is the entire job of a half adder.
Multi-column addition then shows why a carry-in is needed. Consider 0112+0012 (3+1):
| Column | weight | A | B | carry-in | sum bit | carry-out |
|---|---|---|---|---|---|---|
| 0 (LSB) | 1 | 1 | 1 | 0 | 0 | 1 |
| 1 | 2 | 1 | 0 | 1 | 0 | 1 |
| 2 (MSB) | 4 | 0 | 0 | 1 | 1 | 0 |
Result 1002=4, correct. Notice column 1: it adds three bits — its two operand bits plus the carry coming from column 0. Only the least-significant column ever has a guaranteed carry-in of 0; every column above it must add three values, which is precisely why a half adder (two inputs) suffices for the LSB but a full adder (three inputs) is required everywhere else. The carry is the thread that stitches the columns together, and following it is the key to every adder in this lesson.
A half adder adds two single-bit inputs A and B, producing a sum S and a carry C.
| A | B | Sum (S) | Carry (C) |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
Read the two output columns as functions of A and B:
So the half adder is just two gates side by side, both fed by the same two inputs (a clean example of fan-out — A and B each drive two gates):
flowchart LR
A((A)) --> XOR{{"XOR"}}
B((B)) --> XOR
XOR --> S["S (Sum)"]
A --> AND{{"AND"}}
B --> AND
AND --> C["C (Carry)"]
Why "half"? Because it has no carry-in. It can add the least-significant column of two numbers (where there is nothing coming in from the right), but every column to the left of that may receive a carry from its neighbour, and the half adder has no input to accept one. To add multi-bit numbers we need a circuit with three inputs — the full adder.
A full adder adds three single-bit inputs — A, B and a carry-in (Cin) — and produces a sum S and a carry-out (Cout):
| A | B | Cin | Sum (S) | Cout |
|---|---|---|---|---|
| 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 |
The pattern in the Sum column is that S is 1 whenever an odd number of the three inputs are 1 — which is the three-input XOR:
S=A⊕B⊕Cin
The carry-out is 1 whenever at least two of the three inputs are 1 — the majority function. The standard compact form, and the one that drops out of the two-half-adder construction below, is:
Cout=(A⋅B)+(Cin⋅(A⊕B))
In words: there is a carry-out if both A and B are 1 (so a carry is generated regardless of the carry-in), or if exactly one of A and B is 1 (so A⊕B=1) and the carry-in is 1, which the lone 1 then propagates. The two ideas — carry generate (A⋅B) and carry propagate (A⊕B) — are named here because they are exactly what carry-lookahead adders exploit to go faster.
The full adder's structure is most easily seen as two half adders plus an OR gate.
Half adder 1 takes A and B: S1=A⊕B,C1=A⋅B
Half adder 2 takes S1 and Cin: S=S1⊕Cin=(A⊕B)⊕Cin C2=S1⋅Cin=(A⊕B)⋅Cin
The two partial carries are combined by an OR: Cout=C1+C2=(A⋅B)+((A⊕B)⋅Cin)
which is precisely the carry-out expression above.
flowchart LR
A((A)) --> HA1[["Half Adder 1"]]
B((B)) --> HA1
HA1 -- "S1 = A⊕B" --> HA2[["Half Adder 2"]]
Cin((Cin)) --> HA2
HA2 -- "S" --> S["S"]
HA1 -- "C1 = A·B" --> OR{{"OR"}}
HA2 -- "C2" --> OR
OR --> Cout["Cout"]
Why an OR rather than another XOR for the final carry? Because the two partial carries C1 and C2 can never both be 1 at once — if A⋅B=1 then A⊕B=0, killing C2 — so OR and XOR would behave identically here, and OR is the conventional, clearer choice. Expanding the half adders, a full adder is two XORs, two ANDs and one OR: five gates.
It is worth seeing the full adder drawn directly from its expressions, without the half-adder abstraction, because exam questions sometimes ask for the gate-level diagram. With S=A⊕B⊕Cin and Cout=(A⋅B)+(Cin⋅(A⊕B)), and reusing the single A⊕B signal in both outputs (fan-out again), the flat circuit is:
flowchart LR
A((A)) --> X1{{"XOR"}}
B((B)) --> X1
X1 -- "A⊕B" --> X2{{"XOR"}}
Cin((Cin)) --> X2
X2 --> S["S"]
A --> AN1{{"AND"}}
B --> AN1
X1 -- "A⊕B" --> AN2{{"AND"}}
Cin --> AN2
AN1 -- "A·B" --> OR{{"OR"}}
AN2 -- "Cin·(A⊕B)" --> OR
OR --> Cout["Cout"]
The intermediate A⊕B wire is computed once by the first XOR and then shared by the second XOR (for the sum) and the second AND (for the carry). Recognising that one signal can drive several downstream gates is what keeps the gate count at five rather than six. This flat view also makes the critical path visible: from an input through the first XOR, then either the second XOR (to S) or the second AND and the OR (to Cout) — roughly two gate delays to the carry-out, which is the per-stage delay quoted in the ripple-adder timing below.
To cement the behaviour, trace one full adder with A=1, B=1, Cin=1 (the all-ones row, which students most often get wrong).
So S=1, Cout=1 — which represents binary 112=3, exactly 1+1+1=3. The intuition trap here is expecting the sum to be 0 "because 1+1=10"; the third 1 (the carry-in) flips the sum bit back to 1 and the carry-out stays 1. The three-input XOR captures this "odd number of 1s" rule automatically.
To add multi-bit numbers, chain one full adder per bit position, wiring each adder's carry-out into the next adder's carry-in. The least-significant adder's carry-in is tied to 0 (or to 1 to perform subtraction, as below).
flowchart LR
C0(("Cin = 0")) --> FA0[["Full Adder 0<br/>A0, B0"]]
FA0 -- "S0" --> S0["S0"]
FA0 -- "carry" --> FA1[["Full Adder 1<br/>A1, B1"]]
FA1 -- "S1" --> S1["S1"]
FA1 -- "carry" --> FA2[["Full Adder 2<br/>A2, B2"]]
FA2 -- "S2" --> S2["S2"]
FA2 -- "carry" --> FA3[["Full Adder 3<br/>A3, B3"]]
FA3 -- "S3" --> S3["S3"]
FA3 -- "carry" --> COUT["Cout"]
The carry ripples from the least-significant adder up to the most-significant, which is where the name — and the speed limitation — comes from.
Worked trace. Add 01012 (5) and 00112 (3), bit by bit from the LSB, feeding each carry-out forward:
| Position | A | B | Cin | Sum | Cout |
|---|---|---|---|---|---|
| Bit 0 (LSB) | 1 | 1 | 0 | 0 | 1 |
| Bit 1 | 0 | 1 | 1 | 0 | 1 |
| Bit 2 | 1 | 0 | 1 | 0 | 1 |
| Bit 3 (MSB) | 0 | 0 | 1 | 1 | 0 |
Reading the Sum column from MSB to LSB gives 10002=8, and the final carry-out is 0 — so 5+3=8, correct. Notice how the carry-in of each row is the carry-out of the row above it: that data dependency is exactly what forces the columns to be computed in order, not in parallel.
The price of the ripple-carry adder's simplicity is propagation delay. Bit k's full adder cannot produce its correct sum until its carry-in is valid, and that carry-in is bit (k−1)'s carry-out, which in turn waited on bit (k−2), and so on back to the LSB. The carry must therefore ripple through every stage in sequence before the most-significant sum bit is guaranteed correct.
If each full adder contributes roughly two gate delays on the carry path, the worst-case delay grows linearly with the number of bits:
| Adder width | Approx. carry-path gate delays | Consequence |
|---|---|---|
| 4-bit | 4×2=8 | fast enough for most teaching examples |
| 8-bit | 8×2=16 | noticeable |
| 32-bit | 32×2=64 | significant — limits clock speed |
| 64-bit | 64×2=128 | unacceptably slow for a modern CPU |
Subscribe to continue reading
Get full access to this lesson and all 10 lessons in this course.