Synthesis of Arithmetic Circuits: FPGA, ASIC and Embedded Systems

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