Synthesis of Arithmetic Circuits: FPGA, ASIC and Embedded Systems

12.2 INTEGERS

12.2.1 B's Complement Multipliers

A straightforward implementation of Algorithm 5.7 (Section 5.3.1.1: mod B^n+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 C₂ and T₂ are the cost and propagation time of the cell of Figure 12.3.

If m = n, then C(n) = n.(2.n + 1).C₂, and T(n, m) = 2.n.T₂. The computation time is the same as in the case of the natural numbers (12.3) but the cost is almost twice the cost C_CSM = n.(n + 1).C₂ 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 x_n-1 = 0 then for j in 0…m-1 loop P_n(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-y₀)/B; P