Exam Practice

The physical aspects of a computer system: circuit design, control signals, memory types, buses, clock rate. Answers how each component works and how components are connected.

The logical aspects of the system as seen by the programmer: instruction set, instruction formats, data types, addressing modes, registers. Answers what the machine can do.

Would a programmer need to know it to write a correct program? Yes → architecture. If only speed, cost or physical build changes → organization.

Whether a multiply instruction exists is architecture; whether it uses a dedicated circuit or shift-and-add is organization.

A processor to interpret and execute programs, a memory to store data and programs, and a mechanism (I/O system and buses) for transferring data.

Bus: shared wires carrying data, addresses and control. Port: connector for an external device (USB, HDMI). Cache: small fast memory holding copies of frequently used data.

Memory size (RAM, cache) uses powers of 2 (1 KB = $2^{10}$ B). Clock speed, data rates and advertised disk capacity use powers of 10 (1 GHz = $10^9$ Hz, 1 TB = $10^{12}$ B).

$T = 1/f = 1/(2 \times 10^9)$ s = 0.5 ns.

Maker uses $10^{12}$ bytes; the OS divides by $2^{30}$: $10^{12}/2^{30} \approx 931.3$ GiB. No bytes are missing.

$4 \times 2^{30} = 2^{32} = 4{,}294{,}967{,}296$ bytes.

Its dominant (switching) hardware technology, plus the machines, memory, software and uses it made possible.

Mechanical calculators (1642–1945): Schickard's Calculating Clock, Pascal's Pascaline, Babbage's Difference and Analytical Engines, Hollerith's punched-card tabulator.

1st generation (1946), Mauchly and Eckert: first all-electronic general-purpose computer, about 17,468 vacuum tubes, programmed by moving plugs and wires.

Transistors (Bell Labs 1947, germanium), ~10× faster with 1/10 power and space, magnetic core RAM, FORTRAN/COBOL/ALGOL/SNOBOL, IBM 7094, CDC 6600.

Integrated circuits on silicon, ~1 MIPS, online systems (airline reservations), IBM and the BUNCH, IBM System/360 family, PDP-8/PDP-11, Cray-1, UNIX rewritten in C.

VLSI = more than 10,000 components per chip (4th generation). First microprocessor: 4-bit Intel 4004 (1971, about 2,300 transistors).

ULSI multicore CPUs and SoCs, GPUs and AI accelerators (NPU, TPU), multi-level caches, DDR5 and HBM, NVMe SSDs, PCIe/Thunderbolt, 5G/IoT, cloud computing, AI/ML software.

Quantum processors, neuromorphic chips, in-memory computing, optical computing, beyond-silicon materials and 3-D chips, DNA storage, brain-computer interfaces, 6G. Moves beyond silicon and the von Neumann model.

Original (1965): IC transistor density doubles every year. Contemporary: silicon chip density doubles every 18 months. $N(t) = N_0 \times 2^{t/d}$.

Cost of semiconductor fab equipment doubles every 4 years. For Moore's law to hold, Rock's law must fail, or vice versa.

At the digital logic level, by moving plugs and wires and setting switches; each unique problem type needed a different hardware configuration.

Program instructions are stored in the same memory as data, as binary numbers, so a new program is loaded instead of rewiring. Conceived by Mauchly and Eckert, ascribed to von Neumann.

Three hardware systems (CPU, main memory holding programs and data, I/O); sequential instruction processing; a single data path between CPU and main memory.

The single path between CPU and memory that every instruction and operand must cross one at a time, so the CPU waits on memory. Softened by caches, wider buses, split I/D caches.

MAR ← PC, IR ← M[MAR], PC ← PC + 1. The PC is incremented during fetch, so it already points to the next instruction while the current one executes.

PC: address of next instruction. IR: current instruction. MAR: address sent to memory. MBR: data read from or written to memory. AC: working value/ALU results.

Opcode 3 = Add, address 105: AC ← AC + M[105].

Separate memories and paths for instructions and data, so an instruction fetch and a data access can happen at the same time (microcontrollers, DSPs).

Non-von Neumann model with no program counter: an instruction executes as soon as its input data are available.

Harvard, special-purpose processors (GPU), dataflow, quantum, cellular automata, parallel computing, machine intelligence (neural networks, neuromorphic chips).

Nibble = 4 bits (one hex digit); byte = 8 bits, the smallest addressable unit in most machines; word = machine-dependent group of bytes (commonly 16, 32 or 64 bits).

Repeatedly divide by the target base, recording remainders; read them bottom to top (the first remainder is the least significant digit). $104_{10} = 10212_3$.

Repeatedly multiply the fraction by 2; each integer part is the next bit; read top to bottom. $0.375 → 0.011_2$.

Only when, in lowest terms, its denominator is a power of 2. $0.8125 = 13/16$ terminates; $0.1 = 1/10$ gives $0.0\overline{0011}_2$.

Group 4 (hex) or 3 (octal) bits starting at the radix point, moving outward both ways, padding outer groups with 0s. $.11_2 = .110_2 = .6_8$, not $.3_8$.

$\lfloor \log_b N \rfloor + 1$. $1000_{10}$ needs $\lfloor 9.97 \rfloor + 1 = 10$ bits.

$0$ to $2^n - 1$. 12 bits: 0 to 4095.

Byte-addressable: $\log_2(\text{bytes})$. Word-addressable: $\log_2(\text{words})$. $2^{24}$ bytes with 4-byte words: 24 vs 22 bits.

MSB is the sign (1 = negative), remaining $n-1$ bits hold the magnitude. $-18 = 1001\,0010$. Range $\pm(2^{n-1}-1)$, two zeros.

$(2^n - 1) - N$, i.e. flip every bit. $-19 = 1110\,1100$ (8 bits). Two zeros: $00\cdots0$ and $11\cdots1$.

$2^n - N$ = one's complement + 1. $-19 = 1110\,1101$. Range $-2^{n-1}$ to $2^{n-1}-1$, one zero.

Scan from the right, copy bits through the first 1, flip all bits to its left. $0010\,1100 → 1101\,0100$ ($\pm 44$).

MSB has weight $-2^{n-1}$. $1110\,1101 = -128 + 109 = -19$.

Signed magnitude and one's complement: −127 to +127. Two's complement: −128 to +127. Unsigned: 0 to 255.

Two's/one's complement: copy the sign bit into new high bits. Signed magnitude: move sign to new MSB, fill 0s between sign and magnitude. $-5$: SM $1000\,0101$, two's $1111\,1011$.

Two's complement: single zero, widest range, and subtraction uses the same adder with the carry simply discarded.

Same signs: add magnitudes, keep the sign. Different signs: subtract smaller magnitude from larger and take the sign of the larger. Overflow = carry out of the magnitude.

In one's complement addition, a carry out of the MSB is added back into the LSB, because dropping it would leave $A - B - 1$.

$A - B = A + B' + 1$; add including sign bits and discard any carry out of the MSB.

Overflow iff carry into MSB ≠ carry out of MSB: $V = C_{n-1} \oplus C_n$. Equivalently, two same-sign operands give an opposite-sign result.

No. $1100 + 1111 = 1\,1011$ ($-4 + -1 = -5$) has a carry out but no overflow since carry in = carry out.

$M$ feeds every $B_i$ XOR and the carry-in $C_0$. $M = 0$ adds $B$; $M = 1$ adds $B' + 1$, i.e. subtracts.

If $Q_0 = 1$, $C,A ← A + M$; then shift C, A, Q right one bit and decrement Count. After $n$ cycles the $2n$-bit product is in A,Q.

It catches the carry out of $A + M$; the right shift moves it into $A_{n-1}$ so it is not lost (e.g. $0110 + 1011 = 1\,0001$ in $11 \times 13$).

Sign, exponent (sets the range) and significand/mantissa (sets the precision).

1 sign bit, 5-bit exponent (excess-16), 8-bit fraction with an implicit leading 1.

Every normalized nonzero binary number starts with 1., so that bit is not stored, gaining one bit of precision.

Stored = true + 16, giving true exponents −16 to +15. $e = -2 → 14 = 01110$.

An unsigned exponent cannot be negative; the bias allows negative exponents while keeping the field unsigned, so magnitudes compare and sort like plain binary.

Single: 1 + 8 + 23 bits, bias 127. Double: 1 + 11 + 52 bits, bias 1023.

E = 0, F = 0: ±0. E all 1s, F = 0: ±∞. E all 1s, F ≠ 0: NaN.

$1001.101_2 = 1.001101 \times 2^3$ → $0\ 10011\ 00110100$.

$S = 0$, $E = 127 = 01111111$, $F = 0$ → $\text{3F800000}_{16}$.

Check zeros; align by shifting the smaller-exponent significand right; add/subtract; normalize; round/truncate and check over/underflow.

Shifting it right only loses its least significant bits; shifting the larger left would lose its most significant bits.

Sign = XOR of signs; add exponents (biased: $E_X + E_Y - 16$); multiply significands; normalize (at most one right shift).

Sign = XOR; subtract exponents (biased: $E_X - E_Y + 16$); divide significands; normalize. $18 \div 6$: $0.11 \times 2^2 = 1.1 \times 2^1 = 3$.

Overflow: exponent too large to store. Underflow: nonzero result whose exponent is too small, i.e. too close to zero.

$2^{e-8}$ (8 fraction bits). Near 128 the gap is 0.5, so $128.75$ is stored as $128.5$.

Blatant: obvious (crash, overflow/underflow). Subtle: plausible but wrong, e.g. truncation $128.75 → 128.5$. A crash is better than a plausible wrong answer.

Never with == (especially == 0.0); use a tolerance: abs(x - y) < epsilon.

Each decimal digit is encoded separately in 4 bits (0000–1001). $305_{10}$ = 0011 0000 0101; 1010–1111 are unused.

1111 = unsigned, 1100 = positive, 1101 = negative.

Zoned: one digit per byte, zone 1111 except the last digit whose zone is the sign ($+305$ = F3 F0 C5). Packed: two digits per byte plus a sign nibble at the end, padded with 0000 if needed ($+305$ = 30 5C).

IBM's 8-bit Extended Binary-Coded Decimal Interchange Code (1964): zone nibble picks the row, digit nibble the column. "A" = C1, "7" = F7, space = 40.

7 bits, 128 codes (00–7F). "0" = 30 hex, "A" = 41 hex, "a" = 61 hex; upper and lower case differ by 20 hex.

Count the 1s in the 7-bit code; parity bit (leftmost) = 1 if the count is odd, else 0. "C" = 100 0011 → 1100 0011.

Detects any odd number of bit errors but misses an even number, and cannot say which bit is wrong.

21-bit, U+0000 to U+10FFFF: 17 planes × 65,536 = 1,114,112 code points. Plane 0 is the BMP; U+0000–U+007F equal ASCII.

Divide by $65536$ ($10000_{16}$): the hex digits in front of the last four. U+1F600 → plane 1; U+20AC → plane 0 (BMP).

For transmission, the time one bit lasts ($1/\text{bit rate}$; 2 Kbps → 0.5 ms). For storage, the surface area holding one bit.

A change of magnetic polarity between adjacent areas of the surface; the read head detects the change, not the polarity.

1 = high for the whole cell, 0 = low. Most compact, but long runs of identical bits give a flat line and loss of synchronisation.

A 1 causes a transition, a 0 none; the level itself is meaningless. Fixes runs of 1s, still loses sync on long runs of 0s. Transitions = number of 1s.

Mid-cell transition in every cell: 1 = low→high, 0 = high→low, plus a boundary flip between equal neighbours. Self-clocking; classic Ethernet. Up to 2 transitions per bit.

Clock transition at every cell boundary plus a mid-cell data transition for each 1. Transitions = $n$ + number of 1s ("OK": 16 + 10 = 26).

Mid-cell transition for each 1; boundary transition only between two adjacent 0 cells. "OK": 10 + 2 = 12 transitions.

Data is re-coded (2 code bits per data bit) so there are at least 2 and at most 7 zeros between code 1s, then recorded with NRZI. "OK" needs only 8 transitions.

RLL $\gt$ MFM $\gt$ FM: RLL needs the fewest flux reversals per data bit, so the smallest bit cells. RLL saves 25% vs MFM on "OK".

An extra digit computed from the others (e.g. last digit of UPC barcodes and ISBNs) so a single wrong digit is caught.

3 × (sum of odd positions) + (sum of even positions) = $S$; check digit = $10 - (S \bmod 10)$, or 0. 01234567890 → $S = 85$ → 5.

The group of error-control bits appended to the end of a data block.

Both are bitwise XOR with no carries or borrows: $1101 - 0111 = 1010$.

A key of $n+1$ bits (degree $n$) gives an $n$-bit CRC, so the sender appends $n$ zeros. CRC-16-CCITT (17 bits) → 16-bit CRC.

Append $n$ zeros, mod-2 divide by the key, replace the zeros with the $n$-bit remainder. 1111101 / 1101 → 1111101111.

Divide the received codeword by the key: remainder 0 → accept; otherwise reject and request retransmission.

All single-bit errors, all bursts of length $\le n$, and all odd-count errors when $(x+1)$ is a factor of the key.

Only when the error pattern $E(x)$ is a multiple of the key, e.g. key 1101 shifted: 0001101000.

Number of bit positions in which two code words differ: XOR them and count the 1s. $10001001 \oplus 10110001 = 00111000$ → 3.

Detect: $D(\min) = k + 1$. Correct: $D(\min) = 2k + 1$.

Smallest $r$ with $(m + r + 1) \le 2^r$. $m = 8$ → $r = 4$ ($13 \le 16$), $n = 12$.

Number positions 1..n from the right; check bits at powers of 2 (1, 2, 4, 8 …); data fills the rest from the highest position down.

Those whose binary number contains 4: positions 4, 5, 6, 7, 12.

XOR of the data bits in the positions it covers. Data 1011 (m = 4) → P1 = 1, P2 = 0, P4 = 0 → 1010101.

$K \oplus K'$: 0 = no error; a power of 2 = error in that check bit (data fine); any other value = position of the wrong data bit.

Memory has no sender to retransmit, so the code must correct errors, not just detect them.

Error-correcting codes good at burst errors (runs of adjacent damaged bits); used on CD-ROMs.

$2^n$ rows, listed in binary counting order (3 inputs → 8 rows, 5 inputs → 32).

$2^{2^n}$: each of the $2^n$ output bits is free. $n = 2$ → 16 functions.

$x \oplus y = xy' + x'y$; 1 when inputs differ. Multi-input XOR is 1 for an odd number of 1s (parity).

NAND is 0 only when all inputs are 1; NOR is 1 only when all inputs are 0.

Any Boolean function can be built using only NAND (or only NOR); they are cheap to mass-produce and faster / lower-power than other gate configurations.

Invert each input with a NAND whose inputs are tied: $x'$, $y'$; then NAND($x', y'$) $= (x'y')' = x + y$ (3 gates).

NOR($x,x$) $= x'$, NOR($y,y$) $= y'$, then NOR($x', y'$) $= (x' + y')' = xy$ (3 gates).

Two pMOS in series from +5 V to $Y$, two nMOS in parallel from $Y$ to ground: 4 transistors. pMOS conducts on 0, nMOS on 1.

SSI quad 2-input NAND: 14 pins = power + ground + 4 gates × 3 pins. 10 NAND gates need $\lceil 10/4 \rceil = 3$ chips.

$(xy)' = x' + y'$ and $(x + y)' = x'y'$: complement of a product is the sum of complements, and vice versa.

$x + yz = (x + y)(x + z)$; no ordinary-algebra counterpart, but often the key simplification step.

$x + xy = x$ and $x(x + y) = x$.

Complement each variable, swap AND ↔ OR, keep old products grouped: $(xy + x'z)' = (x' + y')(x + z')$.

$(x + x')(x + y) = 1 \cdot (x + y) = x + y$ (Distributive, Inverse, Identity).

$xy + x'z + yz = xy + x'z$: the term $yz$ is redundant.

Minterm: product of all variables, 1 in exactly one row (used in SOP). Maxterm: sum of all variables, 0 in exactly one row (used in POS).

OR the minterms of the rows where $F = 1$; e.g. $F = xz' + y = \Sigma m(2, 3, 4, 6, 7)$.

NOT first, then AND, then OR (parentheses override). $xy'$ complements only $y$; $(xy)'$ complements the product.

$yz$ = 00, 01, 11, 10 (Gray code), giving cell order m0 m1 m3 m2 / m4 m5 m7 m6.

Adjacent cells (including wrap-around) differ in exactly one variable, so each pair of neighbouring 1s merges: $xy'z + xyz = xz$.

Power-of-2 rectangles of 1s (1, 2, 4, 8, 16); no diagonals; as large as possible; overlap and wrap-around allowed.

2 literals (a group of $2^k$ cells eliminates $k$ variables: $4 - 2 = 2$).

m0, m2, m8, m10 form one group (wrap both ways): $x'z'$.

An input that never occurs (e.g. BCD codes 1010–1111). Marked d; used as 1 only if it enlarges a group; never has to be covered.

Using d5, d7: columns 01 and 11 form a group of 4 with $z = 1$ constant, so $F = z$.

Keep only variables constant over the group: constant 1 → uncomplemented, constant 0 → complemented; changing variables drop out.

Sum $= x \oplus y$, Carry $= xy$: one XOR and one AND.

Sum $= x \oplus y \oplus C_{in}$, $C_{out} = xy + C_{in}(x \oplus y)$; built from two half adders and an OR gate.

Slow for wide words: bit $n-1$ waits for the carry to pass through all $n - 1$ previous full adders.

$n$ inputs → $2^n$ outputs, exactly one active; each output is a minterm. Used for memory address decoding (64 outputs → 6 inputs).

$\log_2(\text{data inputs})$: 8 inputs → 3, 32 inputs → 5. The select value chooses which input reaches the single output.

Feed the variables to an $n$-to-$2^n$ decoder and OR the outputs of the function's minterms.

$f_1f_0$: 00 ADD, 01 OR, 10 NOT $A$, 11 AND; a 2-to-4 decoder enables one result.

Outputs depend only on current inputs (no memory, no feedback): adders, decoders, multiplexers, ALU.

Output depends on current inputs and current state; memory is created by feedback; state changes on clock ticks.

Edge-triggered: changes state at the rising or falling edge. Level-triggered: changes whenever the clock is high.

00 hold, 01 reset to 0, 10 set to 1, 11 undefined (both NOR outputs forced to 0).

00 hold, 01 reset, 10 set, 11 toggle. $Q^+ = JQ' + K'Q$; internally $S = JQ'$, $R = KQ$.

$Q^+ = D$; built from SR with $S = D$, $R = D'$. Fundamental 1-bit memory cell; registers are D flip-flops on a shared clock.

JK with $J = K = T$: $Q^+ = T \oplus Q$ (0 hold, 1 toggle). Basis of binary counters.

When Count Enable = 1 and all lower bits are 1 ($J_i = K_i =$ CE$\cdot B_0 \cdots B_{i-1}$); $B_0$ toggles every pulse.

$J = d$ (don't care), $K = 1$: reset (01) or toggle (11) both give 0.

$1 / (800 \times 10^6) = 1.25$ ns.

The datapath (ALU, registers, buses) does the work; the control unit decides which datapath actions happen and when, based on the instruction, PC and status flags.

$t = 1/f$; in ns, $t = 1000 / f_{\text{MHz}}$. 800 MHz → 1.25 ns; 2.5 GHz → 0.4 ns.

Data lines (the value), address lines (where), control lines (what and when: read/write, clock, arbitration, interrupts).

Only one device may drive the shared wires at a time; hardware protocols (bus arbitration) grant access. It is cheap but can become a bottleneck.

Word: $4\text{M} = 2^{22}$ → 22 lines. Byte: $2^{22} \times 2 = 2^{23}$ → 23 lines. Width (16) affects data lines only.

$(L/l) \times (W/w)$. MARIE 4K × 16 from 1K × 8: 4 rows × 2 = 8 chips.

$\log_2(L/l)$ high-order address bits into a decoder; the remaining $\log_2 l$ bits go to every chip. MARIE: 2 bits (2-to-4 decoder) + 10 bits.

High-order: chip select from leftmost bits, consecutive addresses fill one row. Low-order: from rightmost bits, consecutive addresses spread across rows so they can work in parallel.

A D flip-flop stores its input at the clock edge ($Q(t+1) = D$), exactly "load this word"; an n-bit register needs n of them.

Two's complement, stored program, 16-bit fixed words, 4K words word-addressable memory, 16-bit instruction = 4-bit opcode + 12-bit address, 7 registers.

MAR and PC hold addresses: $4\text{K} = 2^{12}$ words. AC, MBR, IR hold data words/instructions, which are 16 bits.

Memory 0, MAR 1, PC 2, MBR 3, AC 4, InREG 5, OutREG 6, IR 7.

Skipcond 000 (8000): skip if AC < 0; 400 (8400): AC = 0; 800 (8800): AC > 0. Condition is in IR bits 11–10.

Load: AC ← M[X]. LoadI: AC ← M[M[X]], X holds a pointer; one extra memory read.

Stores the return address (current PC) in M[X], then PC ← X + 1. AC is overwritten with X + 1. Return with JumpI X.

Opcode B + address 20F → B20F = 1011 0010 0000 1111.

Lets AC ← AC ± MBR return the ALU result to the AC without using the common bus (signal $L_{ALT}$).

4 bits → 16; MARIE uses 15 (0–E), leaving F free.

MAR ← PC; IR ← M[MAR]; PC ← PC + 1.

MAR ← IR[11–0]; the control unit decodes IR[15–12].

Only when the instruction reads a value from memory: Load, Add, Subt, the indirect instructions. Not for Store, Halt, Jump, Clear, Input, Output, Skipcond.

The address of the next instruction, because the PC was incremented during fetch.

MAR, IR and PC. MBR and AC are untouched.

One row per microoperation, values after the step; only the destination register changes (fetch also increments PC); unchanged values are copied down.

4 fetches + 2 operand reads = 6 reads, plus 1 write (Store).

After execute, check for an interrupt; if pending, save PC/state, run the interrupt service routine, restore, continue. MARIE's basic cycle omits this.

Walk the source with a location counter from ORG; record each label → address in the symbol table; LC + 1 per instruction or DEC/HEX word.

Substitute label addresses into operands, convert DEC/HEX constants to 16-bit hex, emit machine words.

Forward references: a label may be used before the line that defines it.

ORG n: start at hex address n. DEC n / HEX n: one data word in decimal / hex. END: end of source. They are assembler instructions, not CPU instructions.

23 = 0017 → invert FFE8 → +1 → FFE9.

Load X / Subt Y / Skipcond 800 / Jump Else then the THEN part; the Jump is skipped when X − Y > 0.

JnS Sub ... Sub, HEX 0000 (return address), body, JumpI Sub. Parameters go through agreed memory locations (no stack).

The CPU cannot tell data from instructions; running into DEC 35 would execute 0023 as JnS 023.

$P_2P_1P_0$ = number of the register read onto the bus (source); $P_5P_4P_3$ = number of the register written from the bus (destination).

00 nothing, 01 add, 10 subtract, 11 clear. With $L_{ALT}$ the AC loads the ALU result.

$T_3$: $P_3P_2P_1P_0T_3$; $T_4$: $P_4P_3T_4M_R$; $T_5$: $C_rA_0P_5T_5L_{ALT}$.

$P_5\ P_1\ P_0\ T_5\ C_r$: MBR (011) onto the bus, AC (100) loads; no ALU, no $L_{ALT}$.

Counter reset: returns the timing ring counter to $T_0$; placed on the last step of each instruction.

Instruction decoder (AND of opcode bits), ring counter for $T_n$, and OR-of-AND logic: each signal = Σ(instruction · $T_n$).

Each instruction runs a microroutine from a control store; one microinstruction is fetched per clock into a buffer, decoded into control signals. A computer in miniature.

18 bits: MicroOp1 (5) | MicroOp2 (5) | Jump (1) | Dest (7). Routine ends with Jump = 1, Dest = 0000000 (back to fetch).

01010 MAR ← PC; 00110 IR ← M[MAR]; 10001 PC ← PC + 1; 01000 MAR ← IR[11–0]; MicroOp2 NOP, Jump 0.

Hardwired is faster (RISC). Microprogrammed is slower but easy to change and good for complex instructions (CISC).