5

ARITHMETIC OPERATIONS: MULTIPLICATION

Basically, multiplication is a very simple operation as it most often reduces to multioperand addition. In early computers, multiplication was assumed too complex to receive a combinational implementation, typically considered too expensive at this time. For this historical reason, in most textbooks on computer arithmetic, multiplication algorithms are strongly biased by the sequential implementations. In this chapter, the authors attempt to remain consistent with their general philosophy, presenting the algorithms in a way that never settles on a specific implementation technique. Although the Ada-like language, utilized in the algorithm descriptions, could suggest some kind of sequential implementations, the actual interpretations cannot involve any choice between space or time iteration of the presented step-by-step processes. This approach is particularly well suited to provide the designer, with a range of options, based on the diversity of technologies at hand, speed–cost compromises, and other constraints to be dealt with. Actually, it is important to realize that the algorithmic complexity is not necessarily tied to the actual required performance of some practical application.

Base-B is generally assumed, while base-2 is extensively treated whenever the specificity of the binary system results in prominent features or allows significant algorithmic simplifications. Most multiplication algorithms share a common feature: they produce, ...

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

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.