how to implement the "how many" logic function?

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,
Tony (remove "_" from email address to reply)

 

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
one-bit) adder.

...Jim Thompson

 

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

 

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

 

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

 

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

 

If you don't need full logic speed, a Microchip PIC microcontroller
can easily handle the task

By my estimate, you could latch the 8 bits and produce a result in
about 5uSec.

 

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.

 

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

 

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...

 

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:

I guess the optimal result will be a cascade of adders, leading to a
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

 

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

 

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.

 

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,
Tony (remove "_" from email address to reply)

 

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,
Tony (remove "_" from email address to reply)

 

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,
Tony (remove "_" from email address to reply)

 

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
misunderstood you, please explain.

Regards,
Tony (remove "_" from email address to reply)

 

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

 

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