# How do you compute and compare the delays between a (4:2) compressor and (3,2) counter carry save tree?

My question: How is Table 6.8 shown below computed for different operands? For example, for 3 operands how did they compute:

Number of levels using (3,2) = 1

Number of levels using (4;2) = 1

Equivalent delay: 1.5

Or how about for 9 operands how did they compute:

Number of levels using (3,2) = 4

Number of levels using (4;2) = 3

Equivalent Delay: 4.5

The textbook also points out that the equivalent delay of a (4;2) compressor carry save tree with 9 operands (4.5) is bigger than that of a carry save tree using (3,2) counters. Why is that?

What are the general conditions when one is bigger than the other?

The following is an image of a (4:2) compressor taken from this book.

The truth table provided for this compressor is:

where $$a=b=c=1$$ and $$d=e=f=0$$. I think these constants are used to generalize the circuit.

An adder tree that uses (4;2) compressors will have a more regular struc-ture and may have a lower delay than an ordinary CSA tree made of (3,2) counters. Table 6.8 compares the delays of carry-save trees using either (3,2) counters or (4;2) compressors. Since the delay of a (4;2) compressor is 1.5 times that of a (3,2) counter, the number of levels of (4;2) compressors in column 3 is multiplied by 1.5 to yield the equivalent delay in column 4. Note that the equivalent delay of a carry save tree using (4;2) compressors (column 4) is not always smaller than that of a carry save tree using (3,2) counters (column 2). For example, for nine partial products, (3,2) counters will yield a carry save tree with an overall lower delay. Various other counters and compressors can be employed in the implementation of the addition tree for the partial product accumulation; for example, (7,3) counters

Please look at the bold face sentence above:

• 3 operands isn't the best of examples - the number of levels of a 3:o₃ compressor or counter will be 1 by definition, as will be that of any compressor or counter with more signals processed/a bigger number before the semicolon/comma. Commented Jan 20 at 17:38

• The first column list all ranges with uniform number of levels for both approaches, up to 42.
One way is to start with one level, and compute how many inputs a circuit with that many outputs accommodates - twice as many with (4;2) compressors, three halves, truncated, with (3,2) counters.
• With a simple timing model (each XOR contributes .5), this means uniform delay, too:
The number of levels with equals the unit delays for (3,2) counters, multiply with 1.5 for (4;2) compressors.

The condition for the (4;2) compressor delay to be bigger than the (3,2) counter one is:
Number of operands is 3 or 9.
It will be smaller above 19 (as well as for 4, 7, 8 and 10-16).

It took me a while to figure out what this circuit does: It takes 5 inputs and produces 3 outputs. (So why is it called a 4-2 compressor and not a 5-3 compressor?) One output is the sum with a value of 1, and two carry bits with a value of 2. If the sum of the inputs is 2 or 3, one of the two carries must be set, and one cleared; it doesn’t matter which one; this gives you the values a, b, c, d, e and f, with arbitrary values.

The number of levels for a given number of inputs is not a continuous function but has jumps, and they are in different places for both methods. So from eight to nine inputs, (4,2) needs an extra level where (3,2) doesn’t yet, and that’s why for this one point (3,2) has less delay.

I’d try to find the best implementation with NAND gates. Then it may be that some outputs are produced faster than others, and some inputs delay the total result while others don’t. Also consider that a circuit may output a negated output quicker, and another circuit might be faster if given a negated input.