Unit 2: Arithmetic and Logic Unit 40 mins study timeADVANCED

Booth's Signed Multiplication Algorithm and Hardware Architecture

Hardware multiplier architecture for 2's complement signed binary arithmetic without sign-extension blowup.

Verified: Karann

Learning Objectives

Essential Prerequisites

Layer 1: Intuition & Why It Matters

The Core Mental Model

“Agar aapko kisi number ko 7 se multiply karna ho: M * 7. Normal tareeke me aap M ko 7 baar add karenge, ya 3 additions karenge (M*4 + M*2 + M*1). Par smart trick kya hai? 7 = (8 - 1). Yani M ko 8 se multiply karo (3 bit left shift) aur 1 baar M subtract kar do! (M << 3) - M. 3 additions ke bajaye sirf 1 subtraction aur 1 shift! Booth's Algorithm theek yahi trick binary numbers ke saath karta hai: Jab bhi 1s ka block aata hai (jaise 0111), yeh block ke shuruat me subtract karta hai aur block ke khatam hone par add karta hai. Isse signed 2's complement multiplication hardware me bina kisi extra sign correction ke direct execute ho jaati hai.”

Why This Exists

Modern CPUs jaise Intel Core aur Apple M-series me arithmetic operations per clock cycle billions of times execute hoti hain. Booth algorithm signed numbers ko efficiently multiply karta hai aur contiguous 1s ki strings ko single addition aur subtraction me convert karke execution cycles drastically reduce karta hai.

Beginner Foundation

Booth's algorithm 2's complement signed binary numbers ko multiply karne ke liye 4 registers use karta hai: 1. M (Multiplicand): Pehla number jise multiply karna hai. 2. Q (Multiplier): Doosra number. 3. A (Accumulator): Result ka high-order register, initially 0. 4. Q-1: Ek 1-bit extra flip-flop register, initially 0. Har cycle me hum Q ki last bit (Q0) aur Q-1 ko check karte hain: - 10: A = A - M, fir Arithmetic Right Shift - 01: A = A + M, fir Arithmetic Right Shift - 00 ya 11: No operation, sirf Arithmetic Right Shift Yeh process N cycles (bits count) tak chalta hai.

Micro Concepts Decomposition

MICRO CONCEPT 1Canonical Object

Booth Recoding Table (00, 01, 10, 11)

10 triggers subtraction (-M), 01 triggers addition (+M), 00 and 11 trigger no addition.

Key Takeaway: Detects transition boundaries between 0s and 1s.

MICRO CONCEPT 2Canonical Object

Arithmetic Shift Right (ASHR)

ASHR right shifts all bits but replicates the sign bit (MSB) to preserve 2's complement value.

Key Takeaway: Sign bit is preserved during ASHR.

MICRO CONCEPT 3Canonical Object

Hardware Register Datapath

Registers A, Q, and Q-1 act as a continuous shift register of length 2n + 1 bits.

Key Takeaway: Combined shift register preserves full 2n-bit product.

Layer 3 & 4: Formal Specification & Mechanism

Hardware State Machine Architecture

Formal Booth's Recoding Theorem: For an n-bit 2's complement multiplier Q = -q_{n-1}2^{n-1} + sum_{i=0}^{n-2} q_i 2^i, the value can be algebraically transformed into: Q = sum_{i=0}^{n-1} (q_{i-1} - q_i) 2^i (where q_{-1} = 0). Thus each bit-pair (q_i, q_{i-1}) maps to a digit in {-1, 0, +1}. Arithmetic Right Shift (ASHR) preserves the most significant bit (Sign Bit MSB): A_{n-1} remains invariant during the shift, guaranteeing 2's complement mathematical sign preservation.

Step 1: Initialization - Load Multiplicand into M register (n bits). - Load Multiplier into Q register (n bits). - Initialize Accumulator A = 0000 (n bits). - Initialize Q-1 = 0 (1 bit). - Initialize Count = n. Step 2: Decision Table Inspection Examine the pair (Q0, Q-1): - If 10: A = A + 2's complement of M (A - M) - If 01: A = A + M - If 00 or 11: Do nothing. Step 3: Arithmetic Shift Right (ASHR) Shift the combined register [A, Q, Q-1] right by 1 position: - The MSB of A is preserved (A[n-1] -> A[n-1] and A[n-2]). - A[0] shifts into Q[n-1]. - Q[0] shifts into Q-1. - Old Q-1 is discarded. Step 4: Decrement Count Count = Count - 1. If Count > 0, return to Step 2. If Count == 0, stop. The 2n-bit result is contained in [A : Q].

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

Worked Numerical Problem: Multiply M = +7 (0111) and Q = -3 (1101 in 2's complement), n = 4 bits. -M in 2's complement = 1001. Initial State: A = 0000, Q = 1101, Q-1 = 0, Count = 4 Cycle 1: Q0=1, Q-1=0 -> Action: A = A - M = 0000 + 1001 = 1001 ASHR: A = 1100, Q = 1110, Q-1 = 1, Count = 3 Cycle 2: Q0=0, Q-1=1 -> Action: A = A + M = 1100 + 0111 = 0011 ASHR: A = 0001, Q = 1111, Q-1 = 0, Count = 2 Cycle 3: Q0=1, Q-1=0 -> Action: A = A - M = 0001 + 1001 = 1010 ASHR: A = 1101, Q = 0111, Q-1 = 1, Count = 1 Cycle 4: Q0=1, Q-1=1 -> Action: No Op ASHR: A = 1110, Q = 1011, Q-1 = 1, Count = 0 Final Output in [A : Q] = 1110 1011 in 2's complement. Verification: 11101011 in 2's complement = -(00010100 + 1) = -(00010101) = -21 Decimal. (+7 * -3 = -21) -> 100% 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

#include <stdio.h>
 
// Booth's multiplication simulator in C
long long boothMultiply(int m, int q, int n) {
    long long A = 0;
    long long Q = q & ((1LL << n) - 1);
    long long M = m & ((1LL << n) - 1);
    int q_minus_1 = 0;
    
    for (int i = 0; i < n; i++) {
        int q0 = Q & 1;
        if (q0 == 1 && q_minus_1 == 0) {
            A = A - m;
        } else if (q0 == 0 && q_minus_1 == 1) {
            A = A + m;
        }
        
        // Arithmetic Right Shift of [A : Q : q_minus_1]
        q_minus_1 = Q & 1;
        Q = (Q >> 1) | ((A & 1) << (n - 1));
        // Arithmetic shift on A preserving sign
        int sign = (A >> (n - 1)) & 1;
        A = (A >> 1) | (sign << (n - 1));
    }
    return (A << n) | Q;
}
 
int main() {
    int m = 7, q = -3;
    printf("Multiplicand: %d, Multiplier: %d\n", m, q);
    printf("Product (+7 * -3): %d\n", m * q);
    return 0;
}

895 chars • 34 lines • Ln 1UTF-8 • 4 Spaces

Interactive Terminal Shell

Sandbox Terminal Ready

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

⚡ AURXON Bitstream Runtime v4.8IDRAS Academic Virtual Node

Layer 8: Practice & Knowledge Verification

Active Assessment Quiz

No Practice Questions Configured

Questions for this topic are currently undergoing faculty review.

Academic Evaluation Preparation

Viva Examination & University Scoring Strategy

Standard Viva Examination Questions

How to Write High-Scoring University Exam Answers

Formal 10-Mark University Answer Structure: 1. Problem Statement: Difficulties of signed multiplication in standard binary logic. 2. Principle of Booth's Algorithm: Recoding strings of 1s to single additions and subtractions. 3. Hardware Register Block Diagram (A, M, Q, Q-1, ALU, Control Sequencer). 4. Step-by-Step Flowchart. 5. Full Numerical Walkthrough: Step-by-step table showing Cycle, Q0 Q-1, Operation, Registers [A : Q : Q-1]. 6. Complexity Analysis: Worst-case, Best-case (alternating 01 vs contiguous 1s).