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

12.1 NATURAL NUMBERS

12.1.1 Basic Multiplier

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

image

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

image

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 xi.Y may exceed Bm − 1. Otherwise, in the binary case, the size of the result is limited to 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 yi.X are n-digit products (instead of m for xi.Y), while the 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 ...

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