12.2  Statically Encoded Multiplier Arrays

In a practical implementation of the algorithm described above, although the coefficients $ \theta_i$ are not actually computed arithmetically as suggested by Definition 12.1.1, some combinational logic is required to derive an encoding of each $ \theta_i$ from the corresponding multiplier bits $ y[2i+1:2i-1]$. If the value of the multiplier is known in advance, i.e., at design time, then these encoded values may be stored instead of the multiplier itself, thereby saving the time and hardware associated with the encoding logic. However, since the range of $ \theta_i$ consists of 5 values, 3 bits are required for each encoding, and therefore $ 3m$ bits in total, as compared to $ 2m$ bits for unencoded multiplier. For a single multiplier, this is a negligible expense, but if the multiplier is to be selected from a array of vectors, then the penalty incurred by such static encoding could be a $ 50\%$ increase in the size of a large ROM.

In this chapter. we present an alternative encoding scheme that involves 4 rather than 5 encoded values, which allows 2-bit encodings and thereby eliminates any increase in space incurred by statically encoded arrays. Again we assume that the multiplicand $ x$ is an $ (n-1)$-bit vector, but the bound on the multiplier is weakened, requiring only that

$\displaystyle y \leq \sum_{i=0}^{m-1}{2^{2i+1}} = 2(2^{2m}-1)/3,$

which implies that $ y$ is a $ 2m$-bit vector. Under this scheme, the coefficients $ \theta_i$ are replaced with the values $ \phi_i$ defined below. Note that the recursive nature of this definition precludes parallel computation of the $ m$ values. Consequently, this technique is not suitable for designs that require dynamic encoding.

The definition of $ \phi_i$ involves a pair of mutually recursive auxiliary functions.

Definition 12.2.1   (mu, chi) For all $ y \in \mathbb{N}$ and $ i \in \mathbb{N}$,

$\displaystyle \mu_i(y) = y[2i+1:2i] + \chi_i(y),$

where

$\displaystyle \chi_i(y) = \left\{\begin{array}{ll}
1 & \mbox{if $i>0$ and $\mu_{i-1}(y) \geq 3$}\\
0 & \mbox{otherwise.}\end{array} \right.$

Definition 12.2.2   (phi) For all $ y \in \mathbb{N}$ and $ i \in \mathbb{N}$,

$\displaystyle \phi_i(y) = \left\{\begin{array}{ll}
-1 & \mbox{if $\mu_i[1:0] = 3$}\\
\mu_i[1:0] & \mbox{if $\mu_i[1:0] \neq 3$,}\end{array} \right.$

where $ \mu_i = \mu_i(y).$

The requirement that $ \phi_i$ be limited to a set of 4 values is satisfied as an immediate consequence of the Definition 12.2.2. On the other hand, the proof that $ \phi_{m-1} \geq 0$ involves a nontrivial induction.

  (chi-m) Let $ y \in \mathbb{N}$ and $ m \in \mathbb{N}$. If $ y \leq \sum_{i=0}^{m-1}{2^{2i+1}}$, then $ \chi_m(y)$=0.

PROOF: Let $ \chi_i = \chi_i(y)$ and $ \mu_i = \mu_i(y)$. More generally, we shall prove that for $ 0 \leq k \leq m$, if $ y[2k-1:0] \leq \sum_{i=0}^{k-1}{2^{2i+1}}$, then $ \chi_k=0$. Assuming that the claim holds for some $ k$, $ 0 \leq k < m$, and proceeding by induction, we must show that if $ y[2k+1:0] \leq \sum_{i=0}^{k}{2^{2i+1}}$, then $ \chi_{k+1}=0$.

First, suppose that $ y[2k+1:2k] \leq 1$. Then

$\displaystyle \mu_k = y[2k+1:2k] + \chi_k \leq 1 + 1 < 3,$

and hence $ \chi_{k+1} =0.$

Thus, we may assume that $ y[2k+1:2k] \geq 2$. Since

$\displaystyle 2^{2k}y[2k+1:2k] + y[2k-1:0]$ $\displaystyle =$ $\displaystyle y[2k+1:0] \leq \sum_{i=0}^{k}{2^{2i+1}}$  
  $\displaystyle =$ $\displaystyle 2^{2k+1} + \sum_{i=0}^{k-1}{2^{2i+1}}$  
  $\displaystyle <$ $\displaystyle 2^{2k+1} + 2^{2k}$  
  $\displaystyle =$ $\displaystyle 2^{2k}\cdot 3,$  

we must have $ y[2k+1:2k] = 2$ and $ y[2k-1:0] \leq \sum_{i=0}^{k-1}{2^{2i+1}}$. Now, the inductive hypothesis yields $ \chi_k=0$. Hence,

$\displaystyle \mu_k = y[2k+1:2k] + \chi_k = 2+0 < 3,$

and once again, $ \chi_{k+1} =0.$ 


The desired result now follows from Lemma 12.2.1 and Definitions 12.2.1 and 12.2.2.

Corollary 12.2.2   (phi-m-1) If $ y \leq \sum_{i=0}^{m-1}{2^{2i+1}}$, then $ \phi_{m-1} \geq 0$.

Lemma 12.2.1 is also needed for the following.

  (sum-phi-lemma) Let $ y \in \mathbb{N}$ and $ m \in \mathbb{N}$. If $ y \leq \sum_{i=0}^{m-1}{2^{2i+1}}$, then

$\displaystyle y = \sum_{i=0}^{m-1}{2^{2i}\phi_i(y)}.$

PROOF: Let $ \chi_i = \chi_i(y)$, $ \mu_i = \mu_i(y)$, and $ \phi_i = \phi_i(y)$. First note that $ 4\chi_{i+1} + \phi_i = \mu_i$, for if $ \mu_i = 3$, then

$\displaystyle 4\chi_{i+1} + \phi_i = 4 - 1 = 3,$

and in all other cases,

$\displaystyle 4\chi_{i+1} + \phi_i = 4\mu_i[2] + \mu[1:0] = \mu_i.$

We shall show that for $ k=0,\ldots,m$,

$\displaystyle y[2k-1:0] = \sum_{i=0}^{k-1}{2^{2i}\phi_i}+2^{2k}\chi_{k}.$

The claim is trivial for $ k=0$. For $ 0 \leq k < m$, by induction, we have


$\displaystyle y[2k+1:0]$ $\displaystyle =$ $\displaystyle 2^{2k}y[2k+1:2k] + y[2k-1:0]$  
  $\displaystyle =$ $\displaystyle 2^{2k}y[2k+1:2k] + \sum_{i=0}^{k-1}{2^{2i}\phi_i}+2^{2k}\chi_{k}$  
  $\displaystyle =$ $\displaystyle 2^{2k}(y[2k+1:2k]+\chi_k) + \sum_{i=0}^{k-1}{2^{2i}\phi_i}$  
  $\displaystyle =$ $\displaystyle 2^{2k}\mu_k + \sum_{i=0}^{k-1}{2^{2i}\phi_i}$  
  $\displaystyle =$ $\displaystyle 2^{2k}(4\chi_{k+1} + \phi_k) + \sum_{i=0}^{k-1}{2^{2i}\phi_i}$  
  $\displaystyle =$ $\displaystyle \sum_{i=0}^{k}{2^{2i}\phi_i} +2^{2(k+1)}\chi_{k+1}.$  

In particular, substituting $ m-1$ for $ k$, we have

$\displaystyle y = y[2m-1:0] = \sum_{i=0}^{m-1}{2^{2i}\phi_i}+2^{2m}\chi_{m} = \sum_{i=0}^{m-1}{2^{2i}\phi_i}. $

Thus, our multiplier $ y$ may be statically encoded as a vector of width $ 2m$,

$\displaystyle z = \{\mu_{m-1}[1:0],\ldots,\mu_0[1:0]\},$

from which each $ \phi_i$ may be readily recovered as

$\displaystyle \phi_i = \left\{\begin{array}{ll}
-1 & \mbox{if $z[2i+1:2i] = 3$}\\
\mu_i[1:0] & \mbox{if $z[2i+1:2i] \neq 3$.}\end{array} \right.$

Applying Theorem 12.1 and invoking Corollary 12.2.2 and Lemma 12.2.3, we have the following result. Note that as a further optimization, which is not pursued here, $ bmux4$ could be replaced with a 4-to-1 multiplexer.

  (static-booth) Let $ m \in \mathbb{N}$, $ m>0$, and $ n \in \mathbb{N}$, $ n > 0$. Let $ x$ be a bit vector of width $ n-1$ and let $ y \in \mathbb{N}$ satisfy $ y \leq \sum_{i=0}^{m-1}{2^{2i+1}}$. Then

$\displaystyle 2^n + \sum_{i=0}^{m-1}{pp4_i(x,n,\Phi)} = 2^{n+2m} + xy,$

where $ \Phi = \{\phi_k(y)\}_{k=0}^{m-1}$.

PROOF: This follows from Theorem 12.1, Corollary 12.2.2, and Lemma 12.2.3


David Russinoff 2017-08-01