O'Reilly logo

Synthesis of Arithmetic Circuits: FPGA, ASIC and Embedded Systems by Gustavo D. Sutter, Gery J.A. Bioul, Jean-Pierre Deschamps

Stay ahead with the world's most comprehensive technology and business learning platform.

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

Start Free Trial

No credit card required

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 xi yj are lined up in the column whose index k = i + j corresponds to the weight Bk. 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 XiYj and xiyj stand, respectively, for the integer product

image

and the mod B product

image

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

image

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 ...

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

Start Free Trial

No credit card required