Conditional carry encoding for carry select adder

Details Conditional carry encoding for carry select adder Conditional carry encoding for carry select adder

1999-07-13

2002-12-17

Ngo, Chuong Dinh (Department: 2124)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

C708S711000

Reexamination Certificate

active

06496846

ABSTRACT:

BACKGROUND
Binary addition is similar to numerical addition. The most basic form of binary addition entails starting with the least significant digit, and adding the two numbers, and moving a carry, if any, into the next significant digit addition. For example, consider the addition of the bit stream 010 and a bit stream 111. The addition of the least significant bits is 0+1, with a sum of 1, and a carry out of 0. The addition of the next significant bits are 1+1 plus a carry in of 0, with a sum of 0, and a carry out 1. The addition of the next significant bits are 0+1 plus a carry in of 1, with a sum of 0, and a carry out 1. Thus, the addition yields 001 plus a carry out of 1, or 1001.
The sequential addition described above works well for small bit streams, e.g. 3 bits, but becomes inefficient for large bit streams, e.g. 64 bits. Thus, the prior art uses carry select addition, which is similar to sequential addition, but breaks the bit streams into smaller blocks and performs two calculations, a first assuming that the carry bit is a zero, the second assumes the carry bit is a one. For example, consider a bit stream of 100101 which is added to bit stream 110001, this would yield 1010110 using sequential addition. With carry select addition these streams would be split into blocks 100 & 101 and 110 & 001, respectively. The addition of the blocks are 101+001 and 100+110. Now 100+110 would be calculated in two ways, the first assumes a carry in of 0 and the second assumes a carry in of 1. Thus, 100+110 +0=1010, and 100+110+1=1011. The addition of 101+001=110 with a carry out of 0, thus the carry in of 0 calculation for the 100+110 addition should be used. The two calculations are then concatenated together to form (1010) (110)=1010110. Note that the additions of the two segments can be performed in parallel. Further note that a 2 to 1 multiplexer (MUX) is typically used to select between the carry 0 and carry 1 calculations.
The only difference between the carry in of 0 calculation and the carry in of 1 calculation is in the carry in to each bit. Hence, two signals are used to encode the conditional carry in to each bit in the block; C
0
is the carry in to a bit for carry in to the block of zero, and C
1
is the carry in to the bit for carry in to this block of one. In a dual-rail domino implementation, the C
0
and C
1
inputs become four signals to represent each bit in the segment: C
0
H, C
0
L, and C
1
H, C
1
L. Thus, the carry in to a particular bit may be H or “true” if the carry in to the block is 0, which is represented by C
0
H. Similarly the carry in to a particular bit may be L or “false” if the carry in to the block is 0, C
0
L. Note that C
0
H and C
0
L are complements of each other. Similar statements may be made for C
1
H and C
1
L. Therefore, the four signals represent the actual and the complement of the signals C
0
and C
1
, with H being the true or actual, and L being the false or complement.
Each of the four signals are required for processing of the carrys, because logical circuits within the system, such as exclusive OR, use both true and complements of input signals. Each of these signals must be generated, and transmitted through the system, and then routed to appropriate destinations. This is costly in terms of chip complexity, and chip area used.
Therefore, there is a need in the art for a carry select adder that requires fewer signals to be generated and transmitted through the system.
SUMMARY OF THE INVENTION
These and other objects, features and technical advantages are achieved by a system and method which has a reduced number of encoded signals to represent the conditional carry bit.
In considering the operation of a carry chain, it is apparent that not all possible combinations of C
0
H, C
0
L and C
1
H, C
1
L need to be generated. For example, C
0
H always implies C
1
H, in other words if carry in to a bit is true for block carry in of zero, then carry in to this bit will certainly be true for block carry in of one. If C
0
H is true, then the carry into the bit is generated within the block, and thus, would not be affected by the addition of 1 from a block carry in of 1. Thus, C
1
H does not have to be calculated for this bit. Similarly, C
1
L always implies C
0
L, in other words if carry in to a bit is false for block carry in of one, then carry in to the bit will certainly be false for block carry in of zero. If C
1
L is true, then the carry into the block is lost within the block, and thus, the carry in to the bit would not be affected by the subtraction of 1 from a block carry in of 0. Thus, C
0
L does not have to be calculated for this bit. Note that with the complement pairs, i.e. C
0
H & C
0
L and C
1
H & C
1
L, only one of each pair will be true at any given time.
Therefore, a more compact encoding of the C
0
/C
1
bits is possible. In keeping with the PKG naming convention (Propagate, Kill, Generate) of encoding the adder inputs, one-of-three encoding can be used to represent the conditional carry into a bit. Only one of the signals would be high at any time, the other two would be low. The three signals are Gin, Kin, and Pin. The Gin signal is true where a bit has a carry in of one regardless of carry in to the block, i.e. the carry in to the bit is generated within the block. The Kin signal is true where a carry in to a bit is zero regardless of the carry in to the block, i.e. any carry in to the block is killed before it gets to the bit. The Pin signal is true where a bit has a carry in that is the same as the carry in to the block, i.e. the carry in to the block is propagated up to the bit. These signals are used in the calculation of the sum bits, i.e. the actual bits of the bit streams being added together.
Since only three signals are generated, the number of field-effect transistors (FETs) required to implement the adder are reduced. Moreover, since only three signals are being transmitted, the amount of routing mechanisms, e.g. wire, is also reduced. Thus, the complexity and surface area of the adder are reduced.
Therefore, it is a technical advantage of one aspect of the present invention to have one-of-three encoding to represent the conditional carry into each bit of a block of bits. It is a further technical advantage of one aspect of the present invention to represent the signals as propagate, kill, or generate, based upon the carry in to the block.
It is still a further technical advantage of one aspect of the present invention to provide a system and method which has a reduced number of encoded signals to represent a conditional carry bit in addition operations. Accordingly, it is a technical advantage of one aspect of the present invention to reduce chip complexity (i.e., circuitry complexity) required for performing addition operations. Also, it is a technical advantage of one aspect of the present invention to reduce the chip area required for performing addition operations.
The foregoing has outlined rather broadly the features and technical advantages of the present invention in order that the detailed description of the invention that follows may be better understood. Additional features and advantages of the invention will be described hereinafter which form the subject of the claims of the invention. It should be appreciated by those skilled in the art that the conception and the specific embodiment disclosed may be readily utilized as a basis for modifying or designing other structures for carrying out the same purposes of the present invention. It should also be realized by those skilled in the art that such equivalent constructions do not depart from the spirit and scope of the invention as set forth in the appended claims.


REFERENCES:
patent: 5500813 (1996-03-01), Song et al.
patent: 6055557 (2000-04-01), Beck et al.
patent: 6175852 (2001-01-01), Dhong et al.

Affiliated with

Also associated with

Rating

Conditional carry encoding for carry select 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 Conditional carry encoding for carry select adder, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Conditional carry encoding for carry select adder will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2949030