High speed parallel multiplier circuit

Claim 1

A binary multiplier circuit for obtaining a product of an M-bit multiplier and an N-bit multiplicand, comprising: binary multiplier means, having inputs connected to receive said multiplier and said multiplicand, for producing a summand matrix having M×N original summand matrix bits and having M rows and M+N columns, the columns each representing a different bit position in said product and being arranged in significance according to increasing bit positions of said product; reduction circuit means, coupled to said binary multiplier means, for producing two addends from said summand matrix bits, said reduction circuit means including a first level adder circuit coupled to receive said original summand matrix bits, said first lever adder circuit including a first set of full adders each corresponding to a selected one of the columns of said summand matrix having three or more original summand matrix bits, except for the one of said columns representing the least significant bit position with only three original summand matrix bits, each of the full adders being connected to receive three different original summand matrix bits from the corresponding column and including means for producing a sum bit for that column and a carry bit for the column representing the next most significant bit position, and a first set of half adders each corresponding to a selected one of the columns of said summand matrix initially having more than three original summand matrix bits and having exactly two original summand matrix bits not connected to one of said full adders in said first set of full adders, and for the one of said columns representing the least significant bit position with only three original summand matrix bits, said half adders each being connected to receive two different original summand matrix bits from the corresponding column and including means for producing a sum bit for that column and a carry bit for the column representing the next most significant bit position, and an intermediate level adder circuit coupled to receive either original summand matrix bits not received by said first set of half adders or full adders, or sum and carry bits from said first set of full adders and half adders, said intermediate level adder circuit being organized into a plurality of different levels and receiving column bits including, for a corresponding column and level, the original summand matrix bits not received by the first set of half or full adders and sum and carry bits which were not inputs at a prior level, said intermediate level adder circuit including a plurality of full adders each corresponding to one of said levels and to a selected one of said columns having three or more column bits, except for the one of said columns at the corresponding level representing the least significant bit position with only three column bits, each of the full adders at each of said levels being connected to receive three column bits for the corresponding column and including means for producing a sum bit for that column and a carry bit for the column representing the next most significant bit position, and a plurality of half adders each corresponding to one of said levels and to a selected one of the columns for which, at each of said intermediate levels, at least one of said plurality of full adders from said first set or from said intermediate level adder circuit corresponds to that column and exactly two bits remain unconnected to any of said full adders, and also corresponding to the one of said columns at each level representing the least significant bit position for which only three bits remain, said half adders each being connected to receive two column bits for the corresponding column, each of said plurality of half adders including means for producing a sum bit for that column and a carry bit for the column representing the next most significant bit position; and full carry-propagating adder means, receiving as inputs the addends which are output from said intermediate level adder circuit, for producing said product.