Classroom Public page

Week 4: Logic Gates and Arithmetic

1,151 words

From Boolean operations to circuits that compute. A half-adder adds two 1-bit numbers. A full adder handles carry. Chain four full adders and you have a 4-bit calculator. That is the core of every ALU ever built.

Theme

Last week you filled in truth tables for AND, XOR, and NAND. This week you combine those gates into circuits that do useful things. The half-adder, which adds two bits and produces a sum and carry-out, is only two gates: XOR and AND. The full adder, which also accepts a carry-in, is a half-adder plus another half-adder plus an OR gate. Four full adders in series: a 4-bit ripple-carry adder that adds two 4-bit numbers.

This week's key insight: arithmetic is logic. There is no separate "arithmetic unit" that is fundamentally different from Boolean logic. It is all switches and wires, arranged to implement the truth tables you already know.

Reading list (~1 hour)

  1. Petzold CODE, Ch 12 ("A Binary Adding Machine"): Petzold builds a binary adder from relays, step by step. Read it slowly and trace every connection.
  2. Petzold CODE, Ch 13 ("How About Subtraction?"): how two's complement and the adder circuit handle subtraction without a separate subtractor circuit
  3. Optional: Wikipedia, "Adder (electronics)", the half-adder and full adder sections with circuit diagrams

Lecture outline (~2 hours)

Section 1: From gates to circuits

  • A gate is a physical device with inputs and outputs; in digital electronics, it is typically a CMOS transistor arrangement
  • Connecting gates produces a circuit; the output of one gate feeds the input of another
  • A combinational circuit has no memory: the output is a pure function of the current inputs with no dependence on history
  • Drawing circuits: convention is to draw gates as standard symbols (D-shape for AND, curved for OR, circle on output for NOT/invert)

Section 2: The half-adder

  • Adding two 1-bit numbers A and B produces two results: a sum bit and a carry-out bit
  • Sum truth table: A+B has sum 0 when both inputs are 0; sum 1 when exactly one is 1; sum 0 (with carry) when both are 1. That is XOR.
  • Carry-out truth table: carry is 1 only when both inputs are 1. That is AND.
  • Half-adder = one XOR gate + one AND gate
  • Limitation: no carry-in. Cannot be chained unless we handle the incoming carry from the previous bit position.

Section 3: The full adder

  • Full adder inputs: A, B, and Cin (carry-in from the next-lower bit)
  • Full adder outputs: Sum and Cout (carry-out to the next-higher bit)
  • Construction: two half-adders + one OR gate
    • First half-adder: A XOR B = partial sum; A AND B = partial carry
    • Second half-adder: (A XOR B) XOR Cin = final Sum; (A XOR B) AND Cin = partial carry 2
    • Cout = partial carry 1 OR partial carry 2
  • Verify by filling in the full 8-row truth table (3 inputs: A, B, Cin)

Section 4: 4-bit ripple-carry adder

  • Chain four full adders in series: bit 0 has Cin = 0; each adder's Cout feeds the next adder's Cin
  • Inputs: two 4-bit numbers (A3 A2 A1 A0) and (B3 B2 B1 B0)
  • Outputs: four sum bits (S3 S2 S1 S0) and a final carry-out (overflow flag)
  • The "ripple" in the name: the carry must propagate from bit 0 through all four positions before the final answer stabilizes; this sets the speed limit of the adder
  • For small bit widths (4-bit, 8-bit) the ripple is acceptable. For 64-bit adders in modern CPUs, more complex carry-lookahead schemes speed it up.
  • Example: add 0101 (5 decimal) + 0011 (3 decimal)
    • Bit 0: 1+1+0 = 10 binary; Sum=0, Cout=1
    • Bit 1: 0+1+1 = 10 binary; Sum=0, Cout=1
    • Bit 2: 1+0+1 = 10 binary; Sum=0, Cout=1
    • Bit 3: 0+0+1 = 01 binary; Sum=1, Cout=0
    • Result: 1000 = 8 decimal. Correct: 5+3=8.

Section 5: Subtraction via two's complement

  • How does a CPU subtract? Two's complement: negate the subtrahend (flip all bits, add 1) then add.
  • The same 4-bit adder circuit handles subtraction: just negate B before feeding it in
  • Negation circuit: NOT gates on each B bit + set Cin of bit 0 to 1 (that is the +1 step)
  • A single hardware circuit handles both addition and subtraction; the CPU chooses the operation by setting or clearing the Cin=1 signal on bit 0

Section 6: The ALU

  • Arithmetic Logic Unit: the component inside a CPU that performs arithmetic and logic operations
  • A real ALU extends the adder with:
    • Logic operations (AND, OR, XOR applied bitwise across all bit positions)
    • A selector input that chooses which operation to perform on each clock cycle
    • Additional flags: zero (result is all zeros), negative (result's MSB is 1), overflow, carry-out
  • CSA-101 students build an ALU in Verilog; FND-101 students understand the logical structure underneath

Labs (~90 minutes)

Lab 4.1: Half-Adder on Paper (labs/lab-4-1-half-adder-paper.md)

  • Design a 1-bit half-adder on paper: draw the circuit diagram with XOR and AND gates
  • Fill in the 4-row truth table to verify
  • Extend to a full adder (on paper): add the second half-adder and OR gate; verify the 8-row truth table
  • Artifact: hand-drawn and photographed circuit diagrams + completed truth tables committed to Git

Independent practice (~4 hours)

  1. Extend your 4-bit adder trace to add 0110 + 0111 (6+7=13). Carry-trace each bit position carefully.
  2. What happens when you add 1111 + 0001 (15+1) in 4-bit unsigned? What is the carry-out? What does the 4-bit result show?
  3. Implement a 1-bit full adder in Python (no + operator; use only and, or, not, ^). Test all 8 input combinations.
  4. Read Petzold Ch 13 carefully. Trace his two's complement subtraction example by hand.
  5. Optional: look up "carry-lookahead adder" and read the Wikipedia summary. How does it eliminate the ripple delay?

Reflection prompts (~30 minutes)

  1. The half-adder is two gates. The full adder is five gates (or fewer with optimization). A 4-bit adder is about 20 gates. A 64-bit adder has hundreds. Does this complexity surprise you, or does it feel proportional?
  2. The lecture said "arithmetic is logic." In what sense is the adder circuit "doing arithmetic" vs "following Boolean rules"? Is there a difference?
  3. You traced addition one bit at a time, carry propagating upward. Your computer's 64-bit adder does this billions of times per second. What does that tell you about how fast individual transistors must switch?
  4. Two's complement makes subtraction an addition problem in hardware. What is the hardware cost of this trick (how many extra components)?
  5. What is the CSA-101 connection you see here? (Hint: check the cross-references in the FND-101 outline.)

What comes next

Week 5 moves from combinational circuits (no memory) to sequential circuits (with memory). You will learn how a D flip-flop stores one bit by feeding output back into input, and how a bank of flip-flops forms a register. Memory is what makes a CPU stateful.