Priority encoder in verilog

Question

I am somewhat new to verilog, I tried running this code but it gives me an error:

module enc(in,out);
  input [7:0] in;
  output [3:0] out;
  reg i;
  reg [3:0] out;

  always @*
    begin
      for (i=0;i<7;i=i+1)
        begin
          if ((in[i]==1) && (in[7:i+1]==0))
            out = i;
          else
            out = 0;
        end
    end
endmodule

I think it complains about in[7:i+1] but i don't understand why ? Can someone please advise..

EDIT ok so I am reluctant to using the X due to their numerous problems.. I was thinking of modifying the code to something like this :

module enc(in,out);
  input [7:0] in;
  output [2:0] out;
  reg i;
  reg [2:0] out,temp;

  always @*
    begin
      temp = 0;
      for (i=0;i<8;i=i+1)
        begin
          if (in[i]==1)
            temp = i;
        end
      out = temp;
    end
endmodule

Do you think that will do the trick ? I currently don't have access to a simulator..

Answer 1

A priority encoder mean giving priority to a one bit if two or more bits meet the criteria. Looking at your code, it appears you wanted to give priority to a LSB while using a up counter. out is assigned in every look, so even if your could compile, the final result would be 6 or 0.

For an LSB priority encoder, first start with a default value for out and use a down counter:

module enc (
    input wire [7:0] in,
    output reg [2:0] out
  );
  integer i;
  always @* begin
    out = 0; // default value if 'in' is all 0's
    for (i=7; i>=0; i=i-1)
        if (in[i]) out = i;
  end
endmodule

Answer 2

If you are only interested in simulation than your linear loop approach should be fine, something like

    out = 0;
    for (i = W - 1; i > 0; i = i - 1) begin
      if (in[i] && !out)
        out = i;
    end

If you also care about performance, the question becomes more interesting. I once experimented with different approaches to writing parameterized priority encoders here. It turned out that Synopsys can generate efficient implementation even from the brain-dead loop above but other toolchains needed explicit generate magic. Here is an excerpt from the link:

    output [WIDTH_LOG - 1:0] msb;

    wire [WIDTH_LOG*WIDTH - 1:0] ors;
    assign ors[WIDTH_LOG*WIDTH - 1:(WIDTH_LOG - 1)*WIDTH] = x;

    genvar w, i;
    integer j;

    generate
      for (w = WIDTH_LOG - 1; w >= 0; w = w - 1) begin
        assign msb[w] = |ors[w*WIDTH + 2*(1 << w) - 1:w*WIDTH + (1 << w)];
        if (w > 0) begin
          assign ors[(w - 1)*WIDTH + (1 << w) - 1:(w - 1)*WIDTH] = msb[w] ? ors[w*WIDTH + 2*(1 << w) - 1:w*WIDTH + (1 << w)] : ors[w*WIDTH + (1 << w) - 1:w*WIDTH];
        end
      end
    endgenerate

Answer 3

So my Edited solution worked... how silly !! I forgot to declare reg [2:0] i; and instead wrote reg i; Thanks everybody

Answer 4

Hunks, I have to tell you, all your solutions are either too complex or non-synthesizable, or implement into slow multiplexors. Alexej Bolshakov at OpenCores uploaded an outstandin' parametrizable encoder on Aug 23, 2015, based on OR elements. No muxes, 100% synthesizable. His code (with my tiny formatting):

module encoder #(
  parameter LINES = 16,
  parameter WIDTH = $clog2(LINES)
)(
  input      [LINES-1:0] unitary_in,
  output wor [WIDTH-1:0] binary_out
);

genvar i, j;

generate
for (i = 0; i < LINES; i = i + 1)
  begin: loop_i
    for (j = 0; j < WIDTH; j = j + 1)
    begin: loop_j
    if (i[j])
      assign binary_out[j] = unitary_in[i];
    end 
  end
endgenerate

endmodule

RTL viewer screenshot, Model-Sim screenshot

Answer 5

This solution divides the input into four blocks and checks for the first nonzero block. This block is further subdivided in the same way. It is reasonably efficient.

// find position of most significant 1 bit in 64 bits input
// (system verilog)
module bitscan(
    input  logic [63:0] in,  // number input
    output logic [5:0]  out, // bit position output
    output logic zeroout     // indicates if input is zero
);

logic [63:0] m0;  // intermediates
logic [15:0] m1;
logic [3:0]  m2;
logic [5:0]  r;

always_comb begin
    m0 = in;
    // choose between four 16-bit blocks
    if (|m0[63:48]) begin
        m1 = m0[63:48];
        r[5:4] = 3;
    end else if (|m0[47:32]) begin
        m1 = m0[47:32];
        r[5:4] = 2;
    end else if (|m0[31:16]) begin
        m1 = m0[31:16];
        r[5:4] = 1;
    end else begin
        m1 = m0[15:0];
        r[5:4] = 0;
    end

    // choose between four 4-bit blocks
    if (|m1[15:12]) begin
        m2 = m1[15:12];
        r[3:2] = 3;
    end else if (|m0[11:8]) begin
        m2 = m1[11:8];
        r[3:2] = 2;
    end else if (|m0[7:4]) begin
        m2 = m1[7:4];
        r[3:2] = 1;
    end else begin
        m2 = m1[3:0];
        r[3:2] = 0;
    end

    // choose between four remaining bits    
    if      (m2[3]) r[1:0] = 3;
    else if (m2[2]) r[1:0] = 2;
    else if (m2[1]) r[1:0] = 1;
    else            r[1:0] = 0;

    out = r;
    zeroout = ~|m2;
end 
endmodule

Here is another solution that uses slightly less resourcess:

module bitscan4 (
    input logic [63:0] in,
    output logic  [5:0] out,
    output logic  zout
);
logic [63:0] m0;
logic [3:0]  m1;
logic [3:0]  m2;
logic [5:0]  r;

always_comb begin
    r = 0;
    m0 = in;
    if (|m0[63:48]) begin
        r[5:4] = 3;
        m1[3] = |m0[63:60];
        m1[2] = |m0[59:56];
        m1[1] = |m0[55:53];
        m1[0] = |m0[51:48];        
    end else if (|m0[47:32]) begin
        r[5:4] = 2;
        m1[3] = |m0[47:44];
        m1[2] = |m0[43:40];
        m1[1] = |m0[39:36];
        m1[0] = |m0[35:32];
    end else if (|m0[31:16]) begin
        r[5:4] = 1;
        m1[3] = |m0[31:28];
        m1[2] = |m0[27:24];
        m1[1] = |m0[23:20];
        m1[0] = |m0[19:16];
    end else begin
        r[5:4] = 0;
        m1[3] = |m0[15:12];
        m1[2] = |m0[11:8];
        m1[1] = |m0[7:4];
        m1[0] = |m0[3:0]; 
    end

    if (m1[3]) begin
        r[3:2] = 3;
    end else if (m1[2]) begin
        r[3:2] = 2;
    end else if (m1[1]) begin
        r[3:2] = 1;
    end else begin
        r[3:2] = 0;
    end

    m2 = m0[{r[5:2],2'b0}+: 4];

    if      (m2[3]) r[1:0] = 3;
    else if (m2[2]) r[1:0] = 2;
    else if (m2[1]) r[1:0] = 1;
    else            r[1:0] = 0;

    zout = ~|m2;
    out = r;
end 

endmodule

Answer 6

To be able to use variable indexes in part-slice suffixes, you must enclose the for block into a generate block, like this:

gen var i;
generate
for (i=0;i<7;i=i+1) begin :gen_slices
  always @* begin
    ... do whatever with in[7:i+1]
  end
end

The problem is that apllying this to your module, the way it's written, leads to other errors. Your rewritten module would look like this (be warned: this won't work either)

module enc (
  input wire [7:0] in,
  output reg [2:0] out  // I believe you wanted this to be 3 bits width, not 4.
  );

  genvar i; //a generate block needs a genvar
  generate
    for (i=0;i<7;i=i+1) begin :gen_block
      always @* begin
        if (in[i]==1'b1 && in[7:i+1]=='b0) // now this IS allowed :)
          out = i;
        else
          out = 3'b0;
      end
    end
  endgenerate
endmodule

This will throw a synthesis error about out being driven from more than one source. This means that the value assigned to out comes from several sources at the same time, and that is not allowed.

This is because the for block unrolls to something like this:

always @* begin
  if (in[0]==1'b1 && in[7:1]=='b0)
    out = 0;
  else
    out = 3'b0;
end
always @* begin
  if (in[1]==1'b1 && in[7:2]=='b0)
    out = 1;
  else
    out = 3'b0;
end
always @* begin
  if (in[2]==1'b1 && in[7:3]=='b0)
    out = 2;
  else
    out = 3'b0;
end
.... and so on...

So now you have multiple combinational block (always @*) trying to set a value to out. All of them will work at the same time, and all of them will try to put a specific value to out whether the if block evaluates as true or false. Recall that the condition of each if statement is mutually exclusive with respect of the other if conditions (i.e. only one if must evaluate to true).

So a quick and dirty way to avoid this multisource situation (I'm sure there are more elegant ways to solve this) is to let out to be high impedance if the if block is not going to assign it a value. Something like this:

module enc (
  input wire [7:0] in,
  output reg [2:0] out  // I believe you wanted this to be 3 bits width, not 4.
  );

  genvar i; //a generate block needs a genvar
  generate
    for (i=0;i<7;i=i+1) begin :gen_block
      always @* begin
        if (in[i]==1'b1 && in[7:i+1]=='b0) // now this IS allowed :)
          out = i;
        else
          out = 3'bZZZ;
      end
    end
  endgenerate
  always @* begin
    if (in[7])  // you missed the case in which in[7] is high
      out = 3'd7;
    else
      out = 3'bZZZ;
  end
endmodule

On the other way, if you just need a priority encoder and your design uses fixed and small widths for inputs and outputs, you may write your encoder as this:

module enc (
  input wire [7:0] in,
  output reg [2:0] out
  );

  always @* begin
    casex (in)
      8'b1xxxxxxx : out = 3'd7;
      8'b01xxxxxx : out = 3'd6;
      8'b001xxxxx : out = 3'd5;
      8'b0001xxxx : out = 3'd4;
      8'b00001xxx : out = 3'd3;
      8'b000001xx : out = 3'd2;
      8'b0000001x : out = 3'd1;
      8'b00000001 : out = 3'd0;
      default     : out = 3'd0;
    endcase
  end
endmodule

(although there seems to be reasons to not to use casex in a design. Read the comment @Tim posted about it in this other question: How can I assign a "don't care" value to an output in a combinational module in Verilog )

In conclusion: I'm afraid that I have not a bullet-proof design for your requirements (if we take into account the contents of the paper Tim linked in his comment), but at least, you know now why i was unallowed inside a part-slice suffix.

---

On the other way, you can have half of the work done by studying this code I gave as an answer to another SO question. In this case, the module works like a priority encoder, parametrized and without casex statements, only the output is not binary, but one-hot encoded. How to parameterize a case statement with don't cares?

Answer 7

out = in&(~(in-1)) gives you the one-hot results(FROM LSB->MSB where the first 1 at)