Computer Organization & Architecture

Unit 7: Computer Arithmetic

From binary addition to floating-point magic — master every arithmetic algorithm the CPU uses, trace them step-by-step, and conquer GATE numericals.

⏱️ 6 hrs theory + 4 hrs lab | 🎯 GATE ~3 marks | 🖥️ ARM Cortex Multiplier

📝 30 MCQs (Bloom's Mapped) | 6 Numerical Problems | 5 GATE Practice Questions

Section A

Opening Hook — How Your Phone Calculates a Bank EMI in Nanoseconds

🏦 ₹10 Lakh Home Loan EMI — Calculated in 0.000000003 Seconds

Open any banking app — HDFC, SBI, ICICI — and tap the EMI calculator. Enter ₹10,00,000 loan, 8.5% interest, 20 years. In literally 3 nanoseconds, your phone shows ₹8,678/month. How?

Inside your phone's ARM Cortex-A78 processor sits a dedicated hardware multiplier — a circuit that multiplies two 64-bit numbers in a single clock cycle. That EMI formula needs multiplication, division, and exponentiation — all done by computer arithmetic circuits we'll study in this chapter.

The same arithmetic unit inside India's Chandrayaan-3 navigation computer calculated trajectory corrections that landed Vikram exactly at the lunar south pole. The same Booth's multiplier algorithm running inside ISRO's onboard processors processed thousands of multiply operations per second to adjust thrust vectors.

What if YOU understood exactly how the CPU does math? Not just "it adds numbers" — but the actual bit-level shift, add, complement, and overflow detection that makes digital arithmetic work? That's what this chapter delivers.

🇮🇳 ISRO (Chandrayaan)ARM CortexQualcomm SnapdragonIntel x86🇮🇳 DRDONVIDIA GPU

The ARM Cortex-A78 inside your Snapdragon 8 Gen 1 can perform 2 billion multiply-accumulate operations per second. Each of these uses a variant of Booth's algorithm — the exact same algorithm you'll trace by hand in this chapter. When GATE asks a Booth's multiplication question worth 2 marks, you're essentially solving what ARM engineers optimised for silicon.

Section B

Learning Outcomes — Bloom's Taxonomy Mapped (12 Outcomes)

Bloom's Level	Learning Outcome
🔵 Remember	LO1: State the rules for 2's complement representation and list the steps of Booth's algorithm
🔵 Remember	LO2: Recall the IEEE 754 single-precision format — sign bit, 8-bit exponent (bias 127), 23-bit mantissa
🟢 Understand	LO3: Explain why 2's complement is preferred over sign-magnitude for hardware arithmetic
🟢 Understand	LO4: Describe how overflow is detected in signed addition using carry-in and carry-out of the MSB
🟡 Apply	LO5: Perform binary multiplication using the shift-and-add method with a complete trace table
🟡 Apply	LO6: Execute Booth's algorithm for signed multiplication including negative operands
🟡 Apply	LO7: Carry out restoring and non-restoring division with quotient and remainder
🟡 Apply	LO8: Convert a decimal number to IEEE 754 single-precision floating-point format
🟠 Analyse	LO9: Compare restoring vs non-restoring division in terms of steps, complexity, and hardware cost
🟠 Analyse	LO10: Analyse Booth's algorithm's advantage when the multiplier has consecutive 1s or 0s
🔴 Evaluate	LO11: Evaluate trade-offs between hardware multiplier (area/speed) vs software multiplication (flexibility)
🔴 Create	LO12: Design and implement a Booth's multiplier simulator in Python

Section C

Concept Explanation — Computer Arithmetic from First Principles

1. 2's Complement — Addition, Subtraction & Overflow

Why 2's Complement? Early computers used sign-magnitude (one bit for sign, rest for value). Problem: two representations of zero (+0 and −0) and complex addition circuits. 2's complement solves both — it has a single zero and lets us use the same adder circuit for both addition and subtraction.

🔢 2's Complement Representation Rules

For an n-bit number:

Positive numbers: Same as unsigned binary. E.g., +5 in 4 bits = 0101

Negative numbers: Invert all bits (1's complement) then add 1.

Range: −2ⁿ⁻¹ to +2ⁿ⁻¹−1. For 4 bits: −8 to +7. For 8 bits: −128 to +127.

Step-by-step: Find 2's complement of −5 (4 bits)

Step 1: Binary of +5 = 0101

Step 2: Invert bits → 1010 (1's complement)

Step 3: Add 1 → 1010 + 0001 = 1011

∴ −5 in 2's complement (4 bits) = 1011 ✅

Hardware Adder/Subtractor Diagram

  ┌─────────────────────────────────────────────────┐
  │          4-BIT ADDER / SUBTRACTOR               │
  │                                                 │
  │   A₃  A₂  A₁  A₀         B₃  B₂  B₁  B₀      │
  │    │   │   │   │           │   │   │   │       │
  │    │   │   │   │          ⊕   ⊕   ⊕   ⊕  ← M  │
  │    │   │   │   │           │   │   │   │       │
  │    ▼   ▼   ▼   ▼           ▼   ▼   ▼   ▼       │
  │  ┌─────────────────────────────────────────┐    │
  │  │        4-BIT PARALLEL ADDER             │    │
  │  │    FA₃    FA₂    FA₁    FA₀             │    │
  │  │                              C_in ← M   │    │
  │  └──┬────┬────┬────┬────┬──────────────────┘    │
  │    C₄   S₃   S₂   S₁   S₀                      │
  │  (C_out)                                        │
  │                                                 │
  │  M = 0 → Addition:    S = A + B                 │
  │  M = 1 → Subtraction: S = A + B̄ + 1 = A − B    │
  │                                                 │
  │  Overflow = C₃⊕C₄ (XOR of last two carries)    │
  └─────────────────────────────────────────────────┘

Worked Example: 2's Complement Addition (+5) + (−3) in 4 bits

📝 Given → Find → Solve

Given:

A = +5 = 0101, B = −3

Find:

A + B using 2's complement addition

Step-by-step:

Step 1: +5 = 0101

Step 2: −3 → +3 = 0011 → invert = 1100 → add 1 = 1101

Step 3: Add:

    0 1 0 1   (+5)
  + 1 1 0 1   (−3)
  ─────────
  1 0 0 1 0
  ↑
  carry out (discard for 4-bit result)

  Result = 0010 = +2 ✅

Step 4: Overflow check → C₃ (carry into MSB) = 1, C₄ (carry out of MSB) = 1 → XOR = 0 → No overflow ✅

Answer: (+5) + (−3) = +2 = 0010

Overflow Detection Rules

Operation	Overflow Condition	Example (4 bits)
+ve + +ve = −ve	Overflow ✅	+5 + +4 = 0101+0100 = 1001 (looks like −7!)
−ve + −ve = +ve	Overflow ✅	−5 + −4 = 1011+1100 = 10111 → 0111 (looks like +7!)
+ve + −ve	Never overflows ❌	Signs differ → result always in range

Students confuse "carry out" with "overflow." They are NOT the same! In 2's complement, overflow = C_in(MSB) ⊕ C_out(MSB). A carry out without overflow is perfectly normal (e.g., adding +5 and −3 produces carry out but no overflow).

GATE 2019 (1 mark): In 8-bit 2's complement, what is the range of representable integers?
Answer: −128 to +127 (−2⁷ to 2⁷−1)

2. Multiplication — Shift-and-Add Method

Binary multiplication is simpler than decimal multiplication. Since each bit is 0 or 1, each partial product is either zero (multiply by 0) or the multiplicand itself (multiply by 1), shifted to the appropriate position.

⚙️ Hardware Multiplier Block Diagram

  ┌──────────────────────────────────────────────────────┐
  │           HARDWARE MULTIPLIER (n-bit)                │
  │                                                      │
  │  ┌──────────┐    ┌──────────┐    ┌──────────┐       │
  │  │    AC    │    │    QR    │    │   Q₋₁    │       │
  │  │(Accumul.)│    │(Multipli-│    │(Extra bit│       │
  │  │ n bits   │←──→│  er)     │←──→│ for Booth│       │
  │  │          │    │ n bits   │    │  1 bit)  │       │
  │  └────┬─────┘    └──────────┘    └──────────┘       │
  │       │                                              │
  │       ▼                                              │
  │  ┌──────────┐                    ┌──────────┐       │
  │  │  ADDER   │←────────────────── │    BR    │       │
  │  │(n-bit)   │                    │(Multipli-│       │
  │  └──────────┘                    │  cand)   │       │
  │                                  │ n bits   │       │
  │  ┌──────────┐                    └──────────┘       │
  │  │    SC    │ ← Sequence Counter (log₂n bits)       │
  │  │(counts   │    Starts at n, decrements each step  │
  │  │ down)    │                                        │
  │  └──────────┘                                        │
  │                                                      │
  │  Algorithm: Repeat n times:                          │
  │    If QR₀ = 1 → AC ← AC + BR                       │
  │    Shift right (AC, QR) combined                     │
  │    SC ← SC − 1                                      │
  │  Product = {AC, QR}                                  │
  └──────────────────────────────────────────────────────┘

Worked Example: 5 × 7 using Shift-and-Add (4-bit unsigned)

📝 Full Trace Table: 5 × 7 = 35

Given:

Multiplicand (BR) = 7 = 0111, Multiplier (QR) = 5 = 0101

Initial State:

AC = 0000, QR = 0101, SC = 4

Step	AC	QR	QR₀	Operation	SC
Init	`0000`	`0101`	1	—	4
1a	`0111`	`0101`	1	AC ← AC + BR (QR₀=1)	4
1b	`0011`	`1010`	—	Shift right {AC,QR}	3
2a	`0011`	`1010`	0	No add (QR₀=0)	3
2b	`0001`	`1101`	—	Shift right {AC,QR}	2
3a	`1000`	`1101`	1	AC ← AC + BR (QR₀=1)	2
3b	`0100`	`0110`	—	Shift right {AC,QR}	1
4a	`0100`	`0110`	0	No add (QR₀=0)	1
4b	`0010`	`0011`	—	Shift right {AC,QR}	0

Product = {AC, QR} = 0010 0011 = 32 + 2 + 1 = 35 ✅ (5 × 7 = 35)

GATE shortcut: In the shift-and-add method, the number of additions equals the number of 1s in the multiplier. For 5 = 0101 (two 1s), we did exactly 2 additions. Use this to quickly verify your trace!

3. Booth's Algorithm — Signed Multiplication

Shift-and-add works for unsigned numbers, but what about signed numbers? Enter Andrew Booth's 1951 algorithm — elegant, efficient, and still used in modern ARM processors.

Booth's = Kirana shopkeeper calculation shortcut. Suppose you buy 9 packets of ₹100 biscuits. Instead of adding ₹100 nine times (9 additions), the shopkeeper says "₹1000 minus ₹100 = ₹900" — that's 1 addition + 1 subtraction (only 2 operations!). Booth's algorithm does the same: instead of adding for every consecutive 1-bit, it subtracts at the start of a block of 1s and adds at the end. Fewer operations = faster hardware.

⚙️ Booth's Algorithm — Step-by-Step Rules

Setup:

AC = 0 (n bits), QR = Multiplier (n bits), Q₋₁ = 0 (extra bit), BR = Multiplicand, SC = n

Repeat n times:

1. Examine QR₀ (LSB of QR) and Q₋₁:

QR₀	Q₋₁	Operation
0	0	No operation (just shift)
0	1	AC ← AC + BR (add multiplicand)
1	0	AC ← AC − BR (subtract multiplicand)
1	1	No operation (just shift)

2. Arithmetic Shift Right {AC, QR, Q₋₁} — preserve the sign bit of AC!

3. SC ← SC − 1. If SC ≠ 0, go to step 1.

4. Product = {AC, QR}

ASCII Block Diagram — Booth's Hardware

  ┌──────────────────────────────────────────────────────────┐
  │               BOOTH'S MULTIPLIER HARDWARE                │
  │                                                          │
  │  ┌──────────┐    ┌──────────┐    ┌─────┐               │
  │  │    AC    │◄──►│    QR    │◄──►│ Q₋₁ │               │
  │  │(Accumul.)│    │(Multipli-│    │(prev│               │
  │  │ n bits   │    │  er)     │    │ LSB)│               │
  │  └────┬─────┘    └──────────┘    └─────┘               │
  │       │                                                  │
  │       ▼            ┌───────────────┐                     │
  │  ┌─────────┐       │ DECISION LOGIC│                     │
  │  │ ADDER / │       │               │                     │
  │  │SUBTRACTR│◄──────│ QR₀  Q₋₁     │                     │
  │  └────┬────┘       │ 00 → NOP      │                     │
  │       │            │ 01 → ADD BR   │                     │
  │       ▼            │ 10 → SUB BR   │                     │
  │  ┌──────────┐      │ 11 → NOP      │                     │
  │  │    BR    │      └───────────────┘                     │
  │  │(Multipli-│                                            │
  │  │  cand)   │      ┌───┐                                 │
  │  └──────────┘      │SC │ ← Sequence Counter              │
  │                    └───┘                                  │
  │                                                          │
  │  After operation: Arithmetic Shift Right {AC, QR, Q₋₁}  │
  │  (Sign bit of AC is preserved during shift)              │
  └──────────────────────────────────────────────────────────┘

Worked Example: (−6) × 7 using Booth's Algorithm (5-bit)

📝 Full Trace Table: (−6) × 7 = −42

Given:

Multiplicand (BR) = +7 = 00111, Multiplier (QR) = −6

−6 in 2's complement (5 bits): +6 = 00110 → invert = 11001 → +1 = 11010

−BR = −7: invert 00111 = 11000 → +1 = 11001

Initial State:

AC = 00000, QR = 11010, Q₋₁ = 0, SC = 5

Step	AC	QR	Q₋₁	QR₀,Q₋₁	Operation	SC
Init	`00000`	`11010`	`0`	0,0	—	5
1: Check	`00000`	`11010`	`0`	0,0	NOP	5
1: ASR	`00000`	`01101`	`0`	—	Arith Shift Right	4
2: Check	`00000`	`01101`	`0`	1,0	AC ← AC − BR	4
2: Sub	`11001`	`01101`	`0`	—	AC = 00000+11001	4
2: ASR	`11100`	`10110`	`1`	—	Arith Shift Right	3
3: Check	`11100`	`10110`	`1`	0,1	AC ← AC + BR	3
3: Add	`00011`	`10110`	`1`	—	AC = 11100+00111	3
3: ASR	`00001`	`11011`	`0`	—	Arith Shift Right	2
4: Check	`00001`	`11011`	`0`	1,0	AC ← AC − BR	2
4: Sub	`11010`	`11011`	`0`	—	AC = 00001+11001	2
4: ASR	`11101`	`01101`	`1`	—	Arith Shift Right	1
5: Check	`11101`	`01101`	`1`	1,1	NOP	1
5: ASR	`11110`	`10110`	`1`	—	Arith Shift Right	0

Result:

Product = {AC, QR} = 11110 10110

This is a 10-bit 2's complement number. To verify: invert 1111010110 → 0000101001 → +1 → 0000101010 = 32+8+2 = 42

Product = −42 ✅ (−6 × 7 = −42)

Arithmetic Shift Right ≠ Logical Shift Right! In Booth's, you must use arithmetic shift right — the sign bit (MSB) of AC is preserved (copied into itself). If AC = 11001, after ASR it becomes 11100 (not 01100). Getting this wrong is the #1 error in GATE Booth's questions.

GATE-style version: Multiply (−3) × (+4) using Booth's algorithm with 5-bit representation. Show the trace table.
Hint: BR = +4 = 00100, QR = −3 = 11101. Expected answer: −12 = 11110 10100 (10-bit).

4. Restoring Division Algorithm

Division is the inverse of multiplication. The hardware divider repeatedly subtracts the divisor from the partial remainder. If the result is negative, we "restore" it (add the divisor back).

📐 Restoring Division — Algorithm Steps

Setup:

AC = 0 (n bits), QR = Dividend (n bits), BR = Divisor (n bits), SC = n

Repeat n times:

1. Shift Left {AC, QR} by 1 bit

2. AC ← AC − BR (subtract divisor)

3. If AC is negative (MSB = 1):

→ QR₀ = 0 (quotient bit = 0)

→ AC ← AC + BR (restore)

If AC is positive or zero (MSB = 0):

→ QR₀ = 1 (quotient bit = 1)

4. SC ← SC − 1

Result:

Quotient = QR, Remainder = AC

Worked Example: 7 ÷ 3 using Restoring Division (4-bit)

📝 Full Trace Table: 7 ÷ 3 → Quotient = 2, Remainder = 1

Given:

Dividend (QR) = 7 = 0111, Divisor (BR) = 3 = 0011

−BR = 2's complement of 3: invert 0011 = 1100 → +1 = 1101

Initial State:

AC = 0000, QR = 0111, SC = 4

Step	AC	QR	Operation	SC
Init	`0000`	`0111`	—	4
1: SHL	`0000`	`111_`	Shift left {AC,QR}	4
	`0001`	`110_`	(after shift: AC=0000←1, QR=110_)
1: Sub	`1110`	`110_`	AC ← AC − BR = 0001+1101
1: Check	`1110`	`1100`	AC < 0 → QR₀=0, Restore
1: Restore	`0001`	`1100`	AC ← AC + BR = 1110+0011	3
2: SHL	`0011`	`100_`	Shift left {AC,QR}	3
2: Sub	`0000`	`100_`	AC ← AC − BR = 0011+1101
2: Check	`0000`	`1001`	AC ≥ 0 → QR₀=1	2
3: SHL	`0001`	`001_`	Shift left {AC,QR}	2
3: Sub	`1110`	`001_`	AC ← AC − BR = 0001+1101
3: Check	`1110`	`0010`	AC < 0 → QR₀=0, Restore
3: Restore	`0001`	`0010`	AC ← AC + BR = 1110+0011	1
4: SHL	`0010`	`010_`	Shift left {AC,QR}	1
4: Sub	`1111`	`010_`	AC ← AC − BR = 0010+1101
4: Check	`1111`	`0100`	AC < 0 → QR₀=0, Restore
4: Restore	`0010`	`0100`	AC ← AC + BR = 1111+0011	0

Wait — let me recalculate more carefully. Let me redo with proper tracking:

Step	AC (4-bit + sign)	QR	Action
Init	`00000`	`0111`	AC=0, QR=Dividend=7
1: SHL	`00000`	`1110`	Left-shift {AC,QR}: AC gets MSB of QR
1: Sub	`11101`	`1110`	AC = 00000 − 00011 = 11101 (neg)
1: Result	`00000`	`1110`	Negative → Q₀=0, Restore (AC+BR)
2: SHL	`00001`	`1100`	Left-shift {AC,QR}
2: Sub	`11110`	`1100`	AC = 00001 − 00011 = 11110 (neg)
2: Result	`00001`	`1100`	Negative → Q₀=0, Restore
3: SHL	`00011`	`1000`	Left-shift {AC,QR}
3: Sub	`00000`	`1000`	AC = 00011 − 00011 = 00000 (≥0)
3: Result	`00000`	`1001`	Non-negative → Q₀=1
4: SHL	`00001`	`0010`	Left-shift {AC,QR}
4: Sub	`11110`	`0010`	AC = 00001 − 00011 = 11110 (neg)
4: Result	`00001`	`0010`	Negative → Q₀=0, Restore

Quotient = QR = 0010 = 2, Remainder = AC = 00001 = 1 ✅ (7 ÷ 3 = 2 remainder 1)

Quick check: Dividend = Quotient × Divisor + Remainder → 7 = 2 × 3 + 1 ✅. Always verify your division answer with this formula in GATE!

5. Non-Restoring Division Algorithm

Why non-restoring? In restoring division, when AC goes negative, we restore (add BR back) and then in the next step shift left and subtract again. That's 2 additions for a failed step. Non-restoring division skips the restore — if AC is negative, we add in the next step instead of subtracting. This saves one addition per negative step.

📐 Non-Restoring Division — Algorithm

Setup:

Same as restoring: AC = 0, QR = Dividend, BR = Divisor, SC = n

Repeat n times:

1. Shift Left {AC, QR}

2. If AC is positive or zero: AC ← AC − BR

If AC is negative: AC ← AC + BR

3. If AC is positive or zero → QR₀ = 1

If AC is negative → QR₀ = 0

4. SC ← SC − 1

After loop:

If AC is negative, restore it once: AC ← AC + BR

Quotient = QR, Remainder = AC

Worked Example: 7 ÷ 3 using Non-Restoring Division (comparison)

📝 Trace Table: 7 ÷ 3 (Non-Restoring)

Given:

QR = 7 = 0111, BR = 3 = 0011

Step	AC (5-bit)	QR	Operation
Init	`00000`	`0111`	AC=0 (positive)
1: SHL	`00000`	`1110`	Shift left
1: Op	`11101`	`1110`	AC≥0 → AC−BR = 00000−00011
1: Q₀	`11101`	`1110`	AC<0 → Q₀=0
2: SHL	`11011`	`1100`	Shift left
2: Op	`11110`	`1100`	AC<0 → AC+BR = 11011+00011
2: Q₀	`11110`	`1100`	AC<0 → Q₀=0
3: SHL	`11101`	`1000`	Shift left
3: Op	`00000`	`1000`	AC<0 → AC+BR = 11101+00011
3: Q₀	`00000`	`1001`	AC≥0 → Q₀=1
4: SHL	`00001`	`0010`	Shift left
4: Op	`11110`	`0010`	AC≥0 → AC−BR = 00001−00011
4: Q₀	`11110`	`0010`	AC<0 → Q₀=0
Final	`00001`	`0010`	AC<0 → Restore: AC+BR

Quotient = 0010 = 2, Remainder = 00001 = 1 ✅ — Same result, fewer additions!

Restoring vs Non-Restoring — Comparison

Parameter	Restoring Division	Non-Restoring Division
Restore step	Required after every negative AC	Not required (skipped)
Operations per cycle	Up to 2 (subtract + restore)	Exactly 1 (add or subtract)
Speed	Slower (more additions)	Faster
Hardware complexity	Simpler control logic	Slightly more complex
Final correction	Not needed	May need one final restore if AC < 0
GATE frequency	Very common (2–3 marks)	Moderate (1–2 marks)

6. IEEE 754 Floating-Point Representation

Integers are fine for counting, but what about 3.14159 or 0.000001? That's where floating-point comes in. The IEEE 754 standard (1985, revised 2008) defines how every computer in the world stores decimal numbers.

📊 IEEE 754 Single-Precision Format (32 bits)

  ┌───┬──────────────┬──────────────────────────────┐
  │ S │   Exponent   │         Mantissa             │
  │1b │    8 bits    │         23 bits              │
  ├───┼──────────────┼──────────────────────────────┤
  │31 │ 30 ──── 23   │ 22 ──────────────── 0        │
  └───┴──────────────┴──────────────────────────────┘

  Value = (−1)ˢ × 1.Mantissa × 2^(Exponent − 127)

  S = 0 → Positive
  S = 1 → Negative
  Exponent: Biased by 127 (actual = stored − 127)
  Mantissa: Fractional part after "1." (implicit leading 1)

Worked Example: Convert 13.75 to IEEE 754 Single Precision

📝 Step-by-Step: 13.75₁₀ → IEEE 754

Step 1: Sign bit

13.75 is positive → S = 0

Step 2: Convert to binary

Integer part: 13 = 1101

Fractional part: 0.75 → 0.75 × 2 = 1.5 → 1 | 0.5 × 2 = 1.0 → 1 | Done

0.75₁₀ = .11₂

∴ 13.75 = 1101.11₂

Step 3: Normalise (scientific notation in binary)

1101.11 = 1.10111 × 2³

Move point 3 places left → exponent = 3

Step 4: Biased exponent

Stored exponent = actual + bias = 3 + 127 = 130 = 10000010

Step 5: Mantissa

After "1." → 10111 padded to 23 bits → 10111000000000000000000

Step 6: Assemble

  S  Exponent    Mantissa
  0  10000010    10111000000000000000000

  Full: 0 10000010 10111000000000000000000
  Hex:  0x41 5C 00 00

13.75₁₀ = 0 10000010 10111000000000000000000 (IEEE 754) ✅

IEEE 754 Special Values

Value	Sign	Exponent (8 bits)	Mantissa (23 bits)	Meaning
+0	0	00000000	00000...0	Positive zero
−0	1	00000000	00000...0	Negative zero
+∞	0	11111111	00000...0	Positive infinity (e.g., 1/0)
−∞	1	11111111	00000...0	Negative infinity
NaN	0 or 1	11111111	non-zero	Not a Number (0/0, √−1)
Denormalised	0 or 1	00000000	non-zero	Very small numbers near 0

The smallest positive normalised float in IEEE 754 is ≈ 1.18 × 10⁻³⁸. That's far smaller than the mass of an electron (9.1 × 10⁻³¹ kg). The largest is ≈ 3.4 × 10³⁸ — larger than the number of atoms in the observable universe (~10⁸⁰). All packed into 32 bits!

Students forget the implicit "1." in the mantissa! IEEE 754 uses an "implied leading 1" — the mantissa field stores only the fractional part. So if mantissa field = 10111..., the actual value is 1.10111.... This gives you 24 bits of precision from a 23-bit field (free extra bit!).

GATE 2020 (2 marks): Convert −27.625 to IEEE 754 single-precision format. Express in hexadecimal.
Approach: S=1, 27.625 = 11011.101₂ = 1.1011101 × 2⁴, Exp = 4+127 = 131 = 10000011, Mantissa = 10111010...0
Answer: 0xC1DC0000

Section D

Learn by Doing — 3-Tier Lab Structure

🟢 Tier 1 — GUIDED LAB: Binary Arithmetic by Hand

⏱️ 45–60 minutesBeginnerPen and paper only

Exercise 1: 2's Complement Conversions

Convert each to 8-bit 2's complement:

+45 → 00101101 (verify: 32+8+4+1)
−45 → Invert 00101101 = 11010010, +1 = 11010011
−128 → 10000000 (the most negative 8-bit number)
+127 → 01111111 (the most positive 8-bit number)

Exercise 2: Addition with Overflow Check

Add in 8-bit 2's complement. Check for overflow.

(+100) + (+30) → Does this overflow? (Hint: 130 > 127)
(−50) + (−80) → Does this overflow? (Hint: −130 < −128)
(+100) + (−30) → Overflow? (Hint: signs differ → never)

Exercise 3: Manual Binary Multiplication

Multiply 6 × 5 using shift-and-add (4-bit). Draw the trace table.

Expected: Product = 30 = 00011110

Self-check: If you got 30, you did it right! Count your additions — should be equal to number of 1s in the multiplier (5 = 0101 has two 1s → 2 additions).

🟡 Tier 2 — SEMI-GUIDED LAB: Booth's Algorithm Trace

⏱️ 60–90 minutesIntermediatePractice with negative numbers

Your Mission:

Trace Booth's algorithm for the following multiplications. Draw the complete table with AC, QR, Q₋₁, Operation columns.

Easy: (+3) × (+4) = +12 (use 5-bit representation)
Medium: (−4) × (+5) = −20 (use 5-bit)
Hard: (−7) × (−3) = +21 (use 5-bit — both operands negative!)

Hints:

For (−7) × (−3): BR = −3 = 11101, QR = −7 = 11001
Remember: Arithmetic shift right preserves the sign bit
The QR₀,Q₋₁ decision: 10→subtract, 01→add, 00/11→NOP

Verify: After completing each trace, convert {AC,QR} back to decimal using 2's complement. Does it match the expected product?

🔴 Tier 3 — OPEN CHALLENGE: Python Booth's Multiplier Simulator

⏱️ 90–120 minutesAdvancedCoding required

Build a Python program that:

Takes two signed integers as input
Converts them to n-bit 2's complement
Executes Booth's algorithm step-by-step
Prints the trace table at each step (AC, QR, Q₋₁, operation)
Outputs the final product in both binary and decimal

Starter Code:

Python
def booths_multiply(multiplicand, multiplier, n_bits=8):
    # Step 1: Convert to 2's complement
    def to_twos_comp(val, bits):
        if val >= 0:
            return format(val, f'0{bits}b')
        return format((1 << bits) + val, f'0{bits}b')

    # Step 2: Initialize registers
    AC = [0] * n_bits      # Accumulator
    QR = list(map(int, to_twos_comp(multiplier, n_bits)))
    Q_minus1 = 0
    BR = list(map(int, to_twos_comp(multiplicand, n_bits)))
    SC = n_bits

    print(f"Init: AC={''.join(map(str,AC))} QR={''.join(map(str,QR))} Q-1={Q_minus1}")

    # Step 3: YOUR CODE HERE
    # Implement the Booth's loop:
    # - Check QR[-1] and Q_minus1
    # - Add/Subtract/NOP
    # - Arithmetic Shift Right
    # - Print trace at each step

# Test
booths_multiply(7, -6)    # Expected: -42
booths_multiply(-3, -7)  # Expected: +21

Portfolio boost: Upload this to GitHub as "Booth's Algorithm Simulator" with a README. This shows embedded systems knowledge — valued by DRDO, ISRO, and semiconductor companies like Qualcomm India.

Section E

Practice Problems — Diagrams, Numericals & GATE

Diagram-Based Questions (3)

📊 Diagram Q1: Draw the hardware block diagram for a 4-bit Booth's multiplier

Required components: AC register (4-bit), QR register (4-bit), Q₋₁ flip-flop, BR register (4-bit), Adder/Subtractor, Sequence Counter (SC), Control Logic, Arithmetic Shift Right circuit.

Show: Data paths between registers, control signals for add/subtract/shift, and the decision logic based on {QR₀, Q₋₁}.

📊 Diagram Q2: Draw the IEEE 754 format layout with bit positions

Show the 32-bit layout with Sign (bit 31), Exponent (bits 30–23), and Mantissa (bits 22–0). Label the bias value (127), the implicit "1." convention, and mark which bit combinations represent +∞, −∞, NaN, and ±0.

📊 Diagram Q3: Draw the flowchart for restoring division algorithm

Include: Start → Initialize (AC=0, QR=Dividend, SC=n) → Shift Left → Subtract BR → Check sign → Branch (Restore or Set Q₀) → Decrement SC → Loop check → Output Quotient and Remainder.

Numerical Problems (6)

🔢 Numerical 1: Booth's Multiplication — (−5) × 3

Given: Multiplicand = 3, Multiplier = −5. Use 5-bit Booth's algorithm. Expected Answer: −15

Work it out: BR = 00011, QR = −5 = 11011. Trace 5 steps. Product {AC,QR} should decode to −15.

🔢 Numerical 2: Booth's Multiplication — (−4) × (−6)

Given: Both operands negative. Use 5-bit. Expected Answer: +24

Hint: BR = −6 = 11010, QR = −4 = 11100. Remember −BR = +6 = 00110.

🔢 Numerical 3: Restoring Division — 11 ÷ 3

Given: Dividend = 11 = 1011, Divisor = 3 = 0011 Expected: Quotient = 3 (0011), Remainder = 2 (0010)

Verify: 3 × 3 + 2 = 11 ✅

🔢 Numerical 4: Non-Restoring Division — 15 ÷ 5

Given: Dividend = 15 = 1111, Divisor = 5 = 0101 Expected: Quotient = 3 (0011), Remainder = 0

🔢 Numerical 5: IEEE 754 — Convert −27.625 to single precision

Steps:

1. S = 1 (negative)

2. 27 = 11011, 0.625 = .101 → 27.625 = 11011.101

3. Normalise: 1.1011101 × 2⁴

4. Exponent: 4 + 127 = 131 = 10000011

5. Mantissa: 10111010000000000000000

Answer:

1 10000011 10111010000000000000000 = 0xC1DD0000

🔢 Numerical 6: IEEE 754 — What decimal does this represent?

Given: 0 10000001 01000000000000000000000

S = 0 (positive), Exponent = 10000001 = 129, Actual = 129 − 127 = 2

Mantissa = 1.01 (with implicit 1)

Value = (+1) × 1.01₂ × 2² = 1.25 × 4 = 5.0

Industry Application Questions (3)

🏭 Industry Q1: ARM Cortex Multiplier

The ARM Cortex-A78 uses a modified Booth's encoding (radix-4 Booth) to reduce the number of partial products by half. If a standard 32-bit Booth's multiplication requires 32 cycles, how many cycles does radix-4 Booth require? Explain the trade-off.

Answer: Radix-4 examines 2 bits at a time → 16 cycles (half). Trade-off: simpler control but needs a more complex partial product generator (±1×, ±2× multiplicand).

🏭 Industry Q2: GPU Floating-Point

NVIDIA's RTX 4090 GPU has 16,384 CUDA cores, each capable of performing one IEEE 754 single-precision multiply-add per cycle at 2.52 GHz. Calculate the theoretical peak FLOPS (Floating-Point Operations Per Second).

Answer: 16384 × 2 (multiply+add) × 2.52 × 10⁹ = 82.6 TFLOPS

🏭 Industry Q3: ISRO Navigation

Chandrayaan-3's onboard computer used fixed-point arithmetic for trajectory calculations instead of floating-point. Why might ISRO prefer fixed-point for space applications? What are the trade-offs?

Answer: Fixed-point is deterministic (no rounding surprises), uses less power, has predictable timing (critical for real-time control), and simpler hardware. Trade-off: limited range and precision compared to floating-point.

GATE Practice Questions (5)

GATE Q1 (1 mark): In 2's complement representation using 8 bits, the value of 11001011 is:
(a) −53 (b) −52 (c) +203 (d) −51
Answer: (a) MSB=1 → negative. Invert: 00110100, +1 = 00110101 = 53. So value = −53.

GATE Q2 (2 marks): Using Booth's algorithm, multiply (−9) × (−5) with 5-bit operands. What is the product in decimal?
Answer: +45. (Both negative → positive product. Trace carefully with ASR.)

GATE Q3 (1 mark): In IEEE 754 single-precision, the exponent field 10000100 represents an actual exponent of:
(a) 132 (b) 5 (c) −123 (d) 4
Answer: (b) 10000100₂ = 132. Actual = 132 − 127 = 5.

GATE Q4 (2 marks): Divide 13 by 5 using the restoring division algorithm with 4-bit operands. What is the quotient and remainder?
Answer: Quotient = 2 (0010), Remainder = 3 (0011). Verify: 2×5+3 = 13 ✅

GATE Q5 (2 marks): The IEEE 754 representation 0 11111111 00000000000000000000000 represents:
(a) +∞ (b) −∞ (c) NaN (d) Largest positive number
Answer: (a) +∞. When exponent = all 1s and mantissa = all 0s, it represents infinity. Sign bit 0 → positive infinity.

Section F

MCQ Assessment Bank — 30 Questions (Bloom's Mapped)

Remember / Identify (Q1–Q5)

In 2's complement representation, the range for an 8-bit number is:

0 to 255
−127 to +127
−128 to +127
−128 to +128

Remember

✅ Answer: (C) −128 to +127. Range = −2⁷ to 2⁷−1. Option B is wrong because it's −127 (that's 1's complement range).

In Booth's algorithm, when QR₀ = 1 and Q₋₁ = 0, the operation performed is:

AC ← AC + BR
AC ← AC − BR
No operation
Shift left

Remember

✅ Answer: (B) AC ← AC − BR. The pair (1,0) indicates the beginning of a block of 1s → subtract.

The bias value in IEEE 754 single-precision floating-point is:

Remember

✅ Answer: (B) 127. Bias = 2^(k−1) − 1 where k=8. So 2⁷−1 = 127.

In restoring division, what operation is performed when the partial remainder becomes negative?

Shift right and set quotient bit to 1
Add divisor back (restore) and set quotient bit to 0
Subtract divisor again
Halt the operation

Remember

✅ Answer: (B) Add divisor back to restore the previous value, and set quotient bit to 0.

The 2's complement of the binary number 0001 (4 bits) is:

1110
1111
0001
1000

Remember

✅ Answer: (B) 1111. Invert 0001 → 1110. Add 1 → 1111. This represents −1.

Understand / Explain (Q6–Q10)

Why is 2's complement preferred over sign-magnitude in hardware?

It uses fewer bits
It has a unique representation for zero and uses the same adder for add/subtract
It can represent larger numbers
It is easier for humans to read

Understand

✅ Answer: (B) Single zero representation and unified adder circuit. Sign-magnitude has +0 and −0, and needs separate add/subtract logic.

In Booth's algorithm, why does the pair (0,1) trigger addition while (1,0) triggers subtraction?

It's an arbitrary convention
(0,1) marks the end of a block of 1s, (1,0) marks the beginning — mimicking add-at-end, subtract-at-start
It reduces hardware cost
It's required for unsigned numbers only

Understand

✅ Answer: (B) Booth's recognises transitions in the multiplier bits. A 1→0 transition means end of a block of 1s (add), and 0→1 means start of a block (subtract).

What does the implicit leading "1" in IEEE 754 mantissa achieve?

Saves 1 bit of storage, giving 24 bits of precision with a 23-bit field
Makes the number always positive
Prevents overflow
Simplifies exponent calculation

Understand

✅ Answer: (A) Since normalised numbers always start with 1.xxx, we don't store the 1 — it's implicit. This gives a free extra bit of precision.

Why does non-restoring division require a final correction step?

Because the quotient might be wrong
Because the remainder may be negative at the end, which needs to be corrected by adding the divisor
Because the divisor changes during division
It doesn't — no correction is needed

Understand

✅ Answer: (B) Non-restoring skips restoring during the loop. If the final AC is negative, one restore (AC + BR) is needed to get the correct positive remainder.

Q10

Overflow in 2's complement addition occurs when:

There is a carry out of the MSB
Two numbers with different signs are added
The carry into the MSB differs from the carry out of the MSB
The result is zero

Understand

✅ Answer: (C) Overflow = C_in(MSB) ⊕ C_out(MSB). If they differ, the sign bit is corrupted → overflow.

Apply / Calculate (Q11–Q17)

Q11

What is the 2's complement of −42 in 8 bits?

00101010
11010110
11010101
10101010

Apply

✅ Answer: (B) +42 = 00101010. Invert → 11010101. Add 1 → 11010110.

Q12

Using shift-and-add, how many addition operations are needed to multiply by the number 01011010?

Apply

✅ Answer: (B) Count the 1s in 01011010: positions 1,3,4,6 → four 1s → 4 additions.

Q13

Convert 6.25 to IEEE 754 single-precision. What is the biased exponent?

Apply

✅ Answer: (C) 6.25 = 110.01₂ = 1.1001 × 2². Biased exp = 2 + 127 = 129.

Q14

In Booth's algorithm for (+7) × (+3) using 4-bit, the first step checks QR₀=1, Q₋₁=0. What operation is performed?

Add BR to AC
Subtract BR from AC
No operation
Complement QR

Apply

✅ Answer: (B) QR₀=1, Q₋₁=0 → Subtract: AC ← AC − BR.

Q15

What is the result of adding 01110 and 00101 in 5-bit 2's complement?

10011 (overflow)
10011 (valid negative)
01011 (no overflow)
Cannot determine

Apply

✅ Answer: (A) 14 + 5 = 19, but 5-bit range is −16 to +15. 19 > 15 → overflow! Result 10011 looks like −13, which is wrong.

Q16

Using restoring division, divide 9 by 4 (4-bit). The quotient is:

0010 (2)
0011 (3)
0001 (1)
0100 (4)

Apply

✅ Answer: (A) 9 ÷ 4 = 2 remainder 1. Quotient = 0010 = 2.

Q17

The IEEE 754 representation of +∞ is:

0 11111111 00000000000000000000000
0 00000000 00000000000000000000000
0 11111111 10000000000000000000000
1 11111111 00000000000000000000000

Apply

✅ Answer: (A) +∞ → Sign=0, Exponent=all 1s, Mantissa=all 0s. Option (D) is −∞, option (C) is NaN.

Analyse / Compare (Q18–Q22)

Q18

For the multiplier 11111110 (8-bit), Booth's algorithm performs how many add/subtract operations?

7 (one per 1-bit)
2 (one subtract at start, one add at end of the block)
6
8

Analyse

✅ Answer: (B) The multiplier 11111110 has one block of consecutive 1s (bits 7–1). Booth's only does operations at transitions: subtract at 0→1 transition, add at 1→0 transition → 2 operations total. This is Booth's key advantage!

Q19

Which division method requires more addition/subtraction operations on average?

Non-restoring (it sometimes adds and subtracts in same step)
Restoring (it needs an extra restore step for every negative remainder)
Both require exactly the same number
It depends on the dividend only

Analyse

✅ Answer: (B) Restoring division requires 2 operations (subtract + restore) when the remainder goes negative, while non-restoring only does 1 operation per cycle.

Q20

A system uses IEEE 754 single precision. Two numbers x = 1.0 × 2²³ and y = 1.0 are added. What is the result?

Exactly 8388609.0
8388608.0 (y is lost due to precision)
Infinity
NaN

Analyse

✅ Answer: (B) 2²³ = 8388608. Adding 1.0 requires aligning exponents. Since the mantissa only has 23 bits of precision, adding 1 to 2²³ is beyond the precision — the 1 gets rounded away! This is a classic floating-point precision issue.

Q21

Compare shift-and-add vs Booth's for multiplying by 01010101. Which is more efficient?

Shift-and-add (fewer shifts)
Booth's (fewer add/subtract operations)
Both are equally efficient
Neither works for this pattern

Analyse

✅ Answer: (C) For 01010101, shift-and-add does 4 additions (four 1s). Booth's sees transitions 01,10,01,10,01,10,01,10 → 4 subtracts + 4 adds = 8 operations! For alternating patterns, Booth's is actually worse. It excels with consecutive 1s.

Q22

In a processor with a 3 ns multiply and 12 ns divide, what is the multiplication-to-division speed ratio?

Analyse

✅ Answer: (A) Multiply is 4× faster than divide (12/3 = 4). This is why compilers often replace division by constants with multiplication by reciprocals.

Evaluate / Justify (Q23–Q26)

Q23

A designer must choose between a hardware multiplier (costs 10,000 gates, 1 cycle) and software multiplication (0 extra gates, 32 cycles). For a real-time audio DSP processing 44,100 samples/sec, which is justified?

Software — saves chip area
Hardware — 32-cycle latency would miss the real-time deadline
Either works equally well
Use a lookup table instead

Evaluate

✅ Answer: (B) At 44.1 kHz sample rate, each sample must be processed within ~22.7 μs. With multiple multiplies per sample, 32-cycle software multiply creates unacceptable latency. Hardware multiplier is essential for real-time DSP.

Q24

IEEE 754 has both +0 and −0. This causes problems for which operation?

Addition
Comparison (is −0 == +0?)
Multiplication
Bit-shifting

Evaluate

✅ Answer: (B) IEEE 754 defines −0 == +0, but their bit patterns differ. This causes subtle bugs in comparison operations, especially in hash functions and sorting algorithms.

Q25

For ISRO's satellite orbit calculation requiring 15 significant decimal digits, which format is appropriate?

IEEE 754 single precision (32-bit)
IEEE 754 double precision (64-bit)
Fixed-point 16-bit
BCD (Binary-Coded Decimal)

Evaluate

✅ Answer: (B) Single precision gives ~7 decimal digits. Double precision gives ~15.9 digits — just enough for 15 significant digits. Single would lose critical precision in trajectory calculations.

Q26

A student claims "Booth's algorithm always performs fewer operations than shift-and-add." Is this correct?

Yes, always
No — for alternating bit patterns (like 010101), Booth's can do more operations
No — Booth's always does more operations
They always do the same number

Evaluate

✅ Answer: (B) Booth's excels when the multiplier has long runs of 1s (like 11111100) but performs poorly on alternating patterns (01010101) where every bit is a transition.

Create / Design (Q27–Q30)

Q27

To design an overflow detection circuit for an n-bit 2's complement adder, you need:

An AND gate on the two MSBs
An XOR gate between the carry-in and carry-out of the MSB position
A NOT gate on the result MSB
A comparator for the full result

Create

✅ Answer: (B) Overflow = C_{n-1} ⊕ C_n (XOR of carry into MSB and carry out of MSB). This requires just one XOR gate — very efficient!

Q28

You are designing a floating-point unit. To handle the special case of 0 ÷ 0, the output should be:

+0
+∞
NaN (Not a Number)
An error signal halting the CPU

Create

✅ Answer: (C) IEEE 754 mandates 0/0 = NaN. The FPU must generate the NaN bit pattern (exponent = all 1s, mantissa ≠ 0) rather than halting.

Q29

To optimise Booth's algorithm for a multiplier like 00111100, how many add/subtract operations are needed?

Create

✅ Answer: (B) The pattern 00111100 has one block of 1s. Booth's does: subtract at 0→1 transition (bit 2) and add at 1→0 transition (bit 6) → just 2 operations!

Q30

You need to design a divider that completes in exactly n cycles regardless of inputs. Which algorithm should you choose?

Restoring division
Non-restoring division
Repeated subtraction
Newton-Raphson division

Create

✅ Answer: (B) Non-restoring division always takes exactly n cycles (one operation per cycle). Restoring division's restore step is an extra operation that varies. Newton-Raphson converges iteratively (variable cycles).

Section G

Short Answer Questions (8)

SA1: What is 2's complement and why is it used?

2's complement is a binary number representation where negative numbers are obtained by inverting all bits of the positive form and adding 1. It is used because:

Single zero: Unlike sign-magnitude (which has +0 and −0), 2's complement has only one zero representation
Unified hardware: The same adder circuit handles both addition and subtraction (subtraction = adding the 2's complement)
Simple overflow detection: XOR of the last two carries gives the overflow flag

Example: −5 in 8-bit 2's complement: +5 = 00000101 → invert → 11111010 → +1 → 11111011

SA2: State the rules of Booth's algorithm. When does it add? When does it subtract?

Booth's algorithm examines two bits — the current LSB (QR₀) and the previous LSB (Q₋₁):

00 → No operation (middle of a block of 0s)
11 → No operation (middle of a block of 1s)
10 → Subtract multiplicand from AC (start of a block of 1s)
01 → Add multiplicand to AC (end of a block of 1s)

After the operation, perform arithmetic shift right (preserving sign bit) on {AC, QR, Q₋₁}. Repeat n times. Product = {AC, QR}.

SA3: How is overflow detected in 2's complement addition?

Overflow occurs when the carry into the MSB position (C_{n-1}) differs from the carry out of the MSB (C_n):

Overflow = C_{n-1} ⊕ C_n

Intuitively: overflow happens when adding two positive numbers gives a negative result, or adding two negative numbers gives a positive result. Adding numbers of different signs never overflows.

SA4: What is the difference between arithmetic shift right and logical shift right?

Logical Shift Right (LSR): Fills the vacated MSB with 0. Used for unsigned numbers.

Arithmetic Shift Right (ASR): Fills the vacated MSB with the sign bit (preserves the sign). Used for signed numbers.

Example: 11010 (−6 in 5-bit 2's complement)

LSR → 01101 (+13 — wrong! sign changed)
ASR → 11101 (−3 — correct! equivalent to ÷2 with rounding toward −∞)

Booth's algorithm must use ASR to maintain correctness with signed numbers.

SA5: Explain the IEEE 754 single-precision format with field sizes.

IEEE 754 single precision uses 32 bits divided into three fields:

Sign (S): 1 bit (bit 31). 0 = positive, 1 = negative.
Exponent (E): 8 bits (bits 30–23). Biased by 127. Actual exponent = E − 127.
Mantissa (M): 23 bits (bits 22–0). Stores the fractional part after an implicit leading 1.

Value = (−1)^S × 1.M × 2^(E−127)

Range: ≈ ±1.18 × 10⁻³⁸ to ±3.4 × 10³⁸. Precision: ~7 decimal digits.

SA6: Why is non-restoring division faster than restoring division?

In restoring division, when the partial remainder goes negative, two operations are needed: (1) restore (add divisor back) and (2) proceed to next step. This means some cycles need 2 additions.

In non-restoring division, when the partial remainder is negative, we skip the restore and instead add in the next step (rather than subtract). This ensures exactly one operation per cycle.

However, non-restoring may require a final correction step if the remainder is negative at the end.

SA7: What are NaN and Infinity in IEEE 754? Give examples of operations that produce them.

Infinity (∞): Exponent = all 1s (255), Mantissa = all 0s. Produced by: 1.0 ÷ 0.0 = +∞, overflow of a very large computation.

NaN (Not a Number): Exponent = all 1s (255), Mantissa ≠ 0. Produced by: 0.0 ÷ 0.0, √(−1), ∞ − ∞, ∞ × 0.

NaN has a special property: NaN ≠ NaN (it's not equal to anything, including itself). This is used in programming to detect invalid results: if (x != x) means x is NaN.

SA8: What is the "kirana shopkeeper" analogy for Booth's algorithm?

Imagine buying 9 packets of ₹100 biscuits. Method 1 (shift-and-add): add ₹100 nine times = 9 operations. Method 2 (Booth's): ₹1000 − ₹100 = ₹900 → only 2 operations (one add + one subtract).

Booth's algorithm uses the same trick: instead of adding the multiplicand for each consecutive 1 in the multiplier, it subtracts at the start of a block of 1s and adds at the end. For a multiplier like 01111110 (six consecutive 1s), shift-and-add does 6 additions, but Booth's does only 1 subtract + 1 add = 2 operations.

Section H

Long Answer Questions (3)

LA1: Explain Booth's Algorithm with a complete trace for (−7) × (5). Draw the hardware block diagram. (10 marks)

Introduction: Booth's algorithm (1951) handles signed binary multiplication by detecting transitions in multiplier bits. It operates on 2's complement numbers and uses arithmetic shift right.

Hardware Components:

AC (Accumulator): n-bit register, initialized to 0
QR (Multiplier Register): holds the multiplier
Q₋₁: 1-bit flip-flop, initialized to 0
BR (Multiplicand Register): holds the multiplicand
SC (Sequence Counter): counts down from n
Adder/Subtractor: performs AC ± BR

Algorithm:

Check QR₀ and Q₋₁: (1,0)→subtract, (0,1)→add, (0,0)/(1,1)→NOP
Arithmetic shift right {AC, QR, Q₋₁}
Decrement SC. Repeat until SC = 0.

Trace for (−7) × 5:

BR = +5 = 01001 (5-bit), QR = −7 = 11001, −BR = 10111

Step	AC	QR	Q₋₁	{QR₀,Q₋₁}	Operation
Init	00000	11001	0	1,0	—
1	10111	11001	0	—	AC−BR (subtract)
1 ASR	11011	11100	1	0,1	Shift right
2	00100	11100	1	—	AC+BR (add)
2 ASR	00010	01110	0	0,0	Shift right
3	00010	01110	0	—	NOP
3 ASR	00001	00111	0	1,0	Shift right
4	11100	00111	0	—	AC−BR (subtract)
4 ASR	11110	00011	1	1,1	Shift right
5	11110	00011	1	—	NOP
5 ASR	11111	00001	1	—	Shift right

Product = {AC,QR} = 11111 00001. Converting: invert 10-bit → 0000011110, +1 → 0000011111 = 31. Negative → −35.

Verification: −7 × 5 = −35 ✅

LA2: Compare Restoring and Non-Restoring Division with traced examples. (10 marks)

Restoring Division: After subtracting the divisor, if the partial remainder is negative, restore it by adding the divisor back. Set quotient bit = 0.

Non-Restoring Division: Don't restore. If remainder is negative, add (instead of subtract) in the next step. Saves one operation per negative remainder.

Key Differences:

Aspect	Restoring	Non-Restoring
Operations/cycle (worst case)	2 (sub + restore)	1 (add or sub)
Control logic	Simpler	Needs sign-based decision
Speed	Slower	Faster
Final correction	Not needed	May need 1 restore at end

Example (7÷3) was traced in Section C. Both methods produce Quotient = 2, Remainder = 1. Non-restoring reaches the same answer with fewer total additions.

Hardware: Both use AC (accumulator), QR (dividend/quotient), BR (divisor), and a shift-left mechanism. Non-restoring adds a MUX to select between add/subtract based on AC's sign bit.

LA3: Explain IEEE 754 floating-point format. Convert −19.6875 to IEEE 754 single precision. (10 marks)

IEEE 754 Format: 32 bits = 1 sign + 8 exponent + 23 mantissa.

Value = (−1)^S × 1.M × 2^(E−127)

Conversion of −19.6875:

Step 1 — Sign: Negative → S = 1

Step 2 — Integer part: 19 = 10011₂

Step 3 — Fractional part: 0.6875:

0.6875 × 2 = 1.375 → 1
0.375 × 2 = 0.75 → 0
0.75 × 2 = 1.5 → 1
0.5 × 2 = 1.0 → 1

0.6875₁₀ = .1011₂

Step 4 — Combined: 19.6875 = 10011.1011₂

Step 5 — Normalise: 1.00111011 × 2⁴

Step 6 — Biased exponent: 4 + 127 = 131 = 10000011₂

Step 7 — Mantissa: 00111011000000000000000 (23 bits)

Final:

  1 | 10000011 | 00111011000000000000000
  S   Exponent   Mantissa

Hex: 0xC19D8000

Special Values: +∞ (E=FF, M=0), −∞ (S=1, E=FF, M=0), NaN (E=FF, M≠0), ±0 (E=0, M=0), Denormalised (E=0, M≠0, implicit 0. instead of 1.)

Section I

Industry Spotlight — A Day in the Life

👩‍💻 Ananya Rao, 29 — VLSI Design Engineer at ISRO Satellite Centre (URSC), Bangalore

Background: B.Tech ECE from NIT Trichy. Fascinated by computer architecture from 2nd year. Did an internship at CDAC Trivandrum working on processor design. Cleared ISRO Scientist/Engineer exam in 2019.

A Typical Day:

9:00 AM — Arrive at URSC, Bangalore. Morning team meeting to discuss progress on the onboard computer module for India's next Earth observation satellite.

10:00 AM — Working on the arithmetic logic unit (ALU) design in Verilog HDL. Today's task: optimise the Booth's multiplier for lower power consumption. "Space-grade processors must work on solar power — every milliwatt counts."

12:00 PM — Run gate-level simulation of the 32-bit multiplier. Verify timing meets the 50 MHz clock requirement. "The same Booth's algorithm I studied in COA class — now I'm implementing it in actual silicon."

2:00 PM — Lunch at the ISRO canteen. Discuss radiation-hardened design techniques with a senior engineer. Space processors face cosmic ray bit-flips!

3:00 PM — Design review with the verification team. They found a corner case: when both inputs are the most negative number (−2³¹), the multiplier output overflows. Need to add overflow detection logic.

5:30 PM — Document the design changes in the engineering notebook. Update the Verilog testbench with new test vectors.

6:30 PM — Study session for upcoming M.Tech entrance (ISRO sponsors higher education). Reading about IEEE 754 floating-point unit design for future satellite navigation systems.

Detail	Info
Tools Used Daily	Verilog HDL, Xilinx Vivado, ModelSim, MATLAB (for algorithm verification), Python
Entry Salary (ISRO SC/Engineer)	₹56,100/month (Level 10, 7th CPC) + DA + HRA ≈ ₹10–12 LPA
Mid-Level (5–8 yrs)	₹15–20 LPA + ISRO housing
Similar Roles	DRDO, CDAC, Qualcomm India (Hyderabad), Intel (Bangalore), Samsung Semiconductor
Key COA Topics Used	Booth's multiplication, ALU design, overflow detection, IEEE 754, pipeline hazards

ISRO recruits 150–200 engineers/year. COA, Digital Electronics, and Microprocessors are heavily tested. Students who can trace Booth's algorithm AND implement it in Verilog have a significant edge. The ISRO exam pattern is very similar to GATE.

Section J

Earn With It — GATE Coaching COA Section

💰 Your Earning Path: GATE Coaching — COA Arithmetic Section

Portfolio Piece: A comprehensive Computer Arithmetic study guide with hand-traced examples for Booth's, restoring division, and IEEE 754 — exactly what GATE aspirants pay ₹15,000–₹50,000 to coaching institutes for.

Earning Opportunities:

• Online tutoring: Teach COA arithmetic on Chegg/Doubtnut/Toppr — ₹500–₹1,500/hour for solving GATE-level numerical questions

• YouTube content: Create "Booth's Algorithm in 10 minutes" videos — monetisable at 10K+ subscribers

• Udemy course: "GATE COA: Computer Arithmetic Masterclass" — 50 numerical problems with video solutions, price ₹499–₹999

• Freelance content: Write COA study material for Unacademy/BYJU'S/Physics Wallah — ₹2,000–₹5,000 per chapter

Platform	What to Create	Earning Potential
Chegg / Bartleby	Solve COA numerical questions	₹200–₹500/question
YouTube	Booth's / IEEE 754 tutorials	₹5,000–₹20,000/month (at scale)
Udemy / Skillshare	Full COA arithmetic course	₹10,000–₹50,000/month
Instagram / Telegram	Daily GATE MCQ + solutions	Sponsorships ₹5,000–₹15,000/month
Freelance Writing	Study notes for coaching platforms	₹2,000–₹5,000/chapter

Quick win: Create a 1-page "Booth's Algorithm Cheat Sheet" as a PDF — include the rules table, one worked example, and common mistakes. Share it on Telegram GATE groups with a link to your Topmate/Instamojo for paid 1-on-1 doubt sessions (₹199–₹499/session).

Section K

Chapter Summary

🔑 Key Takeaways — Computer Arithmetic

1. 2's Complement

Negative numbers: invert all bits + add 1
Range (n bits): −2ⁿ⁻¹ to +2ⁿ⁻¹−1
Overflow = C_in(MSB) ⊕ C_out(MSB)
Same adder works for both addition and subtraction

2. Shift-and-Add Multiplication

For unsigned numbers only
Check LSB of multiplier: if 1 → add multiplicand; then shift right
Number of additions = number of 1s in multiplier
Product stored in {AC, QR}

3. Booth's Algorithm

Works for signed numbers (2's complement)
Examines bit pairs: (1,0)→subtract, (0,1)→add, others→NOP
Uses arithmetic shift right (sign-preserving)
Efficient for multipliers with consecutive 1s
Kirana shopkeeper analogy: 9×100 = 10×100 − 1×100

4. Restoring Division

Shift left, subtract divisor, check sign
If negative: restore (add back) + Q₀=0
If positive: Q₀=1
Verify: Dividend = Quotient × Divisor + Remainder

5. Non-Restoring Division

Skip restore; add (instead of subtract) next time if negative
Faster: exactly 1 operation per cycle
May need final correction

6. IEEE 754 Single Precision

32 bits: 1 sign + 8 exponent (bias 127) + 23 mantissa
Value = (−1)^S × 1.M × 2^(E−127)
Special: ∞ (E=FF,M=0), NaN (E=FF,M≠0), ±0 (E=0,M=0)
Implicit leading 1 gives 24-bit precision from 23-bit field

Formula Quick Reference

Formula	Usage
`−N = ~N + 1`	2's complement negation
`Overflow = C_{n-1} ⊕ C_n`	Overflow detection
`Biased Exp = Actual + 127`	IEEE 754 exponent encoding
`Value = (−1)^S × 1.M × 2^(E−127)`	IEEE 754 to decimal
`Dividend = Q × Divisor + R`	Division verification

Section L

Earning Checkpoint — Self Assessment

Skill	Practice Done?	Artefact Created	Earn-Ready?
2's Complement Conversions	Conceptual	Hand-traced examples	✅ Can solve GATE questions
Shift-and-Add Multiplication	Paper trace	Trace table for 5×7	✅ Can explain in tutorials
Booth's Algorithm	Paper + Python	Trace table + simulator code	✅ YouTube/Chegg content-ready
Restoring Division	Paper trace	Trace table for 7÷3	✅ Can teach doubt sessions
Non-Restoring Division	Paper trace	Comparison table	✅ GATE coaching material
IEEE 754 Conversion	Numerical practice	Step-by-step solutions	✅ Can create cheat sheets
Python Booth's Simulator	Coding lab	GitHub repository	✅ Portfolio piece for jobs

Minimum Viable Earning Setup after this chapter: A Booth's Algorithm cheat sheet PDF + 5 solved GATE numericals + a Telegram/Instagram page posting daily COA MCQs = you can earn ₹5,000–₹15,000/month from GATE aspirants while still in college.

✅ Unit 7 complete. You now understand how every CPU on Earth does arithmetic!

[QR: Link to EduArtha video tutorial — Computer Arithmetic Algorithms]