Multiplier carry bit compression apparatus and method

• US 6,442,582 B1
• Filed: 06/17/1999
• Issued: 08/27/2002
• Est. Priority Date: 06/17/1999
• Status: Expired due to Term

• Current Assignee: ATI Technologies ULC (Advanced Micro Devices, Inc.)
• Original Assignee: ATI International SRL (Advanced Micro Devices, Inc.)
• Inventors: Hale, Stephen C.
• Primary Examiner(s): Malzahn, David H.
• Application Number:
  US09/335,351
• Time in Patent Office: 1,167 Days
• Field of Search: 708/629
• US Class Current: 708/629
• CPC Class Codes: G06F 7/5318 with column wise addition of partial products, e.g. using Wallace tree, Dadda counters G06F7/5324 takes precedence

Abstract

A multiplier carry bit compression apparatus and method for a multiplier using Wallace tree addition structures uses a plurality of early and late carry bit compression operations for each level of the Wallace tree addition structure. For each level in a Wallace tree addition structure, each early carry bit compression operation compresses early compression bits prior to each corresponding late carry bit compression operation that compresses late carry bits.

Claims

1. A multiplier carry bit compression apparatus for a multiplier using Wallace tree addition structures comprising:

a plurality of early carry bit compression circuits with at least one early carry bit compression circuit for each level of the Wallace tree addition structures; and

a plurality of late carry bit compression circuits with at least one late carry bit compression circuits for each level of the Wallace tree addition structures;

wherein for each of at least a first two levels, each early carry bit compression circuit compresses early compression bits prior to each corresponding late carry bit compression circuit compressing late carry bits.

2. The apparatus of claim 1 wherein the plurality of early carry bit compression circuits includes:

a first level early carry bit compression circuit;

a second level early carry bit compression circuit; and

a third level early carry bit compression circuit; and

wherein the plurality of late carry bit compression circuits includes;

a first level late carry bit compression circuit, operatively coupled to the first level early carry bit compression circuit;

a second level late carry bit compression circuit operatively coupled to the second level early carry bit compression circuit; and

a third level late carry bit compression circuit operative to generate a finial carry bit for a multiplication operation.

3. The apparatus of claim 2 including a first level partial products processing circuit including a first first level Wallace compression circuit, a second first level Wallace compression circuit, a third first level Wallace compression circuit and a fourth first level Wallace compression circuit and wherein the first level early carry bit compression circuit includes:

a first XOR circuit operatively coupled to receive at least one early carry bit from the first and second first level Wallace compression circuits and to generate a first, first level intermediate early carry result bit;

a second XOR circuit operatively coupled to receive at least one early carry bit from the third and fourth first level Wallace compression circuits and to generate a second first level intermediate early carry result bit; and

a third XOR circuit operatively coupled to the first and second XOR circuits, that receives the first and second first level intermediate early carry result bits and generates a reduced early carry result bit; and

wherein

the first level late carry bit compression circuit includes;

a fourth XOR circuit operatively coupled to receive at least one late carry bit from each of the first and second first level Wallace compression circuits and to generate a first, first level intermediate late carry result bit;

a fifth XOR circuit operatively coupled to receive at least one late carry bit from each of the third and fourth first level Wallace compression circuits and to generate a second, first level intermediate late carry result bit;

a sixth XOR circuit operatively coupled to the fourth and fifth XOR circuits, that receives the first and second first level intermediate late carry result bits and generates a reduced late carry result bit; and

a seventh XOR circuit operatively coupled to produce a final first level carry bit from the reduced early carry result bit and the reduced late carry result bit.

4. The apparatus of claim 2 including a second level partial products processing circuit including a first second level Wallace compression circuit and a second, second level Wallace compression circuit, and wherein the second level early carry bit compression circuit includes:

a first XOR circuit operatively coupled to receive at least one second level early carry bit from each of the first and second, second level Wallace compression circuits and to generate a first second level intermediate early carry result bit; and

wherein the second level late carry bit compression circuit includes;

a second XOR circuit operatively coupled to receive at least one second level late carry bit from each of the first and second second level Wallace compression circuits and to produce a first second level late carry result bit; and

wherein the second level partial products processing circuit further includes;

a third XOR circuit operatively coupled to produce a second level intermediate early carry result bit from a finial first level carry bit and the second, second level intermediate early carry result bit; and

a fourth XOR circuit operatively coupled to produce a finial first and second level carry result bit from the second level intermediate early carry result bit and the first second level late carry result bit.

5. The apparatus of claim 2 including a third level partial products processing circuit including a third level Wallace compression circuit and wherein the third level early carry bit compression circuit includes:

an XOR circuit operatively coupled to receive a third level early carry bit and a finial first and second level carry result bit and to produce a finial second and third level carry result bit; and

wherein the third level late carry bit compression circuit includes;

an XOR circuit operatively coupled to receive the finial second and third level carry result bit and a third level late carry bit to produce a finial most significant bit carry out bit.

6. The apparatus of claim 1 wherein the plurality of early carry bit compression circuits include at least one intermediate early carry compression circuit operative to produce a reduced early carry result bit from a plurality of early carry bits from a different addition structure in a first level.

7. The apparatus of claim 1 wherein the plurality of early and late carry bit compression circuits are comprised of exclusive OR circuits coupled to produce 2:

1 compression.

8. A multiplier carry bit compression apparatus for a multiplier using Wallace tree addition structures comprising:

a first level early carry bit compression circuit;

a second level early carry bit compression circuit; and

a third level early carry bit compression circuit;

a first level late carry bit compression circuit, operatively coupled to the first level early carry bit compression circuit;

a second level late carry bit compression circuit operatively coupled tot he second level early carry bit compression circuit; and

a third level late carry bit compression circuit operative to generate a final carry bit for a multiplication operation;

a first level partial products processing circuit including a first level Wallace compression circuit, a second first level Wallace compression circuit, a third first level Wallace compression circuit and a fourth first level Wallace compression circuit and wherein the first level early carry bit compression circuit includes;

a first XOR circuit operatively coupled to receive at least one early carry bit from the first and second first level Wallace compression circuits and to generate a first, first level intermediate early carry result bit;

a second XOR circuit operatively coupled to receive at least one early carry bit from the third and fourth first level Wallace compression circuits and to generate a second first level intermediate early carry result bit; and

a third XOR circuit operatively coupled to the first and second XOR circuits, that receives the first and second first level intermediate early carry result bits and generates a reduced early carry result bit; and

wherein

the first level late carry bit compression circuit includes;

a fourth XOR circuit operatively coupled to receive at least one late carry bit from each of the first and second first level Wallace compression circuits and to generate a first, first level intermediate late carry result bit;

a fifth XOR circuit operatively coupled to receive at least one late carry bit from each of the third and fourth first level Wallace compression circuits and to generate a second, first level intermediate late carry result bit;

a sixth XOR circuit operatively coupled to the fourth and fifth XOR circuits, that receives the first and second first level intermediate late carry result bits and generates a reduced late carry result bit; and

a seventh XOR circuit operatively coupled to produce a final first level carry bit from the reduces early carry result bit and the reduce late carry result bit.

9. The apparatus of claim 8 including a second level partial products processing circuit including a first second level Wallace compression circuit and a second, second level Wallace compression circuit, including:

a first XOR circuit operatively coupled to receive at least one second level early carry bit from each of the first and second, second level Wallace compression circuits and to generate a first, second level intermediate early carry result bit;

a second XOR circuit operatively coupled to produce a second level intermediate early carry result bit from a final first level carry bit and the second level intermediate early carry result bit;

a third XOR circuit operatively coupled to receive at least one second level late carry bit from each of the first and second, second level Wallace compression circuits and to produce a first, second level late carry result bit;

a fourth XOR circuit operatively coupled to produce a final first and second level carry result bit from the second level intermediate early carry bit and the first, second level late carry result bit.

10. The apparatus of claim 9 including a third level partial products processing circuit including a third level Wallace compression circuit and also including:

an XOR circuit operatively coupled to receive a third level early carry bit and a final first and second level carry result bit and to produce a final second and third level carry result bit; and

another XOR circuit operatively coupled to receive the final second and third level carry bit and a third level late carry bit to produce a final most significant bit carry out bit.

11. A multiplier carry bit compression method for a multiplier using Wallace tree addition structures comprising the steps of:

sequentially compressing early carry bits for each consecutive level among differing levels formed by the Wallace tree addition structures; and

compressing late carry bits for each respective level after first compressing corresponding early carry bits for each level to produce one final most significant bit as a carry out bit.

12. The method of claim 11 where the step of sequentially compressing early carry bits include the step of:

producing a reduced early carry result bit from a plurality of early carry bits from different addition structures in a first level.

13. The method of claim 11 wherein the step of sequentially compressing early carry bits includes the steps of:

compressing early carry bits from a first level of the Wallace Tree addition structures to generate first level intermediate early carry result bits; and

compressing the intermediate early carry result bits to produce a reduced early carry result bit; and

wherein the step of sequentially compressing late carry bits includes the steps of;

compressing late carry bits from the first level of the Wallace Tree addition structures to generate first level intermediate late level carry result bits; and

compressing the first level intermediate late level carry result bits to produce a late carry result bit.

14. The method of claim 13 further comprising the step of:

compressing the late carry result bit and reduced early carry result bit to produce a finial first level carry bit.

15. The method of claim 14 further comprising the steps of:

compressing early second level carry bits from a second level of the Wallace Tree addition structures to generate a first second level intermediate early carry result bits; and

compressing the finial first level carry bit with the second level intermediate early carry result bit to produce a second second level intermediate carry result bit.

16. The method of claim 15 further comprising the steps:

compressing second level late carry bits from a second level of the Wallace Tree addition structures to produce a second level late carry result bit; and

compressing the second second level intermediate carry result bit with the second level late carry result bit to obtain finial level one and level two carry result bit.

17. The method of claim 16 further comprising the steps of:

compressing the finial level one and level two carry result bit with a third level early carry bit to produce a finial second and third level carry result bit; and

compressing a third level late carry bit and the finial second and third level carry result bit to produce a finial most significant bit carry out bit.