L16: Multipliers#

Let’s practice Boolean algebra!

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

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