The present invention relates generally to computer systems and more particularly to high-speed adder circuitry in and a method for such systems.
The xe2x80x9cbrainxe2x80x9d of most computer systems is a microprocessor, the xe2x80x9cbrainxe2x80x9d of most microprocessors is composed of arithmetic logic units (ALU), and the xe2x80x9cbrainxe2x80x9d of an ALU is made up of adder circuitry. Basic adder circuits, or adders, are used in adder circuitry, and adder circuitry is used to build other circuitry for performing subtraction, multiplication, division, and other operations.
In the past, electronic digital circuitry having conventional logic elements were used as adder circuitry for adding two binary numbers together and providing the appropriate carry-out and carry-in operations. Typical types of adder circuitry include carry-ripple, conditional sum/carry-selection, and carry-look-ahead parallel adder circuitry.
The carry-ripple adder circuitry uses full adder logic circuitry having a first and a second summand input into the logic circuitry plus a carry-out signal from a previous bit as a third input into the logic circuitry. In this circuitry, the carry bit is propagated from the least significant bit to the most significant bit.
While the carry-ripple adder circuitry is extremely simple, the carry bit must propagate through each stage of the logic circuitry so there is a significant propagation delay which limits adding speed and which increases with large bit width adder circuitry.
The conditional sum/carry-selection adder circuitry uses fewer logic circuits than the carry-look-ahead parallel adder circuitry. It consists of conventional logic circuitry with switches to select particular logic levels. Two sums are calculated along with two sets of carries. One carries a carry-in signal to the summand as logic zero (xe2x80x9c0xe2x80x9d) and the other carry assumes a carry-in signal to the summand as logic one (xe2x80x9c1xe2x80x9d). Based on the actual logic value of the carry-in signal, a correct sum signal and a carry-out signal is selected. The conditional sum/carry-selection adder circuitry uses less logic circuitry than the carry-look-ahead adder circuitry and therefore requires a small chip surface area to implement. However, it introduces propagation delays because a carry-in signal bit is propagated from the least significant bit to the most significant bit within each logic block. For wide-bit width adder circuitry, there is a significant propagation delay that limits circuit operation speed.
The carry-look-ahead adder circuitry is used to increase the operational speed for an arithmetic process. It uses standard full adder logic circuitry with a first set of input lines for each bit, plus a separate set of carry lines tied to the input lines to separately determine whether a carry will occur. For example, the carry-look-ahead circuit may evaluate the four low-order input bit signals of two 8-bit numbers being added together to determine if they will generate a carry-out from downstream full adder circuitry. The four higher order inputs can then be added together without having to wait for the carries to propagate through the low-order fill adder logic circuitry.
In the carry-look-ahead adder circuitry, each summand input signal is broken into input blocks with each input block being added independently with a carry-in signal and, if necessary, producing a carry-out signal. The carry-out signals are calculated through the use of logic carry-out blocks. The carry-out signal for each input block is calculated from each carry-out block from the summand input. The calculations are then cascaded together to form wider-bit adder circuitry.
The difficulty with the carry-look-ahead adder circuitry is the need for duplicative logic circuitry for implementing a summand input and a carry-out for each circuit stage. As the number of stages increases, the number of carry-out blocks increases exponentially. The increased stages increase the number of propagation delays for large-bit width adder circuitry and there is a significant increase in chip surface area needed to implement the adder circuitry. This increases the cost for incorporating the necessary logic circuitry for each circuit stage, and an increase in propagation delays that would cancel out initial increases in operational speed.
Essentially, current adder circuitry is subject to internal propagation delays that double each time the number of bits in the addition doubles. This makes current adder circuitry slower when the number of bits needed to perform the addition operation increases. For example, the addition of two 16-bit numbers requires 5 steps to obtain the result and, with each step requiring a 1-unit delay, the propagation delay would be 5 units. When two 32-bit numbers are being added, the current adder circuitry would require 9 steps to obtain the results, and the total delay would be 9 units. When the adder circuitry adds two 64-bit numbers, a total of 17 steps would be required for 17 units of delay.
Over the years, many different mathematical methods have been examined to determine a faster method of addition. Decades ago, a mathematical method was introduced by Jakow Trachtenberg which enabled very quick calculations to be made. However, the mathematical method was applied only to decimal calculations and did not appear to applicable to hexadecimal calculations which are used in computers. Thus, it was long believed that it would not be possible to use the Trachtenberg mathematical method for hexadecimal using computer systems.
Thus, the search has been long ongoing for faster adder circuitry. Unfortunately, it has been a considerable number of years since there have been any significant improvements in the architecture of the adder circuitry and it has not been thought possible by those skilled in the art to substantially increase the speed of basic adder circuitry.
The present invention provides a reduced mathematical method for adding two hexadecimal numbers by adding digits, placing the sums into a plurality of positions, identifying certain patterns, adding numbers in the plurality of positions, and using the identified patterns to derive the answer.
The present invention further provides a reduced mathematical method for adding two 8-bit hexadecimal numbers by adding digits, placing the sums into a plurality of positions, identifying certain patterns, adding numbers in the plurality of positions, and using the identified patterns to derive the answer by:
Adding the first least significant digits of two hexadecimal numbers and: if the answer of the addition is less than or equal to hexadecimal xe2x80x9cFxe2x80x9d, placing the value of the addition in a Digit1 and placing a xe2x80x9c0xe2x80x9d in a Dot1; and, if the answer of the addition is greater than hexadecimal xe2x80x9cFxe2x80x9d, placing the value of the addition without the carry in the Digit1 and placing a xe2x80x9c1xe2x80x9d in the Dot1.
Adding the second least significant digits and: if the answer of the addition is less than hexadecimal xe2x80x9cFxe2x80x9d, placing the value of the addition in a Digit2 and placing a xe2x80x9c0xe2x80x9d in a Dot2; and, if the answer of the addition is greater than or equal to hexadecimal xe2x80x9cFxe2x80x9d, subtracting the value of xe2x80x9c1xe2x80x9d from the value of the addition without the carry and placing this new value in the Digit2 and placing a xe2x80x9c1xe2x80x9d in the Dot2.
Determining the least significant hexadecimal digit, FSum1, as FSum1=Digit1.
Determining the second least significant digit, FSum2, as FSum2=Digit2+Dot2+Dot1=SumA.
Determining the third least significant digit, FCarry, by examining SumA for the certain pattern Exe2x80x941xe2x80x940. If the pattern Exe2x80x941xe2x80x940 is detected in SumA, then FCarry=hexadecimal xe2x80x9c0xe2x80x9d. If the pattern Exe2x80x941xe2x80x940 is not detected in SumA, then FSum3=Dot2.
The present invention further provides a reduced mathematical method for adding two 16-bit hexadecimal numbers by adding digits, placing the sums into a plurality of positions, identifying certain patterns, adding numbers in the plurality of positions, and using the identified patterns to arrive at the answer by:
Adding the first least significant digits of two hexadecimal numbers and: if the answer of the addition is less than or equal to hexadecimal xe2x80x9cFxe2x80x9d, placing the value of the addition in a Digit1 and placing a xe2x80x9c0xe2x80x9d in a Dot1; and, if the answer of the addition is greater than hexadecimal xe2x80x9cFxe2x80x9d, placing the value of the addition without the carry in the Digit1 and placing a xe2x80x9c1xe2x80x9d in the Dot1.
Adding the second least significant digits and: if the answer of the addition is less than hexadecimal xe2x80x9cFxe2x80x9d, placing the value of the addition in a Digit2 and placing a xe2x80x9c0xe2x80x9d in a Dot2; and, if the answer of the addition is greater than or equal to hexadecimal xe2x80x9cFxe2x80x9d, subtracting the value of xe2x80x9c1xe2x80x9d from the value of the addition without the carry and placing this new value in the Digit2 and placing a xe2x80x9c1xe2x80x9d in the Dot2.
Adding the third least significant digits and: if the answer of the addition is less than hexadecimal xe2x80x9cFxe2x80x9d, placing the value of the addition in the Digit3 and placing a xe2x80x9c0xe2x80x9d on Dot3; and, if the answer of the addition is greater than or equal to hexadecimal xe2x80x9cFxe2x80x9d, subtracting the value of xe2x80x9c1xe2x80x9d from the value of the addition without the carry and placing this new value in the Digit3 and placing a xe2x80x9c1xe2x80x9d in the Dot3.
Adding the fourth least significant digits and: if the answer of the addition is less than hexadecimal xe2x80x9cFxe2x80x9d, placing the value of the addition on Digit4 and placing a xe2x80x9c0xe2x80x9d on Dot4; and, if the answer of the addition is greater than or equal to hexadecimal xe2x80x9cFxe2x80x9d, subtracting the value of xe2x80x9c1xe2x80x9d from the value of the addition without the carry and placing this new value on Digit4 and placing a xe2x80x9c1xe2x80x9d in the Dot4.
Determining the least significant hexadecimal digit, FSum1, as FSum1=Digit1.
Determining the second least significant digit, FSum2, as FSum2=Digit2+Dot2+Dot1=SumA.
Determining the third least significant digit, FSum3, by examining SumA for the certain pattern Exe2x80x941xe2x80x940. If the pattern Exe2x80x941xe2x80x940 is detected in SumA, then FSum3=Digit3+Dot3=Sum3. If the pattern Exe2x80x941xe2x80x940 is not detected in SumA, then FSum3=Digit3+Dot3+Dot2=SumB.
Determining the fourth least significant digit, FSum4, by examining SumB and SumA for the pattern Exe2x80x941xe2x80x940, and Sum3 for the pattern Exe2x80x941. If the pattern Exe2x80x941xe2x80x940 detected in SumB, then FSum4=Digit4+Dot4=Sum4. If the pattern Exe2x80x941xe2x80x940 is detected in SumA and pattern Exe2x80x941 is detected in Sum3, then FSum4=Digit4+Dot4=Sum4. If neither pattern is detected then FSum4=Digit4+Dot4+Dot3=SumC.
Determining the fifth least significant digit, Fcarry, by examining SumC, SumB, and SumA for the pattern Exe2x80x941xe2x80x940. If the pattern Exe2x80x941xe2x80x940 is detected in SumC, then FCarry=hexadecimal xe2x80x9c0xe2x80x9d. If pattern Exe2x80x941xe2x80x940 is detected in SumB and pattern Exe2x80x941 is detected in Sum4, then FCarry=hexadecimal xe2x80x9c0xe2x80x9d. If pattern Exe2x80x941xe2x80x940 is detected in SumA, and pattern Exe2x80x941 is detected in Sum4 and Sum3, then FCarry=hexadecimal xe2x80x9c0xe2x80x9d. If none of the patterns is detected, then FCarry=Dot4.
The present invention further provides adder circuitry based on a reduced mathematical method to provide high-speed hexadecimal addition. A first adder adds the least significant binary digits of two hexadecimal numbers to provide a Digit1 and a Dot1, and a second adder adds the second least significant binary digits to provide a Digit2 plus a Dot2 as a Sum2 and a CarryA. A seondary adder adds the Dot1 and the Sum2 to provide the sum of Digit2 plus Dot2 and Dot1 as a SumA. A generator generates a Dot2 of hexadecimal xe2x80x9c1xe2x80x9d for certain values of the Sum2 and the CarryA, and a detector triggers an output device, which outputs a hexadecimal xe2x80x9c0xe2x80x9d, to output the Dot2 in response to a certain pattern of hexadcecimal numbers in the Dot1 and the Sum2. Thus, the least signifigant digit of the added hexadecimal numbers is Digit1, the second least significant digit is SumA, and the third least significant digit is the output of the output device.
The present invention further provides adder circuitry based on a reduced mathematical method to provide high-speed hexadecimal addition. A first adder adds the least significant binary digits of two hexadecimal numbers to provide a Digit1 and a Dot1. A second adder adds the second least significant binary digits to provide a Digit2 plus a Dot2 as a Sum2 and a CarryA. A third adder adds the third least significant binary digits to provide a Digit3 plus a Dot3 as a Sum3 and a CarryB. A fourth adder adds the fourth least significant binary digits to provide a Digit4 plus a Dot4 as a Sum4 and a CarryC. A first secondary adder adds the Dot1 and the Sum2 to provide the sum of Digit2 plus Dot2 and Dot1 as a SumA. A first generator generates a Dot2 of hexadecimal xe2x80x9c1xe2x80x9d for certain values of the Sum2 and the CarryA. A second secondary adder adds the Dot2 and the Sum3 to provide the sum of Digit3 plus Dot3 and Dot2 as a SumB. A second generator generates a Dot3 of hexadecimal xe2x80x9c1xe2x80x9d for certain values of the Sum3 and the CarryB. A third secondary adder adds the Dot3 and the Sum4 to provide the sum of Digit4 plus Dot4 and Dot3 as a SumC. A third generator generates a Dot4 of hexadecimal xe2x80x9c1xe2x80x9d for certain values of the Sum4 and the CarryC. A first detector triggers a first output device, which outputs the Sum3, to output the SumB in response to a certain pattern of hexadcecimal numbers in the Dot1 and the Sum2. A second detector triggers a second output device, which outputs the Sum4, to output the SumC in response to a certain pattern of hexadcecimal numbers in the Dot2, Sum3, Dot1, and Sum2. A third detector triggers a third output device, which outputs a hexadecimal xe2x80x9c0xe2x80x9d, to output the Dot4 in response to a certain pattern of hexadcecimal numbers in the Dot3, Sum4, Dot2, Sum3, Dot1, and Sum2. Thus, the least signifigant digit of the added hexadecimal numbers is Digit1; the second least significant digit is SumA; the third least significant digit is the output of the first output device; the fourth least significant digit is the output of the second output device; and the fifth least significant digit is the output of the third output device.
The above and additional advantages of the present invention will become apparent to those skilled in the art from a reading of the following detailed description when taken in conjunction with the drawings.
USPTO Backgrounds
USPTO Backgrounds