finding number of ones in a binary number of 8 bits

[bunti]

i want a circuit to find the number of ones in a binary number of 8 bits....suggest a method using a counter....i can use 4 full adders but can i reduce the number to a lesser one?

 

[ted]

Using a counter does not sound too simple at all. However it can be done for example by having a gated counter and a sift register controlling the gated counter. Also, a sequential control logic would be required to steer the process.. That would then count the bits during 8 clock cycles. However, I am pretty sure it will be quite complicated machinery, with maybe two counters, a 8 bit sift register, and a bunch of logic gates.

One very easy way is by a look-up table: It is essentially a ROM chip (usually EPROM or similar ), with each location containing number of one-bits for address of that location. For 8 bits in one needs thus 256 locations, and each location programmed with right contents. If that ROM chip is wider than required four bits, you just utilize what you need - four lines as that is enough to show a value 8 (binary 1000), which is the highest required.

I give below an example of such table, As I am bit too lazy for typing the whole table of 256 lines here, I give just few lines from the beginning and from the end:
Address / Contents
(input) / (output)
00000000 0000
00000001 0001
00000010 0001
00000011 0010
00000100 0001
247 values skipped .... you should be able to figure them out
11111100 0110
11111101 0111
11111110 0111
11111111 1000

Of course, there are many other solutions, but hardly too many requiring just one chip. Another example of single-chip solution would be using a programmable logic chip (PAL, PLD, or similar), but writing the equations would take a bit more effort than generating this simple table. The brute force approach would be actually to write a logic equation, in relevant language such as VHDL, for each output using the table above, and then letting the compiler the minimization work and fitting the result to the chip at hand. In other words, the same table, but converted to logic gates by a compiler.

- Ted

 

[jasonc2]

Well, here is a counter-based one: https://tinyurl.com/cyufdax



Set inputs on the left, click the trigger switch and outputs are on the right. You could shift everything left to start at Q0 on the decade counter but it won't sync with the clock as well unless your trigger is also sync'd with the clock. Add latches to buffer input if there's a risk of input changing while counting. Change the clock frequency to 100Hz or so to slow it down enough to see what is going on. Basic idea is use decade counter as driver for 8 channel data select and output latch pulse.

I also made a non clock-based one with 11 1-bit full adders (or 4 half adders and 7 full adders). I can share it if you like, but I don't know if it is the simplest. I am curious how you did it with 4 full adders.

That said, for only 8 bits, I also support Ted's suggestion of using a look-up table in ROM.

 

[jasonc2]

This is the 11-adder circuit I mentioned above, I feel like there should be a better way, and I actually remember having a similar problem to solve back in college but I forget what the solution was:



Inputs on left, outputs on right (msb -> lsb). **broken link removed** file attached.

 

[bunti]

I am sorry I was in a confusion and I thought I could do it with 4 full adders but now I realised that it is wrong......
Thank you Ted,Jasonc2 for giving me some idea...
please explain me how to implement a gated counter.