next up previous contents
Next: Radix-8 Booth Encoding Up: Multiplication Previous: Statically Encoded Multiplier Arrays   Contents

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 chapter, 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 7.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[0]$ , $ \delta_0 = d[0]$ , and for $ i>0$ ,

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

and

$\displaystyle \delta_i = (a_{i-1}[1] \;\verb!&!\; b_{i-1}[1] \;\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 7.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 7.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 7.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 7.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 7.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 7.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 7.1. The result follows from the theorem and Lemmas 7.3.1 and 7.3.2. 

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