# how to implement the "how many" logic function?

Discussion in 'Electronic Design' started by Tony Roe, Aug 28, 2003.

1. ### Tony RoeGuest

I have no idea of the correct name for this function, but I need to generate a
3bit output corresponding to how many of 8 inputs are high. Eg if the inputs
were 11010110, then 5 of these are "1", so the output would be 5 (101 binary).
I'd like to implement the function in a CUPL device if possible. Any
tips/suggestions?
Regards,

2. ### Jim ThompsonGuest

I think what you want was called "majority logic" back in the '60's,
although what you describe is really just a 8-input (each input

...Jim Thompson

3. ### Sir Charles W. Shults IIIGuest

Jim is correct - this is majority logic. You can emulate it any number of
ways, but the most basic is to program a pattern into an EPROM or other memory
device.

Cheers!

Chip Shults
My robotics, space and CGI web page - http://home.cfl.rr.com/aichip

4. ### Jim ThompsonGuest

Yep. I was puzzling over how the original was made... it was done in
CML, but used current imbalance to set a "1" or "0".

But the OP wants a value versus a yeh/nay output.

My initial thoughts were a crude D-A followed by a D-A, but addressing
in a PROM is probably the most succinct.

...Jim Thompson

5. ### MarkyMarkGuest

Tony,
Here's a C code fragment that I use whenever I need to count ones. I assume
it should be reasonable to convert to a logic implementation. It would be
more efficient than an LUT.
Hope it helps.

unsigned char char_count_bits( unsigned char x )
{
x = ((0xAA & x)>>1) + (0x55 & x);
x = ((0xCC & x)>>2) + (0x33 & x);
x = ((0xF0 & x)>>4) + (0x0F & x);
return x; /* returns number of ones found in x */
}

Regards Mark

6. ### GPEGuest

Actually, a Majority vote circuit looks at three (typically) values and give
you a 'vote of the majority'. If 50%+ bits are set - you get a one, if 50%+
are clear - you get a zero. These are widely used in comm equipment.

What Tony is after is a summation of bits set. I have a 64 bit summation in
VHDL. But at 150Mbps - the result is pipelined.

The way I did it - I first break up initial into 4-bit chunks. Do a quick
summation of four bits -- 0 to 3 plus carry. I then have outputs from
summation stage going into adders. In my case, I register the results of
each stage -- and delay the output data by a matching number of cycles.
Tony's input width will determine how many adders he needs.

-- Ed

7. ### Lowly EngineerGuest

If you don't need full logic speed, a Microchip PIC microcontroller

By my estimate, you could latch the 8 bits and produce a result in

8. ### Fred BloggsGuest

How about a multi-bit "bubble swap" followed by thermometer code to
binary conversion- seems fun if nothing else. Adders are for drudges
with more macrocells than brains.

9. ### John FieldsGuest

Here's a brute-force way to do it in 6800 assembler:

inreg contains the the input word and sumit will contain the number of
1's in inreg after the return from the call.

jsr sumones

10. ### GrogGuest

Perhaps latch the parallel data into a shift register and
use the serial data out to clock a binary counter.
Use the load signal to reset the counter and data latch the
counter output.

There's a bit more to it but you get the idea I trust.
HTHs
Greg the Grog.

Greetings MarkyMark the lurker...

11. ### ZakGuest

It is called population count or popcount. The latter term returns
useful references in google groups, it seems.

Some processors inplement it for cryptographic/cryptanalisis stuff, and
I remember seeing at least one clever shortcut method. Don't remember
how it worked though, but it was much faster than counting the bits in a
loop.

However the software solutions you will find will not be optimal for
hardware, but they may give interesting ideas.

A fast software solutions seems to be using bit masks to do adding 'in
parallel' by preventing overflows.

I past from Van:Tim Peters ()'s post in
comp.lang.python:
result in 2log(n) time.

To do 8 bits, you need 4 adders of 1 bit each.

These give 4 results of 2 bits each. Add these with 2 adders with 2 bits
input width.

Finally, an adder with 3 bits in produces the popcount for your input byte.

Thomas

12. ### kansas_rayGuest

Does this really work? I tried 0x35 and calculated 0x02 instead of 0x04.
What am I missing?
Regards,
Ray

x = ((0xAA & 0x35)>>1) + (0x55 & 0x35) = 0x25
x = ((0xCC & 0x25)>>2) + (0x33 & 0x25) = 0x22
x = ((0xF0 & 0x22)>>4) + (0x0F & 0x22) = 0x02

13. ### Frank BemelmanGuest

Let's do that first line again, 0xAA & 0x35 -> 0x20
and after the shift it's 0x10? + 0x55 & 0x35 makes
0x35, not 0x25?

I'm going to bed now.

14. ### Tony RoeGuest

Unfortunately I DO need the logic's speed (ideally want to do 4 complete sets of
these every 300ns, plus lots of other logic-type stuff). But you reminded me
just how quick the faster PICs can be.

Regards,

15. ### Tony RoeGuest

Thanks for the alt.binaries.schematics.electronic tip, and the "ones counter"
name (I replied to that post as well). And thanks to all for the stimulating
replies.

Regards,

16. ### Tony RoeGuest

Conceptually intriguing, but as a beginner in programmable logic, even the lowly
adder still holds my interest. And it doesn't seem that any alternative to the 3
stage adder will take very much less resources or stages.

Regards,

17. ### Tony RoeGuest

As far as I know (not very far, really), the problem with the straightforward
approach is that CUPL chips (and I suspect all the alternatives as well) are
limited in how many terms may be combined. Eg, output bit 1 should be set if
there are 2, 3, 6 or 7 "1"s in the input byte. And there are 120 different bytes
containing 2, 3, 6 or 7 "1"s, much wider than any PLD I have seen. If I've

Regards,

19. ### Fred BloggsGuest

Technically that's a 1 of 16 decoder with outputs combined to yield
number of bits set etc....all in one...

20. ### kansas_rayGuest

Does this really work? I tried 0x35 and calculated 0x02 instead of 0x04.
What am I missing?
Regards,
Ray

x = ((0xAA & 0x35)>>1) + (0x55 & 0x35) = 0x25
x = ((0xCC & 0x25)>>2) + (0x33 & 0x25) = 0x22
x = ((0xF0 & 0x22)>>4) + (0x0F & 0x22) = 0x02