Priority Encoders

Chapter 1 · Section 1.4 · Combinational Building Blocks

1. The Engineering Problem

You are building the front end of an interrupt controller. Eight peripheral devices — a timer, a UART, a DMA engine, three GPIO banks, an SPI master, and an error line — each raise a single request bit into an 8-bit req vector. Your job is to hand the CPU one interrupt number to service this cycle, because the CPU has exactly one program counter and can vector to exactly one handler at a time.

The plain encoder from 1.3 does not solve this. A plain encoder is the inverse of a decoder: it takes a one-hot input and returns its index. That is a beautiful, cheap OR-tree — as long as its input is genuinely one-hot. But an interrupt vector is almost never one-hot. In a busy system the timer, the UART, and the DMA engine can all be asserting on the same cycle: req = 8'b0000_1101. Feed that multi-hot vector to a plain encoder and it does not error — it silently produces garbage, an OR of the indices of every set bit, an index that points at no real requester. That is the multi-hot failure 1.3 warned you about, and it is not a corner case here; it is the normal case.

So the request vector forces two decisions the plain encoder cannot make. First, which one wins? With three devices requesting, you must pick one deterministically — the same input must always yield the same winner, and there must be a defined ordering so the choice is not arbitrary. That ordering is a priority: the error line outranks the UART, the UART outranks a GPIO bank, and so on. Second, is there anyone to service at all? When req = 8'b0000_0000 — no device is requesting — the encoder must say so, because "no request" is a completely different situation from "device 0 is requesting," and an index alone cannot tell them apart.

The structure that answers both questions is the priority encoder: it scans the request vector for the first set bit in a fixed priority order and returns that bit's index, and it emits a separate valid bit that is high if and only if any request bit was set. The index says who; the valid says whether. Miss either and the interrupt controller is wrong — pick the wrong winner and you service the wrong device; drop the valid and you cannot distinguish "service device 0" from "service nobody."

   // Eight devices can all raise a request in the SAME cycle:
   wire [7:0] req;                       // e.g. 8'b0000_1101 = devices 0, 2, 3 all asking
 
   // A PLAIN encoder (1.3) assumes ONE-HOT. On a multi-hot vector it silently
   // ORs the set indices together and points at NO real requester:
   //   plain_encode(8'b0000_1101) -> garbage (0 | 2 | 3 = index 1, a device NOT asking)
 
   // A PRIORITY encoder resolves the contention deterministically and reports 'any?':
   wire [2:0] grant_idx;                 // index of the HIGHEST-priority set bit
   wire       valid;                     // 1 iff ANY req bit is set (|req)
   //   priority_encode(8'b0000_1101) -> grant_idx = 0 (LSB-priority), valid = 1
   //   priority_encode(8'b0000_0000) -> grant_idx = don't-care,       valid = 0

2. Mental Model

3. Pattern Anatomy

The priority encoder is built from one operation — scan for the first set bit — plus two outputs and one design axis.

The scan: find the first '1'. Given a WIDTH-bit req, walk the bits in priority order and stop at the first one that is set; its position is the index. "First" is defined by the priority direction you choose, and this is a decision you must make and document, because both are legal and common:

• MSB-priority (highest-numbered bit wins): scan from bit WIDTH-1 down to bit 0, return the index of the highest set bit. This is the classic "priority encoder" of textbooks and of many interrupt controllers, where a higher line number means higher urgency.
• LSB-priority (lowest-numbered bit wins): scan from bit 0 up to WIDTH-1, return the index of the lowest set bit. This is what most arbiters and free-list allocators use (find first free slot), and what the lowest-set-bit trick below computes directly.

Neither is "more correct" — but a design that is inconsistent about which it uses is a bug (see §6). Pick one, state it in a comment, and verify against it.

The two outputs. A priority encoder has two outputs, and both are load-bearing:

• grant_idx (width IDX_W = clog2(WIDTH)): the index of the winning bit. Undefined/don't-care when no bit is set.
• valid: exactly |req — the reduction-OR of the whole request vector, high if and only if at least one bit is set. This is the bit that makes grant_idx = 0 unambiguous.

The design axis — priority chain vs balanced tree. The same "first set bit" can be built two ways with very different timing:

• Priority chain (cascade). An if / else if / else if … chain, or a casez with a 1 wildcard in each pattern, is the literal spelling of "check the top priority first, then the next, then the next." It synthesizes to a priority cascade whose delay grows roughly linearly with WIDTH, because the lowest-priority branch sits behind every earlier comparison. Simple, obviously correct, and fine for small vectors — but the long chain becomes the critical path on a wide one.
• Balanced tree. The same priority can be computed as a log2(WIDTH)-deep tree: split the vector, ask "is there a set bit in the high half?", and recurse. Delay grows logarithmically. This is what you reach for when the encoder is wide and on a timing-critical path (an arbiter over 64 requesters).

The lowest-set-bit trick. For LSB-priority there is a classic bit-twiddle that isolates the lowest set bit of x in one expression: x & (~x + 1) — equivalently x & (-x) in two's complement. Adding one to ~x propagates a carry up to (and flips) the lowest set bit of x, so ANDing with the original leaves only that bit set — a one-hot mask of the winner. You then feed that one-hot mask through a plain encoder to get the index. It computes "first set bit" without any loop or chain, and it is the seed of the round-robin arbiter's masking logic.

Two facts close the anatomy. First, the valid bit is derived independently of the index — it is a pure reduction-OR of req, so even a completely broken scan cannot corrupt it; that independence is what makes it trustworthy. Second, the winner index is a genuine don't-care when valid is low — a well-written encoder pins it to a defined value (usually 0) so nothing is X, but downstream logic must gate on valid and never act on grant_idx when valid is 0. An encoder that forces you to remember that gate everywhere, instead of shipping the valid bit, has pushed its ambiguity onto every consumer.

4. Real RTL Implementation

This is the core of the page. We build three patterns — (a) a parameterized find-first priority encoder (a clean for-loop scan that emits both grant_idx and valid, with the priority direction documented), (b) a casez / when-style priority form over a fixed width, and (c) the missing-valid bug (buggy vs fixed) — and each is shown in SystemVerilog, Verilog, and VHDL, with both an RTL block and a self-checking testbench. The idea is identical in all three; the syntax differs, and seeing them side by side is what makes the pattern language-independent in your head.

One discipline runs through every RTL block: the encoder emits two outputs, and valid is computed as the plain reduction-OR of the request vector — never inferred from the index. That is what keeps grant_idx = 0 unambiguous, and it is exactly the discipline pattern (c) violates.

4a. Parameterized find-first priority encoder — LSB-priority, with valid

Start with the workhorse: a priority encoder for any width, emitting both the winning index and valid. We choose LSB-priority (lowest set bit wins) and document it, because that is what arbiters and allocators use. The scan is a descending for loop so that the lowest index written last wins — the loop overwrites higher-index hits with lower-index ones, leaving the lowest set bit as grant_idx.

   module prio_enc #(
       parameter int WIDTH = 8,                           // request vector width
       localparam int IDX_W = (WIDTH > 1) ? $clog2(WIDTH) : 1
   )(
       input  logic [WIDTH-1:0] req,                      // multi-hot: any bits may be set
       output logic [IDX_W-1:0] grant_idx,                // index of LOWEST set bit (LSB-priority)
       output logic             valid                     // 1 iff ANY bit set — |req, computed independently
   );
       // Combinational. PRIORITY DIRECTION: lowest-index request wins.
       always_comb begin
           grant_idx = '0;                                // defined default so idx is never X when !valid
           // valid is the reduction-OR of the WHOLE vector — never derived from grant_idx.
           valid     = |req;
           // Descending scan: write higher indices first, then lower ones OVERWRITE them,
           // so after the loop grant_idx holds the LOWEST set bit (LSB-priority).
           for (int i = WIDTH-1; i >= 0; i--)
               if (req[i]) grant_idx = i[IDX_W-1:0];
       end
   endmodule

Two lines carry the whole engineering point. valid = |req is a separate reduction-OR, so valid is trustworthy no matter what the scan does — this is the anti-ambiguity discipline. The descending for with if (req[i]) grant_idx = i realises "lowest wins" because later (lower-index) writes clobber earlier ones; flip the loop to ascending and you get MSB-priority instead — same structure, opposite direction. The testbench sweeps every value of req (exhaustive, because a small WIDTH has only 2**WIDTH codes) and checks grant_idx against an independent reference model, plus the two invariants: valid == |req, and when req == 0 the encoder must report valid == 0.

   module prio_enc_tb;
       localparam int WIDTH = 8;
       localparam int IDX_W = $clog2(WIDTH);
       logic [WIDTH-1:0] req;
       logic [IDX_W-1:0] grant_idx;
       logic             valid;
       int               errors = 0;
 
       prio_enc #(.WIDTH(WIDTH)) dut (.req(req), .grant_idx(grant_idx), .valid(valid));
 
       // Independent reference: index of the LOWEST set bit (LSB-priority).
       function automatic int ref_lowest(input logic [WIDTH-1:0] v);
           for (int i = 0; i < WIDTH; i++) if (v[i]) return i;
           return 0;                                      // no bit set: index is don't-care
       endfunction
 
       initial begin
           for (int code = 0; code < (1 << WIDTH); code++) begin   // EXHAUSTIVE over req
               req = code[WIDTH-1:0];
               #1;
               // Invariant 1: valid is exactly the reduction-OR of req.
               assert (valid === (|req))
                   else begin $error("req=%b valid=%b exp=%b", req, valid, |req); errors++; end
               if (|req) begin
                   // Invariant 2: when any bit is set, grant_idx is the lowest set bit.
                   assert (grant_idx === ref_lowest(req)[IDX_W-1:0])
                       else begin $error("req=%b idx=%0d exp=%0d", req, grant_idx, ref_lowest(req)); errors++; end
               end else begin
                   // Invariant 3: zero input -> valid low; index is a don't-care (we pinned 0).
                   assert (valid === 1'b0)
                       else begin $error("req=0 but valid=%b", valid); errors++; end
               end
           end
           if (errors == 0) $display("PASS: prio_enc lowest-set-bit + valid correct on all %0d codes", 1<<WIDTH);
           else             $display("FAIL: %0d mismatches", errors);
           $finish;
       end
   endmodule

The Verilog form is identical in intent; the differences are wire/reg typing, $clog2 at the port declaration, and an integer loop. The reduction-OR |req and the descending scan are the same, so the priority direction and the independent valid are preserved.

   module prio_enc #(
       parameter WIDTH = 8,
       parameter IDX_W = 3                     // = clog2(WIDTH); set by the instantiator
   )(
       input  wire [WIDTH-1:0] req,
       output reg  [IDX_W-1:0] grant_idx,
       output reg              valid
   );
       integer i;
       // Combinational. PRIORITY DIRECTION: lowest-index request wins (LSB-priority).
       always @(*) begin
           grant_idx = {IDX_W{1'b0}};          // defined default: idx never X when !valid
           valid     = |req;                   // reduction-OR of the WHOLE vector, independent of idx
           for (i = WIDTH-1; i >= 0; i = i - 1)
               if (req[i]) grant_idx = i[IDX_W-1:0];   // lower index written last -> wins
       end
   endmodule

   module prio_enc_tb;
       parameter WIDTH = 8;
       parameter IDX_W = 3;
       reg  [WIDTH-1:0] req;
       wire [IDX_W-1:0] grant_idx;
       wire             valid;
       integer          code, i, exp_idx, exp_valid, errors;
       reg              found;
 
       prio_enc #(.WIDTH(WIDTH), .IDX_W(IDX_W)) dut
           (.req(req), .grant_idx(grant_idx), .valid(valid));
 
       initial begin
           errors = 0;
           for (code = 0; code < (1 << WIDTH); code = code + 1) begin   // EXHAUSTIVE
               req       = code[WIDTH-1:0];
               #1;
               // Reference: lowest set bit and reduction-OR, computed independently.
               exp_valid = (req != 0) ? 1 : 0;
               exp_idx   = 0;
               found     = 1'b0;
               for (i = 0; i < WIDTH; i = i + 1)
                   if (req[i] && !found) begin exp_idx = i; found = 1'b1; end
               if (valid !== exp_valid[0]) begin
                   $display("FAIL: req=%b valid=%b exp=%b", req, valid, exp_valid[0]);
                   errors = errors + 1;
               end
               if (exp_valid && (grant_idx !== exp_idx[IDX_W-1:0])) begin
                   $display("FAIL: req=%b idx=%0d exp=%0d", req, grant_idx, exp_idx);
                   errors = errors + 1;
               end
           end
           if (errors == 0) $display("PASS: prio_enc idx + valid correct on all codes");
           else             $display("FAIL: %0d mismatches", errors);
           $finish;
       end
   endmodule

In VHDL the same scan is a for loop inside a combinational process, req is a std_logic_vector, and the index is produced by writing to_unsigned(i, IDX_W) on a hit. valid is the VHDL reduction-OR or_reduce(req) (from ieee.std_logic_misc, or written as a loop). The descending loop realises LSB-priority exactly as in the other languages, and to_integer/to_unsigned is how VHDL converts between the loop index and the vector index output.

   library ieee;
   use ieee.std_logic_1164.all;
   use ieee.numeric_std.all;
   use ieee.std_logic_misc.all;                            -- or_reduce
 
   entity prio_enc is
       generic ( WIDTH : positive := 8 );                  -- generic == Verilog parameter
       port (
           req       : in  std_logic_vector(WIDTH-1 downto 0);           -- multi-hot allowed
           grant_idx : out std_logic_vector(integer(ceil(log2(real(WIDTH))))-1 downto 0);
           valid     : out std_logic                       -- '1' iff any bit set
       );
   end entity;
 
   architecture rtl of prio_enc is
       constant IDX_W : positive := integer(ceil(log2(real(WIDTH))));
   begin
       -- Combinational. PRIORITY DIRECTION: lowest-index request wins (LSB-priority).
       process (all)
           variable idx : unsigned(IDX_W-1 downto 0);
       begin
           idx   := (others => '0');                       -- defined default: idx never 'U' when invalid
           valid <= or_reduce(req);                        -- reduction-OR of the WHOLE vector, independent
           -- Descending loop: lower indices, written last, OVERWRITE higher ones -> lowest wins.
           for i in WIDTH-1 downto 0 loop
               if req(i) = '1' then
                   idx := to_unsigned(i, IDX_W);
               end if;
           end loop;
           grant_idx <= std_logic_vector(idx);
       end process;
   end architecture;

   library ieee;
   use ieee.std_logic_1164.all;
   use ieee.numeric_std.all;
   use ieee.std_logic_misc.all;
 
   entity prio_enc_tb is
   end entity;
 
   architecture sim of prio_enc_tb is
       constant WIDTH : positive := 8;
       constant IDX_W : positive := 3;                     -- = clog2(WIDTH)
       signal req       : std_logic_vector(WIDTH-1 downto 0);
       signal grant_idx : std_logic_vector(IDX_W-1 downto 0);
       signal valid     : std_logic;
   begin
       dut : entity work.prio_enc
           generic map (WIDTH => WIDTH)
           port map (req => req, grant_idx => grant_idx, valid => valid);
 
       stim : process
           variable exp_idx   : integer;
           variable exp_valid : std_logic;
           variable found     : boolean;
       begin
           for code in 0 to (2**WIDTH - 1) loop            -- EXHAUSTIVE over req
               req <= std_logic_vector(to_unsigned(code, WIDTH));
               wait for 1 ns;
               -- Independent reference: lowest set bit + reduction-OR.
               exp_valid := or_reduce(req);
               exp_idx   := 0;
               found     := false;
               for i in 0 to WIDTH-1 loop
                   if req(i) = '1' and not found then
                       exp_idx := i; found := true;
                   end if;
               end loop;
               assert valid = exp_valid
                   report "prio_enc valid mismatch (valid /= |req)" severity error;
               if exp_valid = '1' then
                   assert to_integer(unsigned(grant_idx)) = exp_idx
                       report "prio_enc index mismatch (not lowest set bit)" severity error;
               end if;
           end loop;
           report "prio_enc self-check complete" severity note;
           wait;
       end process;
   end architecture;

4b. The casez / when-priority form — an explicit ordered scan

The for-loop form is compact, but the explicit priority form makes the ordering visible and is what many textbooks and legacy RTL use. In SystemVerilog and Verilog it is a casez where each pattern uses ? wildcards for the don't-care low bits, so the first matching arm wins — a literal priority cascade. Here we make it MSB-priority (highest set bit wins) to show both directions on the page; the priority casez keyword documents that the arms are checked in order.

   module prio_enc_casez #(
       parameter int WIDTH = 4                             // fixed-width illustrative form
   )(
       input  logic [WIDTH-1:0] req,
       output logic [1:0]       grant_idx,                 // MSB-priority index (highest set bit)
       output logic             valid
   );
       always_comb begin
           valid = |req;                                   // independent reduction-OR
           // priority casez: arms are checked TOP-DOWN, first match wins => MSB-priority.
           // Each ? is a don't-care, so 1??? matches any code with bit 3 set, regardless of lower bits.
           priority casez (req)
               4'b1???: grant_idx = 2'd3;                  // bit 3 set -> highest priority
               4'b01??: grant_idx = 2'd2;
               4'b001?: grant_idx = 2'd1;
               4'b0001: grant_idx = 2'd0;
               default: grant_idx = 2'd0;                  // req == 0: don't-care, valid already 0
           endcase
       end
   endmodule

The ? wildcards are the priority: 4'b1??? matches any code with bit 3 high, so a multi-hot input like 4'b1010 matches the first arm and yields index 3 (MSB-priority), never a blend. priority tells the tool the arms are ordered and that exactly one is meant to match, letting it flag overlap or a missing case. The testbench is exhaustive over the 16 codes and checks against a highest-set-bit reference plus valid == |req.

   module prio_enc_casez_tb;
       localparam int WIDTH = 4;
       logic [WIDTH-1:0] req;
       logic [1:0]       grant_idx;
       logic             valid;
       int               errors = 0;
 
       prio_enc_casez #(.WIDTH(WIDTH)) dut (.req(req), .grant_idx(grant_idx), .valid(valid));
 
       function automatic int ref_highest(input logic [WIDTH-1:0] v);
           for (int i = WIDTH-1; i >= 0; i--) if (v[i]) return i;
           return 0;
       endfunction
 
       initial begin
           for (int code = 0; code < (1 << WIDTH); code++) begin
               req = code[WIDTH-1:0];
               #1;
               assert (valid === (|req))
                   else begin $error("req=%b valid=%b exp=%b", req, valid, |req); errors++; end
               if (|req)
                   assert (grant_idx === ref_highest(req)[1:0])
                       else begin $error("req=%b idx=%0d exp=%0d", req, grant_idx, ref_highest(req)); errors++; end
           end
           if (errors == 0) $display("PASS: casez MSB-priority + valid correct on all 16 codes");
           else             $display("FAIL: %0d mismatches", errors);
           $finish;
       end
   endmodule

The Verilog casez form is identical (Verilog has casez too; there is no priority keyword, so the ordered semantics come from casez arm order alone). The self-check compares against the highest-set-bit reference.

   module prio_enc_casez #(
       parameter WIDTH = 4
   )(
       input  wire [WIDTH-1:0] req,
       output reg  [1:0]       grant_idx,
       output reg              valid
   );
       always @(*) begin
           valid = |req;                                   // independent reduction-OR
           // casez: ? is a wildcard bit; arms are matched in order, so the first
           // (highest) match wins -> MSB-priority.
           casez (req)
               4'b1???: grant_idx = 2'd3;
               4'b01??: grant_idx = 2'd2;
               4'b001?: grant_idx = 2'd1;
               4'b0001: grant_idx = 2'd0;
               default: grant_idx = 2'd0;                  // req == 0: don't-care
           endcase
       end
   endmodule

   module prio_enc_casez_tb;
       parameter WIDTH = 4;
       reg  [WIDTH-1:0] req;
       wire [1:0]       grant_idx;
       wire             valid;
       integer          code, i, exp_idx, exp_valid, errors;
       reg              found;
 
       prio_enc_casez #(.WIDTH(WIDTH)) dut (.req(req), .grant_idx(grant_idx), .valid(valid));
 
       initial begin
           errors = 0;
           for (code = 0; code < (1 << WIDTH); code = code + 1) begin
               req       = code[WIDTH-1:0];
               #1;
               exp_valid = (req != 0) ? 1 : 0;
               exp_idx   = 0;
               found     = 1'b0;
               for (i = WIDTH-1; i >= 0; i = i - 1)        // scan DOWN -> highest set bit
                   if (req[i] && !found) begin exp_idx = i; found = 1'b1; end
               if (valid !== exp_valid[0]) begin
                   $display("FAIL: req=%b valid=%b exp=%b", req, valid, exp_valid[0]);
                   errors = errors + 1;
               end
               if (exp_valid && (grant_idx !== exp_idx[1:0])) begin
                   $display("FAIL: req=%b idx=%0d exp=%0d", req, grant_idx, exp_idx);
                   errors = errors + 1;
               end
           end
           if (errors == 0) $display("PASS: casez MSB-priority + valid correct");
           else             $display("FAIL: %0d mismatches", errors);
           $finish;
       end
   endmodule

VHDL has no casez wildcard for std_logic_vector value matching, so the idiomatic explicit-priority form is a when/else chain (or an ordered if/elsif) — which is the priority cascade, checked top-down. Here the top comparison tests the highest bit, giving MSB-priority; the final else handles req = 0.

   library ieee;
   use ieee.std_logic_1164.all;
   use ieee.numeric_std.all;
   use ieee.std_logic_misc.all;
 
   entity prio_enc_casez is
       generic ( WIDTH : positive := 4 );
       port (
           req       : in  std_logic_vector(WIDTH-1 downto 0);
           grant_idx : out std_logic_vector(1 downto 0);
           valid     : out std_logic
       );
   end entity;
 
   architecture rtl of prio_enc_casez is
   begin
       valid <= or_reduce(req);                            -- independent reduction-OR
       -- when/else is an ORDERED priority chain: the first true condition wins.
       -- Testing the HIGH bit first gives MSB-priority (highest set bit).
       grant_idx <= "11" when req(3) = '1' else            -- bit 3 -> index 3
                    "10" when req(2) = '1' else            -- bit 2 -> index 2
                    "01" when req(1) = '1' else            -- bit 1 -> index 1
                    "00";                                  -- bit 0, or req = 0 (don't-care)
   end architecture;

   library ieee;
   use ieee.std_logic_1164.all;
   use ieee.numeric_std.all;
   use ieee.std_logic_misc.all;
 
   entity prio_enc_casez_tb is
   end entity;
 
   architecture sim of prio_enc_casez_tb is
       constant WIDTH : positive := 4;
       signal req       : std_logic_vector(WIDTH-1 downto 0);
       signal grant_idx : std_logic_vector(1 downto 0);
       signal valid     : std_logic;
   begin
       dut : entity work.prio_enc_casez
           generic map (WIDTH => WIDTH)
           port map (req => req, grant_idx => grant_idx, valid => valid);
 
       stim : process
           variable exp_idx   : integer;
           variable exp_valid : std_logic;
           variable found     : boolean;
       begin
           for code in 0 to (2**WIDTH - 1) loop
               req <= std_logic_vector(to_unsigned(code, WIDTH));
               wait for 1 ns;
               exp_valid := or_reduce(req);
               exp_idx   := 0;
               found     := false;
               for i in WIDTH-1 downto 0 loop              -- scan DOWN -> highest set bit
                   if req(i) = '1' and not found then
                       exp_idx := i; found := true;
                   end if;
               end loop;
               assert valid = exp_valid
                   report "casez valid mismatch (valid /= |req)" severity error;
               if exp_valid = '1' then
                   assert to_integer(unsigned(grant_idx)) = exp_idx
                       report "casez index mismatch (not highest set bit)" severity error;
               end if;
           end loop;
           report "prio_enc_casez self-check complete" severity note;
           wait;
       end process;
   end architecture;

4c. The missing-valid bug — buggy vs fixed, in all three HDLs

Pattern (c) is the signature failure, shown here as buggy vs fixed RTL in each language, then dramatized narratively in §7. The bug is the same everywhere: the encoder emits only grant_idx and drops the valid output. Now grant_idx = 0 is ambiguous — it means both "bit 0 is set" and "no bit is set, index defaulted to 0" — and any consumer that acts on the index alone will service requester 0 even when nobody asked.

   // BUGGY: emits ONLY grant_idx. When req == 0 the loop leaves grant_idx = 0,
   //        which is INDISTINGUISHABLE from "bit 0 set". The consumer cannot tell
   //        "service device 0" from "service nobody" -> phantom grant on idle.
   module prio_enc_bad #(
       parameter int WIDTH = 8,
       localparam int IDX_W = $clog2(WIDTH)
   )(
       input  logic [WIDTH-1:0] req,
       output logic [IDX_W-1:0] grant_idx                 // <-- the ONLY output: the bug
   );
       always_comb begin
           grant_idx = '0;
           for (int i = WIDTH-1; i >= 0; i--)
               if (req[i]) grant_idx = i[IDX_W-1:0];      // req==0 -> grant_idx stays 0 (looks like a grant!)
       end
   endmodule
 
   // FIXED: add the valid output as the independent reduction-OR of req.
   //        Now the consumer gates on valid and idx 0 is unambiguous.
   module prio_enc_good #(
       parameter int WIDTH = 8,
       localparam int IDX_W = $clog2(WIDTH)
   )(
       input  logic [WIDTH-1:0] req,
       output logic [IDX_W-1:0] grant_idx,
       output logic             valid                     // the output that disambiguates idx 0
   );
       always_comb begin
           grant_idx = '0;
           valid     = |req;                              // independent: 1 iff any bit set
           for (int i = WIDTH-1; i >= 0; i--)
               if (req[i]) grant_idx = i[IDX_W-1:0];
       end
   endmodule

   module prio_enc_bug_tb;
       localparam int WIDTH = 8;
       localparam int IDX_W = $clog2(WIDTH);
       logic [WIDTH-1:0] req;
       logic [IDX_W-1:0] grant_idx;
       logic             valid;
       int               errors = 0;
 
       // Bind to prio_enc_good to PASS; to _bad and there is no valid to gate on.
       prio_enc_good #(.WIDTH(WIDTH)) dut (.req(req), .grant_idx(grant_idx), .valid(valid));
 
       initial begin
           // The corner that matters most: NO request pending.
           req = '0; #1;
           // With the FIXED module, valid is the truth: nobody is asking.
           assert (valid === 1'b0)
               else begin $error("req=0 but valid=%b (phantom grant!)", valid); errors++; end
           // A real multi-hot request: lowest set bit wins, valid high.
           req = 8'b0000_1100; #1;                        // devices 2 and 3 asking
           assert (valid === 1'b1 && grant_idx === 3'd2)
               else begin $error("req=%b idx=%0d valid=%b", req, grant_idx, valid); errors++; end
           if (errors == 0) $display("PASS: valid distinguishes 'grant 0' from 'no request'");
           else             $display("FAIL: %0d mismatches (missing/none-gating valid)", errors);
           $finish;
       end
   endmodule

The Verilog buggy/fixed pair is the same story with reg outputs. The whole bug is that the buggy module has no valid port, so the zero-request case looks exactly like a grant to device 0.

   // BUGGY: only grant_idx. req == 0 yields grant_idx == 0 == "device 0 granted".
   module prio_enc_bad #(
       parameter WIDTH = 8, parameter IDX_W = 3
   )(
       input  wire [WIDTH-1:0] req,
       output reg  [IDX_W-1:0] grant_idx
   );
       integer i;
       always @(*) begin
           grant_idx = {IDX_W{1'b0}};
           for (i = WIDTH-1; i >= 0; i = i - 1)
               if (req[i]) grant_idx = i[IDX_W-1:0];      // req==0 -> stays 0 -> phantom grant
       end
   endmodule
 
   // FIXED: emit valid = |req as an INDEPENDENT output.
   module prio_enc_good #(
       parameter WIDTH = 8, parameter IDX_W = 3
   )(
       input  wire [WIDTH-1:0] req,
       output reg  [IDX_W-1:0] grant_idx,
       output reg              valid
   );
       integer i;
       always @(*) begin
           grant_idx = {IDX_W{1'b0}};
           valid     = |req;                              // independent reduction-OR
           for (i = WIDTH-1; i >= 0; i = i - 1)
               if (req[i]) grant_idx = i[IDX_W-1:0];
       end
   endmodule

   module prio_enc_bug_tb;
       parameter WIDTH = 8;
       parameter IDX_W = 3;
       reg  [WIDTH-1:0] req;
       wire [IDX_W-1:0] grant_idx;
       wire             valid;
       integer          errors;
 
       // Bind to prio_enc_good to PASS; to _bad and the valid port doesn't exist.
       prio_enc_good #(.WIDTH(WIDTH), .IDX_W(IDX_W)) dut
           (.req(req), .grant_idx(grant_idx), .valid(valid));
 
       initial begin
           errors = 0;
           req = 8'b0000_0000; #1;                        // NO request pending
           if (valid !== 1'b0) begin
               $display("FAIL: req=0 but valid=%b (phantom grant on idle)", valid);
               errors = errors + 1;
           end
           req = 8'b0000_1100; #1;                        // devices 2,3 -> lowest wins (idx 2)
           if (!(valid === 1'b1 && grant_idx === 3'd2)) begin
               $display("FAIL: req=%b idx=%0d valid=%b", req, grant_idx, valid);
               errors = errors + 1;
           end
           if (errors == 0) $display("PASS: valid disambiguates grant-0 vs no-request");
           else             $display("FAIL: %0d mismatches", errors);
           $finish;
       end
   endmodule

In VHDL the same bug is an entity whose port list omits valid. The or_reduce(req) output is what the fixed version adds; without it, grant_idx = "000" on an all-zero req is read downstream as a legitimate grant to requester 0.

   library ieee;
   use ieee.std_logic_1164.all;
   use ieee.numeric_std.all;
   use ieee.std_logic_misc.all;
 
   -- BUGGY: no valid port. req all-zero -> grant_idx = "000", read as "grant device 0".
   entity prio_enc_bad is
       generic ( WIDTH : positive := 8 );
       port (
           req       : in  std_logic_vector(WIDTH-1 downto 0);
           grant_idx : out std_logic_vector(2 downto 0)
       );
   end entity;
   architecture rtl of prio_enc_bad is
   begin
       process (all)
           variable idx : unsigned(2 downto 0);
       begin
           idx := (others => '0');
           for i in WIDTH-1 downto 0 loop
               if req(i) = '1' then idx := to_unsigned(i, 3); end if;   -- req=0 -> stays 0
           end loop;
           grant_idx <= std_logic_vector(idx);
       end process;
   end architecture;
 
   -- FIXED: add the valid output as the independent reduction-OR of req.
   entity prio_enc_good is
       generic ( WIDTH : positive := 8 );
       port (
           req       : in  std_logic_vector(WIDTH-1 downto 0);
           grant_idx : out std_logic_vector(2 downto 0);
           valid     : out std_logic                       -- disambiguates idx 0
       );
   end entity;
   architecture rtl of prio_enc_good is
   begin
       valid <= or_reduce(req);                            -- independent: '1' iff any bit set
       process (all)
           variable idx : unsigned(2 downto 0);
       begin
           idx := (others => '0');
           for i in WIDTH-1 downto 0 loop
               if req(i) = '1' then idx := to_unsigned(i, 3); end if;
           end loop;
           grant_idx <= std_logic_vector(idx);
       end process;
   end architecture;

   library ieee;
   use ieee.std_logic_1164.all;
   use ieee.numeric_std.all;
   use ieee.std_logic_misc.all;
 
   entity prio_enc_bug_tb is
   end entity;
 
   architecture sim of prio_enc_bug_tb is
       constant WIDTH : positive := 8;
       signal req       : std_logic_vector(WIDTH-1 downto 0);
       signal grant_idx : std_logic_vector(2 downto 0);
       signal valid     : std_logic;
   begin
       -- Bind to prio_enc_good to PASS; the buggy entity has no valid port to bind.
       dut : entity work.prio_enc_good
           generic map (WIDTH => WIDTH)
           port map (req => req, grant_idx => grant_idx, valid => valid);
 
       stim : process
       begin
           req <= (others => '0');                          -- NO request pending
           wait for 1 ns;
           assert valid = '0'
               report "req=0 but valid='1' (phantom grant on idle)" severity error;
           req <= "00001100";                               -- devices 2,3 -> lowest wins
           wait for 1 ns;
           assert valid = '1' and to_integer(unsigned(grant_idx)) = 2
               report "multi-hot: expected valid=1, idx=2" severity error;
           report "prio_enc_bug self-check complete" severity note;
           wait;
       end process;
   end architecture;

Across all three languages the lesson is one sentence: a priority encoder has two outputs, and the valid bit — the independent reduction-OR of the request vector — is what keeps index 0 from meaning two different things.

5. Verification Strategy

A priority encoder is combinational, so its correctness is a truth table over the request vector, and for a small WIDTH that table is small enough to check exhaustively. Two invariants together capture a correct priority encoder:

(1) When any request bit is set, grant_idx is the index of the highest-priority set bit (by the documented direction). (2) valid equals the reduction-OR of the whole request vector — and when req == 0, valid is 0 and the index is a don't-care.

Everything below is those two invariants, made checkable, and it maps directly onto the testbenches in §4.

• Exhaustive req sweep (self-checking). For a WIDTH-bit encoder, drive every code from 0 to 2**WIDTH - 1 and, for each, assert both invariants against an independent reference model. The reference computes the first-set-bit index (scanning in the documented direction) and |req separately from the DUT — never by reading the DUT's own outputs. Because there are only 2**WIDTH codes, this is complete for a small width, not sampled. The three prio_enc testbenches in §4a do exactly this: SV assert (grant_idx === ref_lowest(req)), Verilog if (grant_idx !== exp_idx) $display("FAIL…"), VHDL assert to_integer(unsigned(grant_idx)) = exp_idx report … severity error.
• The valid == |req invariant, checked independently. State it as a property that holds every evaluation: valid is exactly the reduction-OR of req. The critical discipline is that the testbench computes the expected valid from req directly (|req), not from grant_idx, so a design that (wrongly) derives valid from the index cannot pass by accident. This is the invariant the whole page turns on.
• The zero-input corner. Drive req = 0 explicitly and assert valid == 0. This single directed case is the one the missing-valid bug (§4c, §7) fails: a buggy encoder returns grant_idx = 0 with no way to say "nobody asked," so the test that valid is low on an idle vector is the test that catches the phantom grant. Always test the all-zero vector as a named corner, not just as one code in the sweep.
• The priority-direction check (single-bit and adjacent-bit cases). Verify the ordering deliberately: drive each single-bit vector (req = 1 << k for every k) and confirm grant_idx == k — this proves the encoder is a correct plain encoder on one-hot inputs. Then drive adjacent multi-hot pairs (req with bits k and k+1 both set) and confirm the winner is the one your documented direction says — the lower index for LSB-priority, the higher for MSB-priority. Adjacent pairs are where an off-by-one or inconsistent-direction bug shows up.
• The all-bits and single-bit extremes. Drive req = all-ones (every device asking at once — the maximum-contention case) and confirm the top-priority index wins and valid == 1; drive each single set bit as above. These extremes bound the behaviour: exactly one winner even when everyone asks, and a clean pass-through when only one asks.
• Parameter-generic verification (WIDTH = 4, 8, 16). A parameterized encoder must be verified generic, not assumed generic. Re-run the exhaustive sweep for small widths and, for large WIDTH where 2**WIDTH is too big to enumerate, switch to assertion-based random testing: drive random req, and on every cycle assert the two invariants against the reference model. A form that passes at WIDTH=4 can still be wrong at a non-power-of-two width or when the index output is too narrow — the reference-model check catches both.
• Expected waveform. Because a priority encoder has no clock, "correct" on a waveform is immediate: as req changes, valid tracks |req combinationally (high whenever any bit is set, low only on the all-zero vector), and grant_idx tracks the first-set-bit index in the documented direction. The visual signature of the missing-valid bug is grant_idx sitting at 0 on an idle (req == 0) bus with no valid line to tell you it is meaningless — a downstream block reading that as a grant is the §7 failure.

6. Common Mistakes

No valid output → index 0 is ambiguous. The signature priority-encoder bug. If the encoder emits only grant_idx, then grant_idx = 0 means both "bit 0 is set" and "no bit is set and the index defaulted to 0." A consumer cannot tell "service requester 0" from "service nobody," so on an idle bus it services a phantom requester 0 every cycle. The fix is structural: emit valid as the independent reduction-OR of the request vector (valid = |req), and require every consumer to gate on it. (Full post-mortem in §7; buggy-vs-fixed RTL for all three HDLs in §4c.)

Deriving valid from the index instead of from req. A subtler version of the above: the encoder has a valid output but computes it wrongly — e.g. valid = (grant_idx != 0), or valid = |grant_idx. That is broken twice over: it reports valid = 0 when bit 0 is legitimately set (a real request to requester 0 is dropped), and it can report valid = 1 on a stale index. valid must be the reduction-OR of req itself, computed independently of the scan, so it is true if and only if some request bit is high.

Wrong or inconsistent priority direction. Choosing MSB-priority in the encoder but LSB-priority in the reference model, or in the arbiter that consumes it, silently grants the wrong requester. Both directions are legal, but a design must pick one, document it in the RTL, and verify against it consistently. The classic bug is an encoder that scans low-to-high while the spec says "highest line is highest priority" — it passes single-bit tests and fails only on multi-hot inputs, exactly where it matters. Test adjacent-bit pairs to catch it.

A long priority chain as the critical path. Writing a wide priority encoder as a literal if / else if / else if … (or when/else) chain synthesizes to a priority cascade whose delay grows with the number of requesters. On a narrow vector this is fine and readable; on a 64- or 128-wide request vector it becomes the critical path — the lowest-priority branch sits behind every earlier comparison. When timing bites, restructure the same priority as a log2(WIDTH)-deep balanced tree (or use the isolate-lowest-set-bit trick x & (~x + 1) to produce a one-hot winner in constant logic, then encode it), so the delay grows logarithmically instead of linearly.

A latch from an incompletely-specified branch. Like any combinational block, a priority encoder must assign every output on every path. If the scan is written as a bare case/if that leaves grant_idx (or valid) unassigned on some input — for example a casez with no default and an input that matches no arm — the tool infers a latch that holds the stale index. Default-assign both outputs at the top of the block (grant_idx = 0; valid = |req; first, then override), so no input can leave either output undriven. This is the same latch-inference discipline as the mux (1.1), applied to two outputs at once.

Feeding a multi-hot vector to a plain encoder. The mistake that motivates this whole page: using the cheap OR-tree plain encoder (1.3) on a request vector that can be multi-hot. It does not error — it silently ORs the set indices and points at a requester that is not asking. If the input can ever have more than one bit set, you need a priority encoder, not a plain one. The tell is a design that works in unit tests (one request at a time) and produces impossible grants under load (many requests at once).

7. DebugLab

The engineering lesson: a priority encoder's answer has two halves — the winning index and whether there was any winner — and shipping only the index makes value 0 mean both "requester zero" and "nobody," an ambiguity that surfaces exactly when the bus goes idle. The tell is a grant that fires when nothing is requesting: a "who won?" answer with no "did anyone ask?" companion will always mistake the idle case for a grant to requester 0. Two habits make it impossible, and they are identical across SystemVerilog, Verilog, and VHDL: always emit valid as the independent reduction-OR of the request vector (never derive it from the index), and always drive the all-zero req corner in verification asserting valid == 0, because that is the one case the naive one-request-at-a-time unit test skips.

8. Interview Q&A

9. Exercises

Design and reasoning exercises — no syntax drills. Each rehearses the "which first, and any at all?" habit.

Exercise 1 — Diagnose the phantom grant

An interrupt controller's priority encoder emits only grant_idx (no valid), and downstream logic computes irq_vector = base + (grant_idx << 2) unconditionally. In one paragraph, explain (i) exactly what the system does when the request vector is all zeros and why, (ii) why the bug is invisible in a unit test that always drives at least one request, and (iii) the two-part fix (the RTL change and the consumer change). Then state the single directed test case that would have caught it.

Exercise 2 — Pick and defend a priority direction

For each block, state whether you'd use MSB-priority or LSB-priority, and defend it in one line: (a) an interrupt controller where a higher line number means a more urgent device; (b) a free-list allocator returning the first free slot in a bitmap; (c) a fixed-priority bus arbiter where master 0 is the CPU and must always win when it requests; (d) a leading-zero counter for a floating-point normalizer. Then explain why testing only single-bit vectors would fail to catch a wrong choice, and what multi-bit test would catch it.

Exercise 3 — Predict the hardware, then the timing

Two engineers implement the same 32-bit priority encoder. Engineer A writes a casez with 32 ordered arms (a priority chain). Engineer B computes onehot = req & (~req + 1) and encodes that one-hot mask with an OR-tree. Both produce the same grant_idx on every input. Describe (i) how the synthesized delay differs and how each scales with WIDTH, (ii) which one you'd choose if this encoder is on the critical path of a 64-requester arbiter and why, and (iii) which priority direction each implementation naturally produces.

Exercise 4 — Prove it correct on paper

You must verify a parameterized WIDTH-bit LSB-priority encoder with a self-checking testbench. State (i) the two invariants the testbench must assert every cycle and how the reference model computes each independently of the DUT, (ii) why the req == 0 corner must be a named directed case rather than just one code in an exhaustive sweep, and (iii) what you switch to when WIDTH = 32 makes an exhaustive 2**WIDTH sweep infeasible, and what you check on each random vector.

10. Related Tutorials

Continue in RTL Design Patterns (sibling and forward links unlock as they ship):

• Encoders — Chapter 1.3; the plain (one-hot → index) encoder whose multi-hot failure this page fixes — read it first if the OR-tree encoder is unfamiliar.
• Decoders — Chapter 1.2; the inverse operation (index → one-hot) — a decoder on this page's grant_idx turns the priority encoder into a one-hot grant, i.e. a fixed-priority arbiter.
• Fixed-Priority Arbiter — Chapter 10; the direct application — a priority encoder whose winner is expressed as a one-hot grant, with the masking that leads to round-robin.
• FSM Fundamentals — Chapter 4.1; where priority resolution over conditions reappears as next-state selection and where a one-hot state feeds the encoders and muxes of this chapter.

Backward / method:

• Multiplexers (2:1, N:1, one-hot) — Chapter 1.1; the same latch-inference discipline (default-assign every output on every path) applied here to two outputs at once, and the mux a priority encoder's index typically drives.
• The RTL Design Mindset — Chapter 0.2; the Interface → State → Datapath → Control → Verification lenses this page applied to the encoder (pure datapath, two outputs, no state).
• What Is an RTL Design Pattern? — Chapter 0.1; why the priority encoder earns the name "pattern" — a recurring contention problem, a reusable (index, valid) form, a synthesis reality, and a signature failure.

Verilog v1 prerequisites (the grammar this pattern transcribes into):

• Case Statements — the construct behind the casez/priority explicit-priority form, and where wildcard matching and latch inference live.
• Continuous Assignments — the assign / dataflow form of valid = |req and the when/else priority chain, driven on every path.
• The Conditional (? :) Operator — the ternary that expresses each stage of a priority cascade directly.
• Blocking and Non-Blocking Assignments — why this combinational encoder uses blocking (=) in its always @(*), and how that differs from the clocked patterns ahead.
• Generate Blocks — the elaboration-time replication used to build a wide priority tree or a parameterized find-first scan.
• Parameters — the WIDTH / IDX_W parameterization that makes one encoder serve any request-vector width.

11. Summary

• A priority encoder answers two questions at once. Given a multi-hot request vector, it returns which is the highest-priority set bit (grant_idx) and whether any bit is set (valid). It is the fix for the plain encoder's fatal assumption that its input is one-hot — real request vectors (interrupts, arbiter requests, free-lists) are not.
• The valid bit is half the answer, not an optional extra. valid == |req, computed independently of the index. Without it, grant_idx = 0 is ambiguous between "bit 0 set" and "nothing set" — the signature bug (§7) where an idle bus produces a phantom grant to requester 0.
• Priority direction is a documented choice. MSB-priority (highest set bit) or LSB-priority (lowest set bit) — both legal; pick one, state it in the RTL, and verify against it consistently. Inconsistency passes single-bit tests and fails on the multi-hot inputs the encoder exists for.
• "First set bit" is a scan, and how you scan sets the timing. An if / else if (or casez, or when/else) chain is a priority cascade with delay ~WIDTH; the same priority as a balanced tree — or the isolate-lowest-set-bit trick x & (~x + 1) — is log2(WIDTH) deep. Same winner, different hardware.
• Default-assign both outputs, and verify exhaustively — in every HDL. Assign grant_idx and valid on every path (else a latch), compute valid as the reduction-OR of req (never from the index), sweep every req code against an independent reference, and drive the all-zero corner asserting valid == 0 — self-checking testbenches shown here in SystemVerilog, Verilog, and VHDL. The priority encoder built this way is the direct core of the fixed-priority arbiter ahead.