12.4  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 12.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 12.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 12.1.1.

  (sum-eta-lemma) Let $ m \in \mathbb{N}$, $ m>0$, and let $ y$ be a bit vector of width $ 2^{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 12.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 12.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, \ve...
...mbox{-}1}, 3(i\mbox{-}1)\verb!'!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 12.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 12.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 12.2. The result follows from the theorem and Lemma 12.4.1

David Russinoff 2017-08-01