Logic to determine how many bits in 16 bit parallel input are high

Discussion in 'Homework Help' started by manaboutdog, May 24, 2011.

  1. manaboutdog

    Thread Starter New Member

    Jul 28, 2010
    2
    0
    I was wondering if anyone knew of a logic device or failing that a simple method of asynchronously detecting the number of active bits in a 16 bit parallel input?

    I don't care or want to know which individual bits are active, it's only the number of them that I want to know.

    For eg if the input is 0000 0100 0101 0000 then the output would be 0011
    An input of 1110 0011 1010 1100 would be 1001 etc.

    Seems like a simple problem to solve but I've been racking my brain and only coming up with solutions that use loads of ICs.
     
  2. mannycc

    New Member

    Dec 11, 2010
    17
    1
    Hi, i dont think the method is that simple, there are stages i can think of before you come up with what you want. First is to create a 16 bit ring counter AND with the 16bits you like to detect one at a time then the output should be connected to the binary counter as clock in order to get your desired binary output.
    Cheers
     
  3. Georacer

    Moderator

    Nov 25, 2009
    5,142
    1,266
    If your restriction of asynchronous detection is strict, then you are to expect a large number of required circuitry.

    Think about this. You can break down the 16bit input into 8 pairs of 1bit input. Add these 1bit pairs and you get 8 2bit results. Split them together and repeat until you get a result with length of \log_216=5 (with possible zero overhead).

    Is that clear?
     
  4. manaboutdog

    Thread Starter New Member

    Jul 28, 2010
    2
    0
    Thanks for taking the time to have a look at this, I just wanted to be sure I wasn't missing something obvious, the fact that it must be asynchronous is causing the necessary levels of complexity I guess.
     
  5. GetDeviceInfo

    Senior Member

    Jun 7, 2009
    1,571
    230
    bit shift or rotate for bit count, incrementing a counter on carry.
     
  6. Georacer

    Moderator

    Nov 25, 2009
    5,142
    1,266
    A rotational counter won't do, because the OP asked for an asynchronous circuit, and the counter is dependant on a clock.
     
  7. mannycc

    New Member

    Dec 11, 2010
    17
    1
    That's exactly the point, right now i cant think of a detecting system for the output by not introducing a clock using ring counter as output sweeper.
     
  8. ErnieM

    AAC Fanatic!

    Apr 24, 2011
    7,386
    1,605
    Lets see....

    There is only 1 way no bit is high.
    There are 16 ways only 1 bit is high.
    There are 16 * 15 ways only 2 bits are high.
    There are 16 * 15 *14 ways only 3 bits are high.
    There are 16 * 15 *14 *13 ways only 4 bits are high.
    There are 16 * 15 *14 *13 * 12 ways only 5 bits are high.
    There are 16 * 15 *14 *13 * 12 * 11 ways only 6 bits are high.
    There are 16 * 15 *14 *13 * 12 * 11 *10 ways only 7 bits are high.
    There are 16 * 15 *14 *13 * 12 * 11 *10 * 9 ways only 8 bits are high.
    There are 16 * 15 *14 *13 * 12 * 11 *10 ways only 7 bits are low.
    There are 16 * 15 *14 *13 * 12 * 11 ways only 6 bits are low.
    There are 16 * 15 *14 *13 * 12 ways only 5 bits are low.
    There are 16 * 15 *14 *13 ways only 4 bits are low.
    There are 16 * 15 *14 ways only 3 bits are low.
    There are 16 * 15 ways only 2 bits are low.
    There are 16 ways only 1 bit is low.
    There is only 1 way no bit is low.


    1
    +16
    +240
    +3360
    +43680
    +524160
    +5765760
    +57657600
    +518918400
    +57657600
    +5765760
    +43680
    +524160
    +3360
    +240
    +16
    +1

    =646,908,034

    Bah, not even a billion.

    Trivial!
     
  9. Georacer

    Moderator

    Nov 25, 2009
    5,142
    1,266
    What was the purpose of that? Really! U mad?
     
  10. ErnieM

    AAC Fanatic!

    Apr 24, 2011
    7,386
    1,605
    Nope, just thinking out loud. A big number kinda rules out any combinatorial circuit, either discrete or an FPGA.

    You could do it with a mess of full adders (such as the MC14008) used to add up all the bits:

    - add pairs of bits for duals, need qty 8 of 1 bit adders, 2 bit outputs

    - add pairs of duals for quads, need qty 4 of 2 bit adders, 3 bit outputs

    - add pairs of quads for octs, need qty 2 of 3 bit adders, 4 bit outputs

    - add both octs together for final output, need qty 1 of 4 bit adders, 5 bit output

    As the MC14008 suggested is a 4 bit adder (they don't come smaller AFAIK) you would need 15 chips for the full implementation (about $12USD), with a propagation delay multiplier of 4x over the single device. Say 4uS max.

    A single chip implementation would need some sort of persistent memory device with a parallel input. These are becoming rare rare these days, it seems no one is building discrete micro computers anymore and the few devices I can find actually on distributes shelves are all marked "End of Life: Scheduled for obsolescence and will be discontinued by the supplier." But a 64Kx8 ROM could produce the required output asynchronously.

    However, you can still get a couple of On Semi's CAT28C512 512K-Bit CMOS PARALLEL EEPROMs from Mouser for $17.76USD each. "Burn" the memory with the bit pattern, drive A0 to A15 with your 16 bits, and take the output direct from I/O0 to I/O4. There is no maximum spec on read time, the minimum they do spec is 120 ns.
     
  11. Georacer

    Moderator

    Nov 25, 2009
    5,142
    1,266
    The 74166 is a parallel load 8bit register. I have used it to count serially '1' on a string and I think it provides enough versatility to cover all your needs - apart from efficiency, as all the 30-year old IC's.
     
  12. Kermit2

    AAC Fanatic!

    Feb 5, 2010
    3,783
    944
    Convert the digital word to an analog voltage. Scale it such that all 16 bits high is equal to the source voltage and 0 bits high is zero volts. 8 bits high would be Vcc/2. Send that voltage to an ADC and there you go.

    The complexity isn't necessarily less, but the need for clocking and sync is much less reduced.
     
  13. Georacer

    Moderator

    Nov 25, 2009
    5,142
    1,266
    The DAC converter could be as simple as an OpAmp configuration, but the way back is much more complex.

    Of course, the solution must be within the restrictions of your class. No sense in trying to use a microcontroller in an digital IC design class. What class does the question refer to?
     
  14. ErnieM

    AAC Fanatic!

    Apr 24, 2011
    7,386
    1,605
    I think the OP's question has been lost here:

    16 bits enter. 5 bits leave (since 16_{10} = 1000_2)

    Georacer: How do you get a shift register to work asynchronously?

    Kermit2: If I use my digital data to drive a perfect D2A that drives a perfect A2D don't I get out exactly what I put in? But it's on the right track:

    Scale each of the 16 input bits to 1 volt for a hi or 0 volts for a low. Then connect each of these 16 analog voltages to a summing amplifier; the amp's output is a count of 1's in volts.

    If you allow a flash A2D then you would fulfill the asynch requirement.

    There, now we have three ways to skin this cat.
     
  15. Georacer

    Moderator

    Nov 25, 2009
    5,142
    1,266
    My initial post was the response and proposed solution to the problem. Post #11 was a response to your post #10.
     
  16. Ron H

    AAC Fanatic!

    Apr 14, 2005
    7,050
    657
    That was my understanding of Kermit2's proposed solution, i.e., each bit in the D2A has the same weight.
     
  17. Tesla23

    Active Member

    May 10, 2009
    318
    67
    One chip solution: 64k x 5 ROM
     
  18. Georacer

    Moderator

    Nov 25, 2009
    5,142
    1,266
    How does that help the conversation? How can you use a ROM chip asynchronously and stand-alone?

    Please support your proposals with adequate facts.
     
  19. ErnieM

    AAC Fanatic!

    Apr 24, 2011
    7,386
    1,605
    See post #10, last paragraph.
     
  20. Georacer

    Moderator

    Nov 25, 2009
    5,142
    1,266
    Hmm... Expensive - but fast and compact. I like it!
     
Loading...