## 12.1 NATURAL NUMBERS

### 12.1.1 Basic Multiplier

According to the Hörner expansion presented in Chapter 5, formula (5.6),

is easily mapped into a combinational circuit to materialize Algorithm 5.2 (shift and add 2). A basic space iteration of the shift and add multiplier in base *B* is shown in Figure 12.1. The function *Z* implemented by this *n*-digit × *m*-digit multiplier is

where *D* = *P*(0) is an *m*-digit number.

Whenever *B* > 2, the size of the result *Z* is *m* + *n*; moreover, (*m* + 1)-digit adders are needed, because *x _{i}.Y* may exceed

*B*− 1. Otherwise, in the binary case, the size of the result is limited to

^{m}*m*+

*n*− 1, and

*m*-digit adders meet the requirement. After each addition step, a digit result appears as the rightmost digit of the shifted sum. According to the case at hand, inverting the role of

*multiplicand*and

*multiplicator*may appear useful. The effects of this permutation are that the products

*y*are

_{i}.X*n*-digit products (instead of

*m*for

*x*), while the

_{i}.Y*n*(

*m*+ 1)-digit adders are switched for

*m*(

*n*+ 1)-digit ones. Obviously the size of the result doesn't change.

The hardware cost of this circuit is high because of the *n* (resp. *m*) adders involved. The time is roughly equal to *n* (*m* + 1)-digit (resp. *m* (*n* + 1)-digit) adders. As will be observed later, if ripple-carry adders are used, this ...

Get *Synthesis of Arithmetic Circuits: FPGA, ASIC and Embedded Systems* now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.