Fast carry-out generation

Details Fast carry-out generation Fast carry-out generation

2000-05-23

2003-07-22

Malzahn, David H. (Department: 2124)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

Reexamination Certificate

active

06598066

ABSTRACT:

BACKGROUND OF THE INVENTION
Field of the Invention
The present invention is generally directed to a carry-out generator for addition of two positive numbers.
Background
Binary addition operates on an augend and an addend, both of which may include a series of registers having a bit of either unity (=1) or zero (=0). A full adder of two bits combines two bits to find a sum. The addition may be evaluated for a bit register of any length. A carry-in may be received from the adjacent lesser bit register, and the result may detect a carry-out to be received by the adjacent greater bit register. The full adder for bit register receives an augend input A, an addend input B, a carry-in input C
i
. The results from the adder include a sum S and a carry-out C
o
.
FIG. 1
illustrates an adder as a block diagram featuring the inputs and outputs. The adder
10
receives an augend
12
, an addend
14
and a carry-in
16
. The outputs include a sum
18
and a carry-out
20
.
The results S and C
o
depend on the input values. In
FIG. 2
, a logic table shows row of inputs and corresponding outputs for a bit register. The legend
22
identifies the inputs A (augend), B (addend), and C
i
(carry-in), along with the possible outputs S (sum) and C
o
(carry-out). The first four rows
24
,
26
,
28
and
30
are shown for no carry-in bit, while the last four rows
32
,
34
,
36
and
38
are shown for a carry-in bit. The carry-out propagation can be time-consuming for a processor. Various schemes to reduce the propagation time have been developed, including look-ahead carry chain.
In many applications, such as a control shift for a multiplexer or a conditional branch, only the carry-out is required. In such circumstances, calculating the addition of the augend and addend to obtain the sum bit and the cascading carry-out bit needlessly consumes processing time. A solution is desired to expedite the carry-out result without an adder.
SUMMARY OF THE INVENTION
A carry-out bit generator determines if a bit pattern from two positive numbers matches one of the patterns for which a carry-out bit would be generated in addition. These patterns include a T
n
G pattern and a T
m
pattern (with a carry-in). Superscript n represents a number between zero and m−1, superscript m represents the number of registers, T represents a 0/1 or 1/0 pair and G represents a 1/1 pair.


REFERENCES:
patent: 3805045 (1974-04-01), Larsen
patent: 3993891 (1976-11-01), Beck et al.
patent: 4504924 (1985-03-01), Cook et al.
patent: 5508950 (1996-04-01), Bosshart et al.
patent: 5508951 (1996-04-01), Ishikawa
patent: 5539685 (1996-07-01), Otaguro
patent: 5943251 (1999-08-01), Jiang et al.
patent: 5951631 (1999-09-01), Hwang
patent: 6292818 (2001-09-01), Winters
patent: 2001/0037349 (2001-11-01), Hayakawa

Affiliated with

Also associated with

Rating

Fast carry-out generation does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Fast carry-out generation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast carry-out generation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3004171