12.3  Encoding Redundant Representations

In the context of an iterative multiplication-based algorithm, it often occurs that the result of a multiplication is used as the multiplier $ y$ in the next iteration. In this case, if the Booth encoding of $ y$ can be derived directly from the redundant representation produced by the compression tree, then $ y$ need not be computed explicitly and the expensive final step of addition may be avoided.

In this section, we shall assume once again that $ x$ is an $ (n-1)$-bit vector, but now the multipler to be encoded is expressed as a sum of two vectors and two carry bits,

$\displaystyle y = a + b + c + d,$

where $ a$ and $ b$ are bit vectors of width $ 2m-2$ and $ c$ and $ d$ are of width 1. As a consequence,

$\displaystyle y \leq (2^{2m-2} - 1) + (2^{2m-2} - 1) + 1 + 1 = 2^{2m-1}.$

In particular, $ y$ is a bit vector of width $ 2m$.

We define a sequence of coefficients $ \psi_i$ as follows.

Definition 12.3.1   (gamma,delta,psi) Let $ a \in \mathbb{N}$, $ b \in \mathbb{N}$, $ c \in \mathbb{N}$, and $ d \in \mathbb{N}$. For all $ i \in \mathbb{N}$, let

$\displaystyle a_i = a[2i+1:2i]$

and

$\displaystyle b_i = b[2i+1:2i],$

and let $ \gamma_i$ and $ \delta_i$ be defined recursively as follows: $ \gamma_0 = c$, $ \delta_0 = d$, and for $ i>0$,

$\displaystyle \gamma_i = a_{i-1}[1] \;\verb!\vert!\; b_{i-1}[1]$

and

$\displaystyle \delta_i = (a_{i-1}[0] \;\verb!&!\; b_{i-1}[0] \;\verb!\vert!\; a...
...&!\; \gamma_{i-1}[0]) \;\verb!&! \verb! !(a_{i-1}[1] \;\verb!^!\; b_{i-1}[1]).
$

Then for all $ i \in \mathbb{N}$,

$\displaystyle \psi_i(a,b,c,d) = a_i + b_i + \gamma_i + \delta_i - 4(\gamma_{i+1} + \delta_{i+1}).$

  (sum-psi-lemma) Let $ m \in \mathbb{N}$, $ m>0$, and $ y = a+b+c+d$, where $ a$ and $ b$ are $ (2m-2)$-bit vectors and $ c$ and $ d$ are 1-bit vectors. Then

$\displaystyle y = \sum_{i=0}^{m-1}2^{2i}\psi_i(a,b,c,d).$

PROOF: Let $ \psi_i = \psi_i(a,b,c,d)$ and let $ a_i$, $ b_i$, $ \gamma_i$, and $ \delta_i$ be as specified in Definition 12.3.1. We shall prove, by induction, that for $ 0 \leq k \leq m$,

$\displaystyle a[2k-1:0] + b[2k-1:0] + c + d = \sum_{i=0}^{k-1}{2^{2i}\psi_i} + 2^k(\gamma_k + \delta_k).$

Assume that the statement holds for some $ k<m$. Then
$\displaystyle {a[2k+1:0] + b[2k+1:0] + c + d}$
  $\displaystyle =$ $\displaystyle 2^ka_k + a[2k-1:0] + 2^kb_k + b[2k-1:0] + c + d$  
  $\displaystyle =$ $\displaystyle 2^k(a_k + b_k) + \sum_{i=0}^{k-1}{2^{2i}\psi_i} + 2^k(\gamma_k + \delta_k)$  
  $\displaystyle =$ $\displaystyle 2^k(a_k + b_k + \gamma_k + \delta_k) + \sum_{i=0}^{k-1}{2^{2i}\psi_i}$  
  $\displaystyle =$ $\displaystyle 2^k(\psi_k + 4(\gamma_{k+1} + \delta_{k+1})) + \sum_{i=0}^{k-1}{2^{2i}\psi_i}$  
  $\displaystyle =$ $\displaystyle \sum_{i=0}^{k}{2^{2i}\psi_i} + 2^{k+1}(\gamma_{k+1} + \delta_{k+1}).$  

Note that $ a_{m-1} = b_{m-1} = 0$ and therefore, as a consequence of Definition 12.3.1, $ \gamma_m = \delta_m = 0$. Thus,
$\displaystyle a + b + c + d$ $\displaystyle =$ $\displaystyle a[2m-1:0] + b[2m-1:0] + c + d$  
  $\displaystyle =$ $\displaystyle \sum_{i=0}^{m-1}{2^{2i}\psi_i} + 2^m(\gamma_m + \delta_m)$  
  $\displaystyle =$ $\displaystyle \sum_{i=0}^{m-1}{2^{2i}\psi_i}. $  


It is not obvious that the $ \psi_i$ lie within the range required by Theorem 12.1.

  (psi-bnd) Let $ m \in \mathbb{N}$, $ m>0$, let $ a$ and $ b$ be $ (2m-2)$-bit vectors, and let $ c$ and $ d$ be 1-bit vectors. Then for $ i=0,\ldots,m-1$, $ \vert\psi_i(a,b,c,d)\vert \leq 2$.

PROOF: Let $ \psi_i = \psi_i(a,b,c,d)$ and let $ a_i$, $ b_i$, $ \gamma_i$, and $ \delta_i$ be as specified in Definition 12.3.1. Then

$\displaystyle \psi_i = a_i + b_i + \gamma_i + \delta_i - 4(\gamma_{i+1} + \delta_{i+1}),$

where $ \gamma_{i+1}$ and $ \delta_{i+1}$ are functions of $ a_i$, $ b_i$, and $ \gamma_i$. Thus, we may express $ \psi_i$ as a function of $ a_i$, $ b_i$, $ \gamma_i$, and $ \delta_i$. The inequality may then be trivially verified for each of the $ 4 \cdot 4 \cdot 2 \cdot 2 = 64$ possible sets of values of these arguments. 


We may now apply Theorem 12.1.

  (redundant-booth) Let $ m \in \mathbb{N}$, $ m>0$, and $ n \in \mathbb{N}$, $ n > 0$. Let $ x$ be an $ (n-1)$-bit vector and let $ y = a+b+c+d$, where $ a$ and $ b$ are $ (2m-2)$-bit vectors and $ c$ and $ d$ are 1-bit vectors. Then

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

where $ \Psi = \{\psi_k(a,b,c,d)\}_{k=0}^{m-1}$.

PROOF: Let $ a_i$, $ b_i$, $ \gamma_i$, and $ \delta_i$ be as specified in Definition 12.3.1. Since $ a_{m-1} = b_{m-1} = 0$, $ \gamma_m = \delta_m = 0$, and hence $ \psi_{m-1} \geq 0$, i.e., $ neg_{m-1} = 0$ in Theorem 12.1. The result follows from the theorem and Lemmas 12.3.1 and 12.3.2

David Russinoff 2017-08-01