US4839848A — Fast multiplier circuit incorporating parallel ar…

Claim 1

Independent Claim 250 words

A circuit for multiplying two multibit binary numbers together, comprising: a first array of a plurality of logic cells and a second array of a plurality of logic cells, with each array having input lines for receiving the bits of said numbers; every logic cell including a product means for producing a product term of a single power by multiplying a bit of one of said numbers with a bit of the other number; said cells being arranged such that the product means in said first array form one respective product term of each of the powers 0, 1, 2n, 2n-1, and form two respective product terms of each of the powers 2, 3, 2n-2, 2n-3, and form three respective product terms of each of the powers 4, 5, 2n-4, 2n-5, and so forth in the same sequence for all powers between 0 and 2n where n is the power of the most significant bit of said numbers; and wherein the respective product means in said second array form all remaining single power product terms; adder means in selected cells of the first array which are interconnected to add the single power product terms of that array, and adder means in selected cells of the second array which are interconnected to add the single power product terms of that array in parallel with the adder means of the first array; and means for combining the results from the adder means of both arrays to produce the product of said numbers.

Claim 2

Dependent Claim 250 words

A circuit for multiplying two multibit binary numbers together, comprising: a first array of a plurality of logic cells and a second array of a plurality of logic cells, with each array having input lines for receiving the bits of said numbers; every logic cell including a product means for producing a product term of a single power by multiplying a bit of one of said numbers with a bit of the other number; said cells being arranged such that the product means in said first array form one respective product term of each of the powers 0, 1, 2n, 2n-1, and form two respective product terms of each of the powers 2, 3, 2n-2, 2n-3, and form three respective product terms of each of the powers 4, 5, 2n-4, 2n-5, and so forth in the same sequence for all powers between 0 and 2n where n is the power of the most significant bit of said numbers; and wherein the respective product means in said second array form all remaining single power product terms; adder means in selected cells of the first array which are interconnected to add the single power product terms of that array, and adder means in selected cells of the second array which are interconnected to add the single power product terms of that array in parallel with the adder means of the first array; and means for combining the results from the adder means of both arrays to produce the product of said numbers.

Claim 3

Dependent Claim 55 words

A circuit according to claim 1 wherein both of said arrays are integrated into a single semiconductor chip, wherein the cells of each array are arranged by rows and columns in respective triangular patterns which are space apart on the chip, and wherein said means for combining is disposed in the space between said patterns.

Claim 4

Dependent Claim 66 words

A circuit according to claim 2 wherein said means for combining includes a first parallel input adder for producing a complete sum of said product terms in said first array, a second parallel input adder for producing a complete sum of said product terms in said second array, and a third parallel input adder for adding the sums of said first and second parallel input adders.

Claim 5

Dependent Claim 48 words

A circuit according to claim 2 wherein said means for combining includes a plurality of dual four-bit adder stages, with each adder stage receiving partial sum and carry bits of two powers from both arrays and producing two sum bits and two carry bits for the next stage.

Claim 6

Dependent Claim 200 words

A multiplier circuit comprised of: first and second arrays of logic cells, with each array having input lines for receiving two multibit binary numbers that are to be multiplied together; each logic cell also including product means for producing a single power product term by multiplying together one bit from each of said two numbers; one subset of said cells in both arrays further including a respective two-bit adder, and another subset of said cells in both arrays further including a respective three-bit adder; said two-bit adders and said three-bit adders being interconnected within each array such that each array produces an intermediate result, in parallel with the other array, which consists of a partial sum of all product terms in an array and no more than one remaining carry-in for each bit of that partial sum; and parallel input adders for combining the intermediate results from both arrays to product the product of said numbers; wherein said product means of said first array and said product means of said second array are coupled to said input lines in a certain fashion such that each array produces substantially the same number of single power product terms of any particular power.

Claim 7

Dependent Claim 200 words

A multiplier circuit comprised of: first and second arrays of logic cells, with each array having input lines for receiving two multibit binary numbers that are to be multiplied together; each logic cell also including product means for producing a single power product term by multiplying together one bit from each of said two numbers; one subset of said cells in both arrays further including a respective two-bit adder, and another subset of said cells in both arrays further including a respective three-bit adder; said two-bit adders and said three-bit adders being interconnected within each array such that each array produces an intermediate result, in parallel with the other array, which consists of a partial sum of all product terms in an array and no more than one remaining carry-in for each bit of that partial sum; and parallel input adders for combining the intermediate results from both arrays to product the product of said numbers; wherein said product means of said first array and said product means of said second array are coupled to said input lines in a certain fashion such that each array produces substantially the same number of single power product terms of any particular power.

Claim 8

Dependent Claim 62 words

A circuit according to claim 5 wherein said first array produces a certain quantity of single power product terms of power k, wherein said second array produces another quantity of single power product terms of the same power k, and wherein said certain quantity and said another quantity differ by just one or are within 30% of each other, whichever is greater.

Claim 9

Dependent Claim 64 words

A circuit according to claim 5 wherein said parallel input adders include a first parallel input adder for producing a complete sum of said intermediate results from said first array; a second parallel input adder for producing a complete sum of said intermediate results from said second array; and a third parallel input adder for adding the sums of said first and second means.

Claim 10

Dependent Claim 51 words

A circuit according to claim 5 wherein said parallel input adders include a plurality of four-bit adder stages, with each adder stage receiving partial sum and carry bits of two powers in said intermediate results from both arrays and producing two sum bits and two carry bits for the next stage.

Claim 11

Dependent Claim 43 words

A circuit according to claim 5 wherein both of said arrays are integrated into a single semiconductor chip in respective triangular patterns which are spaced apart on the chip, and wherein said means for combining is disposed in the space between said patterns.

Claim 12

Dependent Claim 198 words

A multiplier circuit comprised of: multiple arrays of logic cells, with each array having input lines for receiving two multibit binary numbers that are to be multiplied together; each logic cell also including product means for producing single power product terms by multiplying together one bit from each of said two numbers; one subset of said cells in each array further including a respective two-bit adder, and another subset of said cells in each array further including a respective three-bit adder; said two-bit and said three-bit adders being interconnected within each array such that each array produces an intermediate result, in parallel with the other arrays, which consists of a partial sum of all product terms in an array and no more than one remaining carry-in for each bit of that partial sum; and means for combining the intermediate results from all arrays to produce the product of said numbers; wherein said product means of each array being coupled to said input lines in a certain fashion such that the number of single power product terms of any particular power which each array produces differ by just one or are within 30% of each other, whichever is greater.

Claim 13

Dependent Claim 198 words

A multiplier circuit comprised of: multiple arrays of logic cells, with each array having input lines for receiving two multibit binary numbers that are to be multiplied together; each logic cell also including product means for producing single power product terms by multiplying together one bit from each of said two numbers; one subset of said cells in each array further including a respective two-bit adder, and another subset of said cells in each array further including a respective three-bit adder; said two-bit and said three-bit adders being interconnected within each array such that each array produces an intermediate result, in parallel with the other arrays, which consists of a partial sum of all product terms in an array and no more than one remaining carry-in for each bit of that partial sum; and means for combining the intermediate results from all arrays to produce the product of said numbers; wherein said product means of each array being coupled to said input lines in a certain fashion such that the number of single power product terms of any particular power which each array produces differ by just one or are within 30% of each other, whichever is greater.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	1992-06-12	1992-12-12	1993-06-13	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	1996-06-12	1996-12-12	1997-06-13	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2000-06-12	2000-12-12	2001-06-13	$7700.00	Window Closed / Lapsed

Fast multiplier circuit incorporating parallel arrays of two-bit and three-bit adders

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag