ALU design

ACompressed recap

🧾

ALU = n slices (AND, OR, full-adder sum computed together; MUX picks by operation select); subtraction = a + NOT b + 1; control bits = ⌈log₂ #ops⌉; Z = NOR of result, N = MSB, C = cₙ, V = cₙ₋₁ ⊕ cₙ. Ripple adder: last carry n·t_c, last sum (n−1)t_c + t_s, Θ(n). CLA: gᵢ = aᵢbᵢ, pᵢ = aᵢ ⊕ bᵢ, cᵢ₊₁ = gᵢ + pᵢcᵢ; unlimited fan-in → 4 gate delays; bounded fan-in → Θ(log n); rippled blocks → 2 gate delays per block. Multiplication: shift-and-add (one add per 1 bit); Booth: 10 subtract, 01 add, arithmetic shift; recoding counts transitions.

BMerged rule card

2.1.1 Building an ALU: 1-bit slice, n-bit ALU, subtraction, flags Z N C V

• ALU slice: AND, OR, sum computed together; MUX (operation select) picks one; slices chained by carries.
• a − b = a + NOT b + 1 (B-invert XORs + carry-in₀ = 1).
• Control bits = ⌈log₂ #operations⌉.
• Z = NOR(result); N = MSB; C = cₙ; V = cₙ₋₁ ⊕ cₙ.

2.1.2 Adder speed: ripple-carry delay, carry-lookahead (generate, propagate), gate-delay counting

• Ripple: last carry n·t_c; last sum (n−1)·t_c + t_s; ≈ 2 gate delays per bit for carries; Θ(n).
• gᵢ = aᵢbᵢ, pᵢ = aᵢ ⊕ bᵢ; cᵢ₊₁ = gᵢ + pᵢcᵢ; sᵢ = pᵢ ⊕ cᵢ.
• CLA (unlimited fan-in): 1 (g,p) + 2 (carries) + 1 (sum) = 4 gate delays.
• Bounded fan-in CLA: Θ(log n). Rippled CLA blocks: 2 per block after g/p.

2.1.3 Multiplication: shift-and-add, Booth's algorithm; restoring division

• Shift-and-add (unsigned): one addition per 1 bit; product 2n bits.
• Booth: (Q₀,Q₋₁) 10 → A − M; 01 → A + M; 00/11 → nothing; then arithmetic shift right A,Q,Q₋₁; n steps.
• Recode with a 0 appended: pairs (bit, right neighbour): 10 = −1, 01 = +1.
• Booth operations = transitions; worst case alternating bits (n ops); best case long runs.
• Restoring division: shift, subtract, restore if negative; n steps.

CInterleaved GATE-style questions

Q1NAT1 markALU control

An ALU must support 30 operations with an encoded select field. Bits needed?

Numerical answer: ________

Q2MCQ1 markSubtraction

For subtraction, the ALU must set:

• (A) B-invert = 1 and carry-in₀ = 0
• (B) B-invert = 0 and carry-in₀ = 0
• (C) B-invert = 1 and carry-in₀ = 1
• (D) B-invert = 0 and carry-in₀ = 1

Q3NAT2 marksOverflow by carries

4-bit addition 0111 + 0011. What is V (0 or 1)?

Numerical answer: ________

Q4NAT2 marksRipple delay

A 24-bit ripple-carry adder has t_c = 1.5 ns and t_s = 2 ns. When is the last sum bit ready (ns)?

Numerical answer: ________

Q5NAT1 markCLA delay

A 4-bit CLA with unlimited fan-in: 1 gate delay for g/p, 2 for carries, 1 for sums. Total gate delays?

Numerical answer: ________

Q6NAT2 marksBooth count

Booth's algorithm, 8-bit multiplier 0111 1111. Total additions plus subtractions?

Numerical answer: ________

Q7MSQ2 marksBooth facts

Which are true?

• (A) The shift in Booth's algorithm is arithmetic.
• (B) Booth always needs fewer operations than shift-and-add.
• (C) Alternating bits are Booth's worst case.
• (D) Booth's algorithm handles two's-complement multipliers directly.

Q8NAT2 marksShift-and-add

Unsigned shift-and-add multiplication of two 8-bit numbers, multiplier 1101 0110. Number of additions?

Numerical answer: ________

DAnswer Vault