Connect with us

how to implement the "how many" logic function?

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

Scroll to continue with content
  1. Tony Roe

    Tony Roe Guest

    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)
     
  2. Jim Thompson

    Jim Thompson Guest

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

    Jim Thompson Guest

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

    MarkyMark Guest

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

    GPE Guest

    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. 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.
     
  8. Fred Bloggs

    Fred Bloggs Guest

    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 Fields

    John Fields Guest

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

    Grog Guest

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

    Zak Guest

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

    kansas_ray Guest

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

    Tony Roe Guest

    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)
     
  15. Tony Roe

    Tony Roe Guest

    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)
     
  16. Tony Roe

    Tony Roe Guest

    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)
     
  17. Tony Roe

    Tony Roe Guest

    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)
     
  18. John Fields

    John Fields Guest

     
  19. Fred Bloggs

    Fred Bloggs Guest

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

    kansas_ray Guest

    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
     
Ask a Question
Want to reply to this thread or ask your own question?
You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.
Electronics Point Logo
Continue to site
Quote of the day

-