Skip to content

Multipliers#

Definition: Multiplier

An \(n\times n\)-multiplier is a digital circuit which calculates the \(2n\)-bit product of two unsigned \(n\)-bit binary integers.

Integer Multipliers#

Array Multiplier#

A multiplier can be implemented via a combinational circuit which computes the following algorithm:

Algorithm: Multiplication of Unsigned \(n\)-bit Binary Integers

We want to compute the product \(A \cdot B\) of two \(n\)-bit unsigned binary integers \(A = a_{n-1} \cdots a_0\) and \(B = b_{n - 1}\cdots b_0\).

  1. We compute \(n\) partial products \(C_{n-1}, \dotsc, C_0\), where the \(j\)-th bit \(C_{k,j}\) of \(C_k\) is given by the following product:
\[ C_{k, j} = a_k \cdot b_j \]
  1. We bit-shift the \(k\)-th partial product \(C_k\) to the left by \(k\) bits, adding trailing \(0\)s to obtain \(C_k'\).
  2. The final product is the sum of the bit-shifted partial products:
\[ A \cdot B = \sum_{k = 0}^{n-1} C_k' \]

Combinational Multiplication Algorithm

At the bit level, multiplication is equivalent to a conjunction:

\(a\) \(b\) \(a \cdot b\)
\(0\) \(0\) \(0\)
\(1\) \(0\) \(0\)
\(0\) \(1\) \(0\)
\(1\) \(1\) \(1\)

We can thus compute the above algorithm using AND gates and adders:

Example: \(4\times 4\)-Multiplier (Combinational)

Combinational Multiplier

Combinational multipliers are expensive and slow because they require \(\approx n^2\) gates for computing the product of two \(n\)-bit numbers.

Sequential Multipliers#

We can also implement multipliers via a sequential circuit.

Algorithm: Sequential Multiplication Algorithm

We want to compute the product of two \(n\)-bit unsigned binary integers \(A = A[n-1] \cdots A[0]\) and \(B = B[n - 1] \cdots B[0]\).

  1. Initialize a \((2n+1)\)-bit number \(PR\) by padding \(B\) with \(n+1\) leading zeros, i.e. \(PR \leftarrow \underset{n+1}{\underbrace{0\cdots0}}B[n - 1] \cdots B[0]\).
  2. Check the least significant bit of \(PR\):
    - If \(PR[0] = 1\), then add \(PR[2n] PR[2n - 1] \cdots PR[n]\) to \(A\) and store the result in \(PR[2n+1] PR[2n] \cdots PR[n]\). Shift \(PR\) one bit to the right, filling the gap with a zero.
\[ \begin{aligned} &PR[2n+1] PR[2n] \cdots PR[n] \leftarrow A + PR[2n] PR[2n - 1] \cdots PR[n] \\ &PR \leftarrow \operatorname{ShiftRight}(PR, 1) \end{aligned} \]
  • If \(PR[0] = 0\), then just shift \(PR\) one bit to the right, filling the gap with a zero.
\[ PR \leftarrow \operatorname{ShiftRight}(PR, 1) \]
  1. Repeat Step 2 \(n\) times. At the end, \(PR\) will contain the product of \(A\) and \(B\).

This algorithm can be realized using a \((2n+1)\)-bit parallel right shift register for \(PR\), a register for the multiplicand, an adder, two multiplexers and some control circuitry:

Sequential Multiplier Circuit

The control circuitry is responsible for realizing the following state machine:

Sequential Multiplier State Machine

This can be implemented fairly easily. First, we assign a unique number to each state:

State Number
Initialization 1 0
Initialization 2 1
Addition 1 2
Addition 2 3
Shift 1 4
Shift 2 5
Finished 6

We need a 3-bit register \(\text{State}\) to store the number of the circuit's current state and a \(\lceil \log_2 n \rceil\)-bit register \(\text{Round}\) to store the current round. The four outputs of the control circuit are \(\text{clk\_product}\), \(\overline{\text{init}}\text{ / shift}\), \(\text{multiplexer}\) and \(\text{clk\_multiplicand}\) and they can be determined using a multiplexer which switches on the \(\text{State}\) register:

Sequential Multiplier Control 1

The xs indicate that the value is irrelevant - we can choose either \(0\) or \(1\) and nothing would change.

We also need circuitry which the determines the next value of the \(\text{State}\) register. To achieve this, we construct the transition table of the state machine:

Current State \(PR[0]\) \(\text{Round}_n\) Next State
Initialization 1 Irrelevant Irrelevant Initialization 2
Initialization 2 0 Irrelevant Shift 1
Initialization 2 1 Irrelevant Addition 1
Addition 1 Irrelevant Irrelevant Addition 2
Addition 2 Irrelevant Irrelevant Shift 1
Shift 1 Irrelevant Irrelevant Shift 2
Shift 2 \(0\) \(0\) Shift 1
Shift 2 \(1\) \(0\) Addition 1
Shift 2 Irrelevant \(1\) Finished

Apart from Initialization 2 and Shift 1, each state has only one possible next state. This means that a multiplexer is a good candidate for determining the next state based on the current state:

Sequential Multiplier State Transition Circuit

The last thing we need to implement is circuitry which increments the \(\text{Round}\) register. We want this to happen whenever we are in the Shift 1 state:

Sequential Multiplier Round Incrementer