Project 2: Logic Gate Simulator

Build the foundation of every CPU: wire together AND, OR, NOT, XOR, and NAND gates to create circuits that perform arithmetic. By the end, you’ll have built a working 8-bit adder from nothing but boolean logic.

Quick Reference

Attribute	Value
Language	C (alt: Rust, Python, JavaScript)
Difficulty	Beginner
Time	Weekend - 1 week
Knowledge Area	Digital Logic / Boolean Algebra
Coolness	Genuinely Clever
Portfolio Value	Resume Gold

Learning Objectives

By completing this project, you will:

Internalize boolean algebra: Apply De Morgan’s laws, understand truth tables, and see how any logic function can be built from NAND gates alone
Understand combinational logic: Build circuits where outputs depend only on current inputs (no memory, no state)
Construct a half-adder from first principles: See how XOR produces a sum bit and AND produces a carry
Chain full-adders into a ripple-carry adder: Understand why addition takes time (carry propagation delay)
Detect overflow and understand CPU flags: Implement the logic behind the Overflow, Carry, Zero, and Negative flags
Demystify the ALU: Realize that “addition” in a CPU is just carefully arranged logic gates

The Core Question You’re Answering

“How does a CPU add two numbers when it only has wires that can be ON or OFF?”

This question cuts to the heart of digital computing. When you type 3 + 5 in any programming language, somewhere deep in the silicon, this operation is performed by nothing but voltage levels flowing through transistors arranged as logic gates. By building an adder from gates, you’ll see that arithmetic isn’t magic - it’s just cleverly connected boolean operations.

After completing this project, when someone asks “How does a computer add?”, you won’t say “It just does.” You’ll draw a circuit diagram and explain exactly how carry propagation works.

Concepts You Must Understand First

Before starting this project, ensure you understand these concepts:

Concept	Why It Matters	Where to Learn
Binary number system	Gates operate on binary (0 and 1)	“Code” Chapters 7-9
Boolean AND, OR, NOT operations	These are the building blocks	“Code” Chapter 10
Truth tables	You’ll verify gate behavior with them	“Code” Chapter 10
How binary addition works by hand	You’re automating this in hardware	“Code” Chapter 12
Basic C: structs, pointers, arrays	For implementing the simulator	K&R Chapter 6

Self-Assessment Questions

Before starting, you should be able to answer:

What is 1 AND 0? What is 1 OR 0? What is NOT 1?
How do you add 0b1011 + 0b0101 by hand, including carries?
What is the truth table for XOR (exclusive or)?
Can you express A OR B using only NAND gates?

If you struggle with these, read “Code” Chapters 10-12 first.

Theoretical Foundation

Boolean Algebra: The Language of Logic

Boolean algebra is the mathematics of true/false values. In digital circuits, we represent:

TRUE as 1 (high voltage, ~3.3V or 5V)
FALSE as 0 (low voltage, ~0V)

The fundamental operations are:

AND (conjunction): Output is 1 only if BOTH inputs are 1
    A  B  | A AND B
    0  0  |    0
    0  1  |    0
    1  0  |    0
    1  1  |    1

OR (disjunction): Output is 1 if EITHER input is 1
    A  B  | A OR B
    0  0  |    0
    0  1  |    1
    1  0  |    1
    1  1  |    1

NOT (negation): Output is opposite of input
    A  | NOT A
    0  |   1
    1  |   0

Derived Gates

From AND, OR, and NOT, we can build other useful gates:

XOR (exclusive or): Output is 1 if inputs are DIFFERENT
    A  B  | A XOR B
    0  0  |    0
    0  1  |    1      ←  "One or the other, but not both"
    1  0  |    1
    1  1  |    0

NAND (not-and): Opposite of AND
    A  B  | A NAND B
    0  0  |    1
    0  1  |    1
    1  0  |    1
    1  1  |    0      ←  Only 0 when both inputs are 1

NOR (not-or): Opposite of OR
    A  B  | A NOR B
    0  0  |    1      ←  Only 1 when both inputs are 0
    0  1  |    0
    1  0  |    0
    1  1  |    0

The Universal Gate: NAND

A remarkable fact: any boolean function can be built using only NAND gates. This is why NAND is called a “universal gate.”

Building NOT from NAND:
    NOT A = A NAND A

    Proof:
    A | A NAND A
    0 |    1      (0 NAND 0 = NOT(0 AND 0) = NOT 0 = 1)
    1 |    0      (1 NAND 1 = NOT(1 AND 1) = NOT 1 = 0)

    This IS the NOT function!

Building AND from NAND:
    A AND B = NOT(A NAND B) = (A NAND B) NAND (A NAND B)

Building OR from NAND:
    A OR B = (A NAND A) NAND (B NAND B)
           = (NOT A) NAND (NOT B)

    By De Morgan's law: NOT(NOT A AND NOT B) = A OR B

De Morgan’s Laws

These fundamental equivalences are constantly used in circuit design:

NOT(A AND B) = (NOT A) OR (NOT B)
NOT(A OR B)  = (NOT A) AND (NOT B)

Visual representation:

    ┌───┐          ┌───┐   ┌───┐
A ──┤   │          │NOT├───┤   │
    │AND├──┬──NOT  │   │   │ OR├──
B ──┤   │  │       │   │   │   │
    └───┘  │       └───┘   │   │
           │  =    ┌───┐   │   │
           │       │NOT├───┤   │
           │       │   │   └───┘
           └───────┴───┘

From Logic to Arithmetic: The Half-Adder

Here’s the insight that bridges boolean logic to arithmetic:

When you add two 1-bit numbers:

+ 0 = 00  (sum=0, carry=0)
+ 1 = 01  (sum=1, carry=0)
+ 0 = 01  (sum=1, carry=0)
+ 1 = 10  (sum=0, carry=1)  ← This is "2" in binary!

Look at the patterns:

Sum bit: 1 only when inputs are DIFFERENT → This is XOR!
Carry bit: 1 only when BOTH inputs are 1 → This is AND!

Half-Adder Circuit:

        ┌─────────────┐
   A ───┤             ├───► Sum (A XOR B)
        │  HALF-ADDER │
   B ───┤             ├───► Carry (A AND B)
        └─────────────┘

Implementation:

   A ───┬───────┬───[XOR]───► Sum
        │       │
   B ───┼───┬───┘
        │   │
        └───┴───[AND]───► Carry

Truth table:
   A  B | Sum  Carry
   0  0 |  0     0
   0  1 |  1     0
   1  0 |  1     0
   1  1 |  0     1     ← 1+1 = "10" in binary (2 in decimal)

The Full-Adder: Handling Carry-In

A half-adder can only add two bits. But when adding multi-bit numbers, we need to handle the carry from the previous column. That’s what a full-adder does:

Full-Adder: Adds three bits (A, B, and Carry-In)

        ┌─────────────┐
   A ───┤             ├───► Sum
        │ FULL-ADDER  │
   B ───┤             ├───► Carry-Out
        │             │
  Cin ──┤             │
        └─────────────┘

Truth table:
   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    ← 1+1+1 = 3 = "11" in binary

The full-adder can be built from two half-adders:

Full-Adder from Half-Adders:

   A ────┬────────────────────────────────────────────┐
         │                                            │
   B ────┼────┐                                       │
         │    │                                       │
         ▼    ▼                                       ▼
       ┌──────────┐                              ┌──────────┐
       │   HALF   │──── Sum1 ───────────────────►│   HALF   │─► Sum
       │  ADDER 1 │                              │  ADDER 2 │
       │          │──── Carry1 ──┐               │          │─► Carry2
       └──────────┘              │               └──────────┘
                                 │                    ▲
   Cin ──────────────────────────┼────────────────────┘
                                 │
                                 ▼
                              ┌─────┐
                              │ OR  │────────────────────────► Cout
                              └─────┘
                                 ▲
                                 │
                              Carry2

Logic:
  Sum = (A XOR B) XOR Cin
  Cout = (A AND B) OR ((A XOR B) AND Cin)

The Ripple-Carry Adder: Adding Multi-Bit Numbers

To add 8-bit numbers, chain 8 full-adders together, with each carry-out feeding the next carry-in:

8-Bit Ripple-Carry Adder:

A7 B7    A6 B6    A5 B5    A4 B4    A3 B3    A2 B2    A1 B1    A0 B0
 │  │     │  │     │  │     │  │     │  │     │  │     │  │     │  │
 ▼  ▼     ▼  ▼     ▼  ▼     ▼  ▼     ▼  ▼     ▼  ▼     ▼  ▼     ▼  ▼
┌────┐   ┌────┐   ┌────┐   ┌────┐   ┌────┐   ┌────┐   ┌────┐   ┌────┐
│ FA │◄──│ FA │◄──│ FA │◄──│ FA │◄──│ FA │◄──│ FA │◄──│ FA │◄──│ FA │◄── 0
│  7 │   │  6 │   │  5 │   │  4 │   │  3 │   │  2 │   │  1 │   │  0 │   (Cin)
└──┬─┘   └──┬─┘   └──┬─┘   └──┬─┘   └──┬─┘   └──┬─┘   └──┬─┘   └──┬─┘
   │        │        │        │        │        │        │        │
   ▼        ▼        ▼        ▼        ▼        ▼        ▼        ▼
  S7       S6       S5       S4       S3       S2       S1       S0
   │
   └──► Cout (Carry out / Overflow detection)

The carry "ripples" from right to left, just like when you add by hand!

Why “Ripple” Carry? Understanding Propagation Delay

Each gate takes time to compute its output (nanoseconds in real hardware). In a ripple-carry adder, the carry must propagate through all 8 full-adders:

Time Analysis:

Time 0:  A0,B0 enter FA0
Time 1:  FA0 produces Sum0 and Carry0
Time 2:  Carry0 enters FA1, FA1 produces Sum1 and Carry1
Time 3:  Carry1 enters FA2...
...
Time 8:  Carry7 and Sum7 are finally valid

Total: 8 "gate delays" for the carry to propagate!

This is why faster adders exist (carry-lookahead, carry-select), but ripple-carry is the foundation you must understand first.

Overflow Detection: When Addition Goes Wrong

With 8 bits, you can represent:

Unsigned: 0 to 255
Signed (two’s complement): -128 to +127

Overflow occurs when the result doesn’t fit:

Unsigned Overflow:
  255 + 1 = 256, but 256 doesn't fit in 8 bits!
  11111111 + 00000001 = (1)00000000
                         ↑
                     Carry out indicates overflow

Signed Overflow (two's complement):
  127 + 1 = 128, but max positive 8-bit signed is 127!
  01111111 + 00000001 = 10000000
                        ↑
                     This is -128, not +128!

  Signed overflow = Carry into MSB XOR Carry out of MSB

CPU Status Flags

Real CPUs set flags after arithmetic operations:

┌─────────────────────────────────────────────────────────────┐
│                    STATUS REGISTER (FLAGS)                  │
├──────┬──────┬──────┬──────┬──────────────────────────────────┤
│  Z   │  N   │  C   │  V   │  ...                            │
│ Zero │ Neg  │Carry │ Over │                                 │
├──────┴──────┴──────┴──────┴──────────────────────────────────┤
│                                                              │
│  Z (Zero):     Result is all zeros                          │
│  N (Negative): Most significant bit of result is 1          │
│  C (Carry):    Unsigned overflow (carry out of MSB)         │
│  V (Overflow): Signed overflow (result sign is wrong)       │
│                                                              │
└──────────────────────────────────────────────────────────────┘

Example: 0x7F + 0x01 = 0x80

  Before: A = 01111111 (127), B = 00000001 (1)
  After:  S = 10000000 (-128 signed, 128 unsigned)

  Flags:
    Z = 0 (result is not zero)
    N = 1 (MSB is 1)
    C = 0 (no carry out of bit 7)
    V = 1 (positive + positive = negative? OVERFLOW!)

Project Specification

What You Will Build

A logic gate simulator with a command-line interface that allows you to:

Create individual logic gates (AND, OR, NOT, XOR, NAND, NOR)
Connect gates together to form circuits
Set input values and simulate the circuit
Build compound components (half-adder, full-adder, 8-bit adder)
Perform multi-bit addition with flag calculation

Functional Requirements

Gate Creation & Connection:
- Create named gates of any type
- Connect gate outputs to gate inputs
- Support multiple connections from one output (fan-out)
- Detect and report connection errors (cycles, missing inputs)
Simulation:
- Propagate signals through the circuit
- Handle multi-level circuits (gates connected to gates connected to gates)
- Support stepping through propagation or running to completion
Compound Components:
- Define reusable components from gates (e.g., half-adder as a “black box”)
- Instantiate components multiple times with unique naming
- Build hierarchical designs (full-adder from half-adders, 8-bit adder from full-adders)
8-Bit Adder:
- Add two 8-bit numbers
- Calculate and display: Sum, Carry, Zero, Negative, Overflow flags
- Show step-by-step carry propagation (optional debug mode)

Non-Functional Requirements

Correctness: All gate operations must match their truth tables exactly
Clarity: Output should explain what’s happening, not just show results
Modularity: Code should be organized so adding new gate types is easy
No External Dependencies: Standard library only (no simulation frameworks)

Real World Outcome

When complete, your simulator will work like this:

$ ./gatesim
Gate Simulator v1.0
Type 'help' for commands.

> CREATE and1 AND
Created AND gate 'and1'

> CREATE or1 OR
Created OR gate 'or1'

> CREATE not1 NOT
Created NOT gate 'not1'

> CONNECT and1.out -> or1.in1
Connected and1.out to or1.in1

> SET and1.in1 = 1
> SET and1.in2 = 0
> SET or1.in2 = 1
> SIMULATE
Propagating signals...
  and1: in1=1, in2=0 -> out=0
  or1: in1=0, in2=1 -> out=1
Result: or1.out = 1

> CLEAR

> -- Build a half-adder
> CREATE xor1 XOR
> CREATE and1 AND
> CONNECT input_a -> xor1.in1, and1.in1
> CONNECT input_b -> xor1.in2, and1.in2
> ALIAS xor1.out sum
> ALIAS and1.out carry
> SAVE half_adder

Component 'half_adder' saved with:
  Inputs: input_a, input_b
  Outputs: sum, carry

> LOAD half_adder AS ha1
> SET ha1.input_a = 1
> SET ha1.input_b = 1
> SIMULATE
Propagating signals...
  ha1.xor1: in1=1, in2=1 -> out=0
  ha1.and1: in1=1, in2=1 -> out=1
Result: sum=0, carry=1

Explanation: 1 + 1 = 10 in binary (sum=0, carry=1)

> BUILD 8bit_adder
Building 8-bit ripple-carry adder from full-adders...
  Created fa0, fa1, fa2, fa3, fa4, fa5, fa6, fa7
  Connected carry chain: fa0.cout -> fa1.cin -> ... -> fa7.cin
  Ready for operation.

> ADD 0b00001111 0b00000001
Adding: 15 + 1

Propagation (8 clock cycles for carry ripple):
  Cycle 1: FA0 computes, carry=0
  Cycle 2: FA1 computes, carry=0
  Cycle 3: FA2 computes, carry=0
  Cycle 4: FA3 computes, carry=0
  Cycle 5: FA4 computes, carry=1 (here's where the addition happens!)
  Cycle 6: FA5 computes, carry=0
  Cycle 7: FA6 computes, carry=0
  Cycle 8: FA7 computes, carry=0

Result:
  Input A:    00001111 (15)
  Input B:    00000001 (1)
  Sum:        00010000 (16)

Flags:
  Carry (C):    0 (no unsigned overflow)
  Zero (Z):     0 (result is not zero)
  Negative (N): 0 (MSB is 0)
  Overflow (V): 0 (no signed overflow)

> ADD 0xFF 0x01
Adding: 255 + 1

Result:
  Input A:    11111111 (255 unsigned, -1 signed)
  Input B:    00000001 (1)
  Sum:        00000000 (0)

Flags:
  Carry (C):    1 (UNSIGNED OVERFLOW! 256 doesn't fit in 8 bits)
  Zero (Z):     1 (result is zero)
  Negative (N): 0 (MSB is 0)
  Overflow (V): 0 (no signed overflow: -1 + 1 = 0 is correct)

> ADD 0x7F 0x01
Adding: 127 + 1

Result:
  Input A:    01111111 (127)
  Input B:    00000001 (1)
  Sum:        10000000 (128 unsigned, -128 signed)

Flags:
  Carry (C):    0 (no unsigned overflow)
  Zero (Z):     0 (result is not zero)
  Negative (N): 1 (MSB is 1, result looks negative)
  Overflow (V): 1 (SIGNED OVERFLOW! 127 + 1 should be 128, not -128)

Questions to Guide Your Design

Work through these questions BEFORE writing code:

Data Representation

How will you represent a gate’s state? (What struct fields do you need?)
How will you represent connections between gates?
How will you handle a gate that hasn’t been evaluated yet? (undefined state)
Should gate inputs be indices, pointers, or something else?

Simulation Algorithm

In what order should you evaluate gates? (Hint: topological sort, or iterative propagation until stable)
How do you detect when the circuit has stabilized?
How will you handle invalid circuits (cycles, missing connections)?
Should simulation be synchronous (all gates update at once) or asynchronous (one at a time)?

Composition

How will you build a half-adder from gates? (Separate function? Configuration file? DSL?)
How will you build a full-adder from half-adders?
How will you parameterize the bit-width of the adder?

User Interface

What commands does your CLI need?
How will users specify binary numbers? (0b prefix? Just assume binary?)
What error messages are most helpful when things go wrong?

Thinking Exercise

Before writing any code, work through these exercises on paper:

Exercise 1: Build XOR from NAND

Starting with only NAND gates, draw a circuit that computes A XOR B.

Hint: Use the identity A XOR B = (A NAND (A NAND B)) NAND (B NAND (A NAND B))

Verify your circuit with a truth table.

Exercise 2: Trace a Full-Adder

Given inputs A=1, B=1, Cin=1, trace through a full-adder step by step:

What does the first half-adder output?
What does the second half-adder output?
What is the final Cout?

Your answer should be Sum=1, Cout=1 (since 1+1+1 = 3 = “11” in binary).

Exercise 3: 4-Bit Addition

Manually trace the addition of 0b1011 + 0b0111 (11 + 7 = 18) through a 4-bit ripple-carry adder:

Position:    3      2      1      0
    A:       1      0      1      1
    B:       0      1      1      1
  Cin:       ?      ?      ?      0
  Sum:       ?      ?      ?      ?
 Cout:       ?      ?      ?      ?

Fill in all the ?’s. The final answer should be 0b10010 (18), with Cout=1 indicating overflow for 4 bits.

Exercise 4: Overflow Detection

For each addition, predict the flags (for 8-bit operations):

100 + 50 = ? Flags: Z=? N=? C=? V=?
200 + 100 = ? Flags: Z=? N=? C=? V=?
127 + 127 = ? Flags: Z=? N=? C=? V=?
-128 + (-128) = ? Flags: Z=? N=? C=? V=?

Hints in Layers

If you’re stuck, reveal hints one at a time:

Hint 1: Gate Data Structure

Start with a simple gate representation:

typedef enum {
    GATE_AND, GATE_OR, GATE_NOT,
    GATE_XOR, GATE_NAND, GATE_NOR
} GateType;

typedef struct Gate {
    char name[32];
    GateType type;
    int input1;      // -1 if unconnected, or index to another gate
    int input2;      // -1 for NOT gate (only one input)
    int output;      // 0, 1, or -1 (undefined)
    int evaluated;   // Has this gate been computed this cycle?
} Gate;

Store all gates in an array, refer to them by index.

Hint 2: Simulation Algorithm

Use iterative propagation until stable:

void simulate(Gate *gates, int num_gates) {
    int changed;
    int iterations = 0;
    int max_iterations = 1000; // Prevent infinite loops

    do {
        changed = 0;
        for (int i = 0; i < num_gates; i++) {
            int old_output = gates[i].output;
            int new_output = evaluate_gate(&gates[i], gates);
            if (new_output != old_output) {
                gates[i].output = new_output;
                changed = 1;
            }
        }
        iterations++;
    } while (changed && iterations < max_iterations);

    if (iterations >= max_iterations) {
        printf("Warning: Circuit did not stabilize (cycle detected?)\n");
    }
}

Hint 3: Building the Half-Adder

Create helper functions to build compound circuits:

// Returns indices of [sum_gate, carry_gate]
void build_half_adder(Gate *gates, int *count,
                      int input_a, int input_b,
                      int *sum_out, int *carry_out) {
    int xor_idx = *count;
    gates[xor_idx] = (Gate){
        .name = "xor",
        .type = GATE_XOR,
        .input1 = input_a,
        .input2 = input_b,
        .output = -1
    };
    (*count)++;

    int and_idx = *count;
    gates[and_idx] = (Gate){
        .name = "and",
        .type = GATE_AND,
        .input1 = input_a,
        .input2 = input_b,
        .output = -1
    };
    (*count)++;

    *sum_out = xor_idx;
    *carry_out = and_idx;
}

Hint 4: Building the Full-Adder

A full-adder uses two half-adders and an OR gate:

void build_full_adder(Gate *gates, int *count,
                      int input_a, int input_b, int carry_in,
                      int *sum_out, int *carry_out) {
    int ha1_sum, ha1_carry;
    build_half_adder(gates, count, input_a, input_b, &ha1_sum, &ha1_carry);

    int ha2_sum, ha2_carry;
    build_half_adder(gates, count, ha1_sum, carry_in, &ha2_sum, &ha2_carry);

    // Final carry = ha1_carry OR ha2_carry
    int or_idx = *count;
    gates[or_idx] = (Gate){
        .type = GATE_OR,
        .input1 = ha1_carry,
        .input2 = ha2_carry,
        .output = -1
    };
    (*count)++;

    *sum_out = ha2_sum;
    *carry_out = or_idx;
}

Hint 5: 8-Bit Adder Structure

Chain 8 full-adders, connecting carry-out to carry-in:

void build_8bit_adder(Gate *gates, int *count,
                      int *inputs_a,  // Array of 8 input indices
                      int *inputs_b,  // Array of 8 input indices
                      int *outputs,   // Array of 8 sum output indices
                      int *carry_out, int *overflow) {
    int carry = -1; // No carry-in to first adder (or use constant 0)
    int prev_carry = -1;

    for (int i = 0; i < 8; i++) {
        int sum, new_carry;
        build_full_adder(gates, count,
                        inputs_a[i], inputs_b[i], carry,
                        &sum, &new_carry);
        outputs[i] = sum;

        if (i == 7) {
            *carry_out = new_carry;
            // Overflow = carry_into_msb XOR carry_out_of_msb
            int xor_idx = *count;
            gates[xor_idx] = (Gate){
                .type = GATE_XOR,
                .input1 = carry,  // carry INTO bit 7
                .input2 = new_carry, // carry OUT OF bit 7
                .output = -1
            };
            (*count)++;
            *overflow = xor_idx;
        }

        carry = new_carry;
    }
}

Hint 6: Testing Your Implementation

Create test cases that verify corner cases:

void test_adder(void) {
    struct TestCase {
        uint8_t a, b;
        uint8_t expected_sum;
        int expected_carry, expected_overflow;
    } tests[] = {
        {0, 0, 0, 0, 0},
        {1, 1, 2, 0, 0},
        {255, 1, 0, 1, 0},    // Unsigned overflow
        {127, 1, 128, 0, 1},  // Signed overflow
        {128, 128, 0, 1, 1},  // Both overflows
        {127, 127, 254, 0, 1}, // 0x7F + 0x7F = 0xFE
    };

    for (int i = 0; i < sizeof(tests)/sizeof(tests[0]); i++) {
        // Run your adder and compare results
    }
}

Solution Architecture

High-Level Design

┌─────────────────────────────────────────────────────────────────────────┐
│                           Gate Simulator                                 │
├─────────────────────────────────────────────────────────────────────────┤
│                                                                          │
│  ┌──────────────┐   ┌──────────────┐   ┌──────────────┐   ┌───────────┐ │
│  │    Parser    │──▶│   Circuit    │──▶│  Simulator   │──▶│  Display  │ │
│  │  (Commands)  │   │   Builder    │   │   Engine     │   │  (Output) │ │
│  └──────────────┘   └──────────────┘   └──────────────┘   └───────────┘ │
│         │                  │                  │                 │        │
│         ▼                  ▼                  ▼                 ▼        │
│  ┌──────────────────────────────────────────────────────────────────────┐│
│  │                         Gate Array                                   ││
│  │    [Gate0] [Gate1] [Gate2] ... [GateN]                               ││
│  │                                                                       ││
│  │  Each gate stores: type, inputs (indices), output, name              ││
│  └──────────────────────────────────────────────────────────────────────┘│
│                                                                          │
└─────────────────────────────────────────────────────────────────────────┘

Key Components

Component	Responsibility	Key Decisions
Gate Array	Store all gates with their connections	Fixed array vs dynamic? Index-based connections
Gate Evaluator	Compute output from inputs for each gate type	Switch statement on gate type
Simulator	Propagate signals until stable	Iterative until no changes, with cycle detection
Circuit Builder	Construct compound circuits (adders)	Functions that add gates and wire them
Parser	Handle user commands	Simple string parsing, support hex/binary
Display	Format output for human understanding	Show step-by-step propagation, explain flags

Data Structures

#define MAX_GATES 1024
#define MAX_INPUTS 256

// Primary input (user-settable)
typedef struct {
    char name[32];
    int value;  // 0, 1, or -1 (undefined)
} PrimaryInput;

// Logic gate
typedef struct {
    char name[32];
    GateType type;
    int input1;      // Index into gates array, or negative for primary input
    int input2;      // For 2-input gates
    int output;      // Current output value
    int depth;       // For visualization / propagation order
} Gate;

// Complete circuit
typedef struct {
    PrimaryInput inputs[MAX_INPUTS];
    int num_inputs;
    Gate gates[MAX_GATES];
    int num_gates;
} Circuit;

Algorithm: Signal Propagation

FUNCTION propagate(circuit):
    iteration = 0
    max_iterations = num_gates * 2  // Reasonable bound

    REPEAT:
        changed = false

        FOR each gate in circuit:
            old_output = gate.output

            // Get input values (from other gates or primary inputs)
            in1 = get_input_value(gate.input1)
            in2 = get_input_value(gate.input2)

            // Skip if any input is undefined
            IF in1 == UNDEFINED or in2 == UNDEFINED:
                CONTINUE

            // Compute new output based on gate type
            new_output = compute_gate(gate.type, in1, in2)

            IF new_output != old_output:
                gate.output = new_output
                changed = true

        iteration++

    UNTIL not changed OR iteration >= max_iterations

    IF iteration >= max_iterations:
        REPORT "Circuit may have combinational loop"

Implementation Guide

Development Environment Setup

# Create project structure
mkdir -p gatesim/{src,include,tests}
cd gatesim

# Create Makefile
cat > Makefile << 'EOF'
CC = gcc
CFLAGS = -Wall -Wextra -g -I include
LDFLAGS =

SRC = src/main.c src/gate.c src/circuit.c src/simulate.c src/parser.c
OBJ = $(SRC:.c=.o)
TARGET = gatesim

all: $(TARGET)

$(TARGET): $(OBJ)
    $(CC) $(LDFLAGS) -o $@ $^

%.o: %.c
    $(CC) $(CFLAGS) -c -o $@ $<

clean:
    rm -f $(OBJ) $(TARGET)

test: $(TARGET)
    ./$(TARGET) < tests/test_basic.txt
EOF

Project Structure

gatesim/
├── include/
│   ├── gate.h          # Gate type definitions
│   ├── circuit.h       # Circuit data structure
│   ├── simulate.h      # Simulation functions
│   └── parser.h        # Command parsing
├── src/
│   ├── main.c          # Entry point, REPL loop
│   ├── gate.c          # Gate evaluation logic
│   ├── circuit.c       # Circuit building helpers
│   ├── simulate.c      # Propagation algorithm
│   └── parser.c        # Command parser
├── tests/
│   ├── test_basic.txt  # Basic gate tests
│   ├── test_adder.txt  # Half/full adder tests
│   └── test_8bit.txt   # 8-bit adder tests
├── Makefile
└── README.md

Implementation Phases

Phase 1: Basic Gates (Day 1)

Goals:

Implement the 6 basic gate types
Create the gate evaluation function
Test each gate with its truth table

Tasks:

Define GateType enum and Gate struct
Implement evaluate_gate() function with switch statement
Write unit tests for each gate type
Verify truth tables match exactly

Checkpoint: All 6 gate types produce correct outputs for all input combinations.

Phase 2: Circuit Connections (Day 2)

Goals:

Connect gates together
Implement signal propagation
Handle undefined states

Tasks:

Implement connection tracking (which gate output connects to which input)
Implement iterative propagation algorithm
Handle gates with undefined inputs (don’t evaluate until inputs are defined)
Test with simple 2-3 gate circuits

Checkpoint: A 3-gate circuit (like NOT(AND(A,B))) produces correct output.

Phase 3: Half-Adder and Full-Adder (Days 3-4)

Goals:

Build half-adder from XOR and AND
Build full-adder from two half-adders
Verify with all input combinations

Tasks:

Create build_half_adder() function
Create build_full_adder() function
Write comprehensive tests for all 4 half-adder inputs
Write comprehensive tests for all 8 full-adder inputs
Verify carry propagation works correctly

Checkpoint: Full-adder produces correct sum and carry for all 8 input combinations.

Phase 4: 8-Bit Ripple-Carry Adder (Days 5-6)

Goals:

Chain 8 full-adders
Implement flag calculation
Test edge cases

Tasks:

Create build_8bit_adder() function
Implement Zero flag (NOR of all sum bits)
Implement Negative flag (just the MSB of sum)
Implement Carry flag (carry out of MSB)
Implement Overflow flag (XOR of carry into and out of MSB)
Test: 0+0, 1+1, 127+1, 255+1, 128+128

Checkpoint: 8-bit adder handles all edge cases correctly, flags match expected values.

Phase 5: Command-Line Interface (Day 7)

Goals:

Parse user commands
Display results clearly
Add convenience features

Tasks:

Implement command parser (CREATE, CONNECT, SET, SIMULATE, ADD)
Support binary (0b) and hex (0x) input formats
Add verbose mode showing propagation steps
Display results with explanation
Add HELP command

Checkpoint: User can interactively build circuits and perform 8-bit addition.

Testing Strategy

Test Categories

Category	Purpose	Examples
Unit Tests	Verify each gate type	AND(1,1)=1, OR(0,0)=0
Integration Tests	Verify compound circuits	Half-adder, full-adder
Edge Cases	Verify boundary conditions	255+1, 127+1, 128+128
Regression Tests	Catch regressions after changes	All previous tests

Critical Test Cases

// Gate tests
assert(and_gate(0, 0) == 0);
assert(and_gate(0, 1) == 0);
assert(and_gate(1, 0) == 0);
assert(and_gate(1, 1) == 1);
// ... similar for all 6 gates

// Half-adder tests
assert(half_adder(0, 0) == (Sum: 0, Carry: 0));
assert(half_adder(0, 1) == (Sum: 1, Carry: 0));
assert(half_adder(1, 0) == (Sum: 1, Carry: 0));
assert(half_adder(1, 1) == (Sum: 0, Carry: 1));

// Full-adder tests (all 8 combinations)
assert(full_adder(0, 0, 0) == (Sum: 0, Cout: 0));
assert(full_adder(0, 0, 1) == (Sum: 1, Cout: 0));
assert(full_adder(0, 1, 0) == (Sum: 1, Cout: 0));
assert(full_adder(0, 1, 1) == (Sum: 0, Cout: 1));
assert(full_adder(1, 0, 0) == (Sum: 1, Cout: 0));
assert(full_adder(1, 0, 1) == (Sum: 0, Cout: 1));
assert(full_adder(1, 1, 0) == (Sum: 0, Cout: 1));
assert(full_adder(1, 1, 1) == (Sum: 1, Cout: 1));

// 8-bit adder tests
assert(add8(0, 0) == (Sum: 0, C: 0, Z: 1, N: 0, V: 0));
assert(add8(1, 1) == (Sum: 2, C: 0, Z: 0, N: 0, V: 0));
assert(add8(15, 1) == (Sum: 16, C: 0, Z: 0, N: 0, V: 0));
assert(add8(255, 1) == (Sum: 0, C: 1, Z: 1, N: 0, V: 0));  // Unsigned overflow
assert(add8(127, 1) == (Sum: 128, C: 0, Z: 0, N: 1, V: 1)); // Signed overflow
assert(add8(128, 128) == (Sum: 0, C: 1, Z: 1, N: 0, V: 1)); // Both overflows

Common Pitfalls & Debugging

Frequent Mistakes

Pitfall	Symptom	Solution
Connecting to wrong input	Wrong results	Double-check connection indices
Forgetting to propagate	Outputs stay undefined	Run propagation until stable
Cycle in combinational logic	Infinite loop	Detect cycles or limit iterations
Wrong XOR truth table	Sum bits are wrong	XOR is 1 when inputs DIFFER, not when they’re the same
Wrong overflow detection	V flag is wrong	Overflow = Cin to MSB XOR Cout of MSB, not just Cout
Zero flag on wrong bits	Z flag always 0 or 1	Z = NOR of ALL sum bits

Debugging Strategies

Print gate state after each propagation step: See exactly what’s happening
Test each gate type in isolation first: Verify truth tables before building circuits
Test half-adder before full-adder: Build up complexity gradually
Compare against hand calculation: Do the addition on paper, trace through your circuit
Use small bit widths first: Debug a 4-bit adder before 8-bit

Performance Notes

A ripple-carry adder with N bits needs O(N) gate evaluations to stabilize
For 8 bits, expect ~8 propagation iterations (one per carry stage)
If you exceed 100 iterations, you likely have a bug (or an actual cycle)

Extensions & Challenges

Beginner Extensions

Add XNOR gate: Output 1 when inputs are the SAME
Visualize with ASCII art: Draw the circuit diagram
Save/load circuits to file: Persist circuit definitions

Intermediate Extensions

Build a subtractor: Use two’s complement (invert B, add 1)
Implement multiplexer (MUX): Select between inputs based on control signal
Build a 4-bit ALU: Add, subtract, AND, OR, XOR based on opcode

Advanced Extensions

Carry-lookahead adder: Eliminate ripple delay with parallel carry calculation
Sequential logic: Add flip-flops, build a register
Build a shift register: Essential for multiplication
Graphical visualization: Use SDL or terminal graphics to draw gates

Self-Assessment Checklist

Before considering this project complete, verify:

Understanding

I can draw a half-adder circuit from memory
I can explain why XOR produces the sum bit
I understand carry propagation delay and why it matters
I can explain the difference between Carry and Overflow flags
I can build any gate from NANDs alone

Implementation

All 6 gate types produce correct outputs
Half-adder works for all 4 input combinations
Full-adder works for all 8 input combinations
8-bit adder produces correct sums
All 4 flags (Z, N, C, V) are correctly calculated

Growth

I traced through an addition by hand before coding
I understand why 127+1 causes signed overflow but not unsigned
I can explain what would happen with a 16-bit or 32-bit adder
I see how this connects to real CPU ALU design

The Interview Questions They’ll Ask

After completing this project, you’ll be ready for these common interview questions:

“How does a CPU add two numbers?”
- They want: Addition is performed by an ALU built from logic gates. A full-adder combines XOR (for sum) and AND/OR (for carry). Multiple full-adders are chained to create a multi-bit adder.
“What is a ripple-carry adder and what’s its limitation?”
- They want: Each bit must wait for the carry from the previous bit, creating O(N) delay. Faster alternatives include carry-lookahead adders.
“Explain the difference between the Carry and Overflow flags”
- They want: Carry = unsigned overflow (result doesn’t fit). Overflow = signed overflow (result has wrong sign). They can differ: 255+1 sets C but not V, 127+1 sets V but not C.
“What is a universal gate and why does it matter?”
- They want: NAND (or NOR) can implement any boolean function. This simplifies chip manufacturing - you only need one type of transistor configuration.
“How would you make addition faster?”
- They want: Carry-lookahead calculates carries in parallel. Carry-select computes both possible results and selects based on carry. Modern CPUs use sophisticated hybrid approaches.
“What is combinational vs sequential logic?”
- They want: Combinational = output depends only on current inputs (no memory). Sequential = has state/memory (flip-flops, registers). Your adder is combinational.

Real-World Connections

Industry Applications

CPU Design: Every processor has an ALU built from gates like these
FPGA Development: You’d implement these gates in Verilog/VHDL
Hardware Verification: Testing gate-level simulations before fabrication
Embedded Systems: Understanding hardware helps optimize software
Security Research: Hardware trojans, side-channel attacks exploit gate-level behavior

Logisim: Visual logic gate simulator (Java)
Verilator: Verilog simulator
GHDL: VHDL simulator
Digital: Educational digital logic simulator

Where This Knowledge Applies

After this project, you’ll understand:

How Verilog/VHDL hardware description languages work
Why carry-lookahead is mentioned in CPU marketing
What hardware engineers mean by “propagation delay”
How to think about computation at the transistor level

Resources

Essential Reading

“Code: The Hidden Language” by Charles Petzold, Chapters 10-12: Boolean logic to adders
“Digital Design and Computer Architecture” by Harris & Harris, Chapter 1: Digital logic fundamentals
“Computer Organization and Design” by Patterson & Hennessy, Chapter 3.2: Building an ALU

Video Resources

Ben Eater’s 8-bit computer series: Physical logic gates on breadboard
Nand2Tetris lectures: Building a computer from NAND gates up

Interactive Learning

Nand2Tetris (nand2tetris.org): Build a computer starting from NAND gates
CircuitVerse: Browser-based logic gate simulator
Logisim Evolution: Desktop logic simulator with visualization

Books That Will Help

Topic	Book	Chapter
Boolean Algebra Fundamentals	Code: The Hidden Language	Ch. 10-11
Logic Gate Implementation	Digital Design and Computer Architecture	Ch. 1
Building an Adder	Code: The Hidden Language	Ch. 12
Carry Propagation & ALU Design	Computer Organization and Design	Ch. 3.2-3.3
Carry-Lookahead Adders	Computer Organization and Design	Ch. 3.2
CPU Flags and Condition Codes	Computer Systems: A Programmer’s Perspective	Ch. 3.6

Submission / Completion Criteria

Minimum Viable Completion:

All 6 basic gate types work correctly
Half-adder and full-adder produce correct outputs
8-bit addition works for simple cases
Basic CLI allows user to perform additions

Full Completion:

All flag calculations (Z, N, C, V) are correct
Edge cases handled (overflow, boundary values)
Clear output explains results
Propagation delay is visible in verbose mode
Code is well-structured and commented

Excellence (Going Above & Beyond):

Subtraction mode (using two’s complement)
4-bit ALU with multiple operations
Carry-lookahead adder implementation
Visual circuit diagram output
Performance comparison between adder types

Learning Milestones

Milestone 1: Individual Gates Work

What it proves: You understand boolean logic Test: All 6 gates pass truth table verification Time: End of Day 1

Milestone 2: Half-Adder Works

What it proves: You can combine gates to perform arithmetic Test: 1+1 produces sum=0, carry=1 Time: End of Day 3

Milestone 3: 8-Bit Adder with Flags

What it proves: You understand how CPUs really add numbers Test: 127+1 produces sum=128, V=1, and you can explain why Time: End of Day 6

This guide was expanded from CPU_ISA_ARCHITECTURE_PROJECTS.md. For the complete learning path, see the project index.

“The path from NAND to addition is the path from physics to mathematics. Walk it, and you’ll never see computation the same way again.”

Project 2: Logic Gate Simulator

Quick Reference

Learning Objectives

The Core Question You’re Answering

Concepts You Must Understand First

Self-Assessment Questions

Theoretical Foundation

Boolean Algebra: The Language of Logic

Derived Gates

The Universal Gate: NAND

De Morgan’s Laws

From Logic to Arithmetic: The Half-Adder

The Full-Adder: Handling Carry-In

The Ripple-Carry Adder: Adding Multi-Bit Numbers

Why “Ripple” Carry? Understanding Propagation Delay

Overflow Detection: When Addition Goes Wrong

CPU Status Flags

Project Specification

What You Will Build

Functional Requirements

Non-Functional Requirements

Real World Outcome

Questions to Guide Your Design

Data Representation

Simulation Algorithm

Composition

User Interface

Thinking Exercise

Exercise 1: Build XOR from NAND

Exercise 2: Trace a Full-Adder

Exercise 3: 4-Bit Addition

Exercise 4: Overflow Detection

Hints in Layers

Solution Architecture

High-Level Design

Key Components

Data Structures

Algorithm: Signal Propagation

Implementation Guide

Development Environment Setup

Project Structure

Implementation Phases

Phase 1: Basic Gates (Day 1)

Phase 2: Circuit Connections (Day 2)

Phase 3: Half-Adder and Full-Adder (Days 3-4)

Phase 4: 8-Bit Ripple-Carry Adder (Days 5-6)

Phase 5: Command-Line Interface (Day 7)

Testing Strategy

Test Categories

Critical Test Cases

Common Pitfalls & Debugging

Frequent Mistakes

Debugging Strategies

Performance Notes

Extensions & Challenges

Beginner Extensions

Intermediate Extensions

Advanced Extensions

Self-Assessment Checklist

Understanding

Implementation

Growth

The Interview Questions They’ll Ask

Real-World Connections

Industry Applications

Related Open Source Projects

Where This Knowledge Applies

Resources

Essential Reading

Video Resources

Interactive Learning

Books That Will Help

Submission / Completion Criteria

Learning Milestones

Milestone 1: Individual Gates Work

Milestone 2: Half-Adder Works

Milestone 3: 8-Bit Adder with Flags