Unit 2: Arithmetic and Logic Unit 35 mins study timeINTERMEDIATE

Booth's Signed Multiplication Algorithm

Hardware-efficient multiplication algorithm that multiplies two signed binary numbers in two's complement notation by treating consecutive strings of 1s as single operations.

Verified: Faculty Peer Review Board

Learning Objectives

•Explain the mathematical rationale behind string-of-ones reduction in binary multiplication.
•Construct and trace the hardware register state machine: A, Q, Q-1, and M.
•Execute manual Booth multiplication for positive, negative, and mixed-sign operands.
•Differentiate between Logical Right Shift and Arithmetic Right Shift (ARS).
•Analyze why Booth's algorithm reduces the expected number of additions/subtractions.

Essential Prerequisites

•Binary 2's Complement representation and negation
•Binary Addition and Subtraction using 2's complement logic
•Basic register shift concepts in digital logic

🗣️ Hinglish Peer-Mentor Master Explanation

Booth's Algorithm - Negative Numbers ki Fast Multiplication

Senior Peer Mentor • 100% Humanized

🗣️ Asli Funda (Conversational Breakdown):

Normal school waali binary multiplication mein negative numbers aate hi dimaag kharab ho jaata hai, kyunki MSB bit 1 hone se value negative hoti hai. Andrew Booth ne 1950 mein ek mast trick nikali: Continuous 1s ke block ko baar-baar add karne ke bajaye, shuruat mein ek baar subtract karo aur end mein ek baar add karo! Jaise 99 se multiply karne ke liye 99 baar add mat karo, seedhe x * 100 karke ek baar x minus kar do. Booth's algorithm 2's complement mein naturally negative numbers ko bina kisi sign separation ke multiply kar deta hai.

☕ Real-Life Relatable Analogy:

Bhai socho tumhe kisi ko 99 rupaye dene hain. Ek-ek rupaye ke 99 sikke dene mein kitna time lagega? Smart banda 100 ka note dega aur 1 rupaya wapas maang lega. Exactly yahi Booth's algorithm karta hai binary 11111 ke saath!

📝 University Exam Scoring Funda:

Booth's ka 4-bit manual numerical solve karne ko aata hai (e.g. (+7) * (-3)). Rule hamesha yaad rakhna: Look at (Q0, Q-1): Agar '10' hai toh A = A - M, agar '01' hai toh A = A + M, agar '00' ya '11' hai toh no operation. Aur har cycle ke baad ARS (Arithmetic Right Shift) lagana mat bhoolna, jismein MSB sign bit copy hoti hai!

🎯 Tech Interviewer Trap / Gotcha:

Why Arithmetic Right Shift (ARS) instead of Logical Right Shift? Interviewer yahi trap set karta hai. Bolo: 'Logical shift MSB mein 0 daal deta hai jo negative number ka sign badal kar usse positive bana dega! ARS MSB sign bit ko preserve karta hai taaki 2's complement arithmetic mathematically accurate rahe.'

⚡ 1-Line Revision Rule:(Q0, Q-1) dekho: 10 pe minus, 01 pe plus, 00/11 pe pass, aur har step pe ARS!

Layer 1: Intuition & Why It Matters

The Core Mental Model

“Think of multiplying by 99 in decimal. Instead of adding a number 99 times, you can multiply by 100 and subtract once: (x * 100) - x. Booth's algorithm does the exact same thing in binary for blocks of 1s.”

Why This Exists

Standard binary multiplication performs an addition for every bit '1' in the multiplier. Andrew Donald Booth realized in 1950 that 011110 = 100000 - 000010 (i.e. 2^5 - 2^1). Booth's algorithm replaces a sequence of repeated additions with a single subtraction at the start and a single addition at the end.

Beginner Foundation

When we multiply signed binary numbers, negative numbers normally cause havoc because regular shift-and-add treats MSB 1 as large positive value instead of negative. Booth's algorithm handles both positive and negative operands natively using an extra 1-bit register called Q-1 and an Arithmetic Shift that keeps the negative sign intact.

Micro Concepts Decomposition

MICRO CONCEPT 1Canonical Object

Two's Complement Signed Representation

Negative numbers are represented by taking the 1's complement and adding 1. Booth's algorithm operates directly on 2's complement operands without requiring sign separation.

Key Takeaway: Booth's algorithm works natively on signed negative numbers without manual sign corrections.

MICRO CONCEPT 2Canonical Object

Register Configuration (A, Q, Q-1, M)

A is the Accumulator initialized to 0. Q holds the Multiplier. Q-1 is a single flip-flop initialized to 0 to store the bit shifted out of Q0. M holds the Multiplicand.

Key Takeaway: Hardware register width: A has n bits, Q has n bits, M has n bits, Q-1 has 1 bit.

MICRO CONCEPT 3Canonical Object

Inspection Condition Table (Q0, Q-1)

Examine the least significant bit of Q (Q0) and Q-1: '10' implies transition from 0 to 1 -> A = A - M; '01' implies transition from 1 to 0 -> A = A + M; '00' and '11' imply no arithmetic change.

Key Takeaway: 10 means subtract M, 01 means add M, 00/11 means no arithmetic operation.

MICRO CONCEPT 4Canonical Object

Arithmetic Right Shift (ARS)

ARS shifts bits of [A, Q, Q-1] right by 1 position. Crucially, the most significant bit (MSB) of A remains unchanged to preserve the sign (sign-extension).

Key Takeaway: Arithmetic shift preserves sign: A[n-1] duplicates itself into the new MSB.

MICRO CONCEPT 5Canonical Object

Iteration Count and Termination

The cycle repeats exactly n times, where n is the number of bits in the multiplier. The final 2n-bit product is stored across concatenated registers A and Q.

Key Takeaway: Total product is read from [A concatenated with Q] after exactly n cycles.

Layer 3 & 4: Formal Specification & Mechanism

Hardware State Machine Architecture

Booth's algorithm multiplies signed integers in 2's complement representation. Hardware components: Accumulator Register A (n bits, initialized to 0), Multiplier Register Q (n bits), Extra Flip-Flop Q-1 (1 bit, initialized to 0), Multiplicand Register M (n bits), Sequence Counter SC (initialized to n).

Step-by-step Hardware State Machine: 1. Initialize: A = 0...0, Q-1 = 0, SC = n. Load M and Q. 2. Calculate -M in two's complement. 3. Examine (Q0, Q-1): 10 -> A = A - M; 01 -> A = A + M; 00/11 -> Pass. 4. Shift Phase: Perform Arithmetic Right Shift (ARS) on [A, Q, Q-1]. Sign bit duplicated at MSB. 5. Decrement SC = SC - 1. If SC > 0, repeat. Otherwise HALT.

Layer 7: Interactive Laboratory

Interactive Simulator

COA • SIMULATIONInteractive Booth's Multiplier Laboratory

Launch Fullscreen Lab

Interactive Hardware VisualizerRadix-2 Booth Architecture

Booth's Signed Multiplier State Machine

Inspect register transitions, arithmetic operations, and sign-preserving arithmetic right shifts in real-time.

Presets:

Multiplicand (M) [Decimal]

= 0111₂

Multiplier (Q) [Decimal]

= 1101₂

Bit Width (n)

Accumulator [A]4 bits

Positive sign

Multiplier [Q]4 bits

Q₀ = 0 (Inspected Bit)

Transition Register [Q₋₁]1 bit

Window (Q₀, Q₋₁) = (00)

Hardware ConstantsCycle 0/4

M (+7):0000

-M (2's comp):0000

Sequence Counter:4

Status: Ready

What is happening right now?

Configure operands and start the simulator.

Why did this transition occur?

Booth's algorithm state machine visualizer.

Step 1 of 0

Speed:

Step-by-Step Hardware Trace Log

Step	Cycle	Phase	Operation	A	Q	Q₋₁	SC

Layer 5: Step-by-Step Worked Numerical Example

End-to-End Execution Trace

Problem: Multiply (+7) by (-3) using 4-bit Booth's Algorithm. M = +7 = 0111, Q = -3 = 1101, -M = 1001. A = 0000, Q-1 = 0, SC = 4. Cycle 1: (1, 0) -> A = A - M -> 1001. ARS -> A = 1100, Q = 1110, Q-1 = 1 | SC = 3. Cycle 2: (0, 1) -> A = A + M -> 0011. ARS -> A = 0001, Q = 1111, Q-1 = 0 | SC = 2. Cycle 3: (1, 0) -> A = A - M -> 1010. ARS -> A = 1101, Q = 0111, Q-1 = 1 | SC = 1. Cycle 4: (1, 1) -> Pass. ARS -> A = 1110, Q = 1011, Q-1 = 1 | SC = 0. Result: {A, Q} = 1110 1011 = -21 in decimal. Correct!

Layer 6: Active Runtime CodeLab

Step-by-Step Code Execution (C)

AURXON Sandbox

AURXON Digital Engine

Font

main.cGlacier Light

Ln 1 • GCC 13

// Clean C Implementation of Booth's Multiplication Algorithm
#include <stdio.h>
 
int boothsMultiply(int M, int Q, int n) {
    int mask = (1 << n) - 1;
    M = M & mask;
    Q = Q & mask;
    int A = 0;
    int Q_minus_1 = 0;
 
    for (int step = 1; step <= n; step++) {
        int Q0 = Q & 1;
        if (Q0 == 1 && Q_minus_1 == 0) {
            A = (A - M) & mask;
        } else if (Q0 == 0 && Q_minus_1 == 1) {
            A = (A + M) & mask;
        }
        int new_Q_minus_1 = Q0;
        int lsb_A = A & 1;
        Q = (Q >> 1) | (lsb_A << (n - 1));
        int msb_A = (A >> (n - 1)) & 1;
        A = (A >> 1) | (msb_A << (n - 1));
        Q_minus_1 = new_Q_minus_1;
    }
    return (A << n) | Q;
}

711 chars • 27 lines • Ln 1UTF-8 • 4 Spaces

Interactive Terminal Shell

Sandbox Terminal Ready

Click Run Code or press Ctrl+Enter to compile and execute.

Common Student Pitfalls & Mistakes

Where Students Lose Marks

❌ Mistake: Performing a Logical Right Shift instead of an Arithmetic Right Shift.

✓ Correct Understanding: Logical shift inserts a 0 at the MSB, which turns negative numbers into positive garbage. ARS duplicates the sign bit (A[n-1]).

❌ Mistake: Forgetting to initialize Q-1 to 0 at the beginning.

✓ Correct Understanding: Q-1 is the history flip-flop tracking transitions. It must start at 0.

Layer 8: Practice & Knowledge Verification

Active Assessment Quiz

Interactive Assessment EngineQuestion 1 of 2

Booth's Signed Multiplication Algorithm — Practice Questions

FOUNDATION LevelScore: 0/0

In Booth's algorithm, what arithmetic action is performed when the two inspection bits (Q0, Q-1) are '10'?

Academic Evaluation Preparation

Viva Examination & University Scoring Strategy

Standard Viva Examination Questions

Q1: Why is Booth's algorithm preferred over conventional shift-and-add for signed numbers?

Answer: Because it naturally operates directly on 2's complement numbers without converting them to positive magnitudes and fixing signs later.

How to Write High-Scoring University Exam Answers

Draw register block diagram, state condition table (10: subtract, 01: add, 00/11: shift), show numerical table with iterations and ARS shifts, verify result.