←→ move between slides · F full screen · M slide list
Before we start
Why this matters
How does a calculator add 127 + 1 and confidently tell you the answer is −128?
That's not the calculator having a stroke — it's called overflow, and a real version of this exact bug once sent an actual rocket (Ariane 5) into an actual meltdown seconds after launch. Underneath every calculator, cash register and CPU is a circuit that only ever adds, subtracts and compares — no fingers, no muttering “carry the one” under its breath. Let's build one that behaves.
Outline
Topics in this chapter
Select a topic to jump to the slide that explains it.
Outputs depend only on present inputs. There is no memory. Design procedure: read the specification, list inputs and outputs, write the truth table, derive expressions, simplify (Boolean algebra or K-map), implement, verify. Analysis runs the other way: label gate outputs, write expressions, combine, and check with a truth table.
Adding two bits by hand only has four cases: 0+0=0, 0+1=1, 1+0=1, and 1+1=10 — write down 0 and carry a 1 to the next column. A half adder is the circuit that does exactly this for a single bit: it takes A and B and produces two outputs, a sum bit and a carry bit. It has no carry-in of its own, which is why it's called “half”.
Click the switches to change the inputs and watch the LEDs. Use “Show truth table” when it appears.
Full adder
Full adder
A full adder extends the half adder with a third input, Cin — the carry arriving from the previous column. That extra input is what lets full adders be chained together into a multi-bit adder. It can be built from two half adders and an OR gate: the first half adder adds A and B; the second adds that sum to Cin; the two carry outputs are ORed to give Cout.
Full adder
A
B
Cin
Sum
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
Deriving Sum from the truth table's 1-rows: S = A′B′Cin + A′BCin′ + AB′Cin′ + ABCin. Group the pairs around A: A′(B′Cin + BCin′) + A(B′Cin′ + BCin) = A′(B⊕Cin) + A(B⊕Cin)′ = A ⊕ B ⊕ Cin. Deriving Cout the same way: Cout = A′BCin + AB′Cin + ABCin′ + ABCin. Group around Cin, then pull AB out of the remaining pair: Cin(A′B + AB′) + AB(Cin′ + Cin) = Cin(A⊕B) + AB.
S = A ⊕ B ⊕ Cin Cout = AB + ACin + BCin = AB + Cin(A ⊕ B)
Click the switches to change the inputs and watch the LEDs. Use “Show truth table” when it appears.
Subtractor
Half and full subtractor
Subtraction works the same way as addition but borrows instead of carrying: a half subtractor computes A − B for one bit, assuming no borrow-in. A full subtractor adds a borrow-in Bin, which is what's needed when chaining subtractors across multiple bits, just like Cin does for adders.
Deriving Difference from the 1-rows: D = A′B′Bin + A′BBin′ + AB′Bin′ + ABBin — the same pattern as the full adder's Sum: A′(B⊕Bin) + A(B⊕Bin)′ = A ⊕ B ⊕ Bin. Deriving Bout: Bout = A′B′Bin + A′BBin′ + A′BBin + ABBin. Group the 1st and 2nd terms around A′, and the 3rd and 4th around BBin: A′(B′Bin + BBin′) + BBin(A′ + A) = A′(B⊕Bin) + BBin — which expands to the same A′B + A′Bin + B·Bin shown above.
Equation and circuit
Full subtractor (two half subtractors + OR)
Half subtractor: D = A ⊕ B, Bout = A′B Full subtractor: D = A ⊕ B ⊕ Bin, Bout = A′B + A′Bin + B·Bin
Click the switches to change the inputs and watch the LEDs. Set Bin to 0 to see the half-subtractor case. Use “Show truth table” when it appears.
Equation and circuit
Full subtractor (two half subtractors + OR) (cont.)
4-bit adder
4-bit ripple-carry adder
Chaining n full adders, with each stage's carry-out feeding the next stage's carry-in, gives an n-bit ripple-carry adder. Drawn as a block diagram, each full adder (FA) is a box that takes Ai, Bi and a carry-in and produces Si and a carry-out — the diagram below chains four of them into a 4-bit adder. The name comes from the carry needing to “ripple” through every stage before the final sum is ready, so the worst-case delay grows with the number of bits.
Four full-adder blocks chained by their carry lines (orange) build a 4-bit adder, drawn like a paper addition: A0/B0 (the least significant bit) on the right, A3/B3 on the left, and the carry rippling right to left just like carrying a digit by hand.
Adder-subtractor
4-bit adder/subtractor
Hardware usually subtracts with 2’s complement: A − B = A + B′ + 1. Put an XOR gate on each bit of B, controlled by a single mode signal M, and feed M into the carry-in of the first stage. Each XOR acts as a controllable NOT: with its other input tied to M, it passes B through unchanged when M = 0 and complements it when M = 1. The same 4-bit adder block then does both jobs.
M = 0: each XOR passes B through unchanged, Cin = 0 → S = A + B M = 1: each XOR complements B, Cin = 1 → S = A + B′ + 1 = A − B
For signed numbers, overflow occurs when the carry into the MSB differs from the carry out of the MSB.
Same right-to-left, LSB-on-the-right layout as the plain adder. An XOR gate on each bit of B, with M (orange) entering from the side, works as the “NOT logic”: it either passes B straight through or complements it before the 4-bit adder sees it. M also feeds Cin, so M = 1 adds the extra +1 that 2’s-complement subtraction needs.
Interactive
Demo: 4-bit adder and subtractor
Magnitude comparator
1-bit magnitude comparator
A magnitude comparator outputs three signals: A>B, A=B and A<B. For multi-bit numbers, compare from the most significant bit down — the first pair that differs decides the result, and equal bits pass the decision down to the next pair. These blocks combine with multiplexers and logic gates to form an ALU.
A>B: G = AB′ A=B: E = (A ⊕ B)′ = A XNOR B A<B: L = A′B
E isn't just asserted — it falls out of the other two. Since G and L can never both be true, E is their combined complement: (A>B)+(A<B) = AB′+A′B, and by De Morgan, ((A>B)+(A<B))′ = (AB′)′(A′B)′ = (A′+B)(A+B′) = AB+A′B′, which is exactly A XNOR B — confirming E = (A ⊕ B)′.
Click the switches to change the inputs and watch the LEDs. Use “Show truth table” when it appears.
Equation and circuit
1-bit magnitude comparator (cont.)
Magnitude comparator
Multi-bit magnitude comparator
The 1-bit comparator is the base case. Wider comparators are built with exactly the MSB-down rule already mentioned: compare the top bits first, and only look at the next pair down if the top bits tie. Working through a 2-bit comparator (A1A0 vs B1B0) with a K-map gives:
Each term reads as a tie-break: A1B1′ fires when the top bit alone already decides it; A1A0B0′ fires only when the top bits tie (implicitly, since it's ANDed with the top-bit-decides terms in the full sum) and the next bit decides it instead. That same “tie, so fall through to the next stage” pattern is how fixed-width comparator ICs (e.g. the 74LS85 4-bit magnitude comparator) are chained to compare wider numbers: each chip exposes cascading inputs IA>B, IA=B and IA<B, and the equality/inequality outputs of the lower-order chip feed the higher-order chip's cascading inputs, so a tie at one stage falls through to the next. The least-significant stage's cascading inputs are simply tied to the “start out equal” default (IA>B = 0, IA=B = 1, IA<B = 0).
A BCD adder is a 4-bit binary adder followed by correction logic. Each BCD digit only uses codes 0000–1001 (0–9), so the largest possible sum is 9 + 9 + 1 = 19 — codes 1010–1111 never appear in valid BCD. Whenever the 4-bit sum exceeds 9 (or produces a carry), add 0110 (6) to skip over the six unused codes, producing the correct BCD digit plus a carry into the next decimal digit.
Sums above 9 need +6 (0110). The largest sum is 9 + 9 + 1 = 19.
Circuit diagram
BCD adder
A 4-bit binary adder produces a raw sum and carry; the correction block adds 0110 whenever the sum exceeds 9 or the adder already carried, producing a valid BCD digit and a carry into the next decimal digit.
Worked example 1 of 5
Worked example 1
Add 1011 + 0110 with a ripple-carry adder.
Show the solution
Bit 0: 1+0 = 1, carry 0
Bit 1: 1+1 = 0, carry 1
Bit 2: 0+1+1 = 0, carry 1
Bit 3: 1+0+1 = 0, carry 1
Result 1 0001 = 17.
Worked example 2 of 5
Worked example 2
Compute 0110 − 0011 with 2’s complement.
Show the solution
Invert B: 1100, add 1: 1101.
0110 + 1101 = 1 0011.
Discard the carry: 0011 = 3.
Worked example 3 of 5
Worked example 3
Add 7 + 8 in BCD.
Show the solution
0111 + 1000 = 1111 (greater than 1001).
Add 0110: 1111 + 0110 = 1 0101.
0001 0101 = 15.
Worked example 4 of 5
Worked example 4
Compare A = 0110 and B = 0101 using the MSB-down rule.
Show the solution
Bit 3: A=0, B=0 — tie, move to the next bit down.
Bit 2: A=1, B=1 — tie, move to the next bit down.
Bit 1: A=1, B=0 — they differ, and A's bit is the larger one.
The first pair that differs, scanning from the MSB, decides it: A > B (6 > 5). Bit 0 is never even examined.
Worked example 5 of 5
Worked example 5
Add the two-digit BCD numbers 47 + 38, correcting each decimal digit and carrying into the next.
Show the solution
Units digit: 0111 (7) + 1000 (8) = 1111 (15), which is > 9, so add 0110: 1111 + 0110 = 1 0101 — units digit 0101 (5), carry 1 into the tens digit.
Tens digit: 0100 (4) + 0011 (3) + carry-in 1 = 1000 (8), which is ≤ 9, so no correction is needed — tens digit 1000 (8).
Result 1000 0101 = 85.
Practice
Practice (1 of 2)
Try each one on paper first, then check your answer.
1. Derive the half adder equations.
Show the answer
S = A ⊕ B, C = AB.
2. How do you build a full adder from half adders?
Show the answer
The first half adder adds A and B. The second adds that sum and Cin. OR the two carry outputs to get Cout.
3. Derive the half subtractor equations.
Show the answer
D = A ⊕ B, Borrow = A′B.
Practice
Practice (2 of 2)
Try each one on paper first, then check your answer.
4. Explain ripple-carry delay.
Show the answer
Each stage must wait for the carry from the previous stage, so total delay is roughly n times the carry delay of one full adder.
5. Perform the BCD addition 7 + 8.
Show the answer
0001 0101 (15).
6. Design a 1-bit magnitude comparator.
Show the answer
G = AB′, E = A XNOR B, L = A′B.
Practice in Gate Forge
Open the Half adder and Full adder examples, then chain full adders into a 4-bit ripple-carry adder.
Open Gate ForgeGate ForgeA free circuit simulator — place and wire gates, generate truth tables and timing diagrams, and work through 90+ guided problems.
Check yourself
Quiz
Summary
Summary
Half adder: S = A⊕B, C = AB. Full adder adds a carry-in.
Ripple-carry is simple but slow for wide words.
A − B = A + B′ + 1. XOR gates plus carry-in make an adder-subtractor.
Signed overflow: carry into MSB ≠ carry out of MSB.
BCD correction: add 0110 when the sum exceeds 9 or carries.
Gate ForgeA free circuit simulator — place and wire gates, generate truth tables and timing diagrams, and work through 90+ guided problems.