next up previous contents
Next: Encoding Redundant Representations Up: Multiplication Previous: Radix-4 Booth Encoding   Contents

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 7.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 7.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 7.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 7.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 7.2.1 and Definitions 7.2.1 and 7.2.2.

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

Lemma 7.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 7.1 and invoking Corollary 7.2.2 and Lemma 7.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 7.1, Corollary 7.2.2, and Lemma 7.2.3. 


next up previous contents
Next: Encoding Redundant Representations Up: Multiplication Previous: Radix-4 Booth Encoding   Contents
David Russinoff 2007-01-02