Capstone — Designing a Small Digital Circuit
Boolean Algebra & Digital Logic
Chapter 10 · Capstone — Designing a Small Digital Circuit
One continuous project: a real 3-bit adder/subtractor with overflow detection — the exact same technique a genuine ALU uses to compute both A+B and A-B from a single piece of hardware, touching every chapter of this course in the order a real designer would actually reach for each idea.
| Step | Task | Chapter(s) used |
|---|---|---|
| 1 | The core trick: one mode signal, reusing addition to do subtraction | Ch.9 (two's complement) |
| 2 | Wire the mode-select logic | Ch.1-3 (operators, laws), Ch.6 (gates) |
| 3 | Build the full 3-bit circuit | Ch.7 (full adders, chained) |
| 4 | Trace and verify four real cases | Ch.7, Ch.9 |
| 5 | Derive overflow detection from first principles | Ch.4 (canonical form), Ch.5 (simplification) |
| 6 | Full gate-count accounting | Ch.6 |
Step 1 — The Core Trick
Chapter 9 proved that negating a number in two's complement is "invert every bit, then add 1." A single mode signal M can trigger exactly that, on demand: XOR every bit of B with M (inverting B when M=1, leaving it unchanged when M=0), and feed M itself in as the initial carry-in (supplying the "+1"). When M=0: ordinary addition, A+B. When M=1: A + B' + 1 = A + (-B) = A - B.
Step 2 — Wiring the Mode-Select Logic
Three XOR gates (one per bit of B), each with M as one input — the smallest possible piece of combinational logic (Chapter 6) doing real, load-bearing work.
Step 3 — The Full 3-Bit Circuit
Three full adders, chained exactly as in Chapter 7's own ripple-carry adder — LSB first, each stage's COUT feeding the next stage's cin — except the chain's very first cin is M instead of a hardwired 0, and each adder's own B input is the XOR-modified bit from Step 2, not the raw bit.
Step 4 — Four Real Cases, Fully Traced
full_adder(0,1,cin=0) → SUM=1, COUT=0. Middle: full_adder(1,0,cin=0) → SUM=1, COUT=0. Sign/MSB: full_adder(0,0,cin=0) → SUM=0, COUT=0. Result: 3. Correct.
B XOR M flips 1 (001) to 110. LSB: full_adder(1,0,cin=1) → SUM=0, COUT=1. Middle: full_adder(1,1,cin=1) → SUM=1, COUT=1. Sign/MSB: full_adder(0,1,cin=1) → SUM=0, COUT=1. Result: 2. Correct.
SUM=0, COUT=1. Middle: SUM=1, COUT=0. Sign/MSB: SUM=1, COUT=0. Result bits 110, decoded as two's complement: −2. Correct — the exact same unmodified circuitry handles a negative result with no special case.
SUM=0, COUT=0. Middle: SUM=0, COUT=1. Sign/MSB: SUM=1, COUT=0. Raw result bits 100 decode as −4 — 2+2 is not −4. This is a genuine overflow: 4 falls outside the 3-bit signed range (−4 to 3, per Chapter 9). The circuit doesn't know this on its own — Step 5 builds the logic that catches it.
Step 5 — Deriving Overflow Detection From First Principles
Overflow happens exactly when the carry into the sign bit's own full adder disagrees with the carry out of it — one more bit "wanted" to flow in than the sign position can correctly represent. Both signals already exist as real wires in the circuit built in Step 3, so this is genuinely just overflow = carry_in_sign ⊕ carry_out_sign — a single XOR gate, no new adder logic required.
2+1: carry-in-to-sign 0, carry-out-of-sign 0 → overflow 0. 3−1: 1 and 1 → overflow 0. 1−3: 0 and 0 → overflow 0. 2+2: 1 and 0 → overflow 1 — the exact case flagged as suspicious above, now caught mechanically rather than by manual inspection.
Step 6 — Full Gate-Count Accounting
Each full adder needs 2 XOR + 2 AND + 1 OR gates (5 total, per Chapter 7's own SUM=x⊕y⊕cin, COUT=xy+cin(x⊕y) formulas, reusing the shared x⊕y signal). Three full adders: 15 gates. Three mode-select XOR gates: 3 gates. One overflow XOR gate: 1 gate.
What This Course Doesn't Cover
As stated honestly back in Chapter 1: full computer architecture/CPU design, VLSI/physical circuit engineering, and formal HDL tooling were named as deliberately out of scope, and stayed out of scope through all ten chapters. This capstone's own adder/subtractor is a genuine, real ALU building block — but a real ALU is many such blocks, plus instruction decoding, registers, and control logic this course never claimed to cover.
Where This Course Connects
Algorithms & Complexity's own "fewer operations, less time" reasoning reappeared directly in Chapter 6's gate-count argument, now paying off again in this capstone's own 19-gate, three-function circuit. Discrete Mathematics Fundamentals' own propositional logic was this course's own starting point (Chapter 1), and its proof-technique toolkit underwrote Chapter 3's own exhaustive law proofs. Number Theory & Cryptographic Math's own binary/modular reasoning and this course's Chapter 9 cover genuinely adjacent ground — worth revisiting side by side.
Hands-On Exercises
Using this chapter's own circuit, trace −1 + 1 (M=0) through all three full-adder stages, showing each stage's SUM and COUT, and confirm the result is 0 with no overflow.
Using this chapter's own overflow formula, check whether −3 − 2 (M=1) overflows the 3-bit signed range. Trace the circuit fully, compute the carry-into-sign and carry-out-of-sign values, and state whether the result is trustworthy.
Explain, using this chapter's own gate-count accounting, why building two separate circuits — one dedicated adder and one dedicated subtractor — would very likely need more than 19 gates combined, even though each one individually might look simpler than the combined adder/subtractor.
📄 View solutionChapter 10 Quick Reference
- Full worked project: two's-complement negation via XOR+carry-in (Ch.9) → mode-select gates (Ch.1-3,6) → chained full adders (Ch.7) → four fully traced/verified cases including a caught overflow → overflow formula derived from first principles (Ch.4-5) → full gate count (Ch.6)
- The exact same unmodified circuitry correctly handles addition, subtraction, and negative results — verified directly, no special-casing anywhere
- Overflow = carry-into-sign XOR carry-out-of-sign — one extra gate, reusing wires the circuit already has
- 19 gates total: a real adder, subtractor, and overflow detector, sharing nearly all their hardware
- Out of scope: full CPU/ALU design, VLSI engineering, HDL tooling
- Course complete — Boolean Algebra & Digital Logic, 10 chapters, from truth tables to a working adder/subtractor