Priority encoder for one-hot-to-binary

[promach]

I am trying to understand how using 'or' avoids synthesizing priority encoder with the following circuit diagrams generated by yosys, Why would we have 31:2 bits of $10_Y mapped back to itself ? The verilog source code could be found below or https://www.edaplayground.com/x/4H6a

With OR


Without OR

---

Code Verilog - [expand]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
//
// Convert a one-hot signal to a binary index corresponding to the active bit.
// (Binary encoder)
// If DIRECTION is "LSB0", index 0 corresponds to the least significant bit
// If "MSB0", index 0 corresponds to the most significant bit
//
`timescale 1ns/100ps
 
module oh_to_idx
    #(parameter NUM_SIGNALS = 4,
    parameter DIRECTION = "LSB0",
    parameter INDEX_WIDTH = $clog2(NUM_SIGNALS))
 
    (input[NUM_SIGNALS - 1:0]         one_hot,
    output reg [INDEX_WIDTH - 1:0]   index);
 
    integer oh_index;
  
    always @(*)
    begin : convert
        index = 0;
        for (oh_index = 0; oh_index < NUM_SIGNALS; oh_index=oh_index+1)
        begin
            if (one_hot[oh_index])
            begin
                if (DIRECTION == "LSB0")
                    index = index | oh_index[INDEX_WIDTH - 1:0];    // Use 'or' to avoid synthesizing priority encoder
                else
                    index = index | ~oh_index[INDEX_WIDTH - 1:0];
            end
        end
    end
endmodule

---

---

Code Verilog - [expand]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
`timescale 1ns/100ps
 
module oh_to_idx_tb;
    reg[3:0] one_hot;
    wire[1:0] index;
 
    oh_to_idx A1
    (
        .one_hot(one_hot),
        .index(index)
    );
 
    initial
    begin
        $dumpfile("oh_to_idx.vcd");
        $dumpvars(0, oh_to_idx_tb);
 
        one_hot = 4'b1000;
        #5 one_hot = 4'b0100;       
        #5 one_hot = 4'b0010;       
        #5 one_hot = 4'b0001;       
 
        #20 $finish;
    end
 
 
endmodule

---

- - - Updated - - -

What are actual purposes of the $or labelled $10 and $12 ?

 

[FvM]

Your question is missing a clear specification of the intended decode function. Why do you want to avoid a priority encoder? Do you understand the implications?

Obviously the priority encoder is requiring more logic cells.

 

[promach]

The following circuit diagram is generated from Altera Quartus synthesis tool:

Is it correct to identify the extra multiplexer generated as a form of priority encoder for index[0] ?

 

[FvM]

You'll find the answer when you list the output for all possible codings of the one_hot input, not only the legal combinations.

 

[promach]

The easiest way is to think about what would happen if there was more than one bit set (even though we avoid that in this design, the synthesis tool needs to account for all logic states). If I had implemented it like this:

---

Code Verilog - [expand]
1
2
3
4
5
6
7
8
9
10
11
for (oh_index = 0; oh_index < NUM_SIGNALS; oh_index=oh_index+1)
begin
    if (one_hot[oh_index])
    begin
        if (DIRECTION == "LSB0")
           index = oh_index[INDEX_WIDTH - 1:0]; 
        else
            index = ~oh_index[INDEX_WIDTH - 1:0];
        end
    end
end

---

It would have to encode a binary signal that corresponds to the lowest bit set to be correct. The only way to do that is with a priority encoder (which has a lot of latency). If multiple bits were set with the implementation where there is an OR gate, the outputted index would be the logical OR of indices of set bits, which is meaningless. But I don't care about that case anyway.

The above quoted message is email reply snippet from the code author.

What do you guys understand by "The only way to do that is with a priority encoder (which has a lot of latency)" ?

 

[FvM]

A circuit that outputs either the index of the leftmost or rightmost activated bit is a priority encoder. Saying it has "at lot of latency" is an overstatement, I think. Logic is bit more complex and latency respectively higher.

As previously mentioned

Your question is missing a clear specification of the intended decode function.

 

[promach]

From what I understood, the code from https://github.com/jbush001/NyuziProcessor/blob/master/hardware/core/oh_to_idx.sv#L40 is intended to modify the priority encoder to be a simple encoder where each bit could be checked independently.

What I do not understand is why we specifically use "OR" operator on 'index' for such intention ?

 

[promach]

Alternatively, let me rephrase my question.

How does using "OR" operator on 'index' as in https://github.com/jbush001/NyuziProcessor/blob/master/hardware/core/oh_to_idx.sv#L40 help to transform the boolean function of index[0] of priority encoder to that of simple encoder ?

Priority encoder
index[0] = one_hot[3] + ( not one_hot[2] ) one_hot[1]

Simple encoder
index[0] = one_hot[3] + one_hot[1]

Note: Both priority encoder and simple encoder have similar boolean function of index[1] = one_hot[2] + one_hot[3]

 

[FvM]

What I do not understand is why we specifically use "OR" operator on 'index' for such intention ?

You can use any operation which gives the correct result under the assumption that only one input is active at a time...

The OR has the effect that an output bit can be set unconditionally by a specific one_hot input bit.

Did you notice that the so-called priority encoder is not decoding all possible inputs combination specifically. It doesn't care if one_hot[0] is set, thus not detect the illegal code "0000".

 

[promach]

Thanks FvM. I have understood the effect of "OR" in generating simple encoder which is simpler in hardware and lesser in latency.

Yes, I noticed the illegal code "0000"
I also used Full truth table to derive the two boolean functions which matches the Altera synthesized circuit (using muxes)