next up previous contents
Next: Statically Encoded Multiplier Arrays Up: Multiplication Previous: Multiplication   Contents


Radix-4 Booth Encoding

As a notational convenience, we shall assume that $ x$ and $ y$ are bit vectors of widths $ n-1$ and $ 2m-1$ , respectively. Our objective is an efficient computation of $ xy$ as a sum of $ m$ partial products. Conceptually, the multiplier is partitioned into $ m$ 2-bit slices, $ y[2i+1:2i]$ , $ i=0,\ldots,m-1$ . Corresponding to each slice, we define an integer encoding $ \theta_i$ in the range $ -2 \leq \theta_i \leq 2$ .

Definition 7.1.1   (theta) For $ y \in \mathbb{N}$ and $ i \in \mathbb{N}$ ,

$\displaystyle \theta_i(y) = y[2i-1] + y[2i] - 2y[2i+1].$

  (sum-theta-lemma) Let $ m \in \mathbb{N}$ , $ m>0$ , and let $ y$ be a bit vector of width $ 2^{2m-1}$ . Then

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

PROOF: We shall prove, by induction, that for $ 0 \leq k \leq m$ ,

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

where $ \theta_i = \theta_i(y)$ . The claim is trivial for $ k = 0$ . Assuming that it holds for some $ k<m$ , we have
$\displaystyle y[2k+1:0]$ $\displaystyle =$ $\displaystyle 2^{2k}y[2k+1:2k] + y[2k-1:0]$  
  $\displaystyle =$ $\displaystyle 2^{2k}(2y[2k+1] + y[2k]) + \sum_{i=0}^{k-1}{2^{2i}\theta_i}+ 2^{2k}y[2k-1]$  
  $\displaystyle =$ $\displaystyle 2^{2k}(2y[2k+1] + y[2k] + y[2k-1]) + \sum_{i=0}^{k-1}{2^{2i}\theta_i}$  
  $\displaystyle =$ $\displaystyle 2^{2k}(4y[2k+1] + \theta_k) + \sum_{i=0}^{k-1}{2^{2i}\theta_i}$  
  $\displaystyle =$ $\displaystyle \sum_{i=0}^{k}{2^{2i}\theta_i} + 2^{2(k+1)}y[2(k+1)-1],$  

which completes the induction. In particular, substituting $ m$ for $ k$ , we have

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


Since $ -2 \leq \theta_i \leq 2$ , Lemma 7.1.1 expresses $ y$ as a sum of at most $ m$ nonzero terms, each with absolute value a power of 2. Our goal is to compute

$\displaystyle xy = x\sum_{i=0}^{m-1} 2^{2i}\theta_i = \sum_{i=0}^{m-1} 2^{2i}x\theta_i.$

Each term of this sum will correspond to a partial product, which is constructed by means of a 5-to-1 multiplexer.

Definition 7.1.2   (bmux4) Let $ n \in \mathbb{N}$ , $ n>0$ , let $ x$ be a bit vector of width $ n-1$ , and let $ \zeta \in \mathbb{Z}$ satisfy $ -2 \leq \zeta \leq 2$ . Then

$\displaystyle bmux4(\zeta,x,n) = \left\{\begin{array}{ll} x & \mbox{if $\zeta =... ...n-1:0] & \mbox{if $\zeta = -2$}\\ 0 & \mbox{if $\zeta = 0$}.\end{array}\right.$

Definition 7.1.3   (pp4) 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 $ \zeta_k \in \mathbb{Z}$ satisfy $ -2 \leq \zeta_k \leq 2$ for $ 0 \leq k \leq m-1$ . Then for $ 0 \leq i \leq m-1$ , the $ i^{th}$ radix-4 partial product with respect to $ x$ and $ n$ for the sequence $ \Sigma = \{\zeta_k\}_{k=0}^{m-1}$ is

$\displaystyle pp4_i(x,n,\Sigma) = \left\{\begin{array}{ll} \{1\verb!'b!1, \verb... ...neg_{i-1}, 2(i\mbox{-}1)\verb!'b!0\} & \mbox{if $i$$>$$0$}.\end{array} \right.$

where

$\displaystyle neg_i = \left\{\begin{array}{ll} 0 & \mbox{if $\zeta_i \geq 0$}\\ 1 & \mbox{if $\zeta_i < 0$}\end{array} \right.$

and $ B_i = bmux4(\zeta_i,x,n)$ .

Our main theorem is formulated as generally as possible so that it may be applied in other contexts.

  (booth4-thm) 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 $ \zeta_k \in \mathbb{Z}$ satisfy $ -2 \leq \zeta_k \leq 2$ for $ k=1,\ldots,m-1$ . Then

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

where $ \Sigma = \{\zeta_k\}_{k=0}^{m-1}$ and

$\displaystyle neg_i = \left\{\begin{array}{ll} 0 & \mbox{if $\zeta_i \geq 0$}\\ 1 & \mbox{if $\zeta_i < 0$}\end{array} \right.$

PROOF: Let $ B_i = bmux4(\zeta_i,x,n)$ . A straightforward reformulation of Definition 7.1.2 yields

$\displaystyle B_i = \left\{\begin{array}{ll} x\zeta & \mbox{if $\zeta \geq 0$}\\ x\zeta + 2^n-1 & \mbox{if $\zeta < 0$}.\end{array} \right.$

In order to understand Definition 7.1.3, note that whenever $ neg_i = 1$ , we must correct for the discrepancy between $ 2^{2i}B_i$ and $ 2^{2i}x\zeta_i$ by (1) adding $ 2^{2i}$ and (2) subtracting $ 2^{2i+n}$ . The first is achieved simply by the insertion of $ neg_i$ at index $ 2i$ of $ pp4_{i+1}$ . The second may be viewed as a two-step process. First, we insert 1's at indices $ 2i+n$ and $ 2i+n+1$ of $ pp4_i$ . In the final sum described below, the cumulative result of this is merely a carry-out to a high-order bit (index $ n+m$ ), which may ultimately be ignored. But the motivation for this step is that the $ 1$ at index $ 2i+n$ may now be subtracted off in the case $ neg_i = 1$ . Thus, in the second step, we replace that 1 with $ \verb! !neg_i = 1 - neg_i$ .

This argument underlies the present proof. By Definition 7.1.3, the left-hand side of the conclusion of the theorem is

$\displaystyle 2^n + \sum_{i=0}^{m-1}{[2^{n+1+2i} + 2^{n+2i}(1-neg_i) + 2^{2i}B_i]} + \sum_{i=1}^{m-1}{2^{2(i-1)}neg_{i-1}}.$

We first consider the constant terms of this sum:


$\displaystyle 2^n + \sum_{i=0}^{m-1}{[2^{n+1+2i} + 2^{n+2i}]}$ $\displaystyle =$ $\displaystyle 2^n (1 + \sum_{i=0}^{m-1}{[2^{2i+1} + 2^{2i}]})$  
  $\displaystyle =$ $\displaystyle 2^n (1 + \sum_{j=0}^{2m-1}{2^j})$  
  $\displaystyle =$ $\displaystyle 2^n (1+ (2^{2m} - 1))$  
  $\displaystyle =$ $\displaystyle 2^{n+2m}.$  

Next, we observe that the final term of the sum may be rewritten as

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

Thus, we have
$\displaystyle 2^n + \sum_{i=0}^{m-1}{pp4_i}$ $\displaystyle =$ $\displaystyle 2^{n+2m} + \sum_{i=0}^{m-1}{[-2^{n+2i}neg_i + 2^{2i}B_i]} + \sum_{i=1}^{m-1}{2^{2(i-1)}neg_{i-1}}$  
  $\displaystyle =$ $\displaystyle 2^{n+2m} + \sum_{i=0}^{m-1}{2^{2i}[B_i - (2^{n}-1)neg_i]} - 2^{2(m-1)}neg_{m-1}$  
  $\displaystyle =$ $\displaystyle 2^{n+2m} + \sum_{i=0}^{m-1}{2^{2i}x\zeta_i} - 2^{2(m-1)}neg_{m-1}$  
  $\displaystyle =$ $\displaystyle 2^{n+2m} + x\sum_{i=0}^{m-1}{2^{2i}\zeta_i} - 2^{2(m-1)}neg_{m-1}. $  


In our first application of Theorem 7.1, we substitute $ \theta_i(y)$ for $ \zeta_i$ and invoke Corollary 7.1.1.

  (booth4-corollary) Let $ m \in \mathbb{N}$ , $ m>0$ , and $ n \in \mathbb{N}$ , $ n>0$ . Let $ x$ and $ y$ be bit vectors of widths $ n-1$ and $ 2m-1$ , respectively. Then

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

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

PROOF: Since $ y[2m-1] = 0$ ,

$\displaystyle \theta_{m-1} = y[2m-3] + y[2m-2] - 2y[2m-1] \geq 0,$

i.e., $ neg_{m-1} = 0$ in Theorem 7.1. The result follows from the theorem and Lemma 7.1.1. 

next up previous contents
Next: Statically Encoded Multiplier Arrays Up: Multiplication Previous: Multiplication   Contents
David Russinoff 2007-01-02