Synthesis of Arithmetic Circuits: FPGA, ASIC and Embedded Systems

5.1 NATURAL NUMBERS MULTIPLICATION

5.1.1 Introduction

The most basic multiplication algorithms for n-digit × m-digit B-ary natural numbers (shift and add algorithms) proceed in two phases:

1. Digitwise partial products (n × m),
2. Multioperand addition.

The classic computation scheme to introduce multiplication is given in Figure 5.1a, where partial products appear lined up according to their respective weight. This scheme is historically related to the pencil and paper implementation of the operation. This simple scheme is easily built up by noting that the partial products x_i y_j are lined up in the column whose index k = i + j corresponds to the weight B^k. Observe that whenever B > 2, the partial products may need two base-B digits. For B > 2, a possible multiplication scheme is displayed at Figure 5.1b, where X_iY_j and x_iy_j stand, respectively, for the integer product

and the mod B product

Observe that the column index k remains i + j for products (5.2) but is computed as i + j + 1 for products (5.1).

Figure 5.1 (a) Multiplication scheme and (b) multiplication scheme for B > 2.

The cost/speed constraints are key factors to set trade-offs between combinational parallel schemes and sequential ...