Continue to Site

Welcome to EDAboard.com

Welcome to our site! EDAboard.com is an international Electronics 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

Count the number of 1's

Status
Not open for further replies.
C

cnivaz

Newbie level 6
Newbie level 6
Joined
Sep 22, 2006
Messages
11
Helped
0
Reputation
0
Reaction score
0
Trophy points
1,281
Activity points
1,382
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
 

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)
 
You could consider each bit to be an integer, and calculate their sum:
ones = bit0 + bit1 + bit2 + bit3 + ... + bit31.
 
look up table can be option as well
 

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:

Code: 
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);
  }
 

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.
Code: 
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:
Code: 
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
 
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.

Code: 
 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);
}
 

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

The performance is not good if the loop is used.
 

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:

smileysam said:
can't we use a for loop and then use an if statement and increment the counter on finding 1??
Click to expand...

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.....
 

    C

    cnivaz

    Points: 2
    Helpful Answer Positive Rating
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
 

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

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
 

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
 

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.
 

Take a counter as interger.

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

it may give solution.
enjoy!!!
 

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
 

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

Status
Not open for further replies.

Similar threads

Part and Inventory Search

Welcome to EDABoard.com

Sponsor

Back
Top