12.1  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 12.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 $ 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 12.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 12.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 ...
...1:0] & \mbox{if $\zeta = -2$}\\
0 & \mbox{if $\zeta = 0$}.\end{array} \right.$

Definition 12.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 the $ (2m+n)$-bit vector

$\displaystyle pp4_i(x,n,\Sigma)
= \left\{\begin{array}{ll}
\{2(m-1)\verb!'!0, ...
... neg_{i-1}, 2(i\mbox{-}1)\verb!'!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 12.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 12.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 12.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 12.1, we substitute $ \theta_i(y)$ for $ \zeta_i$ and invoke Corollary 12.1.1.

  (booth4-corollary-1) 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 12.1. The result follows from the theorem and Lemma 12.1.1

Note that computing a product as an application of Corollary 12.1.2 requires injecting an extra bit (with value $ 2^n$) into the partial product array. This requirement can be eliminated through a minor modification of the low-order entry $ \mathit{pp4}_0$:

  (booth4-corollary-2) 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. for $ 0 \leq i \leq m-1$, lLet $ \mathit{pp4}'_i$ be defined just as $ \mathit{pp4}_i$ except that

$\displaystyle [pp4'_0(x,n,\Sigma) = \{(2m-3)\verb!'!0, \verb! !neg_0, neg_0, neg_0, B_0[n$-$\displaystyle 1:0]\}.$

Then

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

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

PROOF: The only difference between $ pp4'_i$ and $ pp4_i$ is that

$\displaystyle pp4_0[n+2:2] = \{1\verb!'!0, 1\verb!'!1, \verb! !neg_0\} = 3 - neg_0,
$

while

$\displaystyle pp4'_0[n+2:2] = \{\verb! !neg_0, neg_0, neg_0\} = 4 - neg_0.
$

Thus,

$\displaystyle pp4'_0 - pp4_0 = 2^n(pp4'_0[n+2:2] - pp4_0[n+2:2]) = 2^n
$

and

$\displaystyle \sum_{i=0}^{m-1}pp4'_i = \sum_{i=0}^{m-1}pp4_i + (pp4'_0 - pp4_0) = (2^{n+2m} + xy - 2^n) + 2^n = 2^{n+2m} + xy. $

David Russinoff 2017-08-01