Circuit and method for adding binary numbers with a difference of one or less

The subject invention is a circuit and method of providing the sum of first and second n bit binary numbers having a difference of one or less. The method comprises combining the least significant bits of the numbers in a first coincidence gate to provide the least significant bit of the sum, combining the nth and (n-1)st bits of the numbers in a first logic network to provide the most significant bit of the sum, and combining solely the ith and (i-1)st bits of the numbers in an ith logic network to provide the ith bit of the sum, for all values of i where 1<i<n+1.

The present invention relates generally to electronic circuits, and more 
particularly to circuits for adding binary numbers. 
BACKGROUND OF THE INVENTION 
Since addition of binary numbers is common in a computer, it is desirable 
to perform this operation quickly. A typical adder is constructed from a 
plurality of logic gates with each gate introducing a delay to the 
operation. Because of the requirement to generate a carry bit when adding 
two numbers, the ripple or propagation delay increases with the number of 
bits in the numbers. For example, adding two digits and a carry bit 
requires a minimum delay path of two gates in order to generate both the 
digit and the next carry bit. If two n-bit numbers are added in this 
manner, a delay path of 2.sup.n gates would be anticipated. Such delays 
are obviously undesirable, particularly for large values of n. 
It is possible to reduce the propagation delay. For example, logic arrays 
consisting of many logic gates can be designed to handle more than a 
single pair of digits simultaneously. A typical logic array, such as a 
745283 chip with four full adders, adds two four bit binary numbers with a 
maximum delay path of three gates from the input of any gate to the carry 
bit. When such adders are cascaded to add larger numbers, the delay will 
increase. The delay path for two n-bit numbers is generally about 3n/4 
gates. In general, the delay in adders is a function of the complexity and 
cost of the gating network used. 
One application for adders in a computer is associated with first-in, 
first-out (FIFO) memory buffer designs. For example, one FIFO memory 
design employs four eight bit FIFO buffers which serve as a buffer between 
an eight bit and 32 bit data bus. Data that is received on the eight bit 
data bus is sequentially distributed to respective ones of the FIFO 
buffers. Data is read out of the FIFO buffers in parallel onto the 32 bit 
data bus. Conversely, data that is received on the 32 bit data bus is 
stored across all four FIFO buffers, and is read out sequentially from the 
buffers onto the eight bit data bus. Each FIFO buffer has a write and read 
pointer associated therewith to track the next location in the buffer 
where data is to be written to and read from, respectively. The difference 
between the write and read pointers is referred to as the count and 
represents the amount of memory space occupied within a FIFO buffer. The 
buffer counts have a particular relationship in that the greatest 
difference between the largest and smallest count will always be one or 
less. In order to know the total amount of data in all four buffers, the 
counts for each buffer must be added. The use of conventional adders for 
this operation would create the normal delays as discussed above. 
OBJECTS OF THE INVENTION 
It is therefore an object of the present invention to provide a new and 
improved circuit for adding binary numbers with a difference of one or 
less. 
It is another object of the present invention to provide a new and improved 
method for adding binary numbers with a difference of one or less. 
It is a further object of the present invention to provide an adder for 
binary numbers with a difference of one or less which has a reduced number 
of gate delays. 
It is yet another object of the present invention to provide an adder for 
binary numbers with a difference of one or less which has the same number 
of gate delays irrespective of the number of bits in the binary numbers. 
It is yet a further object of the present invention to provide an adder for 
binary numbers with a difference of one or less which has a maximum of two 
gate delays irrespective of the number of bits in the binary numbers. 
SUMMARY OF THE INVENTION 
One form of the present invention is a circuit for providing the sum of 
first and second n bit binary numbers having a difference of one or less. 
The circuit comprises a plurality of coincidence gates. A first 
coincidence gate receives the least significant bit of each of the numbers 
and provides the least significant bit of the sum. Each of n-1 second 
coincidence gates receives the (i-1)st bit of each of the numbers 
(l&lt;i&lt;n+1), each of n-1 third coincidence gates receives the ith bit of 
each of the numbers, and each of n-1 fourth coincidence gates receives the 
output of respective ones of the second and third gates and provides the 
ith significant bit of the sum. A fifth coincidence gate receives the nth 
bit of each of the numbers, a sixth coincidence gate receives the nth and 
(n-1)st bits of the first number, a seventh coincidence gate receives the 
nth and (n-1)st bits of the second number, and an eighth coincidence gate 
receives the output of the fifth, sixth and seventh gates and provides the 
(n+1)st significant bit of the sum. 
Another form of the present invention is a method of providing the sum of 
first and second n bit binary numbers having a difference of one or less. 
The method comprises combining the least significant bits of the numbers 
in a first coincidence gate to provide the least significant bit of the 
sum, combining the nth and (n-1)st bits of the numbers in a first logic 
network to provide the most significant bit of the sum, and combining 
solely the ith and (i-1)st bits of the numbers in an ith logic network to 
provide the ith bit of the sum, for all values of i where l&lt;i&lt;n+1.

DESCRIPTION OF A PREFERRED EMBODIMENT 
FIG. 1 shows an adder circuit 10 for adding two n bit binary numbers A and 
B, where A and B have a difference of one or less. A is represented by 
binary digits A.sub.n, A.sub.n-1, . . . , A.sub.i, . . . , A.sub.2, 
A.sub.1, with A.sub.n being the most significant digit and A.sub.1 being 
the least significant digit. Similarly B is represented by binary digits 
B.sub.n, B.sub.n-1, . . . , B.sub.i, . . . , B.sub.2, B.sub.1, with 
B.sub.n being the most significant digit of B and B.sub.1 being the least 
significant digit. The sum of the two numbers A and B is designated as S 
and is represented by binary digits S.sub.n+1, S.sub.n, . . . , S.sub.i, . 
. . , S.sub.2, S.sub.1, with S.sub.n+1 being the most significant digit 
and S.sub.1 being the least significant digit. The value of i in the sum S 
is such that l&lt;i&lt;n+1. 
Circuit 10 comprises a plurality of coincidence gates which receive the 
various binary digits of the numbers A and B and provide an output of the 
binary digits of the sum S. The circuit includes an Exclusive OR gate 12 
for receiving the least significant bits A.sub.1 and B.sub.1 of each of 
the numbers A and B, respectively. Gate 12 provides the least significant 
bit S.sub.1 of the sum S at its output. 
Circuit 10 further includes AND gates 14, 16 and 18, and OR gate 20. AND 
gate 14 receives the most significant bits A.sub.n and B.sub.n of the 
numbers A and B, respectively. AND gate 16 receives the most significant 
bit A.sub.n and second most significant bit A.sub.n-1 of the number A. AND 
gate 18 receives the most significant bit B.sub.n and second most 
significant bit B.sub.n-1 of the number B. OR gate 20 receives as inputs 
the outputs of AND gates 14, 16 and 18 and provides the most significant 
bit S.sub.n+1 of the sum S at its output. 
Circuit 10 also includes n-1 sets 22 of coincidence gates, each set 22 
comprising three coincidence gates. Each set 22 includes an AND gate, 
Exclusive OR gate and OR gate. For example, the set which generates the 
ith bit S.sub.i includes AND gate 24, Exclusive OR gate 26 and OR gate 28. 
And gate 24 receives as inputs the (i-1)st bits A.sub.i-1 and B.sub.i-1 of 
the numbers A and B, respectively. Exclusive OR gate 26 receives as inputs 
the ith bits A.sub.i and B.sub.i of the numbers A and B, respectively. OR 
gate 28 receives as inputs the output of AND gate 24 and Exclusive OR gate 
26 and provides the ith significant bit S.sub.i of the sum S at its 
output. As a further example, the set 22 which generates the second least 
significant bit S.sub.2 of the sum S, includes AND gate 30, Exclusive OR 
gate 32 and OR gate 34. And gate 30 receives as inputs the least 
significant bits A.sub.1 and B.sub.1 of the numbers A and B, respectively. 
Exclusive OR gate 32 receives as inputs the second least significant bits 
A.sub.2 and B.sub.2 of the numbers A and B, respectively. OR gate 34 
receives as inputs the output of AND gate 30 and Exclusive OR gate 32 and 
provides the second least significant bit S.sub.2 of the sum S at its 
output. 
A feature of the subject invention is that there are no carry bits 
generated during the addition of the numbers A and B. The least 
significant bits A.sub.1 and B.sub.1 are combined in Exclusive OR gate 12 
and the least significant bit S.sub.1 is provided. The nth bits A.sub.n 
and B.sub.n and (n-1)st bits A.sub.n-1 and B.sub.n-1 are combined in AND 
gates 14, 16 and 18 and OR gate 20 and the most significant bit S.sub.n+1 
is provided. For all of the other bits of the sum S, solely the ith and 
(i-1)st bits are combined and there is no carry bit required. Since there 
is no carry bit to include in any of the partial sums, all of the bits of 
the sum S are generated substantially simultaneously. Thus, the maximum 
delay associated with the addition of A and B will be two gates. Moreover, 
this delay will not increase irrespective of the value of n, i.e., the 
number of digits in the numbers A and B. 
A further application of the subject invention is illustrated in FIG. 2. 
Rather than adding just two numbers A and B, the FIG. 2 embodiment 
illustrates the addition of four numbers A, B, C and D, all having a 
difference of one or less. Furthermore, the sum of A and C and the sum of 
B and D will have a difference of one or less. An example of four numbers 
having this relationship is found in FIFO memory devices such as described 
above in the Background of the Invention. As long as four FIFO buffers are 
filled sequentially and emptied in parallel, the data count of the buffers 
will exhibit the relationship described above. FIG. 2 shows three adder 
circuits 10a, 10b and 10c, each similar to the adder circuit 10 
illustrated in FIG. 1. Circuit 10a will combine n bit numbers A and C 
which have a difference of one or less and provide an n+1 bit sum S.sub.AC 
on its output. Circuit 10b will combine n bit numbers B and D which have a 
difference of one or less and provide an n+1 bit sum S.sub.BD on its 
output. Circuit 10c will combine n+1 bit numbers S.sub.AC and S.sub.BD 
which have a difference of one or less and provide an n+2 bit sum S on its 
output. S is the sum of the four numbers A, B, C and D. 
It will be clear to those skilled in the art that the present invention is 
not limited to the specific embodiment disclosed and illustrated herein. 
Nor is the invention limited to an application for adding FIFO buffer 
counts. Rather, the invention may be applied equally to any application 
where two or more binary numbers having a difference of one or less are to 
be added. 
Numerous modifications, variations, and full and partial equivalents can be 
undertaken without departing from the invention as limited only by the 
spirit and scope of the appended claims.