L16: Multipliers

Let’s practice Boolean algebra!

Objective
Practice usage of theorems 5-17 of Boolean algebra.

Additional Materials & Formats
Check Box for the most up-to-date versions of this lecture’s materials.

Before the Lecture

Required Textbook Reading:

3.6 (Multiplication)

Optional Supplemental Instruction:

Binary Multiplication – slide deck
A Signed Binary Multiplication Technique – Academic paper from 1951 on signed multiplication

Boolean Multipliers

A Boolean multiplier is a digital circuit that performs multiplication of binary numbers. Unlike addition, multiplication is more complex and requires multiple partial products.

Basic Multiplication Principle

Binary multiplication follows the same principles as decimal multiplication:

Multiply the multiplicand by each bit of the multiplier
Shift partial products by appropriate positions
Add all partial products

For example, multiplying 5 × 3:

    101 (5)
  ×  11 (3)
  ------
    101 (5 × 1)
   1010 (5 × 2, shifted)
  ------
  1111 (15)

Array Multipliers for Unsigned Numbers

An array multiplier (also called parallel multiplier) implements multiplication using a grid of AND gates and adders arranged in an array structure.

Structure

For an $m$-bit multiplicand and $n$-bit multiplier:

Create $n$ rows of partial products
Each row uses $m$ AND gates to multiply the multiplicand by one multiplier bit
Use adder arrays to sum all partial products in parallel

4×4 Array Multiplier Example

For multiplying two 4-bit unsigned numbers $A = a_3a_2a_1a_0$ and $B = b_3b_2b_1b_0$:

Partial Products:

Row 0: AND gates produce ${a_i \cdot b_0}$ for $i = 0..3$
Row 1: AND gates produce ${a_i \cdot b_1}$ for $i = 0..3$ (shifted left by 1)
Row 2: AND gates produce ${a_i \cdot b_2}$ for $i = 0..3$ (shifted left by 2)
Row 3: AND gates produce ${a_i \cdot b_3}$ for $i = 0..3$ (shifted left by 3)

Addition Stage: Multiple adders arranged in columns sum the partial products to produce the 8-bit result.

Advantages and Disadvantages

Advantages:

Fully parallel operation - all partial products computed simultaneously
Regular, modular structure easy to layout in VLSI
Predictable delay (logarithmic in number of adders)

Disadvantages:

Area grows as $O(m \times n)$ for $m \times n$ multiplier
Requires many adders, consuming significant silicon area

Discussion & Practice
As a class, let’s work through the examples in 3.6.1.

Multiplication of Signed Numbers

Discussion & Practice
As a class, let’s work through 3.6.2.

Signed binary numbers require special handling in multiplication. Two primary methods are used:

Sign-Magnitude Multiplication

For sign-magnitude representation:

Multiply the magnitudes using unsigned multiplication
Determine the sign: positive if signs match, negative if signs differ
Apply the sign to the product

Steps:

Extract sign bits and magnitudes
Multiply magnitudes as unsigned numbers
Combine result with computed sign bit

Two’s Complement Multiplication (Baugh-Wooley Algorithm)

The Baugh-Wooley algorithm efficiently handles two’s complement multiplication without converting to positive numbers.

Key Idea: Modify partial products based on bit significance:

For the most significant bit (MSB) of the multiplier and multiplicand: negate the partial product
All other bits: compute standard AND operations

Modified Partial Products: For multiplying $A$ (multiplicand) by $B$ (multiplier), each row $i$:

If $i < n-1$: compute $a_j \cdot b_i$ normally
If $i = n-1$: compute $\overline{a_j} \cdot b_{n-1}$ (NOT $a_j$ AND $b_{n-1}$)

Similarly for columns:

If $j < m-1$: use normal products
If $j = m-1$: use negated products

Advantages:

Works directly with two’s complement without sign extension
Reduces complexity compared to separate sign handling
Hardware can be optimized for this specific operation

Wallace Tree Alternative

For high-speed signed multiplication:

Wallace tree multipliers use parallel arrays of adders to reduce partial products faster
Particularly effective for larger multiplier widths
Combines partial products using a tree structure of adders
Reduces delay to $O(\log^2 n)$

Implementation Considerations

Performance Metrics:

Delay: Time from inputs to valid output
Area: Silicon area required
Power: Dynamic and static power consumption

Design Trade-offs:

Array multipliers: simple, regular, but large area
Wallace trees: faster, but more complex layout
Serial multipliers: small area, but slow
Pipelined multipliers: moderate area/delay, good throughput