First non-zero element encoder in Verilog

Question

Suppose I have an array A containing binary numbers, e.g. [0 0 1 0 1 1]. Now I want to build an encoder that can identify the location of the first '1' in array A. For example, the logic should output 3 for array A if we give index 1 to the first element in that array. Is there any elegant way of doing it? I guess one way to do it is using a ROM, but how do you write it in Verilog? Using a look up table?

Answer 1

You can use generate to automate the construction of combinatorial logic for whatever encoding is desired. The following example returns the index of the highest set bit, or -1 if there is no set bit.

The generate statement is used to unroll a loop. Each stage of the loop can create an arbitrary function of the loop index and some of the input vector bits. Since the output of the first stage is the input to the next, it forms progressively more complex combinatorial logic. The Synthesis tool is relied on to minimize, pack, and combine the many stage combinatorial logic in the most efficient way.

For example, in Xilinx Vivado, the following example reduces to only two 6 input LUT stages for a 16 bit input instead of 16 cascaded 2:1 multiplexers.

module highbit #(
    parameter OUT_WIDTH = 4, // out uses one extra bit for not-found
    parameter IN_WIDTH = 1<<(OUT_WIDTH-1)
) (
    input [IN_WIDTH-1:0]in,
    output [OUT_WIDTH-1:0]out
);

wire [OUT_WIDTH-1:0]out_stage[0:IN_WIDTH];
assign out_stage[0] = ~0; // desired default output if no bits set
generate genvar i;
    for(i=0; i<IN_WIDTH; i=i+1)
        assign out_stage[i+1] = in[i] ? i : out_stage[i]; 
endgenerate
assign out = out_stage[IN_WIDTH];

endmodule

Answer 2

casex can solve your problem.

function [2:0] prienc6;
 input [5:0] select;
 reg   [2:0] out;
 begin
   casex(select)
     6'b000001: out = 3'b101;
     6'b00001x: out = 3'b100;
     6'b0001xx: out = 3'b011; 
     6'b001xxx: out = 3'b010; 
     6'b01xxxx: out = 3'b001; 
     6'b1xxxxx: out = 3'b000; 
   endcase
   prienc6 = out ;
 end
endfunction