How to get the index of first occurance of '1' in a vactor ?

[omara007]

Hi folks

I want to implement a synthesizable verilog code or a function that returns an index of the first occurrence of digit '1' (or digit '0') in a vector. For example, if this is the vector :

reg [7:0] x;

x = 8'b0100_1111

the executioin of the function should return '6' if we start from MSB and should return '0' if we start from LSB.

 

[muni123]

Re: How to get the index of first occurance of '1' in a vact

The following function can be implemented to check for first 1 from MSB side:

function func_first1(input [7:0]x);
begin
for(i=0;i<8;i=i+1)
begin
if(x[0])
func_first1 = i;
else
x=x>>1;
end
end

Accordingly we can write the function for first one from LSB side and first 0 from both sides too...
Correct me if any mistakes.

 

[omara007]

Re: How to get the index of first occurance of '1' in a vact

The following function can be implemented to check for first 1 from MSB side:

function func_first1(input [7:0]x);
begin
for(i=0;i<8;i=i+1)
begin
if(x[0])
func_first1 = i;
else
x=x>>1;
end
end

Accordingly we can write the function for first one from LSB side and first 0 from both sides too...
Correct me if any mistakes.

The function will not work as you don't increment, or decrement the index of the loop .. did you notice that ?

 

[yx.yang]

Re: How to get the index of first occurance of '1' in a vact

input [7:0] bit_in;
input check_bit;
input msb_lsb;

wire [7:0] bit_reverse;
wire [7:0] bit_use;

reg [3:0] fir_loc; //if bit[3] == 1'b1, not find the check_bit.

assign bit_reverse = {bit_in[0], bit_in[1], bit_in[2], bit_in[3],
bit_in[4], bit_in[5], bit_in[6], bit_in[7]};

assign bit_use = (msb_lsb) bit_in : bit_reverse?

always @(bit_use or check_bit)
if(bit_use[7] == check_bit)
fir_loc = 4'h7;
else if(bit_use[6] == check_bit)
fir_loc = 4'h6;
else if(bit_use[5] == check_bit)
fir_loc = 4'h5;
else if(bit_use[4] == check_bit)
fir_loc = 4'h4;
else if(bit_use[3] == check_bit)
fir_loc = 4'h3;
else if(bit_use[2] == check_bit)
fir_loc = 4'h2;
else if(bit_use[1] == check_bit)
fir_loc = 4'h1;
else if(bit_use[0] == check_bit)
fir_loc = 4'h0;
else
fir_loc = 4'h8;

 

[lordsathish]

Re: How to get the index of first occurance of '1' in a vact

What you are asking for is just a priority encoder...
This code is readily available in many text books and
And yx.yang has given the code...

 

[omara007]

Re: How to get the index of first occurance of '1' in a vact

What you are asking for is just a priority encoder...
This code is readily available in many text books and
And yx.yang has given the code...

Can you suggest a code for a vector of a generic width ? .. the given code is implemented for a given known vector size. How can I generalize this code to be used with a vector defined as follows :
reg [width-1 downto 0] x;

 

[j_andr]

Re: How to get the index of first occurance of '1' in a vact

Can you suggest a code for a vector of a generic width ?

may be this will help ?

module select
(
   input   [N-1:0] in_sel,
   output  [N-1:0] sel
);

parameter N = 4;
genvar i;

assign sel[0] = in_sel[0];
generate for ( i=1; i<N; i=i+1 ) 
   begin: x
      sum #( N )      // AND gate
        inst 
          (.out(sel[i]), 
           .in( {
                  { (N-1-i){1'b1} }, // inputs above 'i' index
                     in_sel[i],
                    ~in_sel[i-1:0]   // inputs below 'i' index
                } 
              ) 
          );
   end
endgenerate
      
endmodule 

module sum  //  simple AND 'N' input gate
(
   input  [N-1:0]  in,
   output          out
);

parameter N = 4;
assign out = &in;

endmodule

the idea is to implement 'N' times 'N' input AND
gate sum, input 'i' of the gate is connected to 'select'
signal, all inputs above 'i' are connected to 1'b1
what means no influence on the output, all inputs
of the AND gate 'below' 'i' are connected to inverted
'select' signal - what gives '0' if any of them are '1';
not very elegant, but I did not find a better way;

schematisc:



quartus simulation:



---

 

[FvM]

The variants utilizing a for loop are basically an appropriate way to define the priority encoder as a parameterizable function.

But to complete the above examples, you have to define first what's the intended output for an all zero vector.

 

[j_andr]

Re: How to get the index of first occurance of '1' in a vact

But to complete the above examples, you have to define first what's
the intended output for an all zero vector.

not me, but - eventually - the author of the thread ;
but it seems quite natural that if the input vector contains all '0'
nothing is selected so no action triggered;
---

 

[omara007]

Re: How to get the index of first occurance of '1' in a vact

The variants utilizing a for loop are basically an appropriate way to define the priority encoder as a parameterizable function.

But to complete the above examples, you have to define first what's the intended output for an all zero vector.

My intended output for an all-zero input vector is also all-zero output vector. I believe this circuit by"j_andr" will implement that. Thanks "j_andr".

 

[FvM]

Re: How to get the index of first occurance of '1' in a vact

but it seems quite natural that if the input vector contains all '0' nothing is selected so no action triggered

I also think so, but if you define no output value for the function, the compiler is free to assign an arbitrary (wrong) value.

 

[omara007]

Re: How to get the index of first occurance of '1' in a vact

but it seems quite natural that if the input vector contains all '0' nothing is selected so no action triggered

I also think so, but if you define no output value for the function, the compiler is free to assign an arbitrary (wrong) value.

The output selector (sel) is going to be the condition for a case statement somewhere else .. there, one can include the 'all-zero' case in the default easily ..

 

[j_andr]

Re: How to get the index of first occurance of '1' in a vact

/.../ if you define no output value for the function,
the compiler is free to assign an arbitrary (wrong) value

in my example the compiler has no free choice for "all '0'" input;
zero in gives zero out;
---

 

[FvM]

Re: How to get the index of first occurance of '1' in a vact

in my example the compiler has no free choice for "all '0'" input; zero in gives zero out;

May be, I was referring to the original specification, that defined a result range of 0 to 7, or in other words a bit index. I would expect, that a different value (e. g. 8)should be used to mark the all zero case, cause a value of 0 is already assigned to bit 0.

As far as I understand, is your code a solution to a different problem, not to the original one.

 

[kalyansumankv]

Re: How to get the index of first occurance of '1' in a vact

may be the below code should add some value to your work,
is the x size is 8, then the poscnt and finalpos are of 3 bit width,
then u can change the size of these variables based on ur input(X) size


module positioncnt(clk);

input clk;

reg [3:0] poscnt = 4'b0;//counter width is based on data width
reg [3:0] finalpos;//counter width is based on data width
reg [7:0] x = 8'b0100_1100;


wire msb=1'b0;
always @ (posedge clk)
begin
if(msb)
begin
if(x[7])
begin
finalpos <= 4'd7 - poscnt; // width - poscnt
x <= x;
end
else
begin
poscnt <= poscnt + 1;
x <= {x[6:0],1'b0} ;
end
end
else
begin
if(x[0])
begin
finalpos <= poscnt; // width - poscnt
x <= x;
end
else
begin
poscnt <= poscnt + 1;
x <= {1'b0,x[7:1]} ;
end
end

end

endmodule