+ Post New Thread
Results 1 to 5 of 5
  1. #1
    Member level 1
    Points: 419, Level: 4

    Join Date
    Jun 2011
    Posts
    35
    Helped
    0 / 0
    Points
    419
    Level
    4

    finding number of ones in a binary number of 8 bits

    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?

    •   AltAdvertisement

        
       

  2. #2
    Full Member level 3
    Points: 5,584, Level: 17
    ted's Avatar
    Join Date
    Mar 2002
    Posts
    182
    Helped
    28 / 28
    Points
    5,584
    Level
    17

    Re: finding number of ones in a binary number of 8 bits

    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



    •   AltAdvertisement

        
       

  3. #3
    Full Member level 4
    Points: 1,132, Level: 7
    jasonc2's Avatar
    Join Date
    Jun 2012
    Location
    NYC, USA
    Posts
    204
    Helped
    26 / 26
    Points
    1,132
    Level
    7
    Blog Entries
    1

    Re: finding number of ones in a binary number of 8 bits

    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 by jasonc2; 28th July 2012 at 03:22.



    •   AltAdvertisement

        
       

  4. #4
    Full Member level 4
    Points: 1,132, Level: 7
    jasonc2's Avatar
    Join Date
    Jun 2012
    Location
    NYC, USA
    Posts
    204
    Helped
    26 / 26
    Points
    1,132
    Level
    7
    Blog Entries
    1

    Re: finding number of ones in a binary number of 8 bits

    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.
    Last edited by jasonc2; 28th July 2012 at 03:34.
    J



  5. #5
    Member level 1
    Points: 419, Level: 4

    Join Date
    Jun 2011
    Posts
    35
    Helped
    0 / 0
    Points
    419
    Level
    4

    Re: finding number of ones in a binary number of 8 bits

    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.



--[[ ]]--