Location : Home >> Technology Notes >> ASIC Design for Signal Processing

Carry Save Arithmetic

[Last modified 11:12:00 PM on Tuesday, 27 July 2010]
One of the major speed enhancement techniques used in modern digital circuits is the ability to add numbers with minimal carry propagation. The basic idea is that three numbers can be reduced to 2, in a 3:2 compressor, by doing the addition while keeping the carries and the sum separate. This means that all of the columns can be added in parallel without relying on the result of the previous column, creating a two output "adder" with a time delay that is independent of the size of its inputs.

         10111001
         00101010
         00111001
Sum:     10101010
Carry:  00111001 
Result:	100011100
The sum and carry can then be recombined in a normal addition to form the correct result. This process may seem more complicated and pointless in the above trivial example, but the power of this technique is that any amount of numbers can be added together in this manner. It is only the final recombination of the final carry and sum that requires a carry propagating addition.

The use of a wallace tree [1], arranges the adder tree so that all of the output bits could be obtained while minimising the size of the circuit. However, in the case of multipliers, we know what the expected output size will be, and so we can set all of the input and output sizes to that value. We do not care about any overflowing sign bits, so they can be discarded and the carries can simply be shifted left to the correct alignment. All of the results can then be grouped together as one and continually reduced until we are left with two values. This is demonstrated by figure 1.


Figure 1: Carry-save adder tree for when overflowing carries from the MSB do not matter
This method may appear wasteful because a lot of bits in the first stages of the adder tree will be frozen to zero. However, these will be optimised during synthesis, and this technique seems to produce more favourable synthesis results than trying to code the design efficiently.


3:2 Compressors


The design of the 3:2 compressor is simple, with the following truth table showing that it is nothing more than a full adder:

Inputs Sum Carry
A B C
000 00
001 10
010 10
011 01
100 10
101 01
110 01
111 11
Table 1 : Truth table for the 3:2 compressor. In reality, it is simply a full adder.
Adding three k-bit numbers together simply involves an array of k 3:2 compressors, each being independent of each other and operating on a single bit position:

Several bit-sized 3:2 compressors can be combined in parallel to form a full word 3:2 compressor.
Figure 2: Architecture of the full word 3:2 compressor, using individual bit 3:2 compressors.



4:2 Compressors

The discussion so far has referred only to 3:2 carry-save adders, but it is also possible to add four bits in this format. In reality, there are actually five inputs (one being a carry in), and three outputs (two carries and the sum):

High level view of a 4:2 compressor cell. It is really a 5:3 compressor, but is specially arranged so that one of the carry outs does not depend on the carry-in.
Figure 3 : High level view of the 4:2 compressor
The characteristics of the 4:2 compressor are: The behaviour of the 4:2 compressor is described by table 2.

Inputs Cin = 0 Cin = 1 Cout
A B C D Carry Sum Carry Sum
000000010
00010 110 0
0010
0100
1000
00110 001 1
0110
1100
0101
1010
1001
01110 110 1
1110
1101
1110
1111 10111
Table 2 : Truth table for the 4:2 compressor cell


A k-bit 4:2 word adder is then formed as shown below, in figure 4.

Several bit-sized 4:2 compressors can be combined in parallel to form a full word 4:2 compressor.
Figure 4: Architecture of the full word 4:2 compressor, using individual bit 4:2 compressors



References

(C)opyright 2001-2010, Geoff Knagge.
Continued use of this site indicates your agreement to the Conditions of use and Privacy Policy.
carrysave.shtml, last modified 11:12:00 PM on Tuesday, 27 July 2010