## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

## 12.2 INTEGERS

### 12.2.1 B's Complement Multipliers

A straightforward implementation of Algorithm 5.7 (Section 5.3.1.1: mod Bn+m B's complement multiplication) consists of extending the representation of X and Y to n + m digits and computing the n + m less significant digits of R(Z) = R(X).R(Y). For that purpose any natural-number multiplier can be used. As an example, assume that a carry-save multiplier is used (Figure 12.5). The adder, ripple-carry, or whatever is no longer necessary as the n + m most significant digits must be truncated. So the array is limited to the rightmost n + m columns of the array represented in Figure 12.5. The cost and computation time of the obtained array are where C2 and T2 are the cost and propagation time of the cell of Figure 12.3.

If m = n, then C(n) = n.(2.n + 1).C2, and T(n, m) = 2.n.T2. The computation time is the same as in the case of the natural numbers (12.3) but the cost is almost twice the cost CCSM = n.(n + 1).C2 given by formula (12.4).

Another option is to implement Algorithm 5.8. A circuit similar to the ripple-carry multiplier of Figure 12.4 can be used. Every cell of the last row (Figure 12.3 with i = n − 1) must be replaced by a different one whose behavior is defined by the following rules:

if xn-1 = 0 then for j in 0…m-1 loop Pn(n−1+j) =P (n−1)(n−1+j); c(n−1)(j+1)=0; endloop; else c(n−1)1=(c(n−1)j +P(n−1)(n−1 + j) + B-y0)/B; P

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required