counting consecutive zeroes in 32 bit and shifting in one cycle

[Shosa]

Hi

How i can find 1's in 32 bits binary number using verilog?

for eg: if 32 bit number is 10110010101100110001110010011000 then i need to shift first three zeroes from lsb in one clock cycle and 11 will take 2 cycles
in short consecutive zeroes should shift in one clock cycle and each 1's will take one clock cycle

somebody suggested me to use casex for 32 cases like

---

Code Verilog - [expand]
1
2
3
4
5
6
7
8
casex(abc)
 
32'bxxxxxxxxxxxxxxxxxxxxxxxxxxxxx10 
32'bxxxxxxxxxxxxxxxxxxxxxxxxxxxx100
...
...
upto 32 
32'b1000000000000000000000000000000

---

how can use this to find 1's and shift cycles accordingly?

kindly help..

 

[ads-ee]

---

Code Verilog - [expand]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
casex (abc)
  32'b_xxxx_xxxx_xxxx_xxxx_xxxx_xxxx_xxxx_xx10  : new_abc <= {1'b0, abc[31:1]};
  32'b_xxxx_xxxx_xxxx_xxxx_xxxx_xxxx_xxxx_x100  : new_abc <= {2'b0, abc[31:2]};
  // ...
  32'b_1000_0000_0000_0000_0000_0000_0000_0000  : new_abc <= {31'b0, abc[31]};
endcase
 
// somewhere else you clock new_abc into abc:
always @ (posedge clk) begin
  if (some_condition) begin
    abc <= new_abc;
  end else if (count_ones_condition) begin
    abc <= {1'b0, abc[31:1]};
  end
end

---

 

[vGoodtimes]

you can also look for the number of 0's in 31:1, as this would let you skip over the 0's entirely. any non zero input would transition to an input with a 1 in the lsb. eg, 00000101 would take 2 cycles instead of 3.

 

[K-J]

in short consecutive zeroes should shift in one clock cycle and each 1's will take one clock cycle

A 32 bit barrel shifter will not be very fast if you're planning on implementing this in an FPGA so hopefully your clock period is not terribly fast.

Kevin Jennings

 

[beeflobill]

Here is the same thing but expressed in a more brief way. One downside is that it's harder to guess what the hardware would look like.

   //Assuming that in and out are defined elsewhere
   //Assuming parameter size is defined elsewhere as 32
   function integer countZeros(input [size-1:0] bitstring);
   begin
      countZeros = 1; //Always count the first bit as a zero
      while((countZeros<size) & (bitstring[countZeros]==1'b0)) countZeros = countZeros+1;
   end
   endfunction

   assign out = in >> countZeros(in);

 

[ads-ee]

Here is the same thing but expressed in a more brief way. One downside is that it's harder to guess what the hardware would look like.

It also doesn't do what the OP wanted.

in short consecutive zeroes should shift in one clock cycle and each 1's will take one clock cycle

What you're proposing is computing the number of 1's, which results in a cascade of bit additions.

 

[lucbra]

If I remember well, we had this discussion a couple of years ago ... using VHDL

 

[D.A.(Tony)Stewart]

This is called https://en.m.wikipedia.org/wiki/Hamming_weight for error detection, correction. Numerous solutions.

 

[vGoodtimes]

As described in the first post, it is not hamming weight, at least not directly. it would be hamming weight of -x ^ ~x. (eg: x= 10110000, ~x = 01001111, -x = 01010000, -x ^ ~x = 00001111)

I can think of three implementations. The logic description similar to the while loop or casex above. the while loop looks to match my suggestion, which is a little different than the original post.

The second would be the -x ^ ~x plus adder tree plus barrelshift.

The last I could think of would be -x & x plus a bit-reversal (free) plus a multiplication plus a bit-reversal. eg: x = 10110000, r = 00001101, m = -x & x = 00010000, r*m = 11010000, reversed = 00001011

The first will be mostly LUT based, which might not be that fast. The second is an adder+lut, adder-tree, and 32:1 mux. It will at least make use of the fast carry chain for some logic. The last is an adder+lut and a multiplier.

The latter might work out best if the FPGA has HW support for the addition and the multiplier of correct size. The operation is a fairly heavy operation in any case.

 

[Shosa]

i need a combination logic to run if k= no of one's for abc value from casex
how can i give that condition ?

---

Code Verilog - [expand]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
casex (abc)
  32'b_xxxx_xxxx_xxxx_xxxx_xxxx_xxxx_xxxx_xx10  : new_abc <= {1'b0, abc[31:1]};
  32'b_xxxx_xxxx_xxxx_xxxx_xxxx_xxxx_xxxx_x100  : new_abc <= {2'b0, abc[31:2]};
  // ...
  32'b_1000_0000_0000_0000_0000_0000_0000_0000  : new_abc <= {31'b0, abc[31]};
endcase
 
// somewhere else you clock new_abc into abc:
always @ (posedge clk) begin
  if (some_condition) begin
    abc <= new_abc;
  end else if (count_ones_condition) begin
    abc <= {1'b0, abc[31:1]};
  end
end

---

 

[pbernardi]

Not sure if I understand the question, but isn´t it a simple sum of digits of abc?

 

[vGoodtimes]

I'm also still confused about the question. Are you looking to count the number of 1's in a 32b value? Or are you looking to find the location of the rightmost 1 for some other reason?

"counting consecutive zeroes in 32 bit and shifting in one cycle" -- this one makes me think you are finding the rightmost 1.

"k= no of one's for abc value from casex" -- this makes me think you are trying to find the number of 1's in a 32b value.

 

[Shosa]

Not sure if I understand the question, but isn´t it a simple sum of digits of abc?

ok i actually designing a 32 bit multiplier for variable latency.. there r two parts of the project
one is fixed latency i.e it will take 33 cycles for the product, which i designed and it works
other is variable latency i.e the number of cycles should be number of 1's in 32 bit plus extra cycles to shift any single or consecutive zeroes?

my code is simulating but i am getting the wrong output

 

[vGoodtimes]

I'm assuming this is a school project, and that the idea is to design a shift-add multiplier in two ways. One of which is fixed latency -- do every shift, even if not needed -- and the second is "optimized" to only do shifts as needed. The variable latency design might be impractical, but that is not the point of the project. You seem to want to wait a number of cycles equal to the number of 1's in the input. This can be done by waiting for this shifted vector to become all 0's.

 

[D.A.(Tony)Stewart]

https://en.m.wikipedia.org/wiki/Hamming_weight#Efficient_implementation