Double incrementing, low overhead, adder

Details Double incrementing, low overhead, adder Double incrementing, low overhead, adder

1998-06-19

2001-03-06

Mai, Tan V. (Department: 2121)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

C708S703000, C708S707000, C708S713000

Reexamination Certificate

active

06199090

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to adders, and more specifically, the present invention relates to an adder capable of adding two binary numbers and double incrementing.
BACKGROUND OF THE INVENTION
A common operation in a computer is the adding of one (n+1)-bit binary value a (a[n:0]) by another (n+1)-bit binary value b (b[n:0]). For example, an eight bit value a[7:0] may be added to another eight bit value b[7:0]. In one implementation, corresponding bits from the i'th column location are added together along with carry bits c[i−1] generated from the previous i−1'th column to form a sum bit s[i] for the i'th column and a carry bit c[i] used for the next i+1'th column. A typical addition operation is shown as follows:
1,1100,011
(carry bits c [7:0])
  1111,0001
(bits a [7:0] = −15
10
)
+
  
0110,1011
(bits b [7:0] = 107
10
)
  0101,1100
(sum bits s [7:0] = 92
10
)
FIG. 1
shows a conventional column adder (adder
100
) for adding the i'th bits (a[i] and b[i]) of values a[n:0] and b[n:0], for i equals any integer from 0 to n, inclusive. Column adder
100
has three input lines
102
,
104
and
106
which carry signals respectively representing bit a[i] (the i'th bit of a[n:0]), bit b[i] (the i'th bit of b[n:0]), and carry bit c[i−1] (a carry bit from the next least significant i−1'th bit).
Lines
102
and
104
are input lines to an XOR gate (XOR
110
) which has an output line
112
carrying a signal representing propagate bit p[i]. Lines
102
and
104
are also input lines to an AND gate (AND
120
) which has output line
122
carrying a signal representing generate bit g[i]. Lines
106
and
112
are input lines to an XOR gate (XOR
130
) and an AND gate (AND
140
) which have respective output lines
132
and
142
. Line
132
carries a signal representing the sum bit s[i] of the i'th bit column. Lines
122
and
142
are input lines for an OR gate (OR
150
) which has output line
152
carrying a signal representing the carry bit c[i] generated by adding the i'th bit column.
FIG. 2
shows a truth table for column adder
100
which shows the three input bits a[i], b[i], and c[i−1] are added together to obtain a sum bit s[i] and a carry bit c[i]. For example,
FIG. 2
shows that equations (1) and (2) are true.
If z[i]<2, then s[i]=z[i] and c[i]=0  (1)
If z[i]≧2, then s[i]−z[i]−2 and c[i]=1  (2)
where z[i] is the number of input values (a[i], b[i], or c[i−1]) which equal 1.
n column adders similar to column adder
100
are arrayed such that each adder produces a sum and carry bit associated with the corresponding bit column and outputs a carry value to the neighboring more significant column adder. The array of adders thus perform the addition of the following equation (3).
s=a+b
  (3)
where
s is represented by bits s[n:0],
a is represented by bits a[n:0], and
b is represented by bits b[n:0].
When column 0 is being added (i=0), there is no carry value generated by the previous column i−1 because, by definition, there is no column −1. Conventionally, the input line
106
for column 0 has been used to increment the sum of a[n:0] and b[n:0] by w, which can be achieved by setting c[−
1
] equal to 1 or 0, as appropriate. Note that w is the weight of the least significant bit of a and b (e.g., w is 1 if a and b are integers). This allows the column adder
100
to perform both the addition and a single increment, as expressed in the following equation (4), to produce sum s.
s=a+b+w
  (4)
For example, implementing equation (4), the above longhand form would appear as follows:
1,1100,011
(carry bits c [7:−1])
  1111,0001
(bits a [7:0] = −15
10
)
+
  
0110,1011
(bits b [7:0] = 107
10
)
  0101,1100
(sum bits s [7:0] = 93
10
)
However, some applications require performing both the addition and the double increment expressed in equation (5).
 
s=a+b
+2
w
  (5)
A conventional way of accomplishing both addition and double increment (e.g., that of equation (5)) is to first perform both the addition and the single increment (e.g., that of equation (4)) using a single adder. Subsequently, an additional adder or incrementer increments the result from the first adder by w to complete the addition and double increment. However, this requires two adders or an adder and an incrementer which significantly increases the time and space needed to obtain the double incremented sum, compared to the time and space needed to obtain a single incremented sum.
Therefore, what is a faster way of obtaining a double incremented sum using less space.
SUMMARY OF THE INVENTION
In accordance with the present invention, an adder is provided for adding two input values. The adder includes an AND gate configured to receive bits of the two input values of a common weight (“first weight”). The AND gate has an output terminal configured to carry an AND'ed bit. A three input XOR gate is configured to receive bits of the two input values of a common weight (“second weight”) one bit more significant than the first weight. The three input XOR gate is configured to XOR these values with the AND'ed bit to generate a three input XOR'ed bit.
In accordance with the present invention, a method is also provided. In the method, bits of the two input values of a common weight (“first weight”) are logically AND'ed in an AND gate to generate an AND'ed bit. This AND'ed bit is logically XOR'ed, in a three input XOR gate, with bits of the two input values having a common weight (“second weight”) one bit more significant than the first weight, thereby generating a three input XOR'ed bit.
In accordance with the present invention, a method includes providing an AND gate configured to receive bits of the two input values of a common weight (“first weight”). The AND gate has an output terminal configured to carry an AND'ed bit. The method also includes providing a three input XOR gate configured to receive bits of the two input values of a common weight (“second weight”) one bit more significant than the first weight. The three input XOR gate is configured to XOR these values with the AND'ed bit to generate a three input XOR'ed bit.
The present invention allows for the addition of two values and double increment of the sum without using an extra adder or incrementer. Therefore, the present invention obtains a double incremented sum faster, and using less space, than conventionally known.
The present invention will be more fully understood in light of the following description and the accompanying claims.


REFERENCES:
patent: 4660165 (1987-04-01), Masumoto
patent: 5027310 (1991-06-01), Dalrymple
patent: 5504698 (1996-04-01), Su
patent: 5555517 (1996-09-01), Agrawal et al.
patent: 5586070 (1996-12-01), Purcell
patent: 5898602 (1999-04-01), Rothman et al.

Affiliated with

Also associated with

Rating

Double incrementing, low overhead, adder does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Double incrementing, low overhead, adder, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Double incrementing, low overhead, adder will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2510429