Patent ID: 6434586
Filing Date: 2002-08-13
Classification: G06F

Abstract:
A processor that comprises:a multiplier capable of producing an MÃ—N array of partial product bits of an M bit multiplier and an N bit multiplicand, said multiplier comprising an array of AND gates, each of which receives as inputs a multiplier bit and a multiplicand bit and whose output is a partial product bit; means for arranging said MÃ—N array of partial products bits by shifting, in the direction of increasing bit order of multiplicand, each successive row of partial product bits by the number of bits corresponding to the bit order of the multiplier bit that produced said row, thereby resulting in a parallelogram of shifted partial product bits; means for forming an MÃ—2M rectangle of shifted partial products that shares its diagonal with the longer diagonal of said parallelogram, by completing with zeros the area outside said parallelogram but inside said rectangle; a Wallace compressor comprising a rectangular compressor array of 3:2 carry save adders, the compressor array having M columns and Â½ M rows, and generating a set of sum bits and a set of carry bits as the compressor output, each of the carry save adders receiving as data inputs one of the partial product bits of a quadrant of said rectangle, a sum bit and a carry bit and producing a sum bit and a carry bit as its outputs; and a first adder for summing said set of sum bits and said set of carry bits of said compressor output.