Level 5 — MasteryHow Computers Work

How Computers Work

⏱ 75 minutes60 marksprintable — key stays hidden on paper

Time limit: 75 minutes Total marks: 60 Instructions: Answer all three questions. Show full working. Diagrams may be drawn where helpful. Calculators not permitted — express all numbers in the base requested.

Question 1 — From Boolean Algebra to a Working Adder (22 marks)

Modern arithmetic hardware is built entirely from logic gates that are themselves built from transistors. This question traces that stack from algebra to silicon.

(a) Prove, using a truth table, that the two-input XOR function is equivalent to $A \oplus B = (A \lor B) \land \overline{(A \land B)}.$ State how many of the 16 possible two-input Boolean functions your table row-pattern rules out. (4)

(b) A half adder takes bits $A, B$ and outputs sum $S$ and carry $C$ . Give Boolean expressions for $S$ and $C$ , then show algebraically that a full adder (inputs $A,B,C_{in}$ ) satisfies $S = A \oplus B \oplus C_{in}, \qquad C_{out} = (A \land B) \lor (C_{in} \land (A \oplus B)).$ Verify your $C_{out}$ expression is correct for the input $A=1, B=1, C_{in}=0$ and for $A=1,B=0,C_{in}=1$ . (6)

(c) Using two half adders and one OR gate, draw (as a labelled gate list or diagram) how a full adder is constructed. (3)

(d) A NAND gate is functionally complete. Express $\text{NOT}$ , $\text{AND}$ , and $\text{OR}$ using only NAND gates, and count the minimum number of NAND gates each requires. (4)

(e) A single NAND gate in a basic CMOS design uses 4 transistors. Using only your answers from (d), how many transistors would a 2-input AND gate require if built purely from NAND gates? Comment on why a dedicated AND cell (6 transistors) is preferred in practice. (5)

Question 2 — Number Systems, Registers and Storage (18 marks)

(a) Convert the decimal number $237$ into: (i) binary, (ii) hexadecimal, (iii) octal. Show the division-remainder or grouping method for each. (6)

(b) An 8-bit register stores the pattern from part (a)(i). Explain what physical component stores each single bit, and state which flip-flop type is normally used to build a register and why (contrast with the SR flip-flop). (4)

(c) Interpret the 8-bit pattern for $237$ as a two's complement signed integer. State its signed value and prove it by the standard two's-complement rule. (4)

(d) A cache line is 64 bytes. Express 64 bytes in bits, and explain in terms of the memory hierarchy why registers (measured in a handful of bytes) can be ~100× faster to access than L1 cache despite storing far less data. (4)

Question 3 — The CPU as an Interpreter of Bits (20 marks)

A tiny CPU has 4 general registers (R0–R3), an 8-bit word, and this instruction format: the top 2 bits are an opcode, the next 2 bits select a destination register, and the low 4 bits are an immediate or source encoding.

Opcodes: 00=LOAD (dest ← immediate), 01=ADD (dest ← dest + source-reg), 10=STORE (mem[immediate] ← dest), 11=HALT.

(a) Decode the following machine-code bytes step by step (opcode, dest, operand). For ADD, the low 4 bits 00SS encode source register SS.

00 01 0101      // byte 1
00 10 0011      // byte 2
01 01 0010      // byte 3

State the final value in R1 after execution. (6)

(b) For byte 3, describe the fetch–decode–execute cycle for that one instruction, naming which CPU component (control unit, ALU, register file, program counter) acts at each stage. (6)

(c) The ADD in byte 3 must physically add two 4-bit values. Explain how the full adder from Question 1 is chained into a 4-bit ripple-carry adder, and state the worst-case number of gate-delays for the carry to propagate if each full adder contributes 2 gate-delays of carry latency. (4)

(d) The operating system, not the program, decides when this CPU runs your instructions and where mem[immediate] physically lives. Explain the OS's dual role as resource manager and abstraction layer, giving one concrete example of each drawn from this scenario. (4)

Answer keyMark scheme & solutions

Question 1

(a) (4 marks)

$A$	$B$	$A\lor B$	$A\land B$	$\overline{A\land B}$	$(A\lor B)\land\overline{(A\land B)}$	$A\oplus B$
0	0	0	0	1	0	0
0	1	1	0	1	1	1
1	0	1	0	1	1	1
1	1	1	1	0	0	0

Last two columns match ⇒ identity proven. (3 marks for correct full table + agreement.) A specific output column 0110 is one of the 16 functions; fixing it rules out the other 15 functions. (1 mark.)

(b) (6 marks)

Half adder: $S = A\oplus B$ , $C = A\land B$ . (1)
Full adder sum: adding three bits, $S = A\oplus B\oplus C_{in}$ (parity of the three inputs). (1)
Carry-out reasoning: carry is 1 when at least two inputs are 1. This equals " $A$ and $B$ both 1" OR "exactly one of $A,B$ is 1 (i.e. $A\oplus B$ ) AND $C_{in}=1$ ": $C_{out} = (A\land B)\lor(C_{in}\land(A\oplus B))$ . (2)
Check $A=1,B=1,C_{in}=0$ : $(1\land1)\lor(0\land 0)=1\lor0=1$ . Correct (1+1+0 = binary 10, carry 1). (1)
Check $A=1,B=0,C_{in}=1$ : $(1\land0)\lor(1\land1)=0\lor1=1$ . Correct (1+0+1 = 10, carry 1). (1)

(c) (3 marks)

HA1: inputs $A,B$ → $S_1=A\oplus B$ , $C_1=A\land B$ . (1)
HA2: inputs $S_1, C_{in}$ → $S=S_1\oplus C_{in}$ , $C_2=S_1\land C_{in}$ . (1)
OR gate: $C_{out}=C_1\lor C_2$ . Final outputs $S$ , $C_{out}$ . (1)

(d) (4 marks)

NOT: $\overline{A}=A\ \text{NAND}\ A$ — 1 gate. (1)
AND: $A\land B=\overline{A\ \text{NAND}\ B}=(A\ \text{NAND}\ B)\ \text{NAND}\ (A\ \text{NAND}\ B)$ — 2 gates. (1)
OR: $A\lor B = \overline{A}\ \text{NAND}\ \overline{B}$ = (A NAND A) NAND (B NAND B) — 3 gates. (2)

(e) (5 marks)

AND from NAND uses 2 NAND gates (part d). (1)
Transistors $=2\times4=\mathbf{8}$ transistors. (2)
A dedicated CMOS AND cell needs 6 transistors (a NAND = 4, then an inverter = 2). (1)
Comment: the NAND-only route wastes 2 transistors, more area/power and an extra gate delay; complete-set proofs are elegant but real chips use optimised cells. (1)

Question 2

(a) (6 marks) (i) Binary: $237 = 128+64+32+8+4+1 = 11101101_2$ . (2) Division: 237/2 r1,118 r0,59 r1,29 r1,14 r0,7 r1,3 r1,1 r1 → read up: 11101101. (ii) Hex: group 1110 1101 = E D = $\mathbf{0xED}$ . (2) (iii) Octal: group in 3s from right 011 101 101 = 3 5 5 = $\mathbf{0o355}$ . (2)

(b) (4 marks)

Each bit is stored by one flip-flop (a bistable latch of cross-coupled gates). (1)
Registers use the D flip-flop. (1)
Reason: a D flip-flop has a single data input; on the clock edge output $Q$ simply becomes $D$ — clean, no forbidden state. (1)
Contrast: the SR flip-flop has the illegal input $S=R=1$ and needs two control lines, making it unsuitable for direct data storage. (1)

(c) (4 marks)

Pattern 11101101, MSB = 1 ⇒ negative. (1)
Two's-complement value: invert → 00010010, add 1 → 00010011 = 19. (2)
So the signed value is $-19$ . Check: $237-256=-19$ . ✓ (1)

(d) (4 marks)

$64\text{ bytes} = 64\times8 = \mathbf{512\text{ bits}}$ . (1)
Registers sit inside the CPU datapath, physically adjacent to the ALU, addressed directly (no lookup), so access is essentially one clock; L1 must be indexed/tag-matched and is slightly further away. (2)
Trade-off: speed costs area/power, so we keep only a tiny number of registers and a larger-but-slower cache — the hierarchy principle. (1)

Question 3

(a) (6 marks)

Byte 1 00 01 0101: LOAD R1 ← immediate 0101=5 ⇒ R1=5. (2)
Byte 2 00 10 0011: LOAD R2 ← immediate 0011=3 ⇒ R2=3. (2)
Byte 3 01 01 0010: ADD R1 ← R1 + source reg 10=R2 ⇒ R1 = 5+3. (1)
Final R1 = 8. (1)

(b) (6 marks)

Fetch: program counter (PC) holds the address; control unit places it on the bus, the byte 01010010 is read into the instruction register; PC increments. (2)
Decode: control unit reads opcode 01=ADD, dest 01=R1, source 10=R2; sets up datapath control lines. (2)
Execute: register file reads R1(5) and R2(3), ALU adds them (8), result written back to R1. (2)

(c) (4 marks)

Chain 4 full adders: bit-0 FA takes $C_{in}=0$ ; each FA's $C_{out}$ feeds the next FA's $C_{in}$ (ripple). (2)
Worst case carry ripples through all 4 stages: $4\times2 = \mathbf{8}$ gate-delays. (2)

(d) (4 marks)

Resource manager: the OS scheduler decides when the CPU executes these instructions, time-slicing it among processes (e.g. it may preempt this program between byte 2 and byte 3 to run another). (2)
Abstraction layer: mem[immediate] is a virtual address; the OS (with the MMU) maps it to real RAM/cache, hiding physical location so the program need not know where data truly lives. (2)

[
  {"claim":"237 = 11101101 binary, 0xED, 0o355","code":"result = (bin(237)=='0b11101101') and (hex(237)=='0xed') and (oct(237)=='0o355')"},
  {"claim":"8-bit 11101101 as two's complement is -19","code":"v=0b11101101; sv=v-256 if v>=128 else v; result = (sv==-19)"},
  {"claim":"Full adder Cout matches (A&B)|(Cin&(A^B)) for all inputs","code":"ok=all(((A&B)|(C&(A^B)))==((A+B+C)>>1) for A in(0,1) for B in(0,1) for C in(0,1)); result=ok"},
  {"claim":"Final R1 = 5 + 3 = 8, and 64 bytes = 512 bits","code":"result = (5+3==8) and (64*8==512)"}
]