Digital Logic Components¶

Overview¶

This lecture builds on the gate-level foundations (gates, wires, splitters, sum-of-products, and the ripple-carry adder) to introduce the idea of circuits as reusable components. We design a 1-bit comparator from a truth table, then abstract it into a box and compose copies of that box (using splitters and buses) into 2-bit, 8-bit, and N-bit comparators. We then introduce the multiplexor (MUX) — the universal selection component — implement it directly from its truth table, scale it to wider data and more inputs, and show how MUXes drive an Arithmetic Logic Unit (ALU). We finish by deriving subtraction from addition (invert-then-add-one) and previewing sequential logic, where a clock and stored state let circuits compute over time. The near-term goal for Project 5 is a static analyzer circuit that reads 32-bit machine instructions and counts instruction types.

Learning Objectives¶

Distinguish combinational logic (output depends only on input; the circuit is a DAG) from sequential logic (output depends on input and stored state)
Derive a 1-bit comparator from its truth table and recognize it as an XNOR
Abstract a circuit into a reusable component and control its appearance and ports
Use splitters and buses to break a wide value into bit-fields and feed parallel sub-components
Compose 1-bit comparators into 2-bit, 8-bit, and N-bit comparators
Implement a multiplexor (MUX) from a truth table via sum-of-products, and scale it in width and input count
Explain how MUXes select among parallel arithmetic units to form an ALU
Build subtraction from addition using two's complement (invert then add one)
Describe the structure of a sequential circuit: clock, state register, and a feedback loop through combinational logic

Prerequisites¶

Boolean algebra, truth tables, and the sum-of-products method
The three fundamental gates (AND, OR, NOT) and derived gates (XOR, XNOR, NAND, NOR)
Half adder, full adder, and the ripple-carry adder
Two's complement representation and binary arithmetic — see /guides/key-concepts/
Familiarity with the Digital schematic simulator (wires, splitters, inputs, outputs, ROM)
RISC-V instruction formats (R, I, S, B, J types) — needed for Project 5 context
Source notes: "/notes/CS315-01 2025-10-21 Digital Logic Components.pdf"

1. Where We Are: Combinational Logic Recap¶

Before introducing new components, the lecture recapped the digital-design vocabulary we already have. Everything in this lecture is built from these pieces.

flowchart LR
    G["Gates<br/>AND / OR / NOT<br/>XOR / XNOR"] --> SOP["Sum-of-Products<br/>(truth table -> equation -> circuit)"]
    SOP --> ADD["Ripple-Carry Adder"]
    ADD --> COMP["Circuits as Components<br/>(comparators, MUXes, ALU)"]
    COMP --> SEQ["Sequential Logic<br/>(clock + state)"]

    style COMP fill:#f9f,stroke:#333,stroke-width:2px

Building blocks at a glance¶

Element	Symbol idea	Role
Gate	AND `D-`, OR `D)-`, NOT `-Do-`	Computes one Boolean function
Wire	line	Carries a single bit (or a bus carries many)
Input	square pad	A signal entering the circuit
Output	circle pad	A signal leaving the circuit
Splitter	thick bar	Breaks a wide bus into bit ranges (or merges)

Combinational logic¶

Combinational logic means the outputs depend only on the current inputs — there is no memory of the past.

The circuit is a DAG (directed acyclic graph): signals flow from inputs to outputs with no feedback loops.
Given the same inputs, you always get the same outputs.
Examples so far: gates, adders, and (today) comparators and multiplexors.

Contrast this with sequential logic (Section 9), where a feedback loop and a clock let the circuit hold state, so the output can depend on history.

Sum-of-products, in one line¶

To turn any truth table into a circuit:

Write one product term (AND of inputs, with NOT on the 0-valued inputs) for each row whose output is 1.
OR all those product terms together.

This always yields a correct two-level (AND-then-OR) combinational circuit. We use it repeatedly below.

Near-term goal: static analysis¶

The arc of these labs is to build a static analyzer in Digital: a circuit that reads 32-bit RISC-V machine instructions out of a ROM and counts how many of each instruction type appear (Project 5). That requires comparators (to recognize opcode fields), multiplexors and adders (to route and accumulate), and registers/counters (sequential state). This lecture supplies those components, and Project 6 extends them into a full processor.

2. The 1-Bit Comparator¶

A comparator answers a yes/no question: is a == b? We start with the simplest case, a single bit each.

Truth table¶

With one bit each, a and b are equal in exactly two of the four rows: when both are 0 and when both are 1.

a	b	eq?
0	0	1
0	1	0
1	0	0
1	1	1

Sum-of-products equation¶

Two rows produce a 1, so we OR together two product terms — one for a=0,b=0 and one for a=1,b=1:

eq = (a' . b') + (a . b)

(a' means NOT a; . is AND; + is OR.) The first term fires when both inputs are 0; the second fires when both are 1.

This is XNOR¶

Comparing the comparator's truth table against XOR and XNOR reveals the shortcut:

a	b	XOR	NOT-XOR (XNOR)	eq?
0	0	0	1	1
0	1	1	0	0
1	0	1	0	0
1	1	0	1	1

The eq? column is identical to XNOR. That makes sense:

XOR is 1 exactly when the bits differ.
XNOR (NOT-XOR) is 1 exactly when the bits are the same — which is precisely equality.

So a 1-bit comparator is just an XNOR gate:

 a ---|        |
      | XNOR   |o--- eq        eq = NOT(a XOR b)
 b ---|        |

Abstract it into a component¶

In Digital we draw the gate-level circuit once, then collapse it into a reusable box with two inputs (a, b) and one output (eq). The little 1 tick marks on the wires indicate 1-bit signals. From now on we draw the comparator as:

        +-----------+
 a --1--| a         |
        |        eq |--1-- eq
 b --1--| b         |
        +-----------+
        (1-bit comparator)

Inside the box is the XNOR; outside, we just see "are these two bits equal?" This abstraction is the key move of the whole lecture — once a circuit is a box, we can wire many copies together without thinking about the gates inside.

3. Circuits as Components and Abstraction¶

The single most important idea today is treating a circuit as a black-box component with named ports, exactly like a function in C.

Software analogy	Hardware analogy
Function signature	Component ports (inputs / outputs)
Function body	The gate-level circuit inside the box
Calling the function	Wiring up an instance of the component
Reusing the function many times	Instantiating many copies of the component

Benefits:

Composition — build big circuits from small, tested ones (1-bit comparator → 8-bit comparator).
Readability — the top level shows intent, not gate clutter.
Reuse — one definition, many instances.

In Digital you can also control a component's appearance: choose where ports appear, give them labels, and set the box size. The instructor stressed treating circuit design like code: keep wire layout clean and consistent, route buses neatly, and organize the schematic so a reader can follow the signal flow. Circuit quality counts (it is literally part of the Project 5 rubric).

flowchart TD
    subgraph Inside["Inside the component (hidden)"]
        X["XNOR gate"]
    end
    subgraph Outside["Outside view (what callers see)"]
        P["a, b  -->  [ 1-bit comparator ]  -->  eq"]
    end
    Inside -. "abstract / collapse" .-> Outside

4. The 2-Bit Comparator: Compose + Split + Combine¶

To compare two 2-bit values, two numbers are equal iff every bit position is equal. So we compare bit 0 to bit 0, bit 1 to bit 1, and AND the per-bit results.

The pattern¶

Split each 2-bit input into its two individual bits (this is what the splitter does).
Feed corresponding bits into two 1-bit comparators.
AND the two eq outputs together — equal overall only if both bit positions matched.

            +--------------+
 a(2) --[split]-- a1 ------| 1-bit  | eq1
              \   b1 ------| cmp    |---+
               \                        |
                \                      +---+
                 \                     |AND|--- eq (1-bit)
                /                      +---+
               /                        |
              /   a0 ------| 1-bit  | eq0
 b(2) --[split]-- b0 ------| cmp    |---+
            +--------------+

Why this works¶

101 == 101   ->  eq  (every bit matches)
100 =/= 101   ->  not eq  (bit 0 differs, so the AND is 0)

Equality is conjunctive: a single mismatched bit anywhere forces the answer to "not equal," which the final AND captures perfectly. The 2 tick on the input wire marks a 2-bit bus; after the splitter, each branch is a 1-bit wire.

5. Scaling Up: N-Bit Comparators¶

The same recursive idea scales to any width. The lecture showed the 8-bit comparator built from two 4-bit comparators, where each 4-bit comparator is itself built from 1-bit comparators.

8-bit comparator¶

Split each 8-bit input into a high nibble (4 bits) and a low nibble (4 bits).
Feed each nibble pair into a 4-bit comparator (each produces one eq bit).
AND the two 4-bit eq results to get the final 8-bit eq.

 a(8) --[split]--+-- a[7:4] (4) --| 4-bit |-- eq_hi (1)
                 |   b[7:4] (4) --| cmp   |          \
                 |                                    +---+
                 |                                    |AND|-- eq
                 |                                    +---+
                 |   a[3:0] (4) --| 4-bit |-- eq_lo (1)  /
 b(8) --[split]--+-- b[3:0] (4) --| cmp   |----------+

The recursive structure¶

This is divide-and-conquer in hardware: an N-bit comparator splits into two (N/2)-bit comparators whose results are ANDed. At the leaves sit 1-bit XNOR comparators.

flowchart TD
    C8["8-bit comparator"] --> C4a["4-bit comparator (high)"]
    C8 --> C4b["4-bit comparator (low)"]
    C4a --> C1a["1-bit cmp x4"]
    C4b --> C1b["1-bit cmp x4"]
    C4a -. AND .-> AND8(("AND -> eq"))
    C4b -. AND .-> AND8

Comparators in C (the same idea)¶

The hardware computation has a direct software analog. A bit-by-bit equality test ANDs all the per-bit comparisons; in C we'd more simply write a == b, but the per-bit version mirrors the circuit:

#include <stdint.h>
#include <stdbool.h>

// Mirror of the bit-by-bit hardware comparator for an 8-bit value.
bool eq8(uint8_t a, uint8_t b) {
    bool eq = true;
    for (int i = 0; i < 8; i++) {
        int abit = (a >> i) & 1;
        int bbit = (b >> i) & 1;
        bool bit_eq = (abit == bbit);   // XNOR of the two bits
        eq = eq && bit_eq;              // AND-reduce across positions
    }
    return eq;
}

// In real code you would just write:  return a == b;

For Project 5, comparators recognize fixed bit patterns: you compare an instruction's opcode field against a constant like the R-type opcode, or compare the whole 32-bit word against the end-of-program marker 0xC0001073 (unimp).

6. The Multiplexor (MUX)¶

A multiplexor, or MUX, is a hardware "switch" or if/select: a select signal s chooses which of several data inputs is routed to the output. It is the single most useful component for building processors.

1-bit, 2-input MUX¶

Two data inputs (a, b), one select (s), one result (r):

            s
            |1
        +---+---+
 a --1--| 0     |
        |       |--1-- r
 b --1--| 1     |
        +-------+

Behavior:

s = 0 → r = a (route input labeled 0)
s = 1 → r = b (route input labeled 1)

Wider data: the 32-bit, 2-input MUX¶

A MUX does not care how wide the data lines are — the select stays 1 bit (for 2 inputs) while the data buses grow:

            s
            |1
        +---+---+
 a -32--| 0     |
        |       |--32-- r
 b -32--| 1     |
        +-------+

The select picks all 32 bits of a or all 32 bits of b. Internally this is just 32 independent 1-bit 2-input MUXes sharing one select line.

More inputs: the 1-bit, 4-input MUX¶

With 4 data inputs you need 2 select bits (s1 s0) to address them:

              s(2)
               |
        +------+------+
 a --1--| 0           |
 b --1--| 1           |--1-- r
 c --1--| 2           |
 d --1--| 3           |
        +-------------+

s1	s0	r
0	0	a
0	1	b
1	0	c
1	1	d

In general, an n-input MUX needs ceil(log2 n) select bits: 2 inputs → 1 select, 4 inputs → 2 select, 8 inputs → 3 select, and so on.

MUX as a C expression¶

// 2-input MUX
uint32_t mux2(uint32_t a, uint32_t b, int s) {
    return s ? b : a;          // s==0 -> a, s==1 -> b
}

// 4-input MUX (2-bit select)
uint32_t mux4(uint32_t a, uint32_t b, uint32_t c, uint32_t d, int s) {
    switch (s & 0x3) {
        case 0: return a;
        case 1: return b;
        case 2: return c;
        default: return d;     // case 3
    }
}

A MUX is the hardware embodiment of ?: / switch — it selects a value, it does not compute one.

7. A Major Use of MUXes: The ALU¶

The Arithmetic Logic Unit (ALU) is where MUXes shine. An ALU performs one of several operations on two operands; a select signal chooses which result to emit. The clean way to build it: run all the operations in parallel, then MUX the desired result out.

   A(64)        B(64)              S(2)
    |  \         |  \                |
    |   \________|___\___ +  --64----| 0 |
    |            |      \            |   |
    |____________|______ -  --64----| 1 |---64--> r
    |            |       \           |   |
    |____________|______ x  --64----| 2 |
                         ...         | : |
                                     +---+
                                    (wide MUX selected by S)

How it works:

Operands A and B (64 bits each, RISC-V register width) fan out to every functional unit.
The adder, subtractor, multiplier, etc. all compute simultaneously (combinational logic — nothing stops them).
The select S drives a wide MUX that passes through exactly one of the results to r.
The unused results are simply ignored — wasteful in transistors, but simple and fast, and standard for a single-cycle design.

flowchart LR
    A["A (64)"] --> ADD["+"]
    A --> SUB["-"]
    A --> MUL["x"]
    B["B (64)"] --> ADD
    B --> SUB
    B --> MUL
    ADD --> MUX["MUX"]
    SUB --> MUX
    MUL --> MUX
    S["S (select)"] --> MUX
    MUX --> R["r (64)"]

This is exactly the ALU you will build for the processor in Project 6. The Project 6 ALU supports add, subtract, multiply, shift-left-logical, and shift-right-logical, selected by a 3-bit ALUop. The ALU is combinational — it has no clock and holds no state.

8. Implementing MUXes from a Truth Table¶

Even though Digital provides a built-in MUX, the lecture derived the 1-bit, 2-input MUX from first principles so we understand what's inside the box.

Full truth table¶

Three inputs (a, b, s) means 8 rows. The output r equals a when s=0 and equals b when s=1:

a	b	s	r
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	1
1	0	1	0
1	1	0	1
1	1	1	1

The four highlighted rows (the ones the instructor boxed in red) are where r = 1.

Sum-of-products¶

One product term per 1-output row, ORed together:

r = (a' . b  . s )      <- row a=0 b=1 s=1
  + (a  . b' . s')      <- row a=1 b=0 s=0
  + (a  . b  . s')      <- row a=1 b=1 s=0
  + (a  . b  . s )      <- row a=1 b=1 s=1

This simplifies (the last three terms cover "s=0 and a=1", the others "s=1 and b=1") to the intuitive r = (a AND NOT s) OR (b AND s), but the direct sum-of-products is a perfectly valid implementation.

Direct implementation¶

The clean two-AND / one-OR realization uses the select s to gate a and b:

                 s
                 |
       +---------+---o (NOT s)
       |              \
 a ----+---------\     \
                  )AND a----\
        +--------/           \
        | (NOT s)             )OR----o--- r
 b ----+---------\           /
                  )AND b----/
        +--------/
       (s drives the second AND directly)

Top AND: a AND (NOT s) — passes a only when s = 0.
Bottom AND: b AND s — passes b only when s = 1.
OR: combines them. Exactly one AND is "live" at a time, so the OR outputs the selected value.

Building a 4-input MUX: two design options¶

The instructor showed two ways to build a 1-bit, 4-input MUX, illustrating a recurring engineering choice.

Option 1 — flat sum-of-products. Use four 3-input AND gates (each ANDs one data input with the correct decode of s1 s0, using NOT gates to form the s combinations) feeding one big OR gate:

 a --AND( a, s1', s0' )--\
 b --AND( b, s1', s0  )-- \
                           )---- OR ----o-- r
 c --AND( c, s1 , s0' )-- /
 d --AND( d, s1 , s0  )--/

Option 2 — tree of 2-input MUXes. Compose three 2-input MUXes:

 a --| MUX |
     |  s0 |--+
 b --|     |  |
              +--| MUX |
 c --| MUX |     |  s1 |--o-- r
     |  s0 |--+--|     |
 d --|     |  |
              (s0 selects within each pair; s1 picks the pair)

	Option 1 (flat SOP)	Option 2 (MUX tree)
Built from	AND/OR/NOT gates	smaller MUX components
Levels of logic	2 (fast)	2 MUX stages
Readability	wider, more wires	clean, hierarchical
Reuse	none	reuses the 2-input MUX

Both compute the same function. Option 2 embodies today's theme — reuse a smaller component — and generalizes nicely (an 8-input MUX is a tree of 2-input MUXes). Option 1 is the literal sum-of-products you'd read straight off the truth table.

Wider 4-input style: the 2-bit, 2-input MUX¶

Widening the data path means splitting each operand into bits, running parallel 1-bit MUXes that share the select, then merging the results back into a bus:

       s
       |
 a(2)--[split]-- a1 --| MUX |-- r1 --[merge]
              \- a0 --| MUX |\         |
                              \        +--(2)-- r
 b(2)--[split]-- b1 ----------/|       |
              \- b0 ----------/ -------/

Each bit position gets its own 2-input MUX; all of them obey the same s. This is precisely how the 32-bit and 64-bit MUXes in the ALU are constructed internally.

9. Subtraction from Addition (Two's Complement)¶

We already have a ripple-carry adder. The lecture showed that we get subtraction for free using two's complement, because:

A - B  =  A + (-B)

and in two's complement, negating a value means invert all the bits, then add 1.

Negation = invert then add 1¶

To compute -B:

Invert every bit of B (a row of NOT gates — drawn in red in the notes).
Add 1.

The "add 1" is conveniently absorbed by the adder's carry-in (Cin): feeding Cin = 1 into the least-significant full adder adds 1 to the sum for free.

8-bit subtraction via a ripple-carry adder¶

The notes drew an 8-bit subtractor as a stack of full adders, one per bit, each with a NOT gate on the b input, and Cin = 1 at the bottom:

 Cin = 1
   |
 a0 -------+
 b0 --[NOT]+--| FA |--> s0
              | Cout|--+
                       |  (carry chains upward)
 a1 -------+           |
 b1 --[NOT]+--| FA |<--+--> s1
              | Cout|--+
                       :
                       :
 a7 -------+           |
 b7 --[NOT]+--| FA |<--+--> s7

Each b bit passes through a NOT gate (the red-circled inverters) → that inverts B.
Cin = 1 on the bottom adder → adds the +1.
Result: s = A + (NOT B) + 1 = A + (-B) = A - B.

The carry ripples from the least-significant bit up to the most-significant bit, exactly like the adder — hence "ripple-carry."

Selectable add/subtract with a MUX¶

To make a unit that does either add or subtract, MUX between B and NOT B (and feed the right carry-in). The notes sketched this: route B through a bank of inverters, then use a MUX to choose B vs inverted B before the adder, with a second adder stage handling the +1.

 A ---------------------------------\
                                     [ + ]---o-- r   (r = A +/- B)
 B --[split]--[NOT each bit]--[MUX]--[ +1 ]-/
                                ^
                          sub? select

In C the equivalence is obvious because the hardware is two's complement:

#include <stdint.h>

int8_t sub8(int8_t a, int8_t b) {
    return a + (~b + 1);   // ~b is invert-all-bits; +1 completes two's complement
    // identical to:  return a - b;
}

This is why one adder design serves both addition and subtraction — a cornerstone of every ALU.

10. Sequential Logic (Preview)¶

Everything so far has been combinational: a DAG, no memory, output a pure function of input. To compute over time — to count instructions, hold a program counter, or build registers — we need state. That is sequential logic.

The two new ingredients¶

A clock — a periodic square wave that ticks (the marked rising edges in the drawing). Each tick is a discrete "step" at which state may update.
State — storage elements (registers / flip-flops) that remember a value between ticks.

 CLOCK  _|‾|_|‾|_|‾|_|‾|_     (the / marks are the rising edges)

The canonical structure¶

A sequential circuit is combinational logic plus a state register, wired in a feedback loop, all synchronized by the clock:

flowchart LR
    CLK["CLOCK"] --> ST["State (register)"]
    IN["inputs"] --> ST
    ST --> CL["Combinational Logic"]
    CL -->|feedback| ST
    CL --> OUT["outputs"]

On each clock tick, the state register latches a new value.
That state feeds the combinational logic, which computes the next state (and outputs).
The result loops back into the state register, to be latched on the next tick.

The feedback loop is the crucial difference: combinational circuits are acyclic (a DAG); sequential circuits deliberately contain a cycle, broken only by the clocked register so the loop settles once per tick instead of oscillating.

Why this matters for the projects¶

The next lab builds a 1-bit register and grows it to a 64-bit register. Project 5's analyzer needs sequential state to count instruction types and to step through the ROM one instruction per clock (driven by CLK, with a CLR input to reset the counters). Project 6's processor is one big sequential machine: the PC register holds state, advancing each cycle through combinational fetch/decode/execute/writeback logic.

Key Concepts¶

Concept	Definition	Example
Combinational logic	Output depends only on current inputs; circuit is a DAG (no feedback)	Adder, comparator, MUX, ALU
Sequential logic	Output depends on inputs and stored state, advanced by a clock	Register, counter, processor PC
Comparator	Component that tests `a == b`, outputs 1 if equal	1-bit comparator = XNOR
Abstraction (component)	Collapsing a circuit into a reusable box with named ports	1-bit cmp box reused in 8-bit cmp
Splitter	Breaks a wide bus into bit ranges (or merges them)	8-bit → two 4-bit nibbles
Multiplexor (MUX)	Selects one of N data inputs based on a select signal	`s ? b : a`
Select bits	The MUX control lines; `ceil(log2 N)` of them for N inputs	4-input MUX needs 2 select bits
ALU	Combinational unit that performs one of several ops, chosen by select	add/sub/mul, MUXed by `ALUop`
Two's complement subtraction	`A - B = A + (NOT B) + 1` (invert then add one)	Adder with inverters + `Cin=1`
Clock	Periodic signal whose edges advance sequential state	Square wave, rising-edge ticks
State register	Storage that holds a value between clock ticks	1-bit register, 64-bit register

Practice Problems¶

Problem 1: Comparator truth table¶

Fill in the eq? column for a 1-bit comparator and identify the equivalent single gate.

a	b	eq?
0	0	?
0	1	?
1	0	?
1	1	?

Click to reveal solution

a b | eq?
0 0 |  1
0 1 |  0
1 0 |  0
1 1 |  1

eq = (a' . b') + (a . b)

The output is 1 exactly when the bits are the **same**. That is the truth table of **XNOR** (NOT-XOR). So a 1-bit comparator is a single **XNOR gate**.

Problem 2: How many select bits?¶

You need a MUX that selects among 16 data inputs. How many select bits does it need? How many select bits for a 2-input MUX? An 8-input MUX?

Click to reveal solution

An N-input MUX needs `ceil(log2 N)` select bits: | Inputs N | Select bits | |----------|-------------| | 2 | 1 | | 8 | 3 | | 16 | **4** | A 16-input MUX needs **4 select bits** (because `2^4 = 16`). The 2-input MUX needs **1**, and the 8-input MUX needs **3**.

Problem 3: Build an 8-bit comparator¶

Describe how to build an 8-bit comparator using 4-bit comparators (and how to build those from 1-bit comparators). Why do we AND the results instead of OR them?

Click to reveal solution

 a(8) -[split]-> a[7:4] -+         a[3:0] -+
                          |--4cmp-->eq_hi   |--4cmp--> eq_lo
 b(8) -[split]-> b[7:4] -+         b[3:0] -+

 eq = eq_hi AND eq_lo

- Split each 8-bit input into a high nibble and a low nibble. - Compare each nibble with a **4-bit comparator** (itself four 1-bit XNOR comparators ANDed together). - **AND** the two nibble results. We **AND** (not OR) because two numbers are equal only if **every** bit position matches. Equality is conjunctive: a single mismatched bit must force the whole result to 0, which only AND does. (OR would report "equal" if *any* nibble matched, which is wrong.)

Problem 4: Derive a 4-to-1 MUX equation¶

Write the sum-of-products equation for a 1-bit, 4-input MUX with data inputs a, b, c, d and select bits s1, s0 (where 00→a, 01→b, 10→c, 11→d).

Click to reveal solution

r = (a . s1' . s0')      ; s = 00 selects a
  + (b . s1' . s0 )      ; s = 01 selects b
  + (c . s1 . s0')       ; s = 10 selects c
  + (d . s1 . s0 )       ; s = 11 selects d

Each product term ANDs one data input with the exact decode of the select bits that chooses it; ORing the four terms yields the selected value. Exactly one product term is active for any given `s1 s0`, so `r` equals the chosen input.

Problem 5: Subtraction from addition¶

Using only an 8-bit ripple-carry adder, NOT gates, and a carry-in, show how to compute A - B. Verify with A = 5, B = 3 (so the answer should be 2) using 4-bit values for brevity.

Click to reveal solution

A - B = A + (-B) = A + (NOT B) + 1

Wire each bit of `B` through a NOT gate into the adder, and set the adder's carry-in to 1. Check with 4-bit values, `A = 5 = 0101`, `B = 3 = 0011`:

NOT B = 1100
A + NOT B + Cin:
   0101   (A = 5)
 + 1100   (NOT B = -4 as bits)
 +    1   (Cin = 1)
 -------
  10010   -> drop the carry-out -> 0010 = 2   ✓

The result is `0010 = 2`, which equals `5 - 3`. The carry-out is discarded; the low 4 bits are the answer.

Problem 6: Combinational vs sequential¶

Classify each as combinational or sequential, and justify: (a) the ALU, (b) an instruction counter for Project 5, (c) an 8-bit comparator, (d) the processor's PC.

Click to reveal solution

| Component | Type | Why | |-----------|------|-----| | (a) ALU | **Combinational** | Output is a pure function of `A`, `B`, and `ALUop`; no clock, no memory (it's a DAG) | | (b) Instruction counter | **Sequential** | Must remember the running count between clock ticks; uses state + clock | | (c) 8-bit comparator | **Combinational** | `eq` depends only on the current `a` and `b`; no feedback | | (d) Processor PC | **Sequential** | Holds the current instruction address and updates it each clock cycle | Rule of thumb: if the circuit needs to **remember** anything across clock ticks, it is sequential; if its output is fully determined by the present inputs, it is combinational.

Summary¶

Combinational logic has no memory — outputs depend only on inputs and the circuit is a DAG. Sequential logic adds a clock and state, enabling computation over time.
A 1-bit comparator tests a == b; its truth table is exactly XNOR, so the whole component is a single XNOR gate.
The central skill is abstraction: collapse a working circuit into a reusable box with named ports, then compose copies of it — just like calling a function in C.
Splitters and buses let us break a wide value into bit-fields and feed parallel sub-components; ANDing per-position equality scales a 1-bit comparator up to 2-bit, 8-bit, and N-bit comparators.
A multiplexor (MUX) selects one of N data inputs using ceil(log2 N) select bits; it is the hardware ?:/switch. It can be built flat from sum-of-products or hierarchically as a tree of smaller MUXes.
The ALU runs all operations in parallel and uses a wide MUX (driven by a select) to pass through the one desired result — a combinational unit with no clock.
Subtraction comes free from addition via two's complement: A - B = A + (NOT B) + 1, implemented with inverters on B and a carry-in of 1 to the ripple-carry adder.
Sequential logic = combinational logic + a clocked state register in a feedback loop; it underpins the registers, counters, and PC needed for the Project 5 analyzer and the Project 6 processor.

Digital Logic Components¶

Overview¶

Learning Objectives¶

Prerequisites¶

1. Where We Are: Combinational Logic Recap¶

Building blocks at a glance¶

Combinational logic¶

Sum-of-products, in one line¶

Near-term goal: static analysis¶

2. The 1-Bit Comparator¶

Truth table¶

Sum-of-products equation¶

This is XNOR¶

Abstract it into a component¶

3. Circuits as Components and Abstraction¶

4. The 2-Bit Comparator: Compose + Split + Combine¶

The pattern¶

Why this works¶

5. Scaling Up: N-Bit Comparators¶

8-bit comparator¶

The recursive structure¶

Comparators in C (the same idea)¶

6. The Multiplexor (MUX)¶

1-bit, 2-input MUX¶

Wider data: the 32-bit, 2-input MUX¶

More inputs: the 1-bit, 4-input MUX¶

MUX as a C expression¶

7. A Major Use of MUXes: The ALU¶

8. Implementing MUXes from a Truth Table¶

Full truth table¶

Sum-of-products¶

Direct implementation¶

Building a 4-input MUX: two design options¶

Wider 4-input style: the 2-bit, 2-input MUX¶

9. Subtraction from Addition (Two's Complement)¶

Negation = invert then add 1¶

8-bit subtraction via a ripple-carry adder¶

Selectable add/subtract with a MUX¶

10. Sequential Logic (Preview)¶

The two new ingredients¶

The canonical structure¶

Why this matters for the projects¶

Key Concepts¶

Practice Problems¶

Problem 1: Comparator truth table¶

Problem 2: How many select bits?¶

Problem 3: Build an 8-bit comparator¶

Problem 4: Derive a 4-to-1 MUX equation¶

Problem 5: Subtraction from addition¶

Problem 6: Combinational vs sequential¶

Further Reading¶

Summary¶