About priority_encoder

[GGbang2]

Hi, Sir. I am studying the priority_encoder module and I have some confusion about the following code. I would appreciate it if you could provide me with some explanation

// compress down to single valid bit and encoded bus
for (l = 1; l < LEVELS; l = l + 1) begin : loop_levels
    for (n = 0; n < W/(2*2**l); n = n + 1) begin : loop_compress
        assign stage_valid[l][n] = |stage_valid[l-1][n*2+1:n*2];//compress down to single valid.
        if (LSB_HIGH_PRIORITY) begin
            // bit 0 is highest priority
            assign stage_enc[l][(n+1)*(l+1)-1:n*(l+1)] = stage_valid[l-1][n*2+0] ? {1'b0, stage_enc[l-1][(n*2+1)*l-1:(n*2+0)*l]} : {1'b1, stage_enc[l-1][(n*2+2)*l-1:(n*2+1)*l]};
        end else begin
            // bit 0 is lowest priority
            assign stage_enc[l][(n+1)*(l+1)-1:n*(l+1)] = stage_valid[l-1][n*2+1] ? {1'b1, stage_enc[l-1][(n*2+2)*l-1:(n*2+1)*l]} : {1'b0, stage_enc[l-1][(n*2+1)*l-1:(n*2+0)*l]};
        end
    end
end

Q1:Why do you use the value of stage_valid[l-1][n2+0] to make the selection when LSB_HIGH_PRIORITY is set to 1? I believe that in the code above, you compressed two requests into one valid value with the line "assign stage_valid[0][n] = |input_padded[n2+1:n2];", so why do you skip the odd bit and use the [n2+0] bit here? What I understand is that when LSB_HIGH_PRIORITY is set to 1, it means that the priority is given to the lower bits. However, I don't see the relation between this code and the priority.

Q2：When Width is 4, LEVELS equals 2. Then 'stage_enc[l][(n+1)(l+1)-1:n(l+1)]' is 2 bits, and '{1'b0, stage_enc[l-1][(n*2+1)l-1:(n2+0)*l]}' is 3 bits. This means that the bit width is not matched. Am I misunderstanding something?

[alexforencich]

Q1: stage_valid[l-1][n*2+0] is used to make the selection when LSB_HIGH_PRIORITY is set so that bits set in the lower portion of the input have priority. In this case, stage_valid[l-1][n*2+1] is not used in the selection because the value is irrelevant - if there are no bits set in the low portion, then it's assumed there must be a bit set in the high portion. stage_valid[l][n] = |stage_valid[l-1][n*2+1:n*2] takes care of this case - if there are no bits set in either portion, then the valid bit is not set, and the result of the mux is not used.

Q2: When LEVELS = 2, the value of l can only be 1 based on the loop configuration, resulting in {1'b0, stage_enc[l-1][(n*2+1)*l-1:(n*2+0)*l]} having a width of 2 bits.

[GGbang2]

In this part, when LSB_HIGH_PRIORITY is set to 1, stage_enc[0][n] = !input_padded[n*2+0], why is input_padded inverted and only even bits are taken? but when LSB_HIGH_PRIORITY is 0, it does not need to be inverted and only odd bits are taken.

// compress down to single valid bit and encoded bus
for (n = 0; n < W/2; n = n + 1) begin : loop_in
assign stage_valid[0][n] = |input_padded[n2+1:n2]; //if 1 ,there's a write or read
if (LSB_HIGH_PRIORITY) begin
// bit 0 is highest priority
assign stage_enc[0][n] = !input_padded[n2+0];
end else begin
// bit 0 is lowest priority
assign stage_enc[0][n] = input_padded[n2+1];
end
end

[alexforencich]

Forget about "even" and "odd". The idea is the code is processing bits in pairs. For each pair of inputs, it produces one additional encoded output bit, along with a valid bit indicating if there was a bit set in that portion of the input. Think about what the truth table for this looks like. If the high priority bit is set, the other bit is irrelevant, so for the encoding part only needs to consider one bit, and which bit is considered depends on which end of the input is the higher priority. If it's set for LSB high priority, then if the LSB (which is index 0) is set, then the encoded output should be 0, otherwise it should be 1, hence the value of the LSB should be inverted to produce the encoded output. For MSB high priority, if bit 1 is set then the output should be 1, otherwise the output should be 0, hence it is not inverted.

This module was actually originally written with a recursive structure that might be easier to understand, but causes some tool issues with synthesis: https://github.com/alexforencich/verilog-axi/blob/d694a6719013242680e3aa3bd49092ff724f157e/rtl/priority_encoder.v . The current version implements the exact same logic, but with a loop instead of recursion.

[GGbang2]

It's clear to me now, thank you for your explanation.