+ Post New Thread
Results 1 to 10 of 10
  1. #1
    Member level 3
    Points: 525, Level: 4

    Join Date
    Feb 2016
    Posts
    63
    Helped
    0 / 0
    Points
    525
    Level
    4

    Priority encoder for one-hot-to-binary

    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
    Click image for larger version. 

Name:	for_with_OR.png 
Views:	8 
Size:	58.5 KB 
ID:	138030

    Without OR
    Click image for larger version. 

Name:	for_without_OR.png 
Views:	9 
Size:	48.2 KB 
ID:	138029

    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 ?

  2. #2
    Super Moderator
    Points: 231,459, Level: 100
    Awards:
    1st Helpful Member

    Join Date
    Jan 2008
    Location
    Bochum, Germany
    Posts
    39,954
    Helped
    12203 / 12203
    Points
    231,459
    Level
    100

    Re: Priority encoder for one-hot-to-binary

    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.



    •   Alt19th April 2017, 07:48

      advertising

        
       

  3. #3
    Member level 3
    Points: 525, Level: 4

    Join Date
    Feb 2016
    Posts
    63
    Helped
    0 / 0
    Points
    525
    Level
    4

    Re: Priority encoder for one-hot-to-binary

    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] ?

    Click image for larger version. 

Name:	Screenshot from 2017-04-19 22-19-58.png 
Views:	6 
Size:	44.3 KB 
ID:	138049



    •   Alt19th April 2017, 15:22

      advertising

        
       

  4. #4
    Super Moderator
    Points: 231,459, Level: 100
    Awards:
    1st Helpful Member

    Join Date
    Jan 2008
    Location
    Bochum, Germany
    Posts
    39,954
    Helped
    12203 / 12203
    Points
    231,459
    Level
    100

    Re: Priority encoder for one-hot-to-binary

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



    •   Alt20th April 2017, 07:23

      advertising

        
       

  5. #5
    Member level 3
    Points: 525, Level: 4

    Join Date
    Feb 2016
    Posts
    63
    Helped
    0 / 0
    Points
    525
    Level
    4

    Re: Priority encoder for one-hot-to-binary

    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)" ?



  6. #6
    Super Moderator
    Points: 231,459, Level: 100
    Awards:
    1st Helpful Member

    Join Date
    Jan 2008
    Location
    Bochum, Germany
    Posts
    39,954
    Helped
    12203 / 12203
    Points
    231,459
    Level
    100

    Re: Priority encoder for one-hot-to-binary

    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.



  7. #7
    Member level 3
    Points: 525, Level: 4

    Join Date
    Feb 2016
    Posts
    63
    Helped
    0 / 0
    Points
    525
    Level
    4

    Re: Priority encoder for one-hot-to-binary

    From what I understood, the code from https://github.com/jbush001/NyuziPro..._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 ?



    •   Alt26th April 2017, 09:57

      advertising

        
       

  8. #8
    Member level 3
    Points: 525, Level: 4

    Join Date
    Feb 2016
    Posts
    63
    Helped
    0 / 0
    Points
    525
    Level
    4

    Re: Priority encoder for one-hot-to-binary

    Alternatively, let me rephrase my question.

    How does using "OR" operator on 'index' as in https://github.com/jbush001/NyuziPro..._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]



  9. #9
    Super Moderator
    Points: 231,459, Level: 100
    Awards:
    1st Helpful Member

    Join Date
    Jan 2008
    Location
    Bochum, Germany
    Posts
    39,954
    Helped
    12203 / 12203
    Points
    231,459
    Level
    100

    Re: Priority encoder for one-hot-to-binary

    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".


    1 members found this post helpful.

  10. #10
    Member level 3
    Points: 525, Level: 4

    Join Date
    Feb 2016
    Posts
    63
    Helped
    0 / 0
    Points
    525
    Level
    4

    Re: Priority encoder for one-hot-to-binary

    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)



--[[ ]]--