Binary Multipliers

Hardware multiplication using array multipliers and shift-and-add algorithms.

Binary multiplication follows the same pencil-and-paper method as decimal multiplication: generate partial products, then add them together. The array multiplier implements this directly in hardware using AND gates for partial products and adders for accumulation. The shift-and-add method trades area for time, processing one bit per clock cycle.

Objectives

  • Perform binary multiplication by hand (partial products method)
  • Design an array multiplier from AND gates and adders
  • Understand the shift-and-add algorithm
  • Compare array multiplier (fast, large) vs. shift-and-add (slow, small)
  • Introduction to Booth's algorithm for signed multiplication

Key Takeaways

  • Binary multiplication uses partial products (AND) followed by addition
  • Array multiplier: fast (combinational) but uses N² AND gates + many adders
  • Shift-and-add: slow (N cycles) but uses minimal hardware (one adder + registers)
  • N×N multiplication produces a 2N-bit result
  • Booth's algorithm optimizes signed multiplication by reducing additions

Applications

  • CPU Multiply Instructions: Hardware multipliers in processor ALUs.
  • DSP Filters: Multiply-accumulate (MAC) operations in signal processing.
  • Graphics: Matrix multiplication for 3D transformations.

Practice Problems

Problem 1: Multiply 0101 × 0011 (5 × 3) using the partial products method.

Problem 2: How many AND gates does a 4×4 array multiplier need?

Problem 3: How many clock cycles does a shift-and-add multiplier need for 8×8 bit multiplication?

Problem 4: What is the output width of a 16×16 bit multiplier?