High-speed hexadecimal adding method and system

Details High-speed hexadecimal adding method and system High-speed hexadecimal adding method and system

2000-01-10

2003-04-08

Ngo, Chuong Dinh (Department: 2787)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

C708S493000

Reexamination Certificate

active

06546410

ABSTRACT:

TECHNICAL FIELD
The present invention relates generally to computer systems and more particularly to high-speed adder circuitry in and a method for such systems.
BACKGROUND ART
The “brain” of most computer systems is a microprocessor, the “brain” of most microprocessors is composed of arithmetic logic units (ALU), and the “brain” 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 (“0”) and the other carry assumes a carry-in signal to the summand as logic one (“1”). 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.
DISCLOSURE OF THE INVENTION
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 “F”, placing the value of the addition in a Digit
1
and placing a “0” in a Dot
1
; and, if the answer of the addition is greater than hexadecimal “F”, placing the value of the addition without the carry in the Digit
1
and placing a “1” in the Dot
1
.
Adding the second least significant digits and: if the answer of the addition is less than hexadecimal “F”, placing the value of the addition in a Digit
2
and placing a “0” in a Dot
2
; and, if the answer of the addition is greater than or equal to hexadecimal “F”, subtracting the value of “1” from the value of the addition without the carry and placing this new value in the Digit
2
and placing a “1” in the Dot
2
.
Determining the least significant hexadecimal digit, FSum
1
, as FSum
1
=Digit
1
.
Determining the second least significant digit, FSum
2
, as FSum
2
=Digit
2
+Dot
2
+Dot
1
=SumA.
Determining the third least significant digit, FCarry, by examining SumA for the certain pattern E
—
1
—
0. If the pattern E
—
1
—
0 is detected in SumA, then FCarry=hexadecimal “0”. If the pattern E
—
1
—
0 is not detected in SumA, then FSum
3
=Dot
2
.
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

Affiliated with

Also associated with

Rating

High-speed hexadecimal adding method and system does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with High-speed hexadecimal adding method and system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and High-speed hexadecimal adding method and system will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3034118