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, in one way or another, all the digitwise partial products of the operands. The complexity of the corresponding cell or procedure is thus a key point to be considered by the designer when selecting the base. As quoted in Chapter 3, the most used bases are 2 (binary), 4 (quaternary or radix-4), 8 (octal or radix-8), 16 (hexadecimal or radix-16), and 10 (decimal). The examples treated in this chapter will be limited to those bases, although most theorems hold for any base B. As far as the technology deals with two-level signals and devices, binary coding is assumed in most practical implementations. Nevertheless, from the algorithmic point of view, the base coding aspect is not relevant.

Logarithmic techniques for multiplication are not generally used because logarithm computation algorithms do not exhibit a better complexity behavior than multiplication itself. Actually, if look-up tables (LUTs) are available, the process is interesting because it reduces to a simple addition. Nevertheless, the cost of look-up tables is formidable except for small operand sizes.

Let us point out, finally, that the fast evolution of technology may change the optimization criteria and the performance factors of some types of physical implementations. So it is quite difficult to forecast future interest in the respective algorithm options. This chapter presents the most used multiplication algorithms while Chapter 12 is devoted to multiplier design with some typical FPGA and IC implementations.