12th IEEE Symposium on Computer Arithmetic (ARITH-12 '95)
Reducing the number of counters needed for integer multiplication
Bath, England
July 19-July 21
ISBN: 0-8186-7089-4
R.M. Owens, Dept. of Comput. Sci. & Eng., Pennsylvania State Univ., University Park, PA, USA
R.S. Bajwa, Dept. of Comput. Sci. & Eng., Pennsylvania State Univ., University Park, PA, USA
M.J. Irwin, Dept. of Comput. Sci. & Eng., Pennsylvania State Univ., University Park, PA, USA
In this paper we consider the problem of multiplying reasonably small integers using fewer counters than that required by straightforward partial product accumulation. Not surprisingly the method we use is based on the observation that integer multiplication can be formulated as aperiodic convolution. However, instead of using something like the Fast Fourier Transform to compute the aperiodic convolution, we use what are known as a "fast" convolution algorithms. In this way we can construct multipliers for as small as eighteen bit integers which use fewer counters than that required by straightforward partial product accumulation. Because of the perceived "overhead" involved with an aperiodic formulation of integer multiplication, the ability to do this goes somewhat against the conventional wisdom that aperiodic formulation of integer multiplication gains an advantage over a straightforward partial product formulation only for fairly large integers.
Index Terms:
counting circuits; digital arithmetic; multiplying circuits; counters; integer multiplication; reasonably small integers; partial product accumulation; aperiodic convolution; convolution algorithms; partial product formulation; fairly large integers
Citation:
R.M. Owens, R.S. Bajwa, M.J. Irwin, "Reducing the number of counters needed for integer multiplication," arith, pp.38, 12th IEEE Symposium on Computer Arithmetic (ARITH-12 '95), 1995