Welcome to EDAboard.com

Welcome to our site! EDAboard.com is an international Electronic Discussion Forum focused on EDA software, circuits, schematics, books, theory, papers, asic, pld, 8051, DSP, Network, RF, Analog Design, PCB, Service Manuals... and a whole lot more! To participate you need to register. Registration is free. Click here to register now.

Register Log in

finding number of ones in a binary number of 8 bits

Status
Not open for further replies.

bunti

Member level 1
Joined
Jun 3, 2011
Messages
35
Helped
0
Reputation
0
Reaction score
0
Trophy points
1,286
Activity points
1,488
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

Full Member level 3
Joined
Mar 12, 2002
Messages
182
Helped
28
Reputation
56
Reaction score
24
Trophy points
1,298
Activity points
2,875
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

Full Member level 4
Joined
Jun 23, 2012
Messages
204
Helped
25
Reputation
52
Reaction score
25
Trophy points
1,328
Location
NYC, USA
Activity points
3,415
Well, here is a counter-based one: http://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.
 
Last edited:

jasonc2

Full Member level 4
Joined
Jun 23, 2012
Messages
204
Helped
25
Reputation
52
Reaction score
25
Trophy points
1,328
Location
NYC, USA
Activity points
3,415
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). Logisim file attached.
 

Attachments

Last edited:

bunti

Member level 1
Joined
Jun 3, 2011
Messages
35
Helped
0
Reputation
0
Reaction score
0
Trophy points
1,286
Activity points
1,488
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.
 

Status
Not open for further replies.
Toggle Sidebar

Part and Inventory Search


Welcome to EDABoard.com

Sponsor

Sponsor

Design Fast


×
Top