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
0	0	0	0	0
0	0	1	1	0
0	1	0	1	0
0	1	1	0	1
1	0	0	1	0
1	0	1	0	1
1	1	0	0	1
1	1	1	1	1

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:


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):


Figure 3 : High level view of the 4:2 compressor The characteristics of the 4:2 compressor are:

• The outputs represent the sum of the five inputs, so it is really a 5 bit adder
• Both carries are of equal weighting (i.e. add "1" to the next column)
• To avoid carry propagation, the value of Cout depends only on A, B, C and D. It is independent of Cin.
• The Cout signal forms the input to the Cin of a 4:2 of the next column.

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
0	0	0	0	0	0	0	1	0
0	0	0	1	0	1	1	0	0
0	0	1	0
0	1	0	0
1	0	0	0
0	0	1	1	0	0	0	1	1
0	1	1	0
1	1	0	0
0	1	0	1
1	0	1	0
1	0	0	1
0	1	1	1	0	1	1	0	1
1	1	1	0
1	1	0	1
1	1	1	0
1	1	1	1	1	0	1	1	1

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.


Figure 4: Architecture of the full word 4:2 compressor, using individual bit 4:2 compressors


References

• [1] Behrooz Parhami, "Computer Arithmetic", Oxford Press, 2000, pp131