7.1.1 7.1.1 — Master Rule Sheet (all rule cards merged)

Every Rule Card from the 32 lessons, grouped by phase, in course order. Use it for revision in the last weeks: read one phase per sitting, and for any line you cannot explain in your own words, open its lesson (the lesson ID links to it).

📝

How to revise with this sheet

Cover the rules of a lesson with your hand; say them from its title alone.
Check, and mark the lesson's ID on paper if you missed anything.
Next day, re-test only the marked IDs (spaced recall).

🔢 Phase 0 · Number Systems from Zero

0.1.1 What "digital" means: bits, binary numbers and place value

Binary places are powers of 2: 1, 2, 4, 8, 16, …; value = sum of the places holding 1.
Decimal → binary: divide by 2 repeatedly, read remainders bottom-up.
n bits: 2ⁿ patterns; unsigned range 0 … 2ⁿ − 1; N needs ⌈log₂(N + 1)⌉ bits.
LSB rightmost, MSB leftmost; nibble 4 bits, byte 8 bits.

0.1.2 Octal, hexadecimal and converting between any two bases

Base r: digits 0 … r − 1; value = Σ digit × r^position (negative positions after the point).
Decimal → base r: integer part by repeated division (read up), fraction by repeated multiplication (read down).
Octal = groups of 3 bits, hex = groups of 4, grouped from the point; octal ↔ hex via binary.
p/q terminates in base r only if q's prime factors divide r (binary: q a power of 2).
Find-the-base: write polynomials in b, solve, keep b > every digit.

0.1.3 Binary arithmetic by hand; how many values n bits can hold

Binary column addition: carry when a column reaches 2; subtraction borrows 2.
Multiplication: shift and add copies of the multiplicand.
Left shift k = × 2ᵏ; right shift k = ÷ 2ᵏ (remainder dropped).
Sum of two n-bit numbers needs up to n + 1 bits (carry out); product of n-bit and m-bit needs up to n + m bits.

➕ Phase 1 · Signed Numbers & Binary Arithmetic

1.1.1 Sign-magnitude, 1's complement and 2's complement

Positive numbers: same in SM, 1's and 2's complement (MSB 0).
SM: flip the sign bit. 1's: invert all bits. 2's: invert all and add 1 (or copy up to the first 1 from the right, invert the rest).
2's complement value: MSB worth −2ⁿ⁻¹; range −2ⁿ⁻¹ … 2ⁿ⁻¹ − 1; one zero.
SM and 1's complement: range ±(2ⁿ⁻¹ − 1), two zeros.

1.1.2 2's-complement arithmetic: addition, subtraction, overflow, sign extension

2's-complement add: add the patterns, discard the carry out.
A − B = A + B' + 1.
Overflow: same-sign operands give an opposite-sign result; equivalently carry into MSB ⊕ carry out of MSB = 1. Mixed signs never overflow.
Sign extension: copy the MSB. 1's complement addition needs an end-around carry.

1.1.3 Shifts, multiplication and Booth's algorithm

Logical shifts insert 0; arithmetic right shift copies the MSB (÷2, rounding towards −∞).
Signed n × n product needs 2n bits.
Booth pairs (qᵢ, qᵢ₋₁), q₋₁ = 0: 10 → −M, 01 → +M, 00/11 → nothing; then arithmetic shift right of A, Q, Q₋₁.
Booth operations = number of 01 and 10 pairs; worst case alternating bits.

1.2.1 Binary codes: BCD, excess-3, Gray code and parity

BCD: 4 bits per decimal digit; 1010–1111 invalid; digit sum > 9 or carry → add 0110.
Excess-3: digit + 3; self-complementing.
Gray: g = b ⊕ (b >> 1); back: bᵢ = bᵢ₊₁ ⊕ gᵢ (running XOR from the MSB). Neighbours differ in one bit.
Even parity makes the count of 1s even; detects odd numbers of flipped bits.

🧮 Phase 2 · Fixed & Floating Point

2.1.1 Fixed-point binary fractions: range, precision and rounding

i.f fixed point: value = integer ÷ 2ᶠ; step 2⁻ᶠ (same everywhere).
Unsigned range 0 … 2ⁱ − 2⁻ᶠ; signed 2's complement −2ⁱ⁻¹ … 2ⁱ⁻¹ − 2⁻ᶠ.
Real → fixed: × 2ᶠ, round/truncate, write in n bits. Negatives: 2's complement of all n bits.
Truncation error < 2⁻ᶠ; rounding error ≤ 2⁻ᶠ⁻¹.

2.1.2 Floating point and IEEE 754: sign, biased exponent, mantissa

Normalised value: (−1)ˢ × 1.F × 2^(E − bias).
Single: 1 + 8 + 23 bits, bias 127. Double: 1 + 11 + 52 bits, bias 1023.
Encode: sign → binary → normalise 1.f × 2ᵉ → E = e + bias → F = bits after the point → hex in groups of 4.
Decode: split S | E | F, e = E − bias, value = ±1.F × 2ᵉ.

2.1.3 IEEE 754 special values, denormals, range, precision and gaps

E = 0, F = 0: ±0. E = 0, F ≠ 0: denormal (−1)ˢ × 0.F × 2^(1 − bias). E = all 1s: ±∞ (F = 0) or NaN.
Single: max ≈ 3.4 × 10³⁸ ((2 − 2⁻²³) × 2¹²⁷), min normal 2⁻¹²⁶, min denormal 2⁻¹⁴⁹.
Precision: 24 bits (single), 53 (double). Gap in [2ᵉ, 2ᵉ⁺¹) = 2^(e − 23); integers exact up to 2²⁴.
Float addition aligns exponents; not associative. Bias for k exponent bits = 2ᵏ⁻¹ − 1.

🔣 Phase 3 · Boolean Algebra & Logic Gates

3.1.1 Logic gates and truth tables

AND: 1 iff all 1. OR: 1 iff any 1. NOT inverts. NAND = (AND)', NOR = (OR)'.
XOR: 1 iff an odd number of inputs are 1; XNOR is its NOT.
n variables → 2ⁿ truth-table rows, numbered by the input bits (first variable = MSB).
Precedence: NOT, then AND, then OR.

3.1.2 Boolean algebra: laws, duality, De Morgan and algebraic simplification

Identity, null, idempotent, complement, involution, commutative, associative.
Distributive both ways: A(B + C) = AB + AC and A + BC = (A + B)(A + C).
Absorption A + AB = A; redundant literal A + A'B = A + B; consensus AB + A'C + BC = AB + A'C.
De Morgan (A + B)' = A'B', (AB)' = A' + B'. Complement: swap operators and complement literals.
Dual: swap + ↔ · and 0 ↔ 1 only. XOR: A ⊕ B = A'B + AB'.

3.2.1 Canonical forms: minterms, maxterms, SOP and POS

Minterm mᵢ: AND of all variables, plain where row i has 1. Maxterm Mᵢ: OR of all variables, primed where row i has 1. Mᵢ = mᵢ'.
F = Σm(1-rows) = ΠM(0-rows); F' = Σm(0-rows).
Expand a term by multiplying with (X + X') for each missing variable; k of n variables → 2ⁿ⁻ᵏ minterms.
SOP = OR of AND terms; POS = AND of OR terms; canonical = every term has all variables.

3.2.2 NAND and NOR as universal gates; functionally complete sets

NAND: NOT = 1, AND = 2, OR = 3, XOR = 4, XNOR = 5 gates. NOR: NOT 1, OR 2, AND 3, XNOR 4, XOR 5.
SOP → NAND–NAND; POS → NOR–NOR.
Post: complete ⟺ some gate is not 0-preserving, some not 1-preserving, some not self-dual, some not monotone, some not linear.
Complete: {NAND}, {NOR}, {AND, NOT}, {OR, NOT}, {XOR, AND, 1}, {→, 0}. Not: {AND, OR}, {XOR, AND}, {→}, {majority, NOT}.

3.2.3 Counting Boolean functions; self-dual functions; XOR tricks

n variables: 2ⁿ rows, 2^(2ⁿ) functions.
Exactly k minterms: C(2ⁿ, k). Neutral: C(2ⁿ, 2ⁿ⁻¹). F(0…0) fixed: 2^(2ⁿ − 1).
Self-dual: 2^(2ⁿ⁻¹) (complementary rows have opposite outputs; exactly 2ⁿ⁻¹ minterms). Symmetric: 2ⁿ⁺¹.
XOR chain = 1 iff odd number of 1s; XNOR chain = XOR chain for odd n, its complement for even n.

🗺️ Phase 4 · Minimization

4.1.1 Karnaugh maps for 2, 3 and 4 variables: adjacency and grouping

K-map rows and columns in Gray order (00, 01, 11, 10); adjacent cells differ in one variable; edges and corners wrap.
Groups: rectangles of 2ᵏ cells containing only 1s; a 2ᵏ group drops k variables.
Term of a group: the variables that stay constant (1 → plain, 0 → primed).
Minimise: largest possible groups, fewest groups, every 1 covered; overlaps allowed.

4.1.2 Prime implicants, essential prime implicants, minimal SOP and POS

Implicant ⊂ prime implicant (maximal group) ⊂ essential PI (sole cover of some 1).
Minimal SOP: all EPIs + fewest extra PIs for the remaining 1s; only PIs are used.
Redundant PIs (like a centre square fully covered by EPIs) are left out. Cyclic functions have no EPIs and several minimal answers.
POS: group 0s; clause literal plain if the variable is 0 in the group, primed if 1.

4.1.3 Don't-care conditions and 5-variable maps

Don't-cares (d or X): may be used as 1s to enlarge groups; need not be covered; never group only Xs.
PIs computed with Xs as 1s; essentiality judged on the real 1s.
5-variable map: two 4-variable maps (A = 0, A = 1); same position in both halves is adjacent; a group in both halves drops A.

4.2.1 The Quine–McCluskey tabular method

Group minterms (and don't-cares) by number of 1s.
Merge pairs differing in exactly one bit (dashes aligned); tick merged terms; repeat.
Unticked terms = prime implicants.
Chart (minterms only): single-X columns → EPIs; then cover the rest with the fewest PIs (Petrick if needed).

🧩 Phase 5 · Combinational Circuits

5.1.1 Combinational circuits: analysis, design and propagation delay

Combinational: outputs depend only on current inputs; sequential circuits remember.
Design: specification → truth table → K-map → gates (AND–OR or NAND–NAND).
Circuit delay = largest sum of gate delays along any input-to-output path (critical path).
Static-1 hazard between adjacent 1s in different groups; fix with the consensus term.

5.1.2 Half adder, full adder and the ripple-carry adder

Half adder: S = A ⊕ B, C = AB.
Full adder: S = A ⊕ B ⊕ Cᵢₙ; Cₒᵤₜ = AB + BCᵢₙ + ACᵢₙ = AB + Cᵢₙ(A ⊕ B); = 2 half adders + OR.
n-bit RCA: Cₙ at n·t_c; Sₙ₋₁ at (n − 1)·t_c + t_s; delay linear in n.

5.1.3 Carry-lookahead adder, adder–subtractor and comparators

Gᵢ = AᵢBᵢ, Pᵢ = Aᵢ ⊕ Bᵢ, Cᵢ₊₁ = Gᵢ + PᵢCᵢ, Sᵢ = Pᵢ ⊕ Cᵢ.
Unrolled Cᵢ: i AND gates + one (i + 1)-input OR. CLA delay: 1 (P, G) + 2 (carries) + 1 (sums) = 4.
Rippled 4-bit CLA blocks: 2 gate delays per block for the carry.
Adder–subtractor: Bᵢ ⊕ M, C₀ = M. Equality: AND of XNORs; magnitude: decide at the highest differing bit.

5.2.1 Multiplexers, and implementing functions with them

2ⁿ:1 MUX: n selects; Y = Σ mₖ(S)·Iₖ. 2:1: Y = S'I₀ + SI₁.
Any n-variable function: 2ⁿ:1 MUX with the truth table on the inputs, or 2ⁿ⁻¹:1 MUX with inputs from {0, 1, x, x'}.
Reading a MUX: sum of select minterms times the inputs.
2ⁿ:1 MUX from 2:1 MUXes: 2ⁿ − 1 of them.

5.2.2 Decoders, encoders, priority encoders and demultiplexers

n-to-2ⁿ decoder: Yₖ = mₖ (with enable). Function = decoder + OR of its minterm outputs.
Decoder trees: 4-to-16 from five 2-to-4 decoders, or from two 3-to-8 with enables.
Encoder 2ⁿ-to-n assumes one active input. Priority encoder (4-input): Y₁ = D₃ + D₂, Y₀ = D₃ + D₂'D₁, V = OR of all.
Demultiplexer = decoder with the enable as data.

5.2.3 ROMs and PLAs: programmable logic

ROM: fixed AND (decoder), programmable OR; size 2ⁿ × m bits.
PLA: programmable AND and OR; count distinct product terms; share terms between outputs.
PAL: programmable AND, fixed OR (no sharing).

⏱️ Phase 6 · Sequential Circuits

6.1.1 Latches: the SR latch and the gated D latch

Latch = cross-coupled gates with feedback; stores one bit; level-sensitive.
NOR SR latch: S = 1 sets, R = 1 resets, 00 holds, 11 forbidden.
NAND S̄R̄ latch: 0 sets/resets (active-low), 11 holds, 00 forbidden.
Gated D latch: E = 1 → Q = D (transparent); E = 0 → hold.

6.1.2 Flip-flops: SR, D, JK and T; characteristic and excitation tables

Edge-triggered: inputs sampled only at the clock edge.
D: Q⁺ = D. T: Q⁺ = T ⊕ Q. JK: Q⁺ = JQ' + K'Q (11 toggles). SR: Q⁺ = S + R'Q, SR = 0.
Excitation (Q → Q⁺): D = Q⁺; T = Q ⊕ Q⁺; JK: 0→0 0x, 0→1 1x, 1→0 x1, 1→1 x0; SR: 0x, 10, 01, x0.
Race-around in level-triggered JK with J = K = 1; fixed by master–slave or edge triggering.

6.1.3 Converting flip-flops; timing and the maximum clock frequency

Conversion: X's characteristic table → Y's excitation → minimise. D from JK: J = D, K = D'; T from JK: J = K = T; T from D: D = T ⊕ Q; JK from D: D = JQ' + K'Q.
Setup before the edge, hold after, t_pd from edge to output.
T_min = t_pd + t_comb(max) + t_su (+ skew); f_max = 1/T_min. Hold: t_pd + t_comb(min) ≥ t_h.

6.2.1 Registers, shift registers, ring and Johnson counters

Register: n D flip-flops, common clock. Shift register: D = neighbour's Q; SISO, SIPO, PISO, PIPO; n clocks to load n bits serially.
Ring counter: feed back Q of the last stage; n states; must be initialised.
Johnson counter: feed back Q' of the last stage; 2n states; 2ⁿ − 2n unused.

6.2.2 Asynchronous (ripple) counters and mod-N counters

Ripple up counter: toggling flip-flops, each clocked by the previous output (negative edge); mod-2ⁿ; frequency halves per stage.
Settling n × t_pd; f_max = 1/(n·t_pd).
Mod-N: ⌈log₂ N⌉ flip-flops; asynchronous clear when the count reaches N (detect N's 1-bits); brief glitch state N.
Down counter: clock from Q' (or opposite edge).

6.2.3 Synchronous counters: analysis and design

Synchronous counter: one clock for all flip-flops. Up counter (T): T₀ = 1, Tᵢ = Qᵢ₋₁ ⋯ Q₀.
Analysis: input equations → next states → sequence; check unused states (self-starting vs lock-out).
Design: state table → excitation table → K-maps (unused = don't care) → circuit → check unused states.
With D flip-flops, Dᵢ = next Qᵢ.

6.2.4 Finite state machines: Mealy and Moore, sequence detectors, state minimisation

Moore: output = f(state). Mealy: output = f(state, input); usually fewer states.
k-bit sequence detector: k states (Mealy), k + 1 (Moore). Overlapping vs non-overlapping changes the arrows after a match.
s states → ⌈log₂ s⌉ flip-flops.
Minimise by partition: group by outputs, split by next-state groups, repeat.