4 - Multiplication

Summary

Introduction

The product of two radix polynomials is a radix polynomial whose digits can be expressed as sums of digit products from the operand polynomials. The digits thus expressed are in general from some much larger digit set, and a conversion must be performed in some way to deliver the result in the same digit set as that of the operands. The order in which digit products are generated, and later accumulated, is algorithm specific.

Often intermediate products (called partial products) are formed by multiplying a digit from one operand (the multiplier) by the complete other operand (the multiplicand), followed by accumulation of shifted versions of these, to account for the different weights of the multiplier digits. Hence there are three recognizable steps in forming the product:

1. (i) formation of digit or partial products,

2. (ii) summation of digit or partial products,

3. (iii) final digit set conversion,

where these steps individually or in combination can be performed in parallel or sequentially in various ways.

The order in which digit products or partial products are formed and how accumulation is performed thus characterize the algorithms. Some implicitly perform a base and digit set conversion, utilizing a higher radix to reduce the number of terms that have to be added. The different algorithms can also be characterized according to the way operands are delivered/consumed, and how the result is produced, whether word parallel or digit serial, and in the last case in which order.