Back to the Course 3 syllabus · Practice: Module 1 exercises
This page teaches the hardware vocabulary every later module assumes: how numbers are encoded, how logic is built from gates, how state and time enter a circuit, and how the arithmetic hardware your assembly instructions invoke actually works. It condenses H&H chapters 1–3 and 5.1–5.5 to what the course uses; the H&H problem sets remain the source of the by-hand work in Exercise 1.1.
A width-n register holds 2ⁿ patterns; interpretation is a choice the hardware doesn’t make. The three that matter:
| Interpretation | Range (n bits) | Example (8-bit 1111 1111) |
|---|---|---|
| Unsigned | 0 … 2ⁿ−1 | 255 |
| Two’s complement | −2ⁿ⁻¹ … 2ⁿ⁻¹−1 | −1 |
| Just bits (masks, flags) | — | eight set bits |
Two’s complement wins because addition, subtraction, and multiplication (low half) use identical circuits for signed and unsigned — only comparisons and widening differ. Mechanics you should be able to do half-asleep:
−x = ~x + 1)int8_t −1 = 0xFF → 0xFFFFFFFF); unsigned widening zero-extends. This is exactly A64’s SXTB/SXTH/SXTW vs. UXTB/UXTH, and Module 3’s mov w0, #-1 question.0x7FFFFFFF + 1 = 0x80000000 — max positive wraps to min negative. Firmware meets this as timer wraparound (Module 8 §9’s UB discussion is this circle meeting the C standard).Every flag-setting operation (ADDS, SUBS, CMP = SUBS discarding the result) updates four bits, and this course reads them constantly:
| Flag | Meaning after an operation |
|---|---|
| N | Result’s MSB (negative, if interpreted signed) |
| Z | Result is exactly zero |
| C | Unsigned overflow signal: carry out of the MSB on add; no borrow on subtract (note: subtraction sets C when it does not borrow) |
| V | Signed overflow: result’s sign is wrong for the operands’ signs (pos + pos = neg, etc.) |
C answers unsigned questions, V answers signed ones — the same bits, two interpretations, one hardware. Worked examples (32-bit) — the exact cases of Exercise 1.2:
| Operation | Result | N Z C V | Why |
|---|---|---|---|
0x7FFFFFFF + 1 |
0x80000000 |
1 0 0 1 | Signed overflow: max-int + 1; no unsigned carry |
0 − 1 |
0xFFFFFFFF |
1 0 0 0 | Borrow occurred → C=0; −1 is a fine signed result → V=0 |
0x80000000 − 1 |
0x7FFFFFFF |
0 0 1 1 | Signed overflow the other way (min-int − 1); no borrow |
−1 + 1 |
0 |
0 1 1 0 | Zero result; unsigned carry out (0xFFFFFFFF+1 wraps) |
Underneath: CMOS transistor pairs make NAND and NOR cheap and universal — every other gate is built from them (H&H 1.5–1.7), which is why Exercise 1.3 builds XOR from AND/OR/NOT-family ops.
The algebra you’ll actually use:
A·1 = A, A+0 = A, A·A' = 0, A+A' = 1, idempotence, absorption A + A·B = A.(A·B)' = A' + B' and (A+B)' = A'·B'. Push the bubble through, swap the operator. In bit-twiddling: ~(a & b) == ~a | ~b.Karnaugh maps minimize small functions by making algebraic adjacency spatial: cells ordered in Gray code so neighbors differ by one variable; circle power-of-two blocks of 1s; each block is a product term with the changing variables eliminated. A 3-input example (the full adder’s carry-out, §5):
BC=00 01 11 10
A=0 0 0 1 0
A=1 0 1 1 1
→ Cout = AB + AC + BC ("any two of three")That’s the entire K-map skill the course needs — H&H Ch 2’s exercises drill it; don’t-cares (X) join whichever circles help.
Beyond gates, the combinational building blocks vocabulary (H&H 2.8): the multiplexer (select 1 of 2ⁿ inputs — the hardware if/CSEL), the decoder (n inputs → one-hot 2ⁿ outputs — address decoding), and the tri-state buffer (drive or float — shared buses). A mux can implement any truth table with the table as its inputs — remember that when Exercise 1.6 stores an FSM’s logic as a table in memory: same trick, software edition.
Timing, combinationally: every gate has propagation delay; a circuit’s critical path — the slowest input→output route — sets how fast you can clock whatever consumes it. Glitches (transient wrong outputs while signals race) are why outputs are only trusted at the clock edge, which motivates §3.
Combinational logic has no memory. The SR latch (two cross-coupled NOR gates) is the minimal memory element; the D latch makes it transparent-while-enabled; the D flip-flop — two latches back to back — copies D to Q only on the clock edge and holds otherwise. The flip-flop is the state element of synchronous design; a bank of them is a register (§5).
The synchronous discipline (H&H 3.3): all state lives in flip-flops sharing one clock; combinational logic computes next-state between edges.
T_clk ≥ t_pcq + t_pd(logic) + t_setup — clock-to-Q, plus the critical path, plus setup. This inequality is why a chip has a maximum clock frequency, and it returns in Module 2 as the reason pipelining helps: shorter combinational paths per stage → higher clock.An FSM = state register + next-state logic + output logic. Moore outputs depend on state alone; Mealy on state and input (reacts a cycle earlier, one fewer state, twitchier outputs). The rising-edge detector of Exercise 1.6, as a Moore machine:
stateDiagram-v2
direction LR
[*] --> LOW
LOW --> LOW : in=0
LOW --> EDGE : in=1
EDGE --> HIGH : in=1
EDGE --> LOW : in=0
HIGH --> HIGH : in=1
HIGH --> LOW : in=0
note right of EDGE : output=1 here only
Design procedure, always the same: states → transition table → encoding → next-state equations (K-maps) → output equations. In software the table stays a table — Exercise 1.6 walks input characters through it, and Course 2’s protocol/state-machine firmware is this pattern at scale.
Half adder: sum = A⊕B, carry = A·B. Full adder adds carry-in: S = A⊕B⊕Cin, Cout = AB + ACin + BCin (§2’s K-map). Chain n of them, carry rippling upward, and you have the ripple-carry adder — simple, but its critical path is n carry delays.
That linear carry chain is the whole story of adder design: the carry-lookahead adder computes per-bit generate (G = A·B) and propagate (P = A⊕B) signals and resolves carries in logarithmic depth — hardware spends gates to buy time. When Exercise 1.4 makes you ripple carries in a software loop (hundreds of instructions) and the hardware ADD does the equivalent dataflow in a fraction of a nanosecond, carry-lookahead is the reason.
Subtraction is the two’s complement trick in silicon: A − B = A + B' + 1 — invert B, force carry-in to 1. Same adder, one XOR array on the B inputs. This is why C and V come out of subtraction the way §1 describes.
The ALU (H&H 5.2.4): an adder, the logical ops, and a mux selecting which result exits, plus the four flag bits computed from the result and carries. Your entire Module 3 instruction set — ADD, SUB, AND, ORR, EOR, compares — is “which mux setting.”
Shifters: logical left/right (fill 0), arithmetic right (replicate sign — divide-by-2ⁿ for signed), rotate. A barrel shifter does any shift amount in constant time with log₂n mux stages — which is why A64 offers a free shift on the second operand of data-processing instructions (Module 3 §2).
Overflow-aware arithmetic: saturation (clamp at max/min instead of wrapping) needs just the V flag and a select — Exercise 1.5 builds sat_add32 from exactly ADDS + CSEL/CSINV, and the Cortex-M4’s QADD (Module 6 §9) is this circuit as a single instruction, because wrapped audio samples sound like exactly what they are.
| Lesson section | Exercise |
|---|---|
| All (by-hand design work) | 1.1 — H&H problem sets |
| §1 two’s complement + NZCV | 1.2 — predict-verify vs. the real ALU |
| §2 gates, universality | 1.3 — XOR from other gates |
| §4 ripple carry | 1.4 — adder in software |
| §4 saturation, V flag | 1.5 — saturating add |
| §3 FSMs | 1.6 — FSM in assembly |
Reference shelf: H&H 1–3, 5.1–5.5 (the exercise sets live here — still the by-hand problem source); Plantz 2–8 covers the same arc gently (data formats → arithmetic → Boolean algebra → gates → combinational → sequential → memory) if a second telling helps.