# 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,179
1,286
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 AAC Fanatic!

Jun 7, 2009
1,614
238
bit shift or rotate for bit count, incrementing a counter on carry.

6. ### Georacer Moderator

Nov 25, 2009
5,179
1,286
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,953
1,826
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,179
1,286
What was the purpose of that? Really! U mad?

10. ### ErnieM AAC Fanatic!

Apr 24, 2011
7,953
1,826
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,179
1,286
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
4,166
1,125
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,179
1,286
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,953
1,826
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,179
1,286
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,049
674
That was my understanding of Kermit2's proposed solution, i.e., each bit in the D2A has the same weight.

17. ### Tesla23 Senior Member

May 10, 2009
365
78
One chip solution: 64k x 5 ROM

18. ### Georacer Moderator

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

19. ### ErnieM AAC Fanatic!

Apr 24, 2011
7,953
1,826
See post #10, last paragraph.

20. ### Georacer Moderator

Nov 25, 2009
5,179
1,286
Hmm... Expensive - but fast and compact. I like it!