Multiplier employing carry select or carry look-ahead adders in hierarchical tree configuration

Abstract

A multiplication circuit for a floating point digital processing system includes a partial products generator and a carry adder circuit for determining a product resulting from multiplication of an M bit multiplicand and an N bit multiplier. The partial products generator outputs to the carry adder circuit partial products based on the M bit multiplicand and N bit multiplier. The carry adder circuit contains a plurality of carry adders connected in a hierarchical tree structure such that a plurality of carry adder stages are defined, with each carry adder stage except a first carry adder stage receiving adder sums from a next adjacent, lower carry adder stage in the hierarchical tree structure. The first carry adder stage receives the partial products output from the partial products generator. The multiplication circuit is optimized by employing carry select adders or carry look-ahead adders in the hierarchical tree structure.

I claim: 
     
       1. A multiplier circuit comprising: a plurality of adders connected in a binary tree structure to complete multiplication of an M bit multiplicand (wherein M is an integer) and an N bit multiplier (wherein N=i, i being an integer) given partial products thereof, each adder of said plurality of adders having a number of bits equal to the number of bits M in the M bit multiplicand, and the number of adders in said binary tree structure being equal to the number of bits N in the N bit multiplier, multiple adder stages being defined by said binary tree structure, each adder of said plurality of adders outputting a sum and a carry;   a first adder stage of said multiple adder stages of said plurality of adders receiving pairs of partial products of said M bit multiplicand and said N bit multiplier, each adder of said first adder stage receiving partial product pairings such that the partial products are offset one bit position; and   a final adder stage of said multiple adder stages of said plurality of adders, said final adder stage being coupled to said first adder stage and connected to receive the carrys of all adders of said first adder stage, the sum and the carry of said final adder stage comprising a portion of the product resulting from multiplication of said M bit multiplicand and said N bit multiplier.   
     
     
       2. The multiplier circuit of claim 1, wherein a bit of a sum output by one adder of said first adder stage comprises a portion of the product resulting from multiplication of said M bit multiplicand and said N bit multiplier. 
     
     
       3. The multiplier circuit of claim 1, further comprising a partial products generator for producing said given partial products of said M bit multiplicand and said N bit multiplier. 
     
     
       4. The multiplier circuit of claim 3, further comprising a second adder stage comprising one of said multiple adder stages, said second adder stage being connected to said first adder stage such that each adder of said second adder stage receives sums from two corresponding adders of said first adder stage, said sums received by each adder of said second adder stage being offset two bit positions, and wherein at least two of said adders in said second adder stage also receive an uncollected partial product from said partial products generator, said final adder stage being coupled to said second adder stage and connected to receive the carrys of all adders of said second adder stage. 
     
     
       5. The multiplier circuit of claim 4, wherein two bits of said product resulting from multiplication of said M bit multiplicand and said N bit multiplier are produced by said second adder stage. 
     
     
       6. The multiplier circuit of claim 4, further comprising a third adder stage comprising one of said multiple adder stages, said third adder stage being connected to said second adder stage such that each adder of said third adder stage receives sums from two corresponding adders of said second adder stage, said sums received by each adder of said third adder stage being offset four bit positions, and wherein at least one of said adders in said third adder stage also receives an uncollected partial product of said M bit multiplicand and said N bit multiplier, said final adder stage being coupled to said third adder stage and connected to receive the carrys of all adders of said third adder stage. 
     
     
       7. The multiplier circuit of claim 6, wherein an adder of said third adder stage outputs four bits of said product resulting from multiplication of said M bit multiplicand and said N bit multiplier. 
     
     
       8. The multiplier circuit of claim 6, further comprising a fourth adder stage comprising one of said multiple adder stages, said fourth adder stage being connected to said third adder stage such that each adder of said fourth adder stage receives sums from two corresponding adders of said third adder stage, said sums received by each adder of said fourth adder stage being offset eight bit positions, said fourth adder stage receiving an uncollected partial product of said M bit multiplicand and said N bit multiplier, said final adder stage being coupled to said fourth adder stage and connected to receive the carrys of all adders of said fourth adder stage. 
     
     
       9. The multiplier circuit of claim 8, wherein an adder of said fourth adder stage outputs eight bits of the product resulting from multiplication of said M bit multiplicand and said N bit multiplier. 
     
     
       10. The multiplier circuit of claim 8, wherein the number of bits M in the M bit bit multiplicand equals the number of bits N in the N bit multiplier, and wherein M=N=16. 
     
     
       11. The multiplier circuit of claim 1, wherein each of said adders of said plurality of adders comprises one of a carry select adder and a carry look-ahead adder. 
     
     
       12. A binary multiplier circuit for determining a product of an M bit multiplicand (wherein M is an integer) and an N bit multiplier (wherein N=4i, i being an integer) given partial products thereof, said binary multiplier circuit comprising: a plurality of adders connected in a binary tree configuration to complete multiplication of said M bit multiplicand and said N bit multiplier based on said partial products, said plurality of adders connected in said binary tree configuration having a plurality of adder stages, each adder of said plurality of adders outputting a sum and a carry;   a first adder stage of said plurality of adder stages collecting pairs of partial products of said M bit multiplicand and said N bit multiplier offset one bit position;   a second adder stage of said plurality of adder stages connected to said first adder stage such that each adder of said second adder stage receives sums from two corresponding adders of said first adder stage, said sums received by each adder of said second adder stage being offset two bit positions, and wherein at least two of said adders of said second adder stage also receive an uncollected partial product of said M bit multiplicand and said N bit multiplier for combining with received sums; and   a final adder stage coupled to said first adder stage and said second adder stage, said final adder stage outputting a portion o the product of said M bit multiplicand and said N bit multiplier.   
     
     
       13. The multiplier circuit of claim 12, wherein an adder of said first adder stage outputs one bit of the product resulting from multiplication of said M bit multiplicand and said N bit multiplier, and wherein an adder of said second stage outputs two bits of the product resulting from multiplication of said M bit multiplicand and said N bit multiplier. 
     
     
       14. The multiplier circuit of claim 12, further comprising a third adder stage comprising one of said plurality of adder stages, said third adder stage being connected to said second adder stage such that each adder of said third adder stage receives sums from two corresponding adders of said second adder stage, said sums received by each adder of said third adder stage being offset four bit positions, and wherein at least one of said adders of said third adder stage also receives an uncollected partial product of said M bit multiplicand and said N bit multiplier, said final adder stage being coupled to said third adder stage. 
     
     
       15. The multiplier circuit of claim 14, wherein said third adder stage outputs four bits of said product resulting from multiplication of said M bit multiplicand and said N bit multiplier. 
     
     
       16. The multiplier circuit of claim 14, further comprising a fourth adder stage comprising one of said plurality of adder stages, said fourth adder stage being connected to said third adder stage such that each adder of said fourth adder stage receives sums from two corresponding adders of said third adder stage, said sums received by each adder of said fourth adder stage being offset eight bit positions, and wherein at least one adder of said fourth adder stage also receives an uncollected partial product of said M bit multiplicand and said N bit multiplier, said final adder stage being coupled to said fourth adder stage. 
     
     
       17. The multiplier circuit of claim 16, wherein said fourth adder stage outputs eight bits of said product resulting from multiplication of said M bit multiplicand and said N bit multiplier. 
     
     
       18. The multiplier circuit of claim 16, wherein the number of bits M in the M bit multiplicand equals the number of bits N in the N bit multiplier, and wherein M=N=16. 
     
     
       19. The multiplier circuit of claim 16, wherein said final adder stage is connected to receive carry from all adders in the first adder stage, second adder stage, third adder stage and fourth adder stage, a sum and a carry output from said final adder stage comprising a portion of the product resulting from multiplication of said M bit multiplicand and said N bit multiplier. 
     
     
       20. A multiplication circuit for high speed multiplication in a computer system, said multiplication circuit comprising: a partial products generator having a first input for receiving a binary multiplicand and a second input for receiving a binary multiplier, said partial products generator outputting partial products based on said binary multiplicand and said binary multiplier;   a carry adder circuit for producing a sum and a carry from said partial products output from said partial products generator, said carry adder circuit including a plurality of carry adders arranged in multiple adder stages and connected in a hierarchical tree structure such that each carry adder stage except a first carry adder stage receives sums from a next adjacent, lower carry adder stage in the hierarchical tree structure, said first carry adder stage receiving most of the partial products output from said partial products generator; and   wherein each adder within said carry adder circuit comprises one of a carry select adder and a carry look-ahead adder.   
     
     
       21. The multiplication circuit of claim 20, wherein said multiple adder stages include a final adder stage adder connected to receive carrys of all adders in all other stages of the hierarchical tree structure, the sum and the carry of the final adder stage adder comprising a portion of the product resulting from multiplication of said binary multiplicand and said binary multiplier. 
     
     
       22. The multiplication circuit of claim 20, wherein each of said multiple carry adder stages contributes at least one bit to the product resulting from multiplication of said binary multiplicand and said binary multiplier. 
     
     
       23. The multiplication circuit of claim 20, wherein each adder stage of said multiple adder stages receives at least one partial product from said partial products generator. 
     
     
       24. The multiplication circuit of claim 20, wherein a second adder stage comprises one of said multiple adder stages, said second adder stage being connected to said first adder stage such that each adder of said second adder stage receives sums from two corresponding adders of said first adder stage, said sums received by each adder of said second adder stage being offset two bit positions. 
     
     
       25. The multiplication circuit of claim 24, wherein a third carry adder stage comprises one of said multiple adder stages, said third adder stage being connected to said second adder stage such that each adder of said third adder stage receives sums from two corresponding adders of said second adder stage, said sums received by each adder of said third adder stage being offset four bit positions. 
     
     
       26. The multiplication circuit of claim 25, wherein a fourth carry adder stage comprises one of said multiple adder stages, said fourth carry adder stage being connected to said third carry adder stage such that each adder of said fourth adder stage receives sums from two corresponding adders of said third adder stage, said sums received by each adder of said fourth adder stage being offset eight bit positions.