CSC203 Problem-Solving Guide

1. Introduction

Lecture 1: units, clock speed, memory sizes, Moore’s and Rock’s laws, generations, the von Neumann model.

1.1 Units: the two kinds of “kilo”

Memory sizes use powers of 2. Speeds, frequencies and disk sizes use powers of 10. Cycle time $t = 1/f$, or the shortcut $t_{\text{ns}} = 1000 / f_{\text{MHz}}$ (1 GHz is 1 ns, 500 MHz is 2 ns, 2 GHz is 0.5 ns).

Worked example: a 3.9 GHz PC. 3.9 GHz CPU, 1600 MHz memory, 32 GB RAM, 128 KB L1, 2 MB L2, 1 TB disk at 7200 RPM, 1920 × 1200 screen with 24-bit colour.

• Do not use 1000 for memory or 1024 for clock speeds.
• Convert bits to bytes (divide by 8) for screen memory.
• Convert units (MHz to Hz, ns to s) before dividing.

1.2 Moore’s law and Rock’s law (doubling problems)

Both laws say something doubles every fixed period. Moore: transistors per chip double every 18 months (original 1965 version: every year; Moore later said 2 years). Rock: the cost of a chip factory doubles every 4 years.

$\text{New} = \text{Old} \times 2^{\,\text{time passed} / \text{doubling period}}$

Worked examples: Moore and Rock

Moore and Rock are linked: denser chips need ever more expensive factories, so at some point nobody can pay for the next factory and one of the two trends must stop.

• Check which doubling period the question gives (1 year, 18 months or 2 years).
• Do not mix years and months in the exponent.

1.3 Generations, organization vs architecture, von Neumann

Which generation? Look for the switching technology

Organization or architecture? Ask: “Can the programmer see it?” Yes: architecture (instruction set, addressing modes, data types, number of bits, whether there is a multiply instruction). No: organization (control signals, clock speed, RAM chip type, multiply done by circuit or by shift-and-add).

Von Neumann model: CPU (control unit + ALU + registers), one memory for program and data, I/O, and a single path between CPU and memory. That single path is the von Neumann bottleneck. A Harvard machine has separate instruction and data memories.

Worked example: the von Neumann bottleneck. The memory bus does one transfer every 10 ns. Each instruction needs 2 transfers (fetch the instruction, then read/write the operand).

Fetch-decode-execute order: fetch the instruction from the address in the PC, then PC + 1, decode the opcode, read the operand from memory, and the ALU executes.

• Clock speed and RAM type are organization, not architecture.
• The bottleneck limits instruction rate by bus speed, not CPU speed.

2. Numbers and Arithmetic

Lecture 2: base conversion, signed integers, complement arithmetic, overflow, multiplication, floating point.

2.1 Converting Between Bases

• Any base → decimal: digit × place value ($b^k$), then add.
• Decimal whole part → base $b$: divide by $b$ repeatedly; read remainders bottom to top.
• Decimal fraction → base $b$: multiply by $b$ repeatedly; read whole parts top to bottom.
• Binary ↔ hex: groups of 4 bits. Binary ↔ octal: groups of 3. Group outward from the point, pad with 0s.

Binary ↔ hex table and powers of 2: see Tables 6.4a–b.

Worked example: 147.8125 (decimal) → binary, hex, octal

Whole part (read up): 1001 0011. Fraction (read down): .1101.

• Binary: 10010011.1101₂
• Hex: 1001 0011 . 1101 = 93.D₁₆
• Octal: 010 010 011 . 110 100 = 223.64₈

Check: $128 + 16 + 2 + 1 = 147$ ✓ and $0.5 + 0.25 + 0.0625 = 0.8125$ ✓

Worked example: other bases and fractions that never end

• $2A3_{16}$ → decimal: $2 \cdot 256 + 10 \cdot 16 + 3 = 512 + 160 + 3 =$ 675
• $1011.101_2$ → decimal: $8 + 2 + 1 + 0.5 + 0.125 =$ 11.625
• $104$ → base 3: $104 \to 34$ r 2, $34 \to 11$ r 1, $11 \to 3$ r 2, $3 \to 1$ r 0, $1 \to 0$ r 1. Read up: 10212₃. Check: $81 + 0 + 18 + 3 + 2 = 104$ ✓
• $7A9.C_{16}$ → octal: 0111 1010 1001 . 1100, regroup in 3s from the point: 011 110 101 001 . 110 = 3651.6₈ (both equal 1961.75)
• $0.1$ → binary, 8 bits: $0.2 \to 0$, $0.4 \to 0$, $0.8 \to 0$, $1.6 \to 1$, $1.2 \to 1$, $0.4 \to 0$, $0.8 \to 0$, $1.6 \to 1$ → 0.00011001₂. It never ends (0.4, 0.8, 1.6, 1.2 repeat), so the stored value is only $25/256 = 0.09765625$.

Bits needed for an unsigned value $N$: the smallest $n$ with $2^n > N$ (1000 needs 10 bits, since $2^{10} = 1024$). Range of $n$ unsigned bits: $0$ to $2^n - 1$.

2.2 Signed Integers: Signed Magnitude, One’s and Two’s Complement

8 bits: SM and 1C give $-127 \ldots +127$; 2C gives $-128 \ldots +127$. 4-bit 2C: $-8 \ldots +7$. 16-bit 2C: $-32768 \ldots +32767$.

Worked example: one pattern, four meanings

Pattern 1011 0101:

• Unsigned: $128 + 32 + 16 + 4 + 1 =$ 181
• Signed magnitude: sign 1, rest 011 0101 = 53 → −53
• One’s complement: flip → 0100 1010 = 74 → −74
• Two’s complement: $-128 + 32 + 16 + 4 + 1 =$ −75

Worked example: −18 in 8 bits (+18 = 0001 0010)

Sign extension (4 → 8 bits): SM puts the extra 0s after the sign bit (1101 → 1000 0101); 1C and 2C copy the sign bit (2C 1011 → 1111 1011).

2.3 Integer Arithmetic and Overflow

Two’s complement overflow: $V = C_{\text{in, MSB}} \oplus C_{\text{out, MSB}}$. Quick test: positive + negative never overflows; two same-sign numbers overflow only when the answer has the other sign.

Worked example (a): 19 − 48 in 8-bit two’s complement

$48 =$ 0011 0000, so $-48 =$ 1100 1111 + 1 = 1101 0000.

  carries   0 0 1 0 0 0 0 0     (carry INTO each column)
     19     0 0 0 1 0 0 1 1
  + (-48)   1 1 0 1 0 0 0 0
  ----------------------------
            1 1 1 0 0 0 1 1     carry into MSB 0, carry out 0 -> no overflow

1110 0011 is negative. Flip + 1 → 0001 1101 = 29, so the answer is −29 ✓

Worked example (b): 9 + (−23) in 8-bit one’s complement

$-23 =$ flip(0001 0111) = 1110 1000. 0000 1001 + 1110 1000 = 1111 0001, no carry out, so no end-around carry. Flip → 0000 1110 = 14 → −14 ✓

Worked example (c): 4-bit overflow checks

Worked example (d): −3 − 5 in 4 bits, both systems

$-3 - 5 = (-3) + (-5)$, true answer $-8$.

Worked example (e): a counting loop that wraps (4-bit one’s complement)

j = -2; k = 6; while k ≠ -6 { j = j - 1; k = k + 1 }. Here $j - 1 = j + 1110$ (with end-around carry) and $k + 1 = k + 0001$. The test value $-6 = 1001$.

$0111 + 1 = 1000$ is $-7$ (the count wraps), so the loop runs 3 times: j = 1010 = −5.

• A carry out of the MSB on its own is not overflow in two’s complement.
• Only throw away the MSB carry in 2C; in 1C it goes back into the rightmost bit.

Adder–subtractor circuit

One control line M feeds an XOR gate on every B input and also the first carry $C_0$.

• M = 0: B passes unchanged, $C_0 = 0$ → $A + B$.
• M = 1: every B bit is flipped and $C_0 = 1$ → $A + B' + 1 = A - B$.
• Overflow flag (4 bits): $V = C_3 \oplus C_4$.

Example $6 - 3$: $B \oplus 1111 = 1100$, then $0110 + 1100 + 1 = 1\,0011$ → $S = 0011 = 3$, $C_3 = C_4 = 1$, so $V = 0$.

Sequential (shift-and-add) multiplier

Worked example: 11 × 13 with 4-bit registers (M = 1011, Q = 1101)

Product A Q = 1000 1111₂ = 143 ✓ ($11 \times 13 = 143$).

Keep the carry C: in cycle 4 it becomes the top bit of A after the shift. Without it the top bit is lost.

2.4 Floating Point: the 14-bit Model and IEEE 754

A float is $\pm\, 1.F \times 2^{e}$, normalized to exactly one 1 before the point. That leading 1 is not stored (hidden bit). Moving the point left $k$ places adds $k$ to the exponent. Stored exponent $E = e + \text{bias}$.

Bit layouts, ranges and special patterns of each format: see Table 6.4d.

14-bit model layout (bias 16):

IEEE single layout (bias 127):

For IEEE hex: write all 32 bits in a row, cut into eight groups of 4, and convert each group to one hex digit.

Worked example: 14-bit model (excess-16)

Decode 0 10010 10100000: $S = 0$ (+), $E = 18 \Rightarrow e = 18 - 16 = 2$, value $= 1.101 \times 2^2 = 110.1_2 =$ 6.5

Worked example: IEEE 754 single precision

$-12.375$ → IEEE: $S = 1$. $12.375 = 1100.011 = 1.100011 \times 2^3$. $E = 3 + 127 = 130 = 1000\,0010$. $F = 100011$ then 0s.

S  E          F
1  10000010   10001100000000000000000
1100 0001 0100 0110 0000 0000 0000 0000  ->  C 1 4 6 0 0 0 0

Answer: C1460000₁₆

$\texttt{41C80000}$ → decimal: 0100 0001 1100 1000 0000… → $S = 0$, $E = 1000\,0011 = 131 \Rightarrow e = 4$, $F = 1001$ → $1.1001 \times 2^4 = 11001_2 =$ 25

$0.15625 = 0.00101 = 1.01 \times 2^{-3}$, $E = 124 = 0111\,1100$ → 3E200000₁₆

• Subtract the bias when decoding, add it when encoding.
• A plain 5-bit exponent cannot be negative; the bias (excess-16) lets it run from −16 to +15.

2.5 Floating-Point Arithmetic and Errors

Worked example: add, subtract and multiply in the 14-bit model

(a) $A =$ 0 10010 10000000, $B =$ 0 10000 01000000. $A = 1.1 \times 2^2$ (= 6), $B = 1.01 \times 2^0$ (= 1.25). Align B to $2^2$: $0.0101 \times 2^2$. Add: $1.1000 + 0.0101 = 1.1101 \times 2^2$ (already normal). Result 0 10010 11010000 $= 111.01_2 = 7.25$ ✓

(b) $12 - 1.25$: $12 = 1.1 \times 2^3$, $1.25 = 1.01 \times 2^0 \to 0.00101 \times 2^3$. $1.10000 - 0.00101 = 1.01011 \times 2^3 = 1010.11_2 = 10.75$. Stored: 0 10011 01011000

(c) $12 \times 1.25$ with biased fields: $E = 19 + 16 - 16 = 19$. Significands $1.1 \times 1.01 = 1.111$. Sign $0 \oplus 0 = 0$. Result 0 10011 11100000 $= 1.111 \times 2^3 = 15$ ✓

Never test x == 0.0. 0.1 has no exact binary form, so adding 0.1 ten times is not exactly 1.0. Use a tolerance: abs(x - y) < epsilon. Exponent bits set the range; fraction bits set the precision.

• Overflow: exponent too big to store. Underflow: exponent too small (number too close to 0), e.g. $2^{-18}$ needs $E = -2$ in the 14-bit model. These are blatant errors.
• Subtle errors give a believable wrong value: $128.75 = 1.000000011 \times 2^7$ keeps only 8 fraction bits, so it is stored as 128.5.

3. Codes, Error Detection and Error Correction

Lecture 3: ASCII and parity, BCD, recording codes, check digits, CRC, Hamming distance, Hamming codes.

3.1 Character Codes and Parity

Parity bit = the 8th (leftmost) bit, chosen so the total number of 1s in the byte is even (even parity) or odd (odd parity). A wrong count means an error is detected. Parity cannot say which bit is wrong and misses two errors in the same byte.

Worked example: “CAT” with parity, then checking received bytes

Received (even parity): 53 C9 D4. 53 = 0101 0011 (four 1s, ok) so the character is 53 = ‘S’. C9 = 1100 1001 (four, ok) so 49 = ‘I’. D4 = 1101 0100 (four, ok) so 54 = ‘T’. Message: “SIT”, no error detected. A byte such as 1000 0011 has three 1s, so an error is detected.

BCD: zoned and packed

Sign nibbles: 1100 (C) = +, 1101 (D) = −, 1111 (F) = unsigned. Zoned: one digit per byte, zone F on every digit except the last, whose zone is the sign. Packed: two digits per byte, sign nibble at the right end; add a leading 0000 if the nibble count is odd.

Unicode: 17 planes × 65,536 = 1,114,112 code points (U+0000 … U+10FFFF, so the largest needs 21 bits). Plane 0 is the Basic Multilingual Plane. ASCII is the first 128 code points.

• Count the 1s of the 7 data bits only, then add the parity bit. Do not count the parity bit twice.
• Letters: count from ‘A’ = 41 (A … I = 41 … 49, J … O = 4A … 4F, P = 50, T = 54, Z = 5A).

3.2 Recording and Transmission Codes

Each bit gets a bit cell; the receiver keeps its clock in step by watching for transitions. Cell time = 1 / bit rate (2 Kbps gives 0.5 ms). Density (most data per area): RLL > MFM > FM.

Worked example: data 1 0 0 1 1 in every code

RLL(2,7)

Read the data from the left and cut it into groups:

• starts with 1: take 2 bits
• starts with 01 or 000: take 3 bits
• starts with 001: take 4 bits

Each code is twice as long as its data. Transitions after NRZI = number of 1s in the code.

Worked example: RLL(2,7) for 1000 1111

Cut 10 | 0011 | 11, so the code is 0100 | 00001000 | 1000. The code has three 1s, so NRZI gives 3 transitions for 8 data bits.

• NRZI: only a 1 causes a flip; a 0 keeps the level.
• MFM: a boundary flip appears only between two 0s, never next to a 1.
• Cut RLL data by its leading bits, not into fixed-size blocks.

3.3 Error Detection: Check Digits and CRC

Check digit (UPC-A)

Check digit = 10 − (S mod 10), where S = 3 × (sum of odd positions) + (sum of even positions) over the first 11 digits. If S mod 10 = 0, the check digit is 0.

Worked example: UPC-A check digit for 036000 24145?

Odd positions (1st, 3rd, … 11th): 0 + 6 + 0 + 2 + 1 + 5 = 14, and 14 × 3 = 42. Even positions (2nd … 10th): 3 + 0 + 0 + 4 + 4 = 11. S = 42 + 11 = 53. Check digit = 10 − (53 mod 10) = 10 − 3 = 7.

CRC (modulo-2 division)

Mod-2 add and subtract are both XOR (no carries, no borrows). In the long division, whenever the leftmost remaining bit is 1, write the key under it and XOR; never compare sizes. A key with $n+1$ bits (degree $n$) gives an $n$-bit CRC. Key 1101 = $x^3 + x^2 + 1$.

Key = ________ (n+1 = ___ bits)  ->  append n = ___ zeros

  data + zeros:            _ _ _ _ _ _ _ _ _ _ _ _
  key under the first 1:   _ _ _ _
  XOR, bring down      ->  _ _ _ _ _ _ _ _ _ _ _ _
  key under the next 1:      _ _ _ _
  XOR                  ->  _ _ _ _ _ _ _ _ _ _ _ _
  ... repeat until fewer than (n+1) bits remain after the last 1 ...
  remainder = last n bits = _ _ _

Codeword = data followed by remainder = ________________

Worked example: data 1111101, key 1101

Sender (key has 4 bits, so append 3 zeros):

        1111101000
        1101           step 1
        0010101000
          1101         step 2
        0001111000
           1101        step 3
        0000010000
             1101      step 4
        0000001010
              1101     step 5
        0000000111   -> remainder 111

Codeword = 1111101 | 111 = 1111101111

Receiver divides what arrives by 1101:

• 1111101111 gives remainder 000, so accept.
• 1111100111 gives remainder 101, so reject (bit 4 from the right was flipped).

A CRC with a degree-$n$ key catches all single-bit errors and all bursts of length at most $n$. It only detects; it cannot correct.

• Append zeros only at the sender, never at the receiver.
• The remainder must have exactly $n$ bits: keep leading zeros (for example 011).

3.4 Hamming Distance and Hamming Codes

Hamming distance = number of positions where two code words differ (XOR them, count the 1s). $D_{min}$ = smallest distance over all pairs. A code detects up to $D_{min} - 1$ errors and corrects up to $\lfloor (D_{min} - 1)/2 \rfloor$.

Worked example: $D_{min}$ of $\{00000, 01011, 10101, 11110\}$

$D_{min}$ = 3, so the code detects 2 and corrects 1.

How many check bits?

For $m$ data bits find the smallest $r$ with $m + r + 1 \le 2^r$. The code word has $n = m + r$ bits.

Layout and encoding

Number positions 1 to $n$ from the right. Check bits sit at the powers of 2 (1, 2, 4, 8, 16). Data bits fill the other positions from the highest position down, in the order written. Check bit $P_c$ covers every position whose binary number contains $c$ (position 11 = 8 + 2 + 1 is checked by $P_8$, $P_2$, $P_1$). Even parity: each check bit = XOR of the data bits it covers.

Every position from 1 to 16 in binary, with the check bits that cover it: see Table 6.4c.

Ready lists (use only positions up to your $n$; for the check bit itself use data positions only):

The 7-bit version (4 data bits) is positions 7 6 5 4 3 2 1 = $d_1\, d_2\, d_3\, P_4\, d_4\, P_2\, P_1$, with P1 from 3, 5, 7; P2 from 3, 6, 7; P4 from 5, 6, 7.

Worked example: encode M = 1101 0110

Key K = P8 P4 P2 P1 = 1101. Code word (position 12 first): 1101 1011 1001

Finding and correcting an error (syndrome)

Recompute the check bits from the data read ($K'$), XOR with the stored check bits ($K$). The result $K \oplus K'$, read as binary (P8 P4 P2 P1), is the position of the wrong bit. 0 = no error; a power of 2 = a check bit itself is wrong (data fine); anything else = flip that data position.

Syndrome (P8 P4 P2 P1 as binary) = ______ = position ____

Worked example: data read back as 1101 0100, stored K = 1101

Place the data read at positions 12, 11, 10, 9, 7, 6, 5, 3 = 1, 1, 0, 1, 0, 1, 0, 0.

Syndrome = 0101 = 5, so the bit at position 5 is wrong. Flip it from 0 to 1. Corrected data: 1101 0110 (P4 and P1 failed, and 4 + 1 = 5).

Worked example: labels $M_8 \ldots M_1$ and $C_4 \ldots C_1$, word read = 01000011 1010

Labels count from the right: $C_1, C_2, C_3, C_4$ sit at positions 1, 2, 4, 8 and $M_1 \ldots M_8$ fill positions 3, 5, 6, 7, 9, 10, 11, 12. Here $M_8 \ldots M_1 = 01000011$ and $C_4 C_3 C_2 C_1 = 1010$.

When the check bit is part of the word, count the 1s of the whole group including the check bit: odd means the check fails.

Syndrome = 0111 = 7 → position 7 = $M_4$ is wrong. Flip it: corrected message $M_8 \ldots M_1$ = 0100 1011 (check bits unchanged, 1010).

• Number positions from the right.
• When computing a check bit, use data bits only, never other check bits.
• A single-error-correcting code ($D_{min} = 3$) cannot fix two errors: the syndrome then points at the wrong place.

4. Boolean Algebra and Digital Logic

Lectures 4–5: gates, truth tables, Boolean laws, SOP/POS, K-maps, adders, decoders, multiplexers, flip-flops, sequential circuits

4.1 Gates and Truth Tables

Notation: NOT $x$ is $x'$, AND is $xy$, OR is $x+y$, XOR is $x \oplus y$. Order of work: NOT, then AND, then OR. A function of $n$ variables has $2^n$ rows. NAND alone (or NOR alone) can build every circuit.

Gate symbols, truth tables and NAND/NOR replacements: see Tables 6.2a–c.

An AND–OR circuit becomes NAND–NAND by double complement and DeMorgan: $xy + zw = ((xy)'(zw)')'$. Also, $x \oplus y \oplus z = 1$ when an odd number of inputs are 1 (parity bit).

Why OR is NAND of the complements: NAND gives 0 only when both of its inputs are 1. Feeding it $a'$ and $b'$ gives 0 only when $a = b = 0$, which is exactly when $a + b = 0$.

Recipe: any SOP using only NAND gates

Worked example: XOR from NAND only, $x \oplus y = xy' + x'y$

Step 1, the ordinary circuit: NOT $y$ makes $y'$, and NOT $x$ makes $x'$. AND($x$, $y'$) makes $xy'$, and AND($x'$, $y$) makes $x'y$. An OR joins them.

Steps 2–4: swap each gate, then cancel the NOT pairs.

Check $x = 1$, $y = 0$: $G_1 = 0$, $G_2 = 1$, $G_3 = \text{NAND}(1,1) = 0$, $G_4 = \text{NAND}(0,0) = 1$, $G_5 = \text{NAND}(0,1) =$ 1 ✓. The 4-gate version shares one gate $n_1 = (xy)'$ in place of both inverters, because $x(xy)' = xy'$ and $y(xy)' = x'y$.

• “Only NAND” means no separate NOT gates: every inverter is NAND($a$, $a$).
• Only cancel two NOTs that are directly in a row on the same wire. The NOTs on the input variables have nothing to cancel with, so they stay.

Worked example: bitwise operations on $A = 1011\,0010$, $B = 0110\,1011$ (column by column)

4.2 Boolean Laws, DeMorgan, SOP and POS

Also useful: $(x')' = x$, $x + x'y = x + y$, consensus $xy + x'z + yz = xy + x'z$.

Complement of a whole expression (extended DeMorgan): swap every AND and OR, and prime every variable. Keep the brackets so the order of work does not change. Example: $F = xy + x'z + yz'$ gives $F' = (x'+y')(x+z')(y'+z)$.

SOP (sum of minterms): one AND term per row where $F = 1$; write $x$ for bit 1 and $x'$ for bit 0; OR the terms. Short form $F = \Sigma m(\ldots)$. POS (product of maxterms): one OR term per row where $F = 0$; write $x$ for bit 0 and $x'$ for bit 1; AND the terms.

Worked example: simplify with laws (name the law at every step)

(a) $F = (x+y)(x+y')(xz')'$

(b) Show $x = xy + xy'$: $xy + xy' = x(y+y')$ (distributive) $= x \cdot 1$ (inverse) $=$ $x$ (identity).

(c) $F = \Sigma m(0,2,4,5,6)$: the 1s are rows 000, 010, 100, 101, 110. Rows 0, 2, 4, 6 all have $z = 0$, giving $z'$. Rows 4, 5 have $x = 1$, $y = 0$, giving $xy'$. So $F =$ $z' + xy'$.

4.3 Karnaugh Maps

Rows and columns go in Gray order 00, 01, 11, 10. Circle rectangles of 1s of size 1, 2, 4, 8 or 16 (wrap-around allowed; the four corners form one group). Use as few, as large groups as possible, overlaps allowed, every 1 covered. Don’t-cares may be used as 1s but need not be covered. In each group keep only the variables that do not change (1 gives $x$, 0 gives $x'$); a group of $2^k$ cells removes $k$ variables.

Worked example 1: $F(w,x,y,z) = \Sigma m(0,1,2,5,8,9,10)$

$F =$ $x'y' + x'z' + w'y'z$

Worked example 2: don’t-cares, $F = \Sigma m(1,3,7,11,15) + d(0,2,5)$

Group A is the whole column $yz = 11$ giving $yz$. Group B is the top row, using d0 and d2 as 1s, giving $w'x'$. d5 is not needed, so leave it as 0. $F =$ $yz + w'x'$

Worked example 3: word problem (puppy biscuit). Biscuit ($F=1$) for $SWB$ = 110, 011, 100, 111, otherwise 0.

Group $\{3,7\}$ (column 11) gives $WB$; group $\{4,6\}$ (wraps around the row) gives $SB'$. $F =$ $SB' + WB$ (1 NOT, 2 AND, 1 OR).

• Label order is 00, 01, 11, 10, so cells 12–15 sit above 8–11.
• Groups must be powers of 2 and rectangular, never L-shaped or size 3 or 6.
• Do not forget wrap-around groups (edges and four corners).

4.4 Combinational Circuits

Half adder: Sum $= x\oplus y$, Carry $= xy$. Full adder: Sum $= x\oplus y\oplus C_{in}$, $C_{out} = xy + C_{in}(x\oplus y)$. Sum is 1 for an odd number of 1s; $C_{out}$ is 1 for two or more 1s. Ripple-carry adder: $n$ full adders chained; each $C_{out}$ feeds the next $C_{in}$. Decoder: $n$ inputs give $2^n$ outputs, exactly one is 1 (inputs $= \log_2$ outputs). Multiplexer: $2^n$ data inputs need $n$ select lines.