I'm trying to build an adder tree using 4:2 compressors. I want to add together 16 bytes at total, so I figured that a possible architecture for that tree is the following:

enter image description here

Each 4-Byte adder has 3 outputs, the 2 of them are the sum and the carry (which we send to the next adder) and the third one is the Cout from the last 4:2 compressor of the adder.

My question is, what to do with the Cout? How should I add it to the rest of the sum?

  • \$\begingroup\$ 4 bytes or 4 bits? \$\endgroup\$ – Tom Carpenter Apr 22 '16 at 15:48
  • \$\begingroup\$ 4 bytes. I used eight 4:2 compressors in every 4-byte adder. \$\endgroup\$ – Arkoudinos Apr 22 '16 at 15:53

Typically when we say "compressor" like your usage in the title of a 4:2 compressor, it is a lossy operation, as you are mapping 16 (2^4) input values to 4 (2^2) output values. These are typically used in large multiplier architectures where it is a common problem to compute partial-products and not the entire sum. These are sometimes called carry-save because the carries are saved off, if needed later, but often disregarded. (Source: I have designed an ALU for a commercial microprocessor).

But assuming that the rest of your diagram when you say 4-byte Adder, that you actually mean a full adder is implemented, then you can do what you want to do. It doesn't matter how your adders are implemented inside as long as they are not lossy, i.e. true adders. I'm making that distinction based on your comment that you used compressors inside each 4-byte adder as well.

Essentially at this point you are just adding several partial sums serially, and thus are not needing to do any carry-propagation. In that case, you need to keep widening your adder to fit the full possible results of the addition. I've drawn this out below. You will need to widen your result by three bits and prepend that to the sum. To see why this makes sense, think about the case where you are adding unsigned 0xFFFFFFFF four times.

enter image description here

  • \$\begingroup\$ In fact, I have to implement a given architecture, where we need the Sum of Absolute Differences (for a Motion Estimation processing unit). In that architecture it is suggested to use 4:2 compressors to benefit from the parallelization. So if I understand correctly, you suggest me to keep the final result of the adder tree (32-bit signal), make a sum of the Cout signals from each adder (which will be a 3-bit signal) and concatenate the two, with the 3-bit Cout signal being the MSB. In this way there won't be any loss. Right? \$\endgroup\$ – Arkoudinos Apr 22 '16 at 17:05
  • \$\begingroup\$ I'm not familiar with the Sum of Absolute Differences so you'll have to decide for yourself if what I said is relevant there for your particular application. If you do want a full sum of these 4 32-bit words, then what I said will work. If you are getting subtractions on some of these (the Differences, I'm assuming), then you should be able to do that with the standard inverting an input and a carry in for twos complement arithmetic. But to have a true summation you need to extend your bit width of the result, and put those carries into a 3-bit adder essentially (2 w/carry). \$\endgroup\$ – Joel Wigton Apr 22 '16 at 17:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.