Count the number of 1's

[cnivaz]

Dear Team,
I need to do the design , that will count the number of 1's in an 32 bit register.
I done this using the counter,but that took 32 clock pulse to produce the result.

Without consuming 32 clock , how to do this design.

Regards
Nivaz

 

[salma ali bakr]

you can make a CASE statement...with all the cases of '1's you can have
but since you've got a 32 bit register...that would be really tedious...

so you can have them on parts...like taking every 4 bits
then adding the ones of each part...

for ex: you have one '1' in 1, 2, 4 and 8 (you'll gather them in one statement in a case)

 

[echo47]

You could consider each bit to be an integer, and calculate their sum:
ones = bit0 + bit1 + bit2 + bit3 + ... + bit31.

 

[Iouri]

look up table can be option as well

 

[btbass]

A case statement or a look up table is out of the question!
2^32 = 4,294,967,296.

I think the best you can do is shift and add, but it will take > 32 cycles.

Added after 11 minutes:

unsigned int ones32(unsigned int x)
  {
  x -= ((x >> 1) & 0x55555555);
  x = (((x >> 2) & 0x33333333) + (x & 0x33333333));
  x = (((x >> 4) + x) & 0x0f0f0f0f);
  x += (x >> 8);
  x += (x >> 16);
  return(x & 0x0000003f);
  }

 

[XNOX_Rambo]

https://www.daniweb.com/forums/thread97469.html

 

[echo47]

Here's a non-pipelined version of my summing suggestion in Verilog. It does the complete calculation in one clock cycle, and runs at about 100 MHz in a small XC3S200-4-FG256 Spartan-3 FPGA. It uses a bunch of small adders, and occupies about 1% of the FPGA. The input and output registers aren't necessary for the calculation, but I added them to help estimate the speed.

module top (clk, in, ones);
  input             clk;
  input      [31:0] in;
  reg        [31:0] d;
  output reg  [5:0] ones;

  always @ (posedge clk) begin
    d <= in;
    ones <= (((d[ 0] + d[ 1] + d[ 2] + d[ 3]) + (d[ 4] + d[ 5] + d[ 6] + d[ 7]))
          +  ((d[ 8] + d[ 9] + d[10] + d[11]) + (d[12] + d[13] + d[14] + d[15])))
          + (((d[16] + d[17] + d[18] + d[19]) + (d[20] + d[21] + d[22] + d[23]))
          +  ((d[24] + d[25] + d[26] + d[27]) + (d[28] + d[29] + d[30] + d[31])));
  end
endmodule

Here's a pipelined version that runs over twice as fast, but of course has more latency:

module top (clk, in, ones);
  input             clk;
  input      [31:0] in;
  reg        [31:0] d;
  reg         [2:0] a[0:7];
  reg         [3:0] b[0:3];
  reg         [4:0] c[0:1];
  output reg  [5:0] ones;

  always @ (posedge clk) begin
    d <= in;
    a[0] <= d[ 0] + d[ 1] + d[ 2] + d[ 3];
    a[1] <= d[ 4] + d[ 5] + d[ 6] + d[ 7];
    a[2] <= d[ 8] + d[ 9] + d[10] + d[11];
    a[3] <= d[12] + d[13] + d[14] + d[15];
    a[4] <= d[16] + d[17] + d[18] + d[19];
    a[5] <= d[20] + d[21] + d[22] + d[23];
    a[6] <= d[24] + d[25] + d[26] + d[27];
    a[7] <= d[28] + d[29] + d[30] + d[31];
    b[0] <= a[0] + a[1];
    b[1] <= a[2] + a[3];
    b[2] <= a[4] + a[5];
    b[3] <= a[6] + a[7];
    c[0] <= b[0] + b[1];
    c[1] <= b[2] + b[3];
    ones <= c[0] + c[1];
  end
endmodule

 

[staraimm]

If the verilog language is used, the method provided by echo47 is simpler.

To btbass, if the C language is used, there is another way to calculate the number.

 unsigned int ones32(unsigned int num)
{
    return num - (num<<1) - (num<<2) - (num<<3) - (num<<4)
                     - (num<<5) - (num<<6) - (num<<7) - (num<<8)
                     - (num<<9) - (num<<10) - (num<<11) - (num<<12)
                     - (num<<13) - (num<<14) - (num<<15) - (num<<16)
                     - (num<<17) - (num<<18) - (num<<19) - (num<<20)
                     - (num<<21) - (num<<22) - (num<<23) - (num<<24)
                     - (num<<25) - (num<<26) - (num<<27) - (num<<28)
                     - (num<<29) - (num<<30) - (num<<31);
}

 

[smileysam]

can't we use a for loop and then use an if statement and increment the counter on finding 1??

 

[staraimm]

The performance is not good if the loop is used.

 

[nan_ishan]

You may use the following technique

Divide the 32 bits; i.e.,
1. First take initial 16 bits,compare it with 0, ,if equal to zero,then u save 15 clk cycles
If not equal again divide it in two bytes,compare the bytes separately with zero,if any byte is zero,you again save almost six clk cycles .
Repeat it until come to single bit...

2. Take the other 16 bits and repeat the procedure.........!!!!!!!!!

This will definitely give high efficiency when you have large nos. to count for 1s.....

Ishan
Electronics And Telecom. Engineer

Added after 4 minutes:

can't we use a for loop and then use an if statement and increment the counter on finding 1??

u increment the counter after finding 1 ,for that you will have to find 1 and to find 1,u will have to compare for each bit and this comparison for each bit will take one clk cycle.....

 

[sp]

i would prefer to use combinational logic (I just love it)...

let's use a 2 input OR gate, connect one of the input pin to GND, another to the one bit of the 32 bits. if it's a '1' in tht bit, it will output a 1... after you have done this with all the 32 bits, you can use an adder to add up all the 32 bits output from the OR gates

hehe... ok?..

sp

 

[dsPIC24F]

Probably you need a FPGA, counted it using hardware, so no much delay as the micros.

 

[jep]

A 8-bit address with 4-bit width LUT and 4 level pipeline will be ok for you.

Or a 16-bit address with 5-bit width LUT and 2 level pipeline?

Hope this helps

 

[research_vlsi]

Hi try this

module one(count,x);
input [31:0]x;
output reg [4:0]count;
integer i;
always @(x)
begin
count_one(count,x);
end

task count_one;
output [4:0]count;
input [31:0]x;
integer i;
begin
count=5'b0;
for(i=1;i<=32;i=i+1)
if(x==1)
count=count+1'b1;
else
count=count;
end
endtask
endmodule

 

[echo47]

Hi research_vlsi, Your example will sometimes give incorrect results.
'count' should have six bits, and the 'for' loop should go from 0 to 31.

 

[research_vlsi]

ya it should be from 0 to 31 in for loop

 

[mpatel]

Take a counter as interger.

counter= reg(0)+reg(2)+...+reg(31);

it may give solution.
enjoy!!!

 

[anoop12]

simple man,
use and-xor gates ladder. Each gate will be 2 input. U will need 16and" and 16"xor gates. Final output will be the count' of no of 1s.
regards

 

[echo47]

anoop12, I don't see how to build it with so few gates. Please show a diagram or code.