Fast multiplication, including residue methods for digital signal processing

A contemporary computer spends a large percentage of its time executing multiplication. Although considerable efforts have been directed towards reduction of the computational load of processors used for digital signal processing, the requirement for fast complex vector dot products and additions remains inescapable. Early designs of digital multipliers operating in parallel, were slow in propagating the carry signal across the bits of the multiplicand as the word length increased.

In recent years high speed carry methods and look-ahead carry have been developed, followed by combinational array multipliers. Even so there is a requirement for much faster speeds for signal processing, such as could be achieved by a special purpose "add on" multiplier hardware unit, designed to operate with a host computer. In particular there is a current MID (RN) requirement for a fast multiplier to be used as part of an adaptive beam forming passive sonar processing system.

This investigation considers the possible methods of meeting a specific multiplier requirement rather than for a general purpose multiplier.

The aim, briefly, is to achieve an algorithm for a special purpose multiplier which can be translated into practical hardware and capable of multiplying a complex number, in 200-400 ns, including overheads.

Much of the work reported upon concerns the relatively unfamiliar residue (or modular arithmetic) techniques. These techniques offer very attractive computational speeds, providing the operands can be translated into residue form, and reconstituted into weighted binary results in a sufficiently fast timescale. The factors which define the selection of suitable multiple radices are considered in detail and related to the hardware necessary to construct a high speed multiplier.