Partial product array multiplier

Claim 2

A multiplier advantageously adaptable for implementation with large scale integrated circuits comprising: a. a multiplicand storage means for storing n multiplicand bits of data, and a multiplier storage means for storing m multiplier bits of data, b. a partial product storage means for generating a partial product including no more than m + n-1 storage columns, said partial product storage means being connected to said multiplicand storage means in one coordinate direction associated with said partial product storage means, and also being connected to said multiplier storage means in the other coordinate direction associated with said partial product storage means, c. p (m + n-1)/k multi-operand adders connected to said storage array, where k is an integer equal to or greater than log2 (m-1), and where m + n-1/k is an integer greater than or equal to (m + n-1)/k, d. said partial product storage means being selectively responsive to said m and n bits of data for generating a partial product, and e. said p multi-operand adders being responsive to said generated partial product, independent of said m and n bits of data initially stored in said multiplier and multiplicand storage means, for generating a final product.

Claim 3

A multiplier advantageously adaptable for implementation with large scale integrated circuits as in claim 1 wherein said partial product storage means further includes: a. a plurality of first gating means connected to said storage columns, each of said plurality of first gating means including a first input terminal, a second input terminal, and an output terminal, a plurality of said first terminals being connected to said multiplicand storage means and a plurality of said second terminals being connected to said multiplier storage means, and a plurality of said output terminals being connected to predetermined ones of said storage columns, and b. said plurality of first gating means being selectively responsive to said m and n bits of data for storing a partial product in said storage array.

Claim 4

A multiplier advantageously adaptable for implementation with large scale integrated circuits as in claim 1 wherein: a. said partial product storage means is limited to p storage columns, each one of said p storage columns having a plurality of storage locations and being responsive to said n multiplicand bits of data for storing an initial predetermined skewed pattern of said n multiplicand bits of data, b. said partial product storage means further include means for interconnecting selected storage positions between said storage columns and being responsive to the transfer of data on said means for interconnecting for successively generating predetermined altered skewed patterns of data independent of said n bits of data initially stored in said multiplicand storage means, and a plurality of gating means connected to predetermined storage positions and to said multiplier storage means, said plurality of gating means being responsive to said m multiplier bits of data and serially responsive firstly to said initial predetermined skewed pattern of said n multiplicand bits of data, and then to said predetermined altered skewed patterns of data independent of said n bits of data initially stored in said multiplicand storage means, for generating a plurality of reduced partial product patterns of data, and c. said p multi-operand adders being selectively responsive only to said reduced partial product patterns of data, independent of said m and n bits of data initially stored in said multiplier and multiplicand storage means, for generating a final product.

Claim 5

A multiplier advantageously adaptable for implementation with large scale integrated circuits as in Claim 3 wherein: a. said storage positions comprise a plurality of shift register locations distributed among said p storage columns, and b. said means for interconnecting selected storage positions further comprise shifting means connected between predetermined ones of said shift register locations for selectively transferring data between said p storage columns for generating said predetermined altered skewed patterns of data from said initial predetermined skewed pattern of data.