Skip to content

Quick Reference

Tables and formulas of the six units, for revision

These pages gather the tables and formulas of the six units. Each block agrees with the chapter that develops it; look there for the reasoning.

Q.1 Unit 1: Digital Logic Circuits

Gates and truth tables

Gate Expression Output is 1 when
AND \(A\cdot B\) all inputs are 1
OR \(A + B\) any input is 1
NOT \(A'\) the input is 0
NAND \((AB)'\) not all inputs are 1
NOR \((A+B)'\) all inputs are 0
XOR \(A \oplus B = A'B + AB'\) the inputs differ (odd number of 1s)
XNOR \((A\oplus B)'\) the inputs are equal

An \(n\)-input truth table has \(2^n\) rows. NAND and NOR are universal: NOT \(= A\) NAND \(A\), AND needs 2 NANDs, OR needs 3. XOR is not universal. A positive-logic AND is a negative-logic OR. Any two-level SOP maps to all-NAND, any two-level POS to all-NOR.

Boolean algebra

Law OR form AND form
Identity / null \(x + 0 = x\), \(x + 1 = 1\) \(x\cdot 1 = x\), \(x\cdot 0 = 0\)
Idempotent / complement \(x + x = x\), \(x + x' = 1\) \(xx = x\), \(xx' = 0\)
Distributive \(x(y+z) = xy + xz\) \(x + yz = (x+y)(x+z)\)
Absorption \(x + xy = x\), \(x + x'y = x + y\) \(x(x+y) = x\), \(x(x'+y) = xy\)
Combining \(xy + xy' = x\) \((x+y)(x+y') = x\)
Consensus \(xy + x'z + yz = xy + x'z\) \((x+y)(x'+z)(y+z) = (x+y)(x'+z)\)

DeMorgan: \((x+y)' = x'y'\), \((xy)' = x' + y'\) ("break the bar, change the sign"). Precedence: parentheses, NOT, AND, OR. Dual: swap \(\cdot \leftrightarrow +\) and \(0 \leftrightarrow 1\) (variables unchanged); complement: DeMorgan, so variables are inverted too.

Canonical forms

  • Minterm \(m_i\): unprimed if the bit is 1, primed if 0. Maxterm \(M_i\): the opposite. \(M_i = m_i'\).
  • SOP: \(F = \sum m(\text{rows where } F=1)\). POS: \(F = \prod M(\text{rows where } F=0)\). The two index lists are complements within \(0 \dots 2^n - 1\).
  • Expand a missing variable by multiplying by \((x + x') = 1\); write a repeated minterm once.
  • Design procedure: state the problem, assign variables, truth table, simplify, draw the diagram. The truth table is the design.

Karnaugh maps

  • Rows and columns in Gray order 00, 01, 11, 10; edges wrap round (the four corners of a 4-variable map form a group). Diagonals are not adjacent.
  • Groups: only 1s, rectangles of 1, 2, 4, 8, 16 cells, as large as possible, as few as possible, may overlap and wrap.
  • Reading a group: keep the constant variables (1 as unprimed, 0 as primed); a group of \(2^k\) cells removes \(k\) variables.
  • Prime implicant: cannot be enlarged. Essential: only cover of some 1. Find the essentials first; a minimal cover need not be unique.
  • POS: group the 0s to get \(F'\), then complement (or write each group as a sum, 0 unprimed and 1 primed).
  • Don't-cares: use an X only if it enlarges a group; never a group of Xs alone; never assume all Xs are 1. BCD codes 1010 to 1111 are don't-cares.
  • Beyond four variables: paired maps for 5 or 6 variables, Quine-McCluskey (group by number of 1s, combine pairs differing in one bit, prime-implicant chart) beyond.
  • Static-1 hazard: two adjacent 1s in different groups. Cure: add the consensus term (logically redundant, electrically essential).

Combinational versus sequential

Combinational Sequential
Output function of present inputs function of inputs and state
Memory, clock none flip-flops, usually clocked
Examples adder, MUX register, counter

Latch: level-triggered (transparent while enabled). Flip-flop: edge-triggered. Master-slave: two latches on opposite clock phases.

Flip-flops

Flip-flop Characteristic equation Excitation, \(Q \to Q(t+1)\) = 00, 01, 10, 11
SR \(Q(t+1) = S + R'Q\), \(SR = 0\) \(SR\) = 0X, 10, 01, X0
D \(Q(t+1) = D\) \(D\) = 0, 1, 0, 1
JK \(Q(t+1) = JQ' + K'Q\) \(JK\) = 0X, 1X, X1, X0
T \(Q(t+1) = T \oplus Q\) \(T\) = 0, 1, 1, 0

SR: 00 holds, 01 resets, 10 sets, 11 forbidden. JK: 00 holds, 01 resets, 10 sets, 11 toggles. Characteristic: inputs to next state (analysis). Excitation: required transition to inputs (design).

Conversions: JK to D: \(J = D\), \(K = D'\). D to T: \(D = T \oplus Q\). JK to T: \(J = K = T\). SR to D: \(S = D\), \(R = D'\). Recipe: wanted next-state table, then the available flip-flop's excitation table, then K-maps.

Timing and counters

  • \(f = 1/T\); duty cycle \(= t_{HIGH}/T\). Setup \(t_{su}\) before the edge and hold \(t_h\) after it; clock period \(T \ge t_{cq} + t_{logic} + t_{su}\). Violations cause metastability.
  • A toggling flip-flop divides the clock by 2; \(n\) stages give \(f_{in}/2^n\). A mod-\(N\) counter needs the smallest \(n\) with \(2^n \ge N\) (decade: 4, mod-60: 6).
  • Ripple counter: delay grows with the number of stages. Synchronous counter: one common clock, \(T_i = Q_{i-1}\cdots Q_0\) for an up-counter built from T flip-flops.
  • Race-around (\(J=K=1\), level-triggered) is cured by master-slave or edge triggering.

Q.2 Unit 2: Digital Components

Adders and subtractors

Circuit Equations
Half adder \(S = A \oplus B\), \(C = AB\)
Full adder \(S = A \oplus B \oplus C_{in}\), \(C_{out} = AB + C_{in}(A \oplus B) = AB + AC_{in} + BC_{in}\) (two half adders + OR, 5 gates)
Full subtractor \(D = A \oplus B \oplus B_{in}\), \(B_{out} = A'B + A'B_{in} + BB_{in}\)
  • Sum is parity (odd number of 1s); carry is majority (at least two 1s).
  • Ripple-carry adder: \(n\) full adders, carry of stage \(i\) is the carry-in of stage \(i+1\); worst-case delay about \(2n\) gate delays, so it grows with \(n\).
  • Carry look-ahead: \(G_i = A_iB_i\), \(P_i = A_i \oplus B_i\), \(C_{i+1} = G_i + P_iC_i\), \(S_i = P_i \oplus C_i\); carries are formed in parallel at the price of high fan-in, so real adders use blocks.
  • Adder-subtractor: XOR on each \(B_i\) and \(M\) into \(C_0\). \(M = 0\): \(A + B\). \(M = 1\): \(A + B' + 1 = A - B\).
  • Overflow: unsigned \(\Rightarrow\) carry-out \(C_n = 1\). Signed \(\Rightarrow\) \(V = C_n \oplus C_{n-1}\); possible only when both operands have the same sign. Range of \(n\) bits signed: \(-2^{n-1}\ldots 2^{n-1}-1\). A signed carry-out alone means nothing.
  • Arithmetic microoperations: R3 ← R1 + R2 (add), R3 ← R1 + R2' + 1 (subtract), R2 ← R2' (1's complement), R2 ← R2' + 1 (2's complement), R1 ← R1 + 1 (increment), R1 ← R1 - 1 (decrement), add with carry R3 ← R1 + R2 + C.

Code converters and detectors

Converter Result
BCD to Excess-3 (don't-cares 10-15) \(w = A + B(C+D)\), \(x = B'C + B'D + BC'D' = B \oplus (C+D)\), \(y = (C \oplus D)'\), \(z = D'\)
Binary to Gray \(G_{n-1} = B_{n-1}\), \(G_i = B_{i+1} \oplus B_i\); one XOR level
Gray to binary \(B_{n-1} = G_{n-1}\), \(B_i = B_{i+1} \oplus G_i\); chain of \(n-1\) XORs
  • 2-bit comparator: \(x_i = A_i \odot B_i\); \(E = x_1x_0\), \(G = A_1B_1' + x_1A_0B_0'\), \(L = A_1'B_1 + x_1A_0'B_0\), \(E = (G+L)'\).
  • 3-bit prime detector: \(F = \sum m(2,3,5,7) = A'B + AC\). BCD prime detector with don't-cares: \(F = B'C + BD\).

Decoders, encoders, multiplexers, demultiplexers

Block In \(\to\) out Rule
Decoder \(n \to 2^n\) \(D_i = m_i\) (with enable: \(E\cdot m_i\)); decoder + OR gates = any function
Encoder \(2^n \to n\) octal: \(A_2 = D_4{+}D_5{+}D_6{+}D_7\), \(A_1 = D_2{+}D_3{+}D_6{+}D_7\), \(A_0 = D_1{+}D_3{+}D_5{+}D_7\)
Priority encoder \(2^n \to n + V\) 4-to-2: \(x = D_2{+}D_3\), \(y = D_3{+}D_1D_2'\), \(V = \sum D_i\); \(V\) separates code 0 from no input
MUX \(2^n + n \to 1\) \(Y = \sum m_i I_i\); \(2^n\):1 gives any \(n\)-variable function, \(2^{n-1}\):1 with residue (\(0\), \(1\), \(x\), \(x'\))
DEMUX \(1 + n \to 2^n\) \(Y_i = D\cdot m_i\) = decoder with enable (data on \(E\))
  • Decoder expansion: \(n\)-to-\(2^n\) from \(k\)-to-\(2^k\) modules needs \(2^{n-k}\) modules (plus an enable decoder); low-order bits to every module, high-order bits to the enables.
  • NAND (active-low) decoder: selected line = 0; use NAND gates for the OR. A function with more than \(2^{n-1}\) minterms is cheaper from its complement (NOR).
  • Column rule for MUX input reduction: \((0,0) \to 0\), \((1,1) \to 1\), \((0,1) \to x\), \((1,0) \to x'\).
  • MUX tree: \(M\):1 from \(k\):1 modules needs \((M-1)/(k-1)\) modules (16:1 from 4:1 = 5). DEMUX tree puts the high-order selects at the first level.
  • A decoder + OR, an 8:1 MUX and an \(8\times 1\) ROM all realise the same truth table.
  • Simple encoder wrong if two inputs are 1 (\(D_3 + D_6 \to 111\)); use a priority encoder for interrupts.

Registers, shift registers and memory

  • Register = \(n\) flip-flops, one clock. Parallel load: \(D_i = \text{Load}\cdot I_i + \text{Load}'\cdot Q_i\); Load = 0 holds by feedback. Never gate the clock (clock skew).
  • Shift registers: SISO (delay), SIPO (serial to parallel), PISO (parallel to serial), PIPO (storage). Left shift multiplies by 2, right shift divides by 2.
  • Universal shift register (\(s_1s_0\)): 00 hold, 01 shift right, 10 shift left, 11 parallel load.
Memory facts
\(m\) words \(\times\) \(n\) bits \(k = \log_2 m\) address lines, \(n\) data lines, capacity \(m\cdot n\) bits
\(1\text{K} = 1024\) \(8\to 256\), \(10 \to 1\text{K}\), \(12 \to 4\text{K}\), \(16 \to 64\text{K}\), \(20 \to 1\text{M}\) address lines to words
Chip count \((M/m)\times(N/n)\); depth selected by a decoder on the high-order address lines, width by chips in parallel
ROM \(2^k \times n\) \(k\)-to-\(2^k\) decoder + \(n\) OR gates = stored truth table (combinational)
SRAM DRAM
Cell latch, 4-6 transistors 1 transistor + 1 capacitor
Refresh no yes
Speed / density fast / low slower / high
Use cache main memory
  • ROM types: mask (factory, fixed), PROM (user once), EPROM (UV erase, whole chip), EEPROM (electrical, byte), flash (electrical, block). ROM is non-volatile; RAM is volatile.

Q.3 Unit 3: Data Representation and Arithmetic

Number systems and conversion

System Base Digits Bits per digit
Binary 2 0, 1 1
Octal 8 0 to 7 3
Decimal 10 0 to 9 -
Hexadecimal 16 0 to 9, A to F 4
  • Positional value: \(N = \sum a_i r^i\); positions count from 0 at the radix point and go negative to the right.
  • Base \(r\) to decimal: multiply each digit by its weight and add.
  • Decimal to base \(r\): integer part by repeated division (remainders read bottom-up); fraction part by repeated multiplication (integer parts read top-down).
  • Binary to octal or hex: group in 3s or 4s outwards from the point; pad the integer part on the left, the fraction on the right. Octal to hex goes through binary.
  • \(0.1_{10}\) is \(0.000110011\ldots_2\) (never terminates), hence rounding in floating point.
  • Handy values: \(2^8 = 256\), \(2^{10} = 1024\), \(2^{16} = 65536\), \(255 = \text{FF} = 377_8\), \(1000 = \text{3E8}\).

Complements and subtraction

\((r-1)\)'s complement \(= (r^n-1)-N\) \(r\)'s complement \(= r^n - N\)
Binary 1's: invert every bit 2's: invert, then add 1
Decimal 9's: subtract each digit from 9 10's: 9's complement plus 1
  • 2's complement shortcut: from the right copy bits up to and including the first 1, invert the rest.
  • \(M - N\) with the \(r\)'s complement: add the complement of \(N\) to \(M\). End carry: discard it, result positive. No end carry: result negative; take the \(r\)'s complement of the sum.
  • With the \((r-1)\)'s complement: an end carry is added back to the LSB (end-around carry); no end carry means negative.
  • Work to a fixed width \(n\); the \(r\)'s complement of 0 is 0; taking the complement twice returns the number.

Signed numbers

Scheme Range (\(n\) bits) Zeros Negative of \(x\)
Signed-magnitude \(\pm(2^{n-1}-1)\) two flip the sign bit
Signed 1's complement \(\pm(2^{n-1}-1)\) two invert all bits
Signed 2's complement \(-2^{n-1}\) to \(2^{n-1}-1\) one invert all bits, add 1
  • 8-bit 2's complement: \(-128\) to \(+127\); 16-bit: \(-32768\) to \(+32767\). The MSB has weight \(-2^{n-1}\). Sign-extend by replicating the sign bit.
  • Add: add with the sign bits, discard the carry out. Subtract \(A - B\): add \(A\) to the 2's complement of \(B\).
  • Overflow: \(V = C_{in} \oplus C_{out}\) of the sign bit. Only like-signed operands can overflow (positive + positive = negative, or negative + negative = positive). Opposite signs never overflow. A carry out alone is not overflow (for unsigned numbers it is).
  • Subtraction \(A - B\) overflows when \(A\) and \(B\) have opposite signs and the result sign differs from the sign of \(A\).
  • Shifts: left \(\times 2\); arithmetic right \(\div 2\) (sign kept). Multiply = shift-and-add; divide = shift-and-subtract; result sign = XOR of operand signs.

Floating point

  • Value \(= \pm\, m \times 2^e\); normalised mantissa (leading digit non-zero), biased exponent \(E = e + \text{bias}\), hidden leading 1.
  • IEEE-754 single: 1 + 8 + 23 bits, bias 127, \(V = (-1)^S \times 1.F \times 2^{E-127}\) (about 7 decimal digits). Double: 1 + 11 + 52, bias 1023 (about 16 digits).
  • \(E = 0\): zero or denormal; \(E = 255\): infinity or NaN; \(E = 1\) to \(254\): normal.
  • Encode in four steps: binary; normalise to \(1.x \times 2^e\); \(E = e + 127\), fraction padded to 23 bits; assemble. Example: \(13.625 = 1.101101 \times 2^3 \to\) 0x415A0000; \(-6.5 \to\) 0xC0D00000.
  • More exponent bits: wider range, coarser precision. Never test floating-point values for exact equality.

Binary codes

Code Type Property
BCD (8421) weighted one digit per 4 bits; 1010 to 1111 illegal
Excess-3 non-weighted BCD + 0011; self-complementing
2421 weighted self-complementing
Gray non-weighted one bit changes per step; cyclic
ASCII character 7 bits; '0' = 30H, 'A' = 41H, 'a' = 61H
  • Binary to Gray: \(G = B \oplus (B \gg 1)\), i.e. \(g_i = b_{i+1} \oplus b_i\) with the MSB copied. Gray to binary: \(b_i = b_{i+1} \oplus g_i\) (running XOR from the MSB).
  • A parity bit makes the number of 1s even (or odd); it detects single-bit errors only.
  • BCD addition: add digits in binary; if a digit sum exceeds 1001 or produces a carry, add 0110 (6, the six unused codes) and carry into the next digit. Example: \(7 + 5 = 1100 + 0110 = 1\,0010\), digit 2 and carry 1.

Q.4 Unit 4: Basic Computer Organization and Design

Basic computer: parameters and registers

Memory 4096 × 16 (12 address lines, 16 data lines, 65 536 bits = 8 KB). Instruction word = I (bit 15) + opcode (bits 14-12) + address (bits 11-0) = 1 + 3 + 12 = 16. Instructions: 7 memory-reference + 12 register-reference + 6 input-output = 25. Stored program: instructions and data share one memory; a word is an instruction only because it is fetched as one.

Register Bits Function
AR 12 memory address (the only register wired to the memory address lines)
PC 12 address of the next instruction
DR 16 operand read from or written to memory
AC 16 accumulator
IR 16 instruction being executed
TR 16 temporary (control unit scratch)
INPR 8 input character
OUTR 8 output character

Flip-flops: I (indirect), S (run/halt), E (carry / extended AC), R (interrupt), IEN (interrupt enable), FGI, FGO (device flags). Field sizing: address = \(\lceil\log_2 \text{words}\rceil\), mode = \(\lceil\log_2 \text{modes}\rceil\), register = \(\lceil\log_2 \text{registers}\rceil\), opcode = remainder; always add back to the word length.

Common bus and control signals

S2S1S0 000 001 010 011 100 101 110 111
Source none AR PC DR AC IR TR memory M[AR]
  • Template for X ← Y: S2S1S0 = code of Y (the source), LD(X) = 1, Read if Y is memory, Write if X is memory.
  • Each register has LD, INR, CLR; INR and CLR act locally and need no bus.
  • Rules: one bus source per pulse; memory only through AR; AC loaded only through the adder-and-logic circuit (inputs AC, DR).
  • IR ← M[AR], PC ← PC + 1 shares one pulse because PC increments locally.

Instruction formats and decoding

Class Opcode I Hex Count
Memory-reference 000-110 0 / 1 0xxx-6xxx / 8xxx-Exxx 7
Register-reference 111 0 7xxx (one-hot, 12 bits) 12
Input-output 111 1 Fxxx (one-hot, 6 bits) 6

Memory-reference opcodes: AND 0, ADD 1, LDA 2, STA 3, BUN 4, BSA 5, ISZ 6; I = 1 adds 8 to the leading hex digit. Leading hex digit: 0-6 direct, 8-E indirect, 7 register-reference, F input-output. Direct: EA = address field. Indirect: EA = M[address field], once only (one extra memory read).

Timing and the instruction cycle

SC (4 bits) → 4-to-16 decoder → T0-T15; IR(12-14) → 3-to-8 decoder → \(D_0\)-\(D_7\); control logic gates AND them (D3T4). SC ← 0 ends every instruction.

T0: AR ← PC
T1: IR ← M[AR], PC ← PC + 1
T2: D0..D7 ← decode IR(12-14), AR ← IR(0-11), I ← IR(15)
D7'IT3:  AR ← M[AR]          (memory-reference, indirect)
D7'I'T3: nothing             (memory-reference, direct)
D7I'T3:  register-reference, execute, SC ← 0
D7IT3:   input-output, execute, SC ← 0

PC is incremented at T1, not after execution. Memory-reference instructions execute from T4. Indirect uses the T3 slot for one extra memory read; the clock-pulse count is the same as for direct.

Memory-reference microoperations

Instruction Microoperations Pulses
AND D0T4: DR ← M[AR]; D0T5: AC ← AC ∧ DR, SC ← 0 6
ADD D1T4: DR ← M[AR]; D1T5: AC ← AC + DR, E ← Cout, SC ← 0 6
LDA D2T4: DR ← M[AR]; D2T5: AC ← DR, SC ← 0 6
STA D3T4: M[AR] ← AC, SC ← 0 5
BUN D4T4: PC ← AR, SC ← 0 5
BSA D5T4: M[AR] ← PC, AR ← AR + 1; D5T5: PC ← AR, SC ← 0 6
ISZ D6T4: DR ← M[AR]; D6T5: DR ← DR + 1; D6T6: M[AR] ← DR, if (DR = 0) PC ← PC + 1, SC ← 0 7

Only AND, ADD, LDA, ISZ read the operand into DR. BSA returns with an indirect BUN through the first word (BSA 470 at 30 saves 31 at 470 and jumps to 471; return C470). ISZ with a counter of \(-N\) runs a loop body \(N\) times.

Trace checklist

Build the instruction word; fetch (AR, IR, PC one past the instruction); decode (AR = address field, I, D); if I = 1 do AR ← M[AR] once; execute; SC ← 0. Final AR = effective address (for memory-reference), PC = instruction address + 1 unless branched. Common slips: PC left at the instruction's own address, AR left at the instruction's own address, S2S1S0 set for the destination instead of the source.

Register-reference instructions (7xxx)

Executed when \(r = D_7I'T_3\); each instruction is selected by one bit \(B_i\) of the address field, and every one ends with \(SC \leftarrow 0\).

Sym Hex Bit Microoperation
CLA 7800 \(B_{11}\) AC ← 0
CLE 7400 \(B_{10}\) E ← 0
CMA 7200 \(B_9\) AC ← AC'
CME 7100 \(B_8\) E ← E'
CIR 7080 \(B_7\) AC ← shr AC, AC(15) ← E, E ← AC(0)
CIL 7040 \(B_6\) AC ← shl AC, AC(0) ← E, E ← AC(15)
INC 7020 \(B_5\) AC ← AC + 1
SPA 7010 \(B_4\) skip if AC(15) = 0
SNA 7008 \(B_3\) skip if AC(15) = 1
SZA 7004 \(B_2\) skip if AC = 0
SZE 7002 \(B_1\) skip if E = 0
HLT 7001 \(B_0\) S ← 0

Skip means PC ← PC + 1. CMA then INC negates AC. Circulates rotate the 17-bit ring AC + E: the count of 1s is unchanged. CMA does not touch E; INC does not touch E.

Input-output instructions (Fxxx)

Executed when \(p = D_7IT_3\).

Sym Hex Microoperation
INP F800 AC(0-7) ← INPR, FGI ← 0
OUT F400 OUTR ← AC(0-7), FGO ← 0
SKI F200 skip if FGI = 1
SKO F100 skip if FGO = 1
ION F080 IEN ← 1
IOF F040 IEN ← 0

Polling: LOOP, SKI / BUN LOOP / INP (wastes the CPU). INPR and OUTR are 8 bits; FGI and FGO tell the CPU when the slow device is ready.

Interrupt

Set R:  T0'T1'T2'(IEN)(FGI + FGO) :  R ← 1        (only between instructions)
RT0:  AR ← 0,  TR ← PC
RT1:  M[AR] ← TR,  PC ← 0
RT2:  PC ← PC + 1,  IEN ← 0,  R ← 0,  SC ← 0

Return address saved at word 0; service routine starts at word 1; routine ends with ION then BUN I 0. IEN is cleared so that a second interrupt cannot overwrite word 0. With interrupts, fetch is \(R'T_0\), \(R'T_1\), \(R'T_2\).

Control-gate design (hardwired)

Each control input is the OR of every control function in the table that changes the register.

Register Expressions
AR \(LD = R'T_0 + R'T_2 + D_7'IT_3\); \(CLR = RT_0\); \(INR = D_5T_4\)
PC \(LD = D_4T_4 + D_5T_5\); \(CLR = RT_1\); \(INR = R'T_1 + RT_2 +\) skip conditions
Memory \(Read = R'T_1 + D_7'IT_3 + (D_0 + D_1 + D_2 + D_6)T_4\); \(Write = RT_1 + D_3T_4 + D_5T_4 + D_6T_6\)

Bus select: \(S_0 = x_1 + x_3 + x_5 + x_7\), \(S_1 = x_2 + x_3 + x_6 + x_7\), \(S_2 = x_4 + x_5 + x_6 + x_7\) (encoder of the source lines \(x_1 \ldots x_7\) = AR, PC, DR, AC, IR, TR, memory); \(x_1 = D_4T_4 + D_5T_5\), \(x_2 = T_0 + D_5T_4\), \(x_7 = Read\). Only one \(x_i\) is 1 at a time.

Hardware: memory 4096 × 16; nine registers; seven flip-flops (I, S, E, R, IEN, FGI, FGO); 3 × 8 and 4 × 16 decoders; 16-bit bus; control gates; adder and logic circuit at AC.

Control unit styles

Hardwired Microprogrammed
Built from gates, decoders, flip-flops control memory of microinstructions (CAR sequences it)
Speed faster slower (a control-memory read per step)
Change redesign the circuit rewrite the microcode
Suits RISC, the basic computer CISC, emulation

20-bit microinstruction: F1 (3) F2 (3) F3 (3) CD (2) BR (2) AD (7); control memory up to \(2^7 = 128\) words. Microoperation = one register transfer in one clock; microinstruction = one control word; microprogram = all the microinstructions that implement the instruction set.

Pipelining

Segments: FI fetch instruction, DA decode and effective address, FO fetch operand, EX execute. Clock period = slowest segment (plus register delay).

Quantity Formula
Cycles, pipelined / unpipelined \(k + n - 1\) / \(k \cdot n\)
Time, pipelined / unpipelined \((k + n - 1)\,t_p\) / \(n\,t_n\)
Speedup \(S = n\,t_n / ((k + n - 1)\,t_p)\)
Ceiling \(t_n/t_p\) (\(= k\) if \(t_n = k\,t_p\))
Efficiency, throughput \(S/k\); \(n\) over pipelined time

Pipelining raises throughput, not latency. Hazards insert bubbles: structural (same hardware, for example FI and FO both need memory; separate instruction and data memories), data (result not ready; forwarding, stalls), control (branch makes fetched instructions wrong; prediction, delayed branch, flush).

Q.5 Unit 5: Processors

The control word (general register organization)

Datapath: register file R1 to R7, MUX A (SELA) and MUX B (SELB) feed the A and B buses, the ALU (OPR) computes, a 3 × 8 decoder (SELD) loads the destination, all in one clock pulse.

Field Bits Selects
SELA 3 register on the A bus
SELB 3 register on the B bus
SELD 3 destination register
OPR 5 ALU operation

Register codes: 000 = external input (SELA, SELB) or none (SELD); 001 to 111 = R1 to R7. Sample OPR codes: TSFA 00000, INCA 00001, ADD 00010, SUB 00101, DECA 00110, AND 01000, OR 01010, XOR 01100, COMA 01110, SHRA 10000, SHLA 11000. Always use the codes a question supplies.

Method for Rd ← Ra op Rb: SELA = Ra, SELB = Rb, SELD = Rd, OPR = op, written in the order SELA SELB SELD OPR (14 bits). Unary operations leave SELB = 000. Clear a register by XOR with itself. Example: R1 ← R2 − R3 is 010 011 001 00101.

Stacks and reverse Polish notation

Stack Push Pop
Register stack (64 words) SP ← SP + 1; M[SP] ← DR; if SP = 0 then FULL ← 1; EMTY ← 0 DR ← M[SP]; SP ← SP − 1; if SP = 0 then EMTY ← 1; FULL ← 0
Memory stack (grows down, SP at top) SP ← SP − 1; M[SP] ← DR DR ← M[SP]; SP ← SP + 1

State the growth direction and whether SP points at the top item or the next free slot. Memory stack limits are checked with limit registers.

RPN: operand, push; operator, pop two (the second popped is the left operand), apply, push. (A + B) × (C + D) is A B + C D + *; A + B × C is A B C × +. An expression with n operands has n − 1 binary operators.

Instruction formats for X = (A + B) × (C + D): three-address 3 instructions, two-address 6, one-address 7, zero-address (stack) 8. Expanding opcode: each unused code gains the freed address bits (16-bit word, 6-bit addresses, 14 two-address instructions: 2 × 64 = 128 one-address, then (128 − 100) × 64 = 1792 zero-address).

Addressing modes and the instruction set

Mode EA Mano's example (A = 500, PC = 202, R1 = 400, XR = 100)
Immediate none (operand = field) 500
Direct A 500, AC = 800
Indirect M[A] 800, AC = 300
Relative PC + A 702, AC = 325
Indexed XR + A 600, AC = 900
Register none AC = 400
Register indirect R 400, AC = 700
Autoincrement R, then R + 1 400, AC = 700
Autodecrement R − 1 first, then used 399, AC = 450

PC is the updated PC (a two-word instruction at 200 and 201 gives PC = 202). Indexed: field = array base, register varies; base-register: register = base, field = displacement. Relative addressing gives relocatable code. Notation: # immediate, @ indirect, $ relative, (R) register indirect, ADR(X) indexed, (R)+ autoincrement.

Instruction families: data transfer (LD, ST, MOV, XCH, IN, OUT, PUSH, POP); arithmetic (INC, DEC, ADD, SUB, MUL, DIV, ADC, SBB, NEG); logical (CLR, COM, AND, OR, XOR; with a mask AND clears, OR sets, XOR complements); shifts (logical, arithmetic, rotate, rotate through carry); program control (BR, JMP, SKP, CALL, RET, CMP, TST). CALL: SP ← SP − 1; M[SP] ← PC; PC ← EA; RET: PC ← M[SP]; SP ← SP + 1.

Status bits: C = C8, S = F7, Z = all-zero result, V = C7 ⊕ C8. After A − B: unsigned A ≥ B iff C = 1 (BHI: C = 1 and Z = 0, BLO: C = 0); signed A < B iff S ⊕ V = 1 (BLT). An interrupt saves the PC and the PSW; a subroutine call saves only the PC.

RISC and CISC

Point RISC CISC
Instructions few, simple (under 100) many, complex (100 to 250)
Length fixed variable
Memory access LOAD and STORE only most instructions
Cycles per instruction about 1 several
Registers many (windows) few
Control hardwired microprogrammed
Addressing modes 3 to 5 5 to 20
Complexity in the compiler the hardware
Examples ARM, MIPS, SPARC, RISC-V x86, VAX, 68000

Register windows: window size = L + 2C + G; register file = (L + C)W + G (G = 10, L = 10, C = 6, W = 4 gives 32 and 74; W = 8 gives 138). The caller's output registers are the callee's input registers. Berkeley RISC I: 31 instructions, three 32-bit formats (opcode 8 bits). RISC-V: x0 = 0, six formats R, I, S, B, U, J; opcode bits 6 to 0, rd 11 to 7, rs1 19 to 15, rs2 24 to 20; add x5, x6, x7 = 0x007302B3; addi x5, x6, 100 = 0x06430293; sub x10, x11, x12 = 0x40C58533.

CPU time = instruction count × CPI × clock period (period = 1/frequency). Pipeline of k segments: n instructions take (k + n − 1) clock periods. Example: 800 × 6 × 2 ns = 9600 ns (CISC) against 1600 × 1.2 × 1 ns = 1920 ns (RISC), a factor of 5.

Multicore, Amdahl's law and GPUs

Power wall: dynamic power ≈ C·V²·f; higher f needs higher V, so clocks stopped rising around 2005. Multicore: private L1 and L2, shared L3, cache coherence keeps copies consistent. Flynn: SISD, SIMD (GPU), MISD, MIMD (multicore).

Amdahl: S = 1 / ((1 − p) + p/n); ceiling 1/(1 − p); p = (1 − 1/S)/(1 − 1/n).

p n = 2 n = 4 n = 8 n = 16 ceiling
0.50 1.33 1.60 1.78 1.88 2
0.75 1.60 2.29 2.91 3.37 4
0.80 1.67 2.50 3.33 4.00 5
0.90 1.82 3.08 4.71 6.40 10
0.95 1.90 3.48 5.93 9.14 20

"25% cannot be parallelised" means p = 0.75.

CPU GPU
Goal low latency high throughput
Cores few (4 to 64), complex thousands, simple
Model MIMD SIMD or SIMT (warp of 32)
Cache and control large small; area goes to ALUs
Best for serial, branchy code data-parallel work (matrices, pixels, deep learning)

Branch divergence: a warp whose threads take different branches runs both paths in turn (32-way divergence is 32 times slower). A GPU hides memory latency by switching warps.

Q.6 Unit 6: Memory and Input-Output Organization

Memory hierarchy and chips

Level Technology Access time Capacity Cost per bit
Registers flip-flops about 1 ns bytes highest
Cache SRAM 1-10 ns KB-MB high
Main memory DRAM, ROM 50-100 ns GB medium
SSD / disk / tape flash, magnetic 50 µs / 10 ms / seconds TB lowest
  • Going down: access time rises, cost per bit falls, capacity grows. It works because of locality of reference.
  • RAM is volatile (SRAM for cache, DRAM for main memory); ROM is non-volatile and holds the bootstrap loader. ROM family: mask ROM, PROM, EPROM (UV erase), EEPROM, flash.
  • A chip of \(2^k \times n\) has \(k\) address lines and \(n\) data lines. K = 1024.
  • Chips \(=\) (words needed / words per chip) \(\times\) (bits needed / bits per chip), each factor rounded up. The decoder has \(\log_2(\text{rows})\) inputs.
  • Memory map: low-order lines go to every chip; high-order lines feed the decoder. Block sizes in hex: 256 B = 100, 512 B = 200, 1 KB = 400, 4 KB = 1000, 8 KB = 2000.

Disk

  • Capacity \(=\) surfaces \(\times\) tracks \(\times\) sectors per track \(\times\) bytes per sector.
  • Access time \(= T_{seek} + T_{rot} + T_{transfer}\), with average \(T_{rot} = \tfrac12 \times 60/\text{RPM}\) s. At 7200 RPM one revolution is 8.33 ms and the latency 4.17 ms.
  • Tape is sequential and cheapest (backup); an SSD has no seek or rotational latency.

Cache

  • \(t_{avg} = h\,t_c + (1-h)\,t_m\); hit ratio \(h\) = hits / references.
  • Address split: word bits \(= \log_2(\text{block size})\); lines \(=\) cache size / block size; direct index \(= \log_2(\text{lines})\); \(k\)-way set bits \(= \log_2(\text{lines}/k)\); tag \(=\) the rest.
Mapping Fields Block may go in Tags compared
Direct TAG, INDEX, WORD one line 1
Associative TAG, WORD any line all
\(k\)-way set-associative TAG, SET, WORD any of \(k\) lines of one set \(k\)
  • More associativity at fixed size: fewer sets, index shrinks, tag grows, word unchanged.
  • Write-through: memory always consistent, heavy traffic. Write-back: dirty bit, light traffic, memory stale. Replacement (FIFO, LRU, random, LFU) only for associative and set-associative caches.
  • Misses: compulsory, capacity, conflict. Virtual memory: page number translated, offset copied; presence bit 0 means a page fault.

I/O interface and transfer

  • Interface registers: port (data), control, status; selected by CS, RS1, RS0. Isolated I/O: separate space, IN/OUT. Memory-mapped I/O: one space, load/store, reduces memory, must be non-cacheable.
  • Strobe: one line, no reply. Handshake: two lines (data valid / data accepted or ready for data), timeout detects failure.
  • Serial frame: start 0, data LSB first, optional parity, stop 1. Characters per second \(=\) baud / bits per frame (11 bits at 9600 baud: 872).

Modes of transfer

Programmed I/O Interrupt-initiated DMA
Who moves data CPU CPU in ISR DMA controller
CPU waits? yes (polls) no no
CPU interventions every word + polling every word once per block
Speed slowest moderate fastest
  • Daisy chain: acknowledge passes through PI/PO; the device with PI = 1, PO = 0 is served; nearest the CPU wins.
  • Parallel priority: interrupt register AND mask register, priority encoder; \(x = I_0'I_1'\), \(y = I_0'I_1 + I_0'I_2'\), IST \(= I_0+I_1+I_2+I_3\).
  • Polling cost: checks per word \(=\) time per word / time per check.

DMA

  • BR: controller asks; CPU finishes its bus cycle, floats its lines (high impedance), asserts BG.
  • Registers: address (incremented), word count (decremented, zero ends), control (direction, mode). One interrupt at completion.
  • Burst: whole block, fastest, CPU locked out. Cycle stealing: one word per cycle, CPU slowed slightly. Burst time \(=\) words \(\times\) memory cycle.
  • IOP (channel): executes its own I/O program; interrupts the CPU once per whole operation.