🔢 Multiplication Algorithms

Computer System Architecture - Section 10.3

📚 Introduction

Multiplication in digital computers is implemented through a sequence of shift and add microoperations. This section explores three fundamental approaches to hardware multiplication for fixed-point binary numbers, each with unique advantages in terms of speed, efficiency, and complexity.

1

Signed-Magnitude Multiplication

▼

Core Concept

Simulates traditional manual binary multiplication through repeated additions and shifts, working with magnitude values separately from sign bits.

Key Principles

  • Sign Determination: Product sign is determined by XOR of operand signs (same signs → positive, different signs → negative)
  • Iterative Process: Examines multiplier bits sequentially; adds multiplicand if bit is 1, skips if bit is 0
  • Shifting Operations: Partial product shifts after each bit examination to align with next bit weight
  • Double-Width Registers: Product of two n-bit numbers requires 2n bits (typically A and Q registers)
Simple Implementation Sequential Processing

Example: 5 × 3 (Binary: 101 × 011)

2

Booth Multiplication Algorithm

▼

Core Concept

Highly efficient method for multiplying binary numbers in signed-2's complement form, particularly effective with long strings of consecutive 1's or 0's.

Key Advantages

  • Direct Negative Handling: Works directly with 2's complement without separating sign and magnitude
  • String Skipping: Efficiently processes consecutive 1's or 0's with fewer operations
  • Reduced Operations: Uses subtraction and addition based on bit patterns

Operation Logic

Bit Pattern (Qᵢ, Qᵢ₋₁) Action
00 Shift only (no arithmetic)
01 Add multiplicand to partial product
10 Subtract multiplicand (add 2's complement)
11 Shift only (no arithmetic)
Highly Efficient 2's Complement Support

Optimal for: Multipliers with consecutive bit patterns

3

Array Multiplier

▼

Core Concept

Purely combinational logic circuit designed for maximum speed through parallel processing. Trades hardware complexity for performance.

Key Characteristics

  • Parallel Architecture: All partial products calculated simultaneously using interconnected logic gates
  • Combinational Logic: No sequential elements; multiplication completes in propagation delay time
  • High-Speed Performance: Significantly faster than iterative methods
  • Hardware Trade-off: Requires extensive gate arrays and interconnections
Fastest Method High Hardware Cost

Perfect for: High-performance applications requiring minimal latency

⚖️ Quick Comparison

Algorithm Speed Hardware Best Use Case
Signed-Magnitude Moderate Simple General-purpose, educational
Booth Algorithm Efficient Moderate 2's complement systems, string patterns
Array Multiplier Fastest Complex High-speed applications, real-time processing