Reducing the number of carry-look-ahead adder stages in high-speed arithmetic units, structure and method

An add circuit for adding an addend and an augend and generating a final sum, the addend, augend, and final sum each being binary numbers having a plurality of bits, the bits of the same order in the addend and the augend forming columns, the add circuit comprising:

• at least one data reduction circuit, each data reduction circuit comprising at least one multi-column adder, the at least one data reduction circuit for using the columns of addend and augend bits to generate a reduced addend and a reduced augend, the reduced augend having fewer bits than the augend;
• a generate/propagate calculation circuit coupled to the at least one data reduction circuit for using the reduced addend and the reduced augend for calculating generate and propagate data, the generate/propagate calculation circuit having a number of stages, the number of stages being fewer than required to calculate generate and propagate data using the addend and the augend;
• a carry-generate circuit coupled to the generate/propagate calculation circuit for using the generate and propagate data to generate at least one final carry;
• and
• a final sum calculation circuit coupled to the carry-generate circuit for using the propagate data and the at least one final carry for calculating the final sum.

An add circuit for adding an addend and an augend and generating a final sum, the addend, augend, and final sum each being binary numbers having a plurality of bits, the bits of the same order in the addend and the augend forming columns, the augend having only specific non-zero bits, the add circuit comprising:

• a generate/propagate calculation circuit using the columns of addend and augend bits for calculating generate and propagate data, the generate and propagate data comprising a first generate datum and a first propagate datum for each group of consecutive columns where the augend bit for each of the consecutive columns is known to be logic zero, the first generate datum equal to logic zero and the first propagate datum equal to the logical AND of the addend bits in the consecutive columns;
• a carry-generate circuit coupled to the generate/propagate circuit for using the generate and propagate data to generate at least one final carry;
• and
• a final sum calculation circuit coupled to the carry-generate circuit for using the propagate data and the at least one final carry for calculating the final sum.

A method of adding an addend and an augend and generating a final sum, the addend, augend, and final sum each being binary numbers having a plurality of bits, the method comprising the steps of:

• organizing bits of the same order in the addend and the augend into columns;
• performing operations with the columns of addend and augend bits to generate a reduced addend and a reduced augend, the reduced augend having fewer bits than the augend;
• calculating generate and propagate data using the reduced addend and the reduced augend;
• generating at least one final carry using the generate and propagate data;
• and
• calculating the final sum using the propagate data and the at least one final carry.