next up previous contents
Next: Bibliography Up: Multiplication Previous: Encoding Redundant Representations   Contents

Radix-8 Booth Encoding

As we shall see in this section, a partitioning of our multiplier $ y$ into slices of four bits instead of three leads to a decomposition

$\displaystyle y = \sum{2^{3i} \eta_i},$

where $ \eta_i$ is an encoding of the $ i^{th}$ slice. While the number of terms of this sum is only 1/4 (rather than 1/3) of the width of $ y$ , the range of encodings is now $ -4 \leq \eta_i \leq 4$ , and hence the value of each term is no longer guaranteed to be a power of 2 in absolute value. Consequently, a multiplier based on this radix-8 scheme generates fewer partial products than a radix-4 multiplier, but the computation of each partial product is more complex. In particular, a partial product corresponding to an encoding $ \eta_i = \pm 3$ requires the computation of $ 3x$ , and therefore a full addition.

The choice between radix-8 and radix-4 multiplication is generally decided by the timing details of a hardware design. In a typical implementation, the partial products are computed in one clock and the compression tree is executed in the next. If there is sufficient time during the first clock to perform the addition required for radix-8 encoding (which is more likely to be the case, for example, for a low-precision operation), then this scheme is feasible. Since most of the silicon area allocated to a multiplier is associated with the compression tree, the resulting reduction in the number of partial products may represent a significant gain in efficiency.

For the purpose of this analysis, which is otherwise quite similar to that of Section 7.1, we shall assume that $ x$ and $ y$ are bit vectors of widths $ n-2$ and $ 3m-1$ , respectively. The multiplier $ y$ is now partitioned into $ m$ 3-bit slices, $ y[3i+2:3i]$ , $ i=0,\ldots,m-1$ , and encoded as follows.

Definition 7.4.1   (eta) For $ y \in \mathbb{N}$ and $ i \in \mathbb{N}$ ,

$\displaystyle \eta_i(y) = y[3i-1] + y[3i] + 2y[3i+1] - 4y[3i+2].$

The proof of the following identity is essentially the same as that of Lemma 7.1.1.

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

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

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

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

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

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

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

The partial products are computed with an 9-1 multiplexer.

Definition 7.4.2   (bmux8) Let $ n \in \mathbb{N}$ , $ n>0$ , let $ x$ be a bit vector of width $ n-2$ , and let $ \xi \in \mathbb{Z}$ satisfy $ -4 \leq \xi \leq 4$ . Then

$\displaystyle bmux8(\xi,x,n) = \left\{\begin{array}{ll} \xi x & \mbox{if $\xi \... ...$}\\ \verb! !(\vert\xi\vert x)[n-1:0] & \mbox{if $\xi < 0$}.\end{array}\right.$

Definition 7.4.3   (pp8) Let $ m \in \mathbb{N}$ , $ m>0$ , and $ n \in \mathbb{N}$ , $ n>0$ . Let $ x$ be a bit vector of width $ n-2$ and let $ \xi_k \in \mathbb{Z}$ satisfy $ -4 \leq \xi_k \leq 4$ for $ 0 \leq k \leq m-1$ . Then for $ 0 \leq i \leq m-1$ , the $ i^{th}$ radix-8 partial product with respect to $ x$ and $ n$ for the sequence $ \Sigma = \{\xi_k\}_{k=0}^{m-1}$ is

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

where

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

and $ B_i = bmux8(\xi_i,x,n)$ .

Once again, our theorem is formulated as generally as possible, although in this case, we shall use it only once, in order to establish Corollary 7.4.2.

  (booth8-thm) Let $ m \in \mathbb{N}$ , $ m>0$ , and $ n \in \mathbb{N}$ , $ n>0$ . Let $ x$ be a bit vector of width $ n-2$ and let $ \xi_k \in \mathbb{Z}$ satisfy $ -4 \leq \xi_k \leq 4$ for $ k=1,\ldots,m-1$ . Then

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

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

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

PROOF: Let $ B_i = bmux8(\xi_i,x,n)$ . After a trivial reformulation of Definition 7.4.2, we have

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

Thus, the left-hand side of the conclusion of the theorem is

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

We first consider the constant terms of this sum:


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

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

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

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


  (booth8-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-2$ and $ 3m-1$ , respectively. Then

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

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

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

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

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

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