Exam Practice

Cheat sheet, flashcards and quiz covering Lectures 1–7: computer evolution & the von Neumann model, number representation & arithmetic, floating point, character & recording codes, CRC & Hamming codes, Boolean algebra, K-maps, combinational & sequential circuits, and the MARIE processor, assembly language & control unit.

Reference text: The Essentials of Computer Organization and Architecture, Linda Null & Julia Lobur

Need step-by-step recipes and blank templates? Open the Problem-Solving Guide →

1.1 Organization vs. Architecture & Components

	Computer organization	Computer architecture
Covers	All the physical aspects of the system	The logical aspects as seen by the programmer
Examples	Circuit design, control signals, memory types (SRAM, DRAM, DDR3/DDR4), bus design, clock rate, how a multiplier is built	Instruction set, instruction formats, data types, addressing modes, number of programmer-visible registers, whether a multiply instruction exists
Question answered	How does each component work and how are components connected?	What can the machine do: how components work together to run programs
Quick test	Program runs the same; only speed/cost/physical build changes	A programmer must know it to write a correct program
Lecture example: macOS	Apple M1 chip, Thunderbolt ports, Retina display	Unix-based system, APFS, iCloud/Apple services (App Store)
Lecture example: Windows	Intel or AMD processors, various motherboards, USB peripherals	Windows NT-based system, NTFS, OneDrive, Office 365
Three basic components	1. Processor (CPU): interprets and executes programs 2. Memory: stores both data and programs 3. I/O system + buses: transfers data between components and external devices	Same architecture, different organization: every x86-64 chip from Intel and AMD runs the same programs

1.1 Units, Prefixes & Spec-Sheet Reading

Powers of 2 (memory size)K =

2^{10}

= 1,024; M =

2^{20}

= 1,048,576; G =

2^{30}

= 1,073,741,824; T =

2^{40}

; P =

2^{50}

. Used for RAM and cache.

Powers of 10 (speed, data rate, disk)K =

10^3

, M =

10^6

, G =

10^9

, T =

10^{12}

. Used for Hz, bits/s, and advertised disk/SSD capacity.

Small units (time)milli m =

10^{-3}

(disk, display ms); micro µ =

10^{-6}

; nano n =

10^{-9}

(CPU cycles, RAM); pico p =

10^{-12}

(gate delays).

Frequency ↔ period

T = 1/f

. 1 MHz → 1 µs; 1 GHz → 1 ns; 3.9 GHz → 0.256 ns; 1600 MHz → 0.625 ns.

Byte vs bit1 B = 8 b. Storage uses capital B; network speed uses lowercase b (Mbps). 1000 Mbps =

125 \times 10^6

bytes/s.

"1 TB" shows as 931 GB

10^{12} / 2^{30} \approx 931.3

GiB. Same bytes, bigger unit. IEC binary prefixes: KiB, MiB, GiB, TiB.

Disk rotationrev/s = RPM / 60; time per rev = 1/(rev/s); average rotational delay = half a revolution. 7200 RPM → 8.33 ms/rev, 4.17 ms average.

Frame buffer sizepixels × (bits per pixel / 8). 1920×1200 at 24-bit = 6,912,000 B ≈ 6.59 MB; 24-bit colour =

2^{24}

= 16,777,216 colours.

Ad vocabularyBus: shared wires for data/address/control. Port: connector for an external device (USB, HDMI). Cache: small fast memory of recently used data (L1 smallest/fastest). Hz: cycles per second. DDR = double data rate (both clock edges); SDRAM = synchronous dynamic RAM.

Classifying ad linesi7 Quad Core 3.9 GHz → processor; DDR3 SDRAM, L1/L2 cache → memory; SATA HDD, USB/PCI/PCIe slots, monitor, video/sound card, Ethernet → I/O.

1.2 Generations of Computers (incl. 5th & 6th)

Generation	Switching technology	Key machines / facts
0 (1642–1945)	Mechanical gears, wheels, levers	Schickard's Calculating Clock; Pascal's Pascaline (adding machine); Babbage's Difference Engine and Analytical Engine (mill + store + punched cards, never built; Ada Lovelace); Hollerith's punched-card tabulator (1890 US census → IBM)
1 (1945–1953)	Vacuum tubes	ENIAC (Mauchly & Eckert, 1946): ~17,468 tubes, ~30 tons, ~174 kW, programmed by plugs and wires; UNIVAC I (1951, first US commercial); IBM 650 (1955, first mass-produced). WWII: Turing's Bombe (Enigma), Colossus (Lorenz)
2 (1954–1965)	Transistors (Bell Labs 1947, germanium)	~10× faster, 1/10 power and space; switches in µs; magnetic core RAM; FORTRAN, COBOL, ALGOL, SNOBOL; IBM 7094, DEC PDP-1, CDC 6600 (first supercomputer, Cray); CS becomes a discipline
3 (1965–1980)	Integrated circuits (Kilby, Noyce; silicon)	~1 MIPS; online systems (airline reservations), time-sharing; IBM + BUNCH (Burroughs, Univac, NCR, Control Data, Honeywell); IBM System/360 (first family sharing one architecture), PDP-8/PDP-11, Cray-1 (1976); UNIX rewritten in C on PDP-11 (1973)
4 (1980– )	VLSI (more than 10,000 components/chip)	Microprocessor: Intel 4004 (1971, 4-bit, ~2,300 transistors), 8080, 808x (8088 in 1981 IBM PC) → personal computing; parallel architectures
5 (2000– )	ULSI (billions of transistors)	Multicore and big.LITTLE CPUs, SoCs (Apple M-series), GPUs, AI accelerators (NPU, TPU), multi-level caches, DDR5/LPDDR, HBM, NVMe SSDs, PCIe/USB-C/Thunderbolt, Wi-Fi 6/7, 4G/5G, IoT, cloud; AI/ML software. Still IC technology, so some say still 4th gen
6 (expected)	Beyond silicon and beyond von Neumann	Quantum processors (qubits), neuromorphic chips (artificial neurons/synapses, non-von Neumann), in-memory computing (memristors, removes the bottleneck), optical/photonic computing, carbon nanotubes/graphene, 3-D chips and chiplets, DNA storage, brain-computer interfaces, AR/VR, 6G, edge computing. Mostly research prototypes

1.2 Integration Scales, Moore's Law & Rock's Law

Integration scalesSSI 10–100; MSI 100–1,000; LSI 1,000–10,000; VLSI more than 10,000; ULSI more than 1,000,000 components per chip.

Moore's law (1965)Gordon Moore: transistor density in an IC doubles every year. Contemporary version: density of silicon chips doubles every 18 months (Moore revised to 2 years in 1975).

Rock's lawArthur Rock: cost of capital equipment to build semiconductors doubles every 4 years. 1968 plant ≈ USD 12,000; 2012 plants well over USD 5 billion.

Growth formula

N(t) = N_0 \times 2^{t/d}

.
1.

k = t/d

doublings (same units).
2. Multiply by

2^k

.
3. Backwards:

k = \log_2 F

t = k \times d

Handy values

2^{10} = 1024 \approx 1000

: 10 doublings ≈ ×1000 → 15 years (18-month) or 20 years (2-year). 3 years at 18 months = 2 doublings (×4); 9 years = 6 doublings (×64).

Moore vs. RockFor Moore's law to hold, Rock's law must fail, or vice versa: each density doubling needs costlier fabs, and eventually no one can afford the next plant.

Why Moore's law cannot lastTransistors cannot shrink below a few atoms; heat and quantum effects grow at tiny sizes.

Identifying a generationLook for the switching technology: gears → 0, tubes → 1, transistors/core memory → 2, ICs → 3, single-chip microprocessor (VLSI) → 4, ULSI multicore/AI → 5.

1.3 The von Neumann Model

ENIAC programmingAll programming at the digital logic level: moving plugs and wires, setting switches. A different hardware configuration for every unique problem type.

Stored-program conceptInstructions stored in the same memory as data, as binary numbers. Conceived by Mauchly and Eckert, ascribed to John von Neumann (1945 EDVAC report). Change program = load new numbers, no rewiring.

Von Neumann characteristics1. Three hardware systems: CPU (control unit, ALU, registers, PC), main memory (programs + data), I/O system.
2. Sequential instruction processing.
3. A single data path between CPU and main memory.

Von Neumann bottleneckThe single CPU–memory path: every instruction and operand travels over it one transfer at a time. Max rate = 1 / (transfers per instruction × transfer time). Softened by caches, wider buses, split I/D caches.

Fetch-decode-execute1. Fetch: MAR ← PC, IR ← M[MAR], PC ← PC + 1.
2. Decode: examine opcode; MAR ← IR[11–0].
3. Fetch operand: MBR ← M[MAR].
4. Execute: ALU operates, result to AC or memory. Repeat.

MARIE registersPC = address of next instruction; IR = current instruction; MAR = address sent to memory; MBR = data read/written; AC = accumulator.

Instruction format used16 bits = 4 hex digits: first hex digit = opcode (1 Load, 2 Store, 3 Add, 7 Halt), last three = address. 1104 = Load 104.

Sample traceLoad 104 (0023), Add 105 (FFE9 = −23), Store 106 →

\text{0023}_{16} + \text{FFE9}_{16} = \text{1000C}_{16}

, keep 16 bits → M[106] = 000C = 12. PC is incremented during fetch.

1.3 Non-von Neumann Models

Model	Departure from von Neumann	Example / use
Harvard	Separate memories and paths for instructions and data; fetch and data access overlap	Microcontrollers (AVR, PIC), DSPs; modern CPUs are modified Harvard (split L1 I/D caches)
Special-purpose (GPU)	Many simple cores in parallel, offloading the CPU	Graphics, scientific computing, neural-network training
Dataflow	No program counter: an instruction fires when its input data are available	Research machines; ideas in out-of-order CPUs
Quantum	Qubits in superpositions of 0 and 1	Factoring, molecule simulation
Cellular automata	Grid of simple cells updating from neighbours	Simulation, theoretical models
Parallel computing	Many processors at the same time, not one sequential stream	Multicore CPUs, supercomputers, clusters
Machine intelligence	Networks of artificial neurons instead of explicit instruction sequences	ANN, DNN, GPT-style models, neuromorphic chips
Bottleneck example	Von Neumann: 2 transfers × 10 ns = 20 ns → 50 million instr/s	Harvard (two 10 ns buses overlapping): 10 ns → 100 million instr/s

2.1 Bits, Bytes & Units

Bit / Nibble / Byte / Word1 bit; nibble = 4 bits = 1 hex digit; byte = 8 bits = 2 hex digits (smallest addressable unit); word = machine-dependent group of bytes (16, 32, 64 bits).

Address bits

\log_2(\text{number of addressable units})

2^{24}

bytes, 32-bit words: byte-addressable 24 bits; word-addressable

2^{24}/2^2 = 2^{22}

words → 22 bits.

Positional value

(d_{n-1}\cdots d_0.d_{-1}\cdots)_b = \sum d_i \times b^{i}

, digits

0 \le d_i \le b-1

Digits needed

n

base-

b

digits give

b^n

values (

0

b^n-1

). Digits for

N

\lfloor \log_b N \rfloor + 1

; highest power

b^{\lfloor \log_b N \rfloor}

\log_b N = \ln N / \ln b

Any base → decimalMultiply each digit by its weight and add.

10212_3 = 81+0+18+3+2 = 104

;

101.11_2 = 5.75

Decimal integer → base

b

1. Divide by

b

, record remainder.
2. Repeat on the quotient until 0.
3. Read remainders bottom to top (first remainder = LSD).
(Or subtraction method: subtract largest powers

b^k

Decimal fraction → base

b

1. Multiply fraction by

b

.
2. Integer part = next digit.
3. Keep fraction, repeat until 0 or enough digits.
4. Read digits top to bottom.

0.8125 = 0.1101_2

Terminating binary fractionsTerminates only if (in lowest terms) the denominator is a power of 2.

0.1_{10} = 0.0\overline{0011}_2

0.6_{10} = 0.\overline{1001}_2

never terminate.

Binary ↔ hex/octal groupingGroup 4 bits (hex) or 3 bits (octal) starting at the radix point: left for the integer, right for the fraction; pad outer groups with 0s. Hex ↔ octal: go through binary.

\text{7A9.C}_{16} = 0111\,1010\,1001.1100_2 = 011\,110\,101\,001.110_2 = 3651.6_8 = 1961.75

2.1 Grouping: Binary ↔ Hex ↔ Octal

Hex	Binary	Hex	Binary	Hex	Binary	Hex	Binary
0	0000	4	0100	8	1000	C	1100
1	0001	5	0101	9	1001	D	1101
2	0010	6	0110	A	1010	E	1110
3	0011	7	0111	B	1011	F	1111

2.2 Signed Integer Representations

Scheme	Form −N	Range (n bits)	8 bits	Zeros	Arithmetic
Unsigned	—	$0$ to $2^n-1$	0 to 255	one	plain binary
Signed magnitude	sign bit 1 + magnitude	$-(2^{n-1}-1)$ to $2^{n-1}-1$	−127 to +127	two (+0, −0)	worst: compare signs/magnitudes
One's complement	$(2^n-1)-N$ = flip all bits	$-(2^{n-1}-1)$ to $2^{n-1}-1$	−127 to +127	two (00…0, 11…1)	add + end-around carry
Two's complement	$2^n-N$ = flip + 1	$-2^{n-1}$ to $2^{n-1}-1$	−128 to +127	one	add, discard carry (best)

2.2 Two's Complement Toolkit

Negate (flip + 1)

19 = 0001\,0011

→ flip

1110\,1100

→ +1 →

-19 = 1110\,1101

Copy-then-flip shortcutFrom the right, copy bits up to and including the first 1, flip the rest.

44 = 0010\,1100

→

-44 = 1101\,0100

Reading a patternMSB weight is

-2^{n-1}

b_{n-1}\cdots b_0 = -b_{n-1}2^{n-1} + \sum_{i<n-1} b_i 2^i

1011\,0101 = -128+53 = -75

Same pattern, 4 readings

1011\,0101

: unsigned 181, signed magnitude −53, one's −74, two's −75. Sign bit 0 → all readings equal.

3-bit table (100…111)SM: −0, −1, −2, −3. One's: −3, −2, −1, −0. Two's: −4, −3, −2, −1.

Sign extensionTwo's / one's: copy the sign bit (

1101 → 1111\,1101

). Signed magnitude: sign to new MSB, insert 0s after it (

1101 → 1000\,0101

). Unsigned: zero-fill.

Why two's complement winsOne zero, widest range, subtraction = addition with carry simply discarded (one extra negative is the only cost).

2.3 Add/Subtract Rules

Scheme	Procedure	Overflow
Signed magnitude	Same signs: add magnitudes, keep common sign. Different signs: subtract smaller magnitude from larger, sign of larger. $A-B = A+(-B)$ (flip B's sign).	Carry out of the leftmost magnitude bit
One's complement	Add all bits incl. sign. Carry out of MSB → add it back to LSB (end-around carry).	Same-sign operands give opposite-sign result
Two's complement	Add all bits incl. sign; discard carry out. $A-B = A + B' + 1$ .	$V = C_{\text{in,MSB}} \oplus C_{\text{out,MSB}}$ ; different signs never overflow

2.3 Overflow, Adder/Subtractor & Multiplier

Carry ≠ overflow

(-4)+(-1) = 1100+1111 = 1\,1011

: carry out, but

1011 = -5

correct (carry in = carry out = 1).

Overflow example (4-bit)

5+4 = 0101+0100 = 1001

: carry in 1, out 0 → overflow (reads −7).

XOR adder/subtractorEach

B_i

passes through XOR with

M

;

M

is also

C_0

M=0

A+B

M=1

A+B'+1 = A-B

V = C_{n-1} \oplus C_n

Block diagramB register → complementer → switch (SW) → adder ← A register; result back to A; OF bit = overflow flag.

Sequential multiplier registersM = multiplicand (

n

), Q = multiplier (

n

), A = accumulator (

n

, starts 0), C = carry (1 bit), Count =

n

Multiplier algorithm1. If

Q_0 = 1

C,A ← A + M

.
2. Shift C,A,Q right 1 (

C→A_{n-1}

A_0→Q_{n-1}

Q_0

dropped).
3. Count ← Count − 1; repeat until 0.
4. Product (

2n

bits) in A,Q.

Example 11 × 13 (4-bit)Cycle 4 add

0110+1011 = 1\,0001

sets C = 1; shift moves it into

A_3

. Final

AQ = 1000\,1111 = 143

2.4 Lecture's 14-bit Floating-Point Model

Layout1 sign | 5 exponent (excess-16) | 8 fraction bits. Implicit leading 1: value

= (-1)^S \times 1.F \times 2^{E-16}

NormalizationForm

1.\text{xxx} \times 2^e

. Point left

k

places → exponent

+k

; right

k

→

-k

1001.101 = 1.001101 \times 2^3

Excess-16 exponentStored = true + 16. Stored 0–15 → −16 to −1; 16 → 0; 17–31 → +1 to +15. Unbiased (plain unsigned) exponent cannot hold negatives.

Why bias?Allows negative exponents while the field stays unsigned, so values compare/sort like ordinary binary numbers.

Decimal → 14-bit1. Sign bit.
2.

|x|

to binary.
3. Normalize

1.f \times 2^e

.
4. Exponent field

= e + 16

(5 bits).
5. Fraction

f

padded/truncated to 8 bits.

Worked values

17 → 0\ 10100\ 00010000

;

9.625 → 0\ 10011\ 00110100

;

-0.375 → 1\ 01110\ 10000000

;

0.1 → 0\ 01100\ 10011001

(= 0.099853515625).

LimitsTrue exponents −16 to +15. Largest:

0\ 11111\ 11111111 = (2-2^{-8}) \times 2^{15} = 65408

2.4 IEEE 754

Item	Single (32)	Double (64)
Sign / Exponent / Fraction	1 / 8 / 23	1 / 11 / 52
Bias	127	1023
Value (normal)	$(-1)^S \times 1.F \times 2^{E-127}$	$(-1)^S \times 1.F \times 2^{E-1023}$
E = 0, F = 0	±0 (two zeros)	±0
E = all 1s, F = 0	±∞ (E = 255)	±∞ (E = 2047)
E = all 1s, F ≠ 0	NaN (e.g. 0/0, √−1)	NaN
Approx. range	max ≈ $3.4 \times 10^{38}$ , min normal $2^{-126} \approx 1.18 \times 10^{-38}$	≈ $10^{-308}$ to $10^{308}$ ( $1024 \log_{10}2 \approx 308$ )
Examples	$1.0 = \text{3F800000}$ ; $-12.375 = \text{C1460000}$ ; $0.15625 = \text{3E200000}$ ; $+\infty = \text{7F800000}$ ; $-0 = \text{80000000}$	$1.0 = \text{3FF0000000000000}$ ; $-2.5 = \text{C004000000000000}$

2.5 Floating-Point Arithmetic

Operation	Significands	Exponents	Steps
$X \pm Y$	add/subtract after alignment	made equal (the larger)	1. Check zeros. 2. Shift the smaller-exponent significand right until exponents match. 3. Add/subtract. 4. Normalize. 5. Round/truncate; check over/underflow.
$X \times Y$	multiply	add: $E = E_X + E_Y - 16$	Sign $= S_X \oplus S_Y$ ; product in $[1,4)$ needs at most one right shift.
$X / Y$	divide	subtract: $E = E_X - E_Y + 16$	Sign = XOR; normalize (quotient may need a left shift).

2.5 Range, Precision & Errors

Range vs precisionExponent field → range. Significand field → precision.

Overflow / underflowOverflow: exponent too large to store. Underflow: nonzero value whose exponent is too small (too close to 0). 14-bit:

2^{18}

needs field 34 > 31 (overflow);

2^{-18}

needs field −2 (underflow).

SpacingWith 8 fraction bits, values near

2^e

are

2^{e-8}

apart. Near 128: spacing 0.5, so

128.75

stores as

128.5

Blatant vs subtle errorBlatant: obvious failure (crash, overflow/underflow). Subtle: plausible but slightly wrong (truncation). Better to crash than give plausible wrong results.

Equality testsNever test x == 0.0 or sum == 1.0; use abs(x - y) < epsilon. Summing 0.1 ten times in double gives 0.9999999999999999.

FP emulationSoftware doing floating point on integer hardware; most CPUs instead have a dedicated FPU (much faster).

3.1 Character Codes: BCD, EBCDIC, ASCII & Unicode

Code	Bits / char	Characters	Notes
BCD (6-bit)	6	$2^6 = 64$	IBM 1950s–60s; each decimal digit = 4 bits (0000–1001); 1010–1111 unused
EBCDIC	8	$2^8 = 256$	IBM mainframes; zone (high nibble) \| digit (low nibble); upper + lower case
ASCII	7 (+1 parity)	$2^7 = 128$	From Telex codes; hex 00–7F; 8th bit = parity or extended set
Unicode	21-bit code space	$17 \times 65{,}536 = 1{,}114{,}112$	U+0000–U+10FFFF; 17 planes; U+0000–U+007F = ASCII

3.1 Key Codes, BCD Signs & Parity

ASCII anchors"0" = 30 hex (48), "A" = 41 hex (65), "a" = 61 hex (97), space = 20, LF = 0A, CR = 0D, DEL = 7F. Upper/lower case differ by 20 hex (bit 5).

EBCDIC landmarksspace 40; a–i 81–89; j–r 91–99; s–z A2–A9; A–I C1–C9; J–R D1–D9; S–Z E2–E9; 0–9 F0–F9 (letters not contiguous).

BCD zone / sign nibble1111 = unsigned, 1100 = +, 1101 = −.

Zoned decimalOne digit per byte. Zone 1111 on every digit except the last, whose zone is the sign.

+305

= F3 F0 C5.

Packed BCDTwo digits per byte, sign nibble at the right end; pad a leading 0000 if the nibble count is odd.

-26

= 02 6D;

-1265

= 01 26 5D.

Even / odd parityParity bit is the leftmost (8th) bit. Even: total 1s even. Odd: total 1s odd. Detects any odd number of flipped bits, misses an even number, cannot locate the error.

Unicode planePlane = code point

\div 65536

= hex digits in front of the last four. Plane 0 = BMP (U+0000–U+FFFF); planes 1–16 supplementary. U+1F600 → plane 1.

Encoding formsUTF-16: one 16-bit unit for BMP, surrogate pair otherwise. UTF-8: 1–4 bytes, ASCII unchanged in 1 byte.

3.2 Data Recording & Transmission Codes

Code	Rule	Transitions / data bit	Weakness / use
NRZ	1 = high whole cell, 0 = low whole cell	0 – 1	Loses sync on long runs of 0s or 1s
NRZI	1 = transition (mid-cell), 0 = none; level meaningless	0 – 1	Loses sync on runs of 0s; RS-232, tape, basic optical
Manchester	Mid-cell: 1 = low→high, 0 = high→low; extra boundary flip between equal bits	1 – 2	Self-clocking, 2× NRZ bandwidth; classic Ethernet
FM	Clock transition at every cell boundary (end of cell) + mid-cell transition for each 1	1 – 2	Least dense disk code; easy to decode
MFM	Mid-cell transition for each 1; boundary transition only between two adjacent 0s	0.5 – 1	Floppies, early hard disks
RLL(2,7)	Re-code via table (2 code bits per data bit), then NRZI	0.25 – 0.67	2 to 7 zeros between code 1s; densest

3.2 Counting Transitions & RLL(2,7)

Bit cellTransmission: time for one bit

= 1/\text{bit rate}

(2 Kbps → 0.5 ms). Storage: area of surface holding one bit. A flux reversal = change of magnetic polarity.

Counting formulas (

n

bits)NRZ = number of adjacent unequal pairs. NRZI = number of 1s. Manchester =

n

+ adjacent equal pairs. FM = number of 1s +

n

(clock at end of each cell). MFM = number of 1s + adjacent 00 pairs. RLL = number of 1s in the code.

Half-cell levelsNRZI (start high) 10011: HL LL LL LH HL. Manchester: 1 = LH, 0 = HL. FM: 1 cell = halves differ, 0 cell = halves equal, level always flips between cells. FM (start low) 1100: LH LH LL HH.

RLL(2,7) table10→0100, 11→1000, 000→000100, 010→100100, 011→001000, 0010→00100100, 0011→00001000.

RLL parsing1. Next bit 1 → take 2 bits. 2. Next bits 01 → take 3. 3. Next 000 → take 3. 4. Next 001 → take 4. 5. Replace by codes, record with NRZI (one transition per code 1).

RLL(d,k)At least

d

, at most

k

zeros between 1s. (2,7): reversals ≥ 3 code cells apart, at least one every 8 code cells.

"OK" (16 bits) counts11001111 01001011: NRZ 8, NRZI 10, Manchester 23, FM 26, MFM 12, RLL 8. RLL saves

(12-8)/16 = 25\%

vs MFM.

Density rankingFor a fixed number of flux reversals per area: RLL

\gt

MFM

\gt

FM. Modern drives use PRML.

3.3 Check Digits & CRC

UPC-A check digit1. Sum odd positions (1,3,…,11). 2. ×3. 3. Add even positions (2,…,10) →

S

. 4. Check

= 10 - (S \bmod 10)

, or 0 if

S \bmod 10 = 0

. 03600024145 →

S=53

→ 7.

Modulo-2 arithmeticNo carries/borrows: add = subtract = XOR.

1011 + 0110 = 1101

. Divide: XOR the key under each leading 1.

Polynomial keyLeftmost bit = highest power. 1101 =

x^3 + x^2 + 1

. Key of

n+1

bits (degree

n

) → CRC of

n

bits.

Sender1. Append

n

zeros. 2. Mod-2 divide by key. 3. Remainder (

n

bits) replaces the zeros. 1111101, key 1101 → remainder 111 → 1111101111.

ReceiverDivide the whole codeword by the key (no zeros appended). Remainder 0 → accept; non-zero → reject, request retransmission.

Why it works

T(x) = M(x)x^n + R(x)

is a multiple of

G(x)

. Received remainder = remainder of the error

E(x)

; missed only if

E(x)

is a multiple of

G(x)

DetectsAll single-bit errors; all bursts of length

\le n

; all odd-count errors if

(x+1)

divides the key; fraction

1 - 2^{-n}

of long random errors.

Standard keysCRC-12:

x^{12}+x^{11}+x^3+x^2+x+1

. CRC-16:

x^{16}+x^{15}+x^2+1

(USB). CRC-16-CCITT:

x^{16}+x^{12}+x^5+1

(XMODEM, X.25, Bluetooth, PPP). CRC-32: Ethernet, MPEG-2.

3.4 Hamming Codes: Rules

Code word

n = m + r

(data bits + check bits).

Hamming distanceNumber of differing positions = number of 1s in the XOR.

D(\min)

= smallest distance over all pairs of legal words.

Detect / correctDetect

k

errors:

D(\min) = k + 1

. Correct

k

D(\min) = 2k + 1

. So detect

D(\min)-1

, correct

\lfloor (D(\min)-1)/2 \rfloor

Check-bit bound

(m + r + 1) \le 2^r

, smallest

r

. m = 4 → 3 (n 7); 8 → 4 (12); 10 → 4 (14); 16 → 5 (21); 32 → 6 (38); 64 → 7 (71).

LayoutPositions 1..n numbered from the right; check bits at 1, 2, 4, 8, …; data fills the other positions from the highest down, leftmost data bit first.

Generate (even parity)Each check bit

c

= XOR of the data bits whose position number has the

c

bit set. Key

K

= P8 P4 P2 P1. 11010110 → K = 1101, code 110110111001.

Syndrome

K \oplus K'

(stored key XOR recomputed key), read P8 P4 P2 P1. 0 = no error; power of 2 = that check bit is wrong; otherwise = position of the wrong data bit, flip it.

Limits

D(\min) = 3

corrects only 1 error; a 2-bit error gives a misleading syndrome. SEC-DED adds an overall parity bit. Reed-Solomon handles burst errors (CDs).

3.4 Coverage Table (12-bit code, m = 8)

Check bit	Binary	Covers positions	Contents layout (12 → 1)
P1	0001	1, 3, 5, 7, 9, 11	d d d d P8 d d d P4 d P2 P1
P2	0010	2, 3, 6, 7, 10, 11	data positions: 12, 11, 10, 9, 7, 6, 5, 3
P4	0100	4, 5, 6, 7, 12	position 11 = 8 + 2 + 1 → checked by P8, P2, P1
P8	1000	8, 9, 10, 11, 12	7-bit (m = 4): data at 7, 6, 5, 3; P4 covers 5, 6, 7

4.1 Boolean Operators & Logic Gates

Gate	Expression	Output is 1 when…	Symbol
AND	$xy$ (Boolean product)	all inputs are 1	D shape: flat back, round front
OR	$x + y$ (Boolean sum)	at least one input is 1 ( $1 + 1 = 1$ )	shield/arrowhead: concave back, pointed front
NOT	$x'$ (same as $\overline{x}$ )	input is 0	triangle with bubble at the tip
XOR	$x \oplus y = xy' + x'y$	inputs differ; multi-input: odd number of 1s (parity)	OR shape with extra curved input line
NAND	$(xy)'$	NOT all inputs are 1 (0 only when all are 1)	AND + output bubble
NOR	$(x + y)'$	all inputs are 0	OR + output bubble

4.1 Truth Tables, Universal Gates, CMOS & SSI

Truth table size

n

inputs →

2^n

rows, listed in binary counting order. Number of distinct functions of

n

variables

= 2^{2^n}

(16 for

n = 2

, 256 for

n = 3

PrecedenceNOT, then AND, then OR.

xz' + y = (x \cdot z') + y

NAND-onlyNOT

x

= NAND(

x, x

). AND = NAND then NAND-inverter. OR = NAND(

x', y'

)

= (x'y')' = x + y

NOR-onlyNOT

x

= NOR(

x, x

). OR = NOR then NOR-inverter. AND = NOR(

x', y'

)

= (x' + y')' = xy

Why universalAny function can be built from NAND only or NOR only; cheap to mass-produce; faster and lower power than other gate configurations.

SOP → NAND-NAND

xy + z = ((xy)' \cdot z')'

: NAND(

x,y

), NAND(

z,z

), NAND of the two → 3 NAND gates.

Not associativeNAND(NAND(

x,y

z

)

= xy + z'

, not

(xyz)' = x' + y' + z'

CMOSpMOS conducts on 0 (pulls output up to +5 V); nMOS conducts on 1 (pulls down to ground). NOT = 2 transistors; NOR = 2 pMOS in series + 2 nMOS in parallel (4); AND = NAND + inverter (6).

7400 chipSSI, 14 pins: power + ground + 12 pins = 4 two-input NAND gates × 3 pins. Chips needed

= \lceil \text{gates}/4 \rceil

; gate types cannot share a chip.

Parity with XOREven-parity bit

P = x \oplus y \oplus z \oplus \cdots

(makes total number of 1s even); odd parity uses

P'

4.2 Boolean Identities

Law	AND form	OR form
Identity	$1x = x$	$0 + x = x$
Null (dominance)	$0x = 0$	$1 + x = 1$
Idempotent	$xx = x$	$x + x = x$
Inverse	$xx' = 0$	$x + x' = 1$
Commutative	$xy = yx$	$x + y = y + x$
Associative	$(xy)z = x(yz)$	$(x + y) + z = x + (y + z)$
Distributive	$x + yz = (x + y)(x + z)$	$x(y + z) = xy + xz$
Absorption	$x(x + y) = x$	$x + xy = x$
DeMorgan	$(xy)' = x' + y'$	$(x + y)' = x'y'$
Double complement	$(x')' = x$

4.2 DeMorgan, Patterns & Canonical Forms

Complement of a whole function1. Complement every variable. 2. Swap AND ↔ OR. 3. Keep each old product grouped in parentheses.

(xy + x'z + yz')' = (x' + y')(x + z')(y' + z)

Patterns

xy + xy' = x

;

(x + y)(x + y') = x

;

x + x'y = x + y

;

x(x' + y) = xy

Consensus

xy + x'z + yz = xy + x'z

(multiply

yz

x + x'

, then absorb).

Canonical SOPFor each row with

F = 1

write a minterm (variable if 1, complement if 0) and OR them:

F = \Sigma m(\ldots)

Canonical POSFor each row with

F = 0

write a maxterm (variable if 0, complement if 1) and AND them:

F = \Pi M(\ldots)

. E.g. row 101 →

x' + y + z'

Σm ↔ ΠMThe ΠM list is exactly the rows missing from the Σm list:

\Sigma m(0,2,4,5,6) = \Pi M(1,3,7)

Full adderSum

= x \oplus y \oplus z = \Sigma m(1,2,4,7)

;

C_{out} = xy + z(x \oplus y) = \Sigma m(3,5,6,7)

Proving an equalityEither compare truth-table columns in every row, or transform one side with identities, naming the law at each step.

4.3 Karnaugh Map Layout & Rules

Gray orderColumns (and 4-var rows) are labelled 00, 01, 11, 10, so adjacent cells differ in one variable. Cell order: m0 m1 m3 m2 / m4 m5 m7 m6.

4-var map rows

wx

= 00: m0 m1 m3 m2; 01: m4 m5 m7 m6; 11: m12 m13 m15 m14; 10: m8 m9 m11 m10.

Grouping rules1. Only 1s (and d's). 2. Rectangles only, no diagonals. 3. Size a power of 2. 4. As large as possible. 5. Overlap and wrap-around allowed (left↔right, top↔bottom; four corners form a group). Cover every 1 with as few groups as possible.

Reading a groupKeep only variables that are constant over the group (1 →

x

, 0 →

x'

); variables that change drop out.

Group size → literals3-var map: 1→3, 2→2, 4→1, 8→

F = 1

. 4-var map: 1→4, 2→3, 4→2, 8→1, 16→

F = 1

Don't cares (d / X)Input combinations that never occur. Treat d as 1 only if it makes a bigger group; never needs to be covered.

Procedure1. Draw Gray-labelled map. 2. Enter 1s and d's. 3. Circle largest groups, starting with 1s that can be covered only one way. 4. Add groups until all 1s covered. 5. OR the group terms.

Classic results

\Sigma m(1,3,5,7) = z

;

\Sigma m(0,2,4,6) = z'

; corners

\Sigma m(0,2,8,10) = x'z'

;

\Sigma m(0,2,5,7,8,10,13,15) = x'z' + xz

4.4 Adders, Decoder, MUX

Circuit	Inputs → outputs	Equations / key facts
Half adder	$x, y$ → Sum, Carry	Sum $= x \oplus y$ , Carry $= xy$ (1 XOR + 1 AND)
Full adder	$x, y, C_{in}$ → Sum, $C_{out}$	Sum $= x \oplus y \oplus C_{in}$ ; $C_{out} = xy + C_{in}(x \oplus y)$ ; = 2 half adders + 1 OR (2 XOR, 2 AND, 1 OR)
Ripple-carry adder	$n$ full adders	Each $C_{out}$ feeds the next $C_{in}$ ; bit 0 has $C_{in} = 0$ . Simple but slow: carry ripples through all stages. Final carry 1 = unsigned overflow.
Decoder	$n$ → $2^n$	Exactly one output active (the one numbered by the input); each output is a minterm. Used for memory address decoding. Inputs $= \log_2(\text{outputs})$ .
Multiplexer	$2^s$ data + $s$ select → 1	Select value chooses the input passed to the output. Select lines $= \log_2(\text{inputs})$ . 4-to-1: $S_1'S_0'I_0 + S_1'S_0I_1 + S_1S_0'I_2 + S_1S_0I_3$ .
Decoder + OR	any function	OR the decoder outputs of the function's minterms, e.g. full adder: Sum $= D_1 + D_2 + D_4 + D_7$ , $C_{out} = D_3 + D_5 + D_6 + D_7$ .

4.4 Simple 2-bit ALU & Circuit Building

ALU operations (

f_1f_0

)00 ADD, 01 OR, 10 NOT

A

, 11 AND. Result

C_1C_0

+ overflow (carry out of bit 1).

ALU structure2-to-4 decoder on

f_1f_0

gives one enable line; per bit an AND, OR, NOT unit; half adder (bit 0) + full adder (bit 1); each result ANDed with its enable, then ORed per bit.

AND-OR circuit from SOP1 inverter per complemented variable, 1 AND per product term (single literal needs none), 1 OR combining them. Simplify first to save gates.

Address decodingHigh address bits → decoder selects the chip; low bits select the word in the chip. 8 chips → 3-to-8 decoder.

CombinationalOutput depends only on current inputs; no memory, no feedback.

4.5 Flip-Flop Characteristic Tables

Flip-flop	Inputs → $Q(t+1)$	Characteristic equation	Built from
SR	00 hold, 01 reset (0), 10 set (1), 11 undefined	$Q^+ = S + R'Q$ (with $SR = 0$ )	2 cross-coupled NOR gates: $Q' = (S + Q)'$ , $Q = (R + Q')'$
JK	00 hold, 01 reset, 10 set, 11 toggle ( $Q'$ )	$Q^+ = JQ' + K'Q$	SR with $S = JQ'$ , $R = KQ$ (never both 1)
D	$Q^+ = D$	$Q^+ = D$	SR with $S = D$ , $R = D'$ ; basic 1-bit memory cell
T	0 hold, 1 toggle	$Q^+ = T \oplus Q$	JK with $J = K = T$

4.5 Clocks, Counters & Circuit Analysis

Sequential vs combinationalSequential output depends on inputs and current state; memory comes from feedback; state changes only on clock ticks.

ClockPeriod = 1/frequency (800 MHz → 1.25 ns). Edge-triggered: changes at rising or falling edge. Level-triggered: changes while the clock is high.

n

D flip-flops with a shared clock; all bits loaded at once on the edge, held between edges.

4-bit JK counter

J = K

B_0

= Count Enable;

B_1

= CE·

B_0

;

B_2

= CE·

B_0B_1

;

B_3

= CE·

B_0B_1B_2

. A bit toggles when all lower bits are 1. Output Carry = CE·

B_0B_1B_2B_3

JK excitation0→0:

J = 0, K = d

. 0→1:

J = 1, K = d

. 1→0:

J = d, K = 1

. 1→1:

J = d, K = 0

Analysis procedure1. Identify state variables and inputs. 2. Write input equations (

J_A

K_A

D_B

…). 3. One row per state+input combination. 4. Evaluate equations with present values. 5. Apply characteristic tables.

Simultaneous updateAll flip-flops share the clock: every input equation uses present state values, never the value another flip-flop is changing to.

MN flip-flop example

M = 1

complement,

M = 0

load

N

Q^+ = M'N + MQ'

; from JK:

J = M + N

K = M + N'

6.1 CPU Basics, Buses & Clocks

Four componentsCPU (control unit + ALU + registers), main memory (stored program: code and data), I/O subsystem, buses.

Datapath vs control unitDatapath = ALU + registers + bus wiring (the muscle). Control unit = decides which datapath actions happen and when, using the instruction, PC and status register (flags).

Q(t+1) = D

). MARIE total: 16+12+16+12+16+8+8 = 88 flip-flops.

Bus line groupsData lines: the value (both ways). Address lines: where (CPU → memory/device). Control lines: what/when (read/write, clock, arbitration, interrupts).

Point-to-point vs multipointPoint-to-point links exactly 2 devices, no arbitration, n devices need

n(n-1)/2

links. Multipoint (shared) bus: one set of wires, cheap, but needs hardware protocols (bus arbitration) and can be a bottleneck. MARIE uses one common bus.

Clock

t = 1/f

. Shortcut:

t\,[\text{ns}] = 1000 / f\,[\text{MHz}]

. 800 MHz → 1.25 ns; 2.5 GHz → 0.4 ns; 0.5 ns → 2 GHz.

Execution timeinstructions × cycles per instruction × cycle time. A faster clock alone does not guarantee a faster program.

Bus bandwidth(data lines / 8) bytes × transfers per second. 32 lines at 100 MHz → 4 B ×

10^8

= 400 MB/s.

I/O interfacesRS-232 serial ≈ 115.2 kbit/s; USB(-C) up to ≈ 10 Gbit/s; RJ-45 Ethernet 100 Mbit/s – 10 Gbit/s; Wi-Fi hundreds of Mbit/s+. MARIE I/O = 8-bit InREG and OutREG.

6.1 Memory Organization & Chips

Length × width(number of addressable locations) × (bits per location). Length → address lines; width → data lines.

Address lines

\lceil \log_2 N \rceil

for N addressable units. 4M × 16 word-addr:

2^{22}

→ 22. Same, byte-addr:

2^{22} \times 2 = 2^{23}

→ 23. MARIE 4K words → 12.

Prefixes1K =

2^{10}

, 1M =

2^{20}

, 1G =

2^{30}

; 4K =

2^{12}

, 64K =

2^{16}

, 256K =

2^{18}

, 2M =

2^{21}

Building L × W from l × w chips1. Chips per row = W / w.
2. Rows = L / l.
3. Total = (L/l)(W/w).
4.

\log_2 l

address bits go to every chip;

\log_2(L/l)

high-order bits feed a decoder (chip select).

MARIE 4K × 16 from 1K × 84 rows × 2 chips = 8 chips. 12 address bits: A11 A10 → 2-to-4 decoder; A9–A0 to every chip. Rows: 000–3FF, 400–7FF, 800–BFF, C00–FFF.

InterleavingHigh-order: chip select from the leftmost bits, consecutive addresses stay in one row. Low-order: chip select from the low bits, consecutive addresses spread across rows (parallel access).

6.2 MARIE Architecture & Registers

Register	Bits	Holds	Bus no.
Memory	4K × 16	program + data, word-addressable 000–FFF	0 (000)
MAR	12	address being accessed	1 (001)
PC	12	address of next instruction	2 (010)
MBR	16	data to/from memory	3 (011)
AC	16	operand / result (two's complement, −32768..32767)	4 (100)
InREG	8	data from input device	5 (101)
OutREG	8	data for output device	6 (110)
IR	16	instruction being executed	7 (111)

6.2 MARIE Instruction Set (opcode + 12-bit address)

Hex	Binary	Instruction	RTN
0	0000	JnS X	MBR ← PC; MAR ← X; M[MAR] ← MBR; MBR ← X; AC ← 1; AC ← AC + MBR; PC ← AC
1	0001	Load X	MAR ← X; MBR ← M[MAR]; AC ← MBR
2	0010	Store X	MAR ← X, MBR ← AC; M[MAR] ← MBR
3	0011	Add X	MAR ← X; MBR ← M[MAR]; AC ← AC + MBR
4	0100	Subt X	MAR ← X; MBR ← M[MAR]; AC ← AC − MBR
5	0101	Input	AC ← InREG
6	0110	Output	OutREG ← AC
7	0111	Halt	(stop)
8	1000	Skipcond	IR[11–10]: 00 → skip if AC < 0 (8000); 01 → AC = 0 (8400); 10 → AC > 0 (8800)
9	1001	Jump X	PC ← IR[11–0]
A	1010	Clear	AC ← 0
B	1011	AddI X	MAR ← X; MBR ← M[MAR]; MAR ← MBR; MBR ← M[MAR]; AC ← AC + MBR
C	1100	JumpI X	MAR ← X; MBR ← M[MAR]; PC ← MBR
D	1101	LoadI X	MAR ← X; MBR ← M[MAR]; MAR ← MBR; MBR ← M[MAR]; AC ← MBR
E	1110	StoreI X	MAR ← X; MBR ← M[MAR]; MAR ← MBR; MBR ← AC; M[MAR] ← MBR

6.2 Encoding, Skipcond & Indirection

Encodeopcode hex digit + 3-digit address. Store 1A3 → 21A3; AddI 20F → B20F; Halt → 7000; Clear → A000; Input → 5000; Output → 6000.

DecodeSplit 16 bits into 4 + 12: 0100 0000 1111 1111 → 40FF → Subt 0FF. 0000 0011 0000 0000 → 0300 → JnS 300.

SkipcondSkips next instruction (one extra PC ← PC + 1). AC is read as 16-bit two's complement: FFFB = −5, 8000 = −32768. 0 is not > 0.

Indirect resultsLoadI X: AC ← M[M[X]]; AddI X: AC ← AC + M[M[X]]; StoreI X: M[M[X]] ← AC; JumpI X: PC ← M[X]. One extra memory read vs direct.

JnS XM[X] ← return address (PC, already incremented); PC ← X + 1; AC is overwritten with X + 1. Return with JumpI X.

Format limits4 opcode bits → 16 opcodes, 15 used (0–E), F free. 12 address bits → 4K words reachable directly.

6.3 Fetch–Decode–Execute

Fetch1. MAR ← PC
2. IR ← M[MAR]
3. PC ← PC + 1

DecodeMAR ← IR[11–0]; decode opcode IR[15–12].

Get operandMBR ← M[MAR], only if the instruction reads memory (Load, Add, Subt, AddI, LoadI, JumpI, StoreI pointer). Not for Store, Halt, Jump, Clear, Input, Output, Skipcond.

ExecuteOpcode-specific RTN, then back to fetch. Real CPUs check for interrupts after execute (save PC, run ISR, restore).

PC during executeAlready holds the address of the next instruction (incremented during fetch).

Trace table rulesOne row per microoperation; write values after the step; only the register left of ← changes; copy others down.

Memory accessesEach instruction: 1 fetch read. Load/Add/Subt +1 read; Store +1 write; LoadI/AddI +2 reads; StoreI +1 read +1 write; JumpI +1 read.

Addition program100: 1104 Load 104; 101: 3105 Add 105; 102: 2106 Store 106; 103: 7000 Halt; 104: 0023; 105: FFE9 → M[106] = 000C (35 − 23 = 12).

6.4 Assembly Language & Two-Pass Assembler

Line formatLabel, Mnemonic Operand / comment. Label (with comma) = address of that line.

DirectivesORG n start at hex n; DEC n decimal word; HEX n hex word; END. Directives produce no CPU instruction; DEC/HEX take one word each.

Pass 1LC starts at ORG. For each line: record label → LC in symbol table, translate opcode (address left blank), LC + 1.

Pass 2Replace label operands with symbol-table addresses, convert DEC/HEX constants to 16-bit hex, output each word.

Why two passesForward references: a label can be used before it is defined.

Negative DECTwo's complement: DEC −23 → 0017 → invert FFE8 → +1 → FFE9. DEC −12 → FFF4. DEC −40 → FFD8.

Data placementPut data after Halt: the CPU cannot tell data from code (0023 would execute as JnS 023).

6.4 Control-Structure Templates

Condition	AC holds	Skipcond to enter body	Pattern
X > Y	X − Y	Skipcond 800 (8800)	Load X / Subt Y / Skipcond 800 / Jump Else / THEN...
X < Y	X − Y	Skipcond 000 (8000)	While: Load X / Subt Y / Skipcond 000 / Jump EndW / body / Jump While
X = Y	X − Y	Skipcond 400 (8400)	Skip the Jump that bypasses the body
X > 1	X − 1	Skipcond 800	Load X / Subt One / Skipcond 800 / Jump EndIf
Count N > 0	N	Skipcond 800	Loop: Load N / Skipcond 800 / Jump Done / body / N ← N − 1 / Jump Loop
X ≥ Y	X − Y	test X < Y (Skipcond 000)	swap THEN and ELSE parts
Subroutine	—	—	JnS Sub / ... / Sub, HEX 0000 / body / JumpI Sub

7.1 Control Signals & Execute-Phase Signal Lists

Instr.	T3	T4	T5
Signals	$P_2P_1P_0$ = source read onto bus; $P_5P_4P_3$ = destination (memory 0, MAR 1, PC 2, MBR 3, AC 4, InREG 5, OutREG 6, IR 7)	$A_1A_0$ : 00 none, 01 add, 10 subtract, 11 clear; $L_{ALT}$ = AC loads from ALU (also $P_5$ )	$M_R$ memory source, $M_W$ memory dest; $T_n$ timing (exactly one high); $C_r$ reset counter on last step
Recipe	Fetch/decode = $T_0$ – $T_2$ ; execute from $T_3$ , one microop per cycle (single bus: one transfer per cycle)	List only the bits that are 1	Timing diagram: each signal high exactly in the cycles whose list contains it
Load X	P3 P2 P1 P0 T3 (MAR ← X)	P4 P3 T4 MR (MBR ← M[MAR])	P5 P1 P0 T5 Cr (AC ← MBR)
Add X	P3 P2 P1 P0 T3	P4 P3 T4 MR	Cr A0 P5 T5 LALT (AC ← AC + MBR)
Subt X	P3 P2 P1 P0 T3	P4 P3 T4 MR	Cr A1 P5 T5 LALT (AC ← AC − MBR)
Store X	P3 P2 P1 P0 T3	P4 P3 P2 T4 (MBR ← AC)	P1 P0 T5 MW Cr (M[MAR] ← MBR)
JumpI X	P3 P2 P1 P0 T3	P4 P3 T4 MR	P4 P1 P0 T5 Cr (PC ← MBR)
Jump X	P4 P2 P1 P0 T3 Cr (PC ← IR[11–0])
Input	P5 P2 P0 T3 Cr (AC ← InREG)
Output	P5 P4 P2 T3 Cr (OutREG ← AC)
Clear	A1 A0 P5 T3 LALT Cr (AC ← 0)

7.1 Hardwired vs Microprogrammed Control

	Hardwired	Microprogrammed
Built from	instruction decoder (AND of opcode bits) + ring counter ( $T_n$ ) + AND/OR logic	microprogram (firmware) in a control store ROM
Signal equation	OR of (instruction · $T_n$ ), e.g. Add = $IR_{15}'IR_{14}'IR_{13}IR_{12}$ ; $M_R = (\text{Load}+\text{Add})T_4$	one microinstruction fetched per clock, decoded into signals
Speed	fast	slower (extra fetch/decode level, jump-table lookups)
Change ISA / fix bug	redesign circuit	rewrite microprogram
Complex instructions	logic grows large	just a longer microroutine
Typical	RISC	CISC
RISC vs CISC	few, fixed-length instructions; easy pipelining; short opcode (15 instr → 4 bits, 12 address bits)	many instructions; denser code; 509 instr → 9 opcode bits, only 7 address bits in 16-bit word

7.1 Microinstruction Format & Microop Codes (Table 4.9)

Code	Microoperation	Code	Microoperation
00000	NOP	01101	MBR ← M[MAR]
00001	AC ← 0	01110	OutREG ← AC
00010	AC ← MBR	01111	PC ← IR[11–0]
00011	AC ← AC − MBR	10000	PC ← MBR
00100	AC ← AC + MBR	10001	PC ← PC + 1
00101	AC ← InREG	10010	If AC = 00
00110	IR ← M[MAR]	10011	If AC > 0
00111	M[MAR] ← MBR	10100	If AC < 0
01000	MAR ← IR[11–0]	10101	If IR[11–10] = 00
01001	MAR ← MBR	10110	If IR[11–10] = 01
01010	MAR ← PC	10111	If IR[11–10] = 10
01011	MAR ← X	11000	If IR[15–12] = MicroOp2[4–1]
01100	MBR ← AC
Format	18 bits = MicroOp1 (5) \| MicroOp2 (5) \| Jump (1) \| Dest (7)	Store	`01011 01100 0 0000000` / `00111 00000 1 0000000`
Fetch lines 0–3	01010, 00110, 10001, 01000 (each with NOP, Jump 0)	Jump table	JnS → 32 (0100000), Load → 39, Store → 42, Add → 44, Subt → 47; routine ends Jump = 1, Dest = 0000000
Control store	128 lines × 18 bits = 2304 bits; Dest 7 bits since $2^7 = 128$	Add	`01011 00000 0` / `01101 00000 0` / `00100 00000 1 0000000`