Computer-implemented multiplication with shifting of pattern-product

Abstract

A constant multiplication device is designed for multiplying a received binary multiplicand by a constant multiplier which, when expressed in binary or signed-digit notation, includes a repeated pattern with three or more non-zero values. The device includes a pattern-product term generator that receives the multiplicand and generates terms corresponding to each of the non-zero values of the pattern. If, when all instances of the pattern are subtracted from the multiplier there are non-zero values in the difference, the pattern-product term generator can also generate remainder-product terms. The pattern-product terms, but not the remainder-product terms, are input to a pattern compressor that yields pattern-product partials; the compressor can be a carry-save adder and the partials can be in the form of a pseudo sum and a pseudo carry. A replica generator generates shifted replicas of each pattern-product partial. The replicas are input to a replica compressor, as are any remainder-product terms. The replica compressor converts these inputs to final-product partials. The replica compressor can be a carry-save adder and the final-product partials can be a pseudo sum and a pseudo carry. These are input to a product ripple accumulator, which can be a carry-propagate adder, to yield the product of the multiplicand and the multiplier. Since there is only one ripple stage, the device provides for relatively high-speed multiplication for multipliers with repeated patterns.