# In fast multiplier circuits, what is the difference between a Counter and a Compressor?

When working on fast parallel multiplier circuit designs, like Wallace tree multipliers or Dada tree multipliers I found many papers and books refer to different components used in the tree to reduce the partial products called things like (4:2) compressor, or (7,3) counter or (7:3) compressor. My question is :

"What is the difference between a (7:3) compressor and a (7,3) counter?"

What makes us to call it a compressor rather than a counter? is there any rule?

• Welcome to Computer Science Stack Exchange. Please read cs.stackexchange.com/tour, if you have not yet done so. When posting a question, make sure to give enough context, and show how you tried to answer it on your own, so as to be very precise regarding your problem. This helps better answers. Giving some references from the web may help, and would also show what you tried to read. – babou Aug 23 '15 at 10:16
• @Raphael, The terminology is familiar to anyone who regularly reads papers from ARITH, the IEEE Computer Society's annual Symposium on Computer Arithmetic. I agree that the terms compressor and counter need to be defined, but that is the OPs question. – Wandering Logic Aug 23 '15 at 14:32

In multiplier design an (n,k) counter takes an n bit input and produces a k bit output which is the binary representation of the number of input bits that are 1s. That is: it counts the number of input bits set to 1.

A (3,2) counter is just a full adder.

A (7,3) counter is a circuit with 7 input bits and 3 output bits. The 3 output bits tell you (in binary) how many of the input bits are set to 1.

In an (n, k) counter it must be the case that $k = \lceil \log_2 (n+1) \rceil$.

A (n:k) compressor is any circuit that takes in n equal weight input bits (plus, possibly, some carry in bits) and outputs a k bit count, plus some additional carry-out bits. The number of carry-in bits usually equals the number of carry-out bits, but you have to figure out the number by looking at the context. (Hopefully there's a picture or a detailed description in the paper or book you are reading.)

So a (7,3) counter is also a (7:3) compressor. But a (7:3) compressor could also mean something else, like something that takes in 7 input bits, plus a carry-in and outputs 3 output bits, plus a carry-out.

The most commonly used compressor is the (4:2) compressor. This takes in 5 inputs, and output 3 outputs. The reason it is not just a (5,3) counter is because the output is not a binary number in the range $[0, 5]$. Rather the output is a 2-bit value in the range $[0,3]$ plus an additional carry-out. So there are several ways of representing some of the outputs. For example "2" can be represented as "0+carry-out" or as "2+no-carry-out".