Encoders and Priority Encoders

Turn one active line into its number, and decide what happens when several lines are active at once.

You Will Be Able To

  • Build a binary encoder for one-hot inputs.
  • Explain what a plain encoder outputs when two inputs are active.
  • Write a priority encoder with a valid output using casez or an if chain.
  • Use a priority encoder to find the leading 1 of a word.
Lesson
G4.4
Time
25 min
Runs on
Your browser
Check
5 questions

A small interrupt controller turns four request lines into a 2-bit device number. Its encoder was written for one request at a time. One day devices 1 and 2 raise their requests together. The CPU reads device 3, which never asked.

A Plain Encoder Meets Two RequestsOne request pattern per step, req written as req3 req2 req1 req0.
0123req0010010001100000code1230two requests: code 3no request: code 0
Scroll horizontally ↔
  1. Cycle 0

    Device 1 alone. Code bit 0 is req3 OR req1, so the code is 1. Correct.

  2. Cycle 1

    Device 2 alone. Code bit 1 is req3 OR req2, so the code is 2. Correct.

  3. Cycle 2

    Devices 1 and 2 together. Both code bits are 1, and the CPU reads device 3.

  4. Cycle 3

    No request gives code 0, the same as a request from device 0.

Measured on the simulator. Each code bit is an OR of the inputs whose number has that bit set.

One-Hot to Binary

An encoder does the reverse of a decoder. It has 2^n inputs, of which one is 1, and outputs that input's number in n bits.

Code bit j is 1 for every input whose number has bit j set. So each code bit is an OR. For four inputs, code[1] = d3 + d2 and code[0] = d3 + d1. Input d0 drives no gate at all.

A 4-to-2 Encoder With Don't-Cares
d3d2d1d0y1y0
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111

Each output alone

  • y1 = ~d1 & ~d0
  • y0 = ~d2 & ~d0

2 terms · 4 literals

Shared product terms

  • y1 = ~d1 & ~d0
  • y0 = ~d2 & ~d0

2 distinct terms · 4 literals. No term helps more than one output here.

A 4-to-2 Encoder With Don't-Caresg0 · NOTinv_d1=1g1 · NOTinv_d0=1g2 · ANDt0=1g3 · NOTinv_d2=1g4 · ANDt1=1g5 · BUFy1=1g6 · BUFy0=1d3=0d2=0d1=0d0=0
d3=0 d2=0 d1=0 d0=0
g0 · NOTd1=0 → inv_d1=1
g1 · NOTd0=0 → inv_d0=1
g2 · ANDinv_d1=1, inv_d0=1 → t0=1
g3 · NOTd2=0 → inv_d2=1
g4 · ANDinv_d2=1, inv_d0=1 → t1=1
g5 · BUFt0=1 → y1=1
g6 · BUFt1=1 → y0=1
Read the connections
GateKindInputsOutput
g0NOTd1inv_d1
g1NOTd0inv_d0
g2ANDinv_d1, inv_d0t0
g3NOTd2inv_d2
g4ANDinv_d2, inv_d0t1
g5BUFt0y1
g6BUFt1y0

Outputs: y1, y0. MUX inputs: d0, d1, select. Latch/flip-flop inputs: data, enable/clock. Unknown values are marked x; high impedance is folded into x in this model.

Only the one-hot rows are specified. Every other row is a don't-care, and the minimum is two OR gates.

The encoder is small only because the other rows were left as don't-cares. The hook shows what those rows really give.

Priority and the Valid Output

A priority encoder outputs the number of the highest-priority active input. Here the highest number wins. Lower inputs are ignored while a higher one is active.

A valid output says whether any input is active. It is the OR of all the inputs. Without it, code 0 could mean "input 0" or "nothing".

A Priority Encoder in an Interrupt ControllerArrows show signals. Four request lines enter the encoder. The CPU reads the code only when valid is 1.
  • I/O
  • Datapath
  • Processor
  • Interrupt
  • Data
  • Control
CallValueReturnWaiting
A priority encoder in an interrupt controllerArrows show signals. Four request lines enter the encoder. The CPU reads the code only when valid is 1. io Requests req3 to req0 datapath Priority encoder highest wins io code 2 bits io valid any request processor CPU serves one device request linesnumberOR of allwhich deviceinterrupt
  1. io Requestsreq3 to req0
    • request lines → Priority encoder
  2. datapath Priority encoderhighest wins
    • number → code
    • OR of all → valid
  3. io code2 bits
    • which device → CPU
  4. io validany request
    • interrupt → CPU
  5. processor CPUserves one device
  1. Two requests

    Devices 2 and 1 ask. The encoder ignores device 1 while device 2 asks.

    Follow the calls, values and waits
    1. data 0110: Requests → Priority encoder
  2. Code and valid

    code = 2 and valid = 1. The CPU serves device 2 first; device 1 waits.

    Follow the calls, values and waits
    1. data code 2: code → CPU
    2. data valid 1: valid → CPU
  3. No request

    With no request, valid = 0. The code is 0, but the CPU does not read it.

    Follow the calls, values and waits
    1. data 0000: Requests → Priority encoder
    2. data valid 0: valid → CPU
Read the diagram as text
  • Requests: req3 to req0
  • Priority encoder: highest wins
  • code: 2 bits
  • valid: any request
  • CPU: serves one device
  • Requests → Priority encoder: request lines
  • Priority encoder → code: number
  • Priority encoder → valid: OR of all
  • code → CPU: which device
  • valid → CPU: interrupt

valid gates the code. Device 1 is served once device 2 drops its request.

d3 d2 d1 d0codevalid
1 X X X31
0 1 X X21
0 0 1 X11
0 0 0 101
0 0 0 000

A 4-input priority encoder. X means "either value". Five rows cover all sixteen input patterns.

The Lab Encoder on Several Requests at OnceOne request pattern per step, req7 on the left.
012345req000001000010010011111111000000010000000000010011code25704validtwo requestsnone
Scroll horizontally ↔
  1. Cycle 1

    Requests 5 and 2 are both active. The higher one, 5, wins.

  2. Cycle 2

    All eight are active, and the code is 7.

  3. Cycle 4

    No request: valid falls to 0. The code is 0 but means nothing.

The lines printed by the lab below, measured on the simulator.

Casez Against an If Chain

Both forms describe priority. In a casez, a ? in a pattern matches 0 or 1, and the first matching arm wins. In an if chain, the first true test wins.

An if chain

always_comb begin
  valid = 1'b1;
  if      (req[7]) code = 3'd7;
  else if (req[6]) code = 3'd6;
  else if (req[5]) code = 3'd5;
  else if (req[4]) code = 3'd4;
  else if (req[3]) code = 3'd3;
  else if (req[2]) code = 3'd2;
  else if (req[1]) code = 3'd1;
  else begin
    code  = 3'd0;
    valid = req[0];
  end
end

Synthesized on this site: 15 cells, 6 logic levels.

A loop: the last match wins

always_comb begin
  code  = 3'd0;
  valid = 1'b0;
  for (int i = 0; i < 8; i++)
    if (req[i]) begin            // a later (higher) i overwrites an earlier one
      code  = 3'(i);
      valid = 1'b1;
    end
end

The same function on all 256 inputs: 18 cells, 4 logic levels.

The casez of the lab gives 17 cells and 4 levels. All three forms are the same function, checked on all 256 inputs, yet the tool built them differently.

The if chain kept more of its chain shape: fewer cells, more levels. Do not read a form as a promise of a structure. Write the clearest form, then let Synthesize show the cost.

The loop form scales to any width. It visits the bits from low to high, and each later match overwrites the earlier one, so the highest 1 wins.

Finding the Leading One

A priority encoder over a whole word finds the position of its highest 1, the leading one. A floating-point adder uses it to normalize a result. A divider uses it to align the operands.

Asked in interviews
  1. What goes wrong when two inputs of a plain encoder are active?

    The code bits of both inputs are ORed. Inputs 1 and 2 give code 3. A plain encoder is only correct for one-hot inputs.

  2. Why does a priority encoder need a valid output?

    Code 0 means "input 0 is active", but also comes out when nothing is active. Valid, the OR of all inputs, tells the two apart.

  3. casez or casex?

    Prefer casez. It treats z and ? as don't-cares, in the input and in the patterns. casex treats x the same way. Then an unknown input can match an arm and hide a bug.

Try It

With several requests the highest one wins: 00100100 gives 5 and 00010011 gives 4. With none, valid is 0.

Swap the order of the arms so that 8'b00000001 comes first, and run. Nothing changes: the patterns do not overlap, so the order of arms does not matter here.

Now make the lowest request win: write the patterns with the ? marks on the left, such as 8'b???????1 for code 0. Predict the line for 00100100 before you run.

Press Synthesize and compare the cells and levels with the two other forms above.

RTLIcarus Verilog · in your browser · Lint: Verilator service · Synthesize: Yosys service
Edit the design, then Run, Lint or Synthesize
Expected: req=00000100 code=2 valid=1 req=00100100 code=5 valid=1 req=11111111 code=7 valid=1 req=00000001 code=0 valid=1 req=00000000 code=0 valid=0 req=00010011 code=4 valid=1

Original design · 17 cells · 0 flip-flops · 0 latches · 4 logic levels. Synthesis uses Yosys; counts depend on the toolchain.

Read included file: tb.sv
// tb.sv: a few request patterns, including several requests at once (read-only).
module tb;
  logic [7:0] req;
  logic [2:0] code;
  logic       valid;
  prio8 dut (.req(req), .code(code), .valid(valid));
  task automatic show(input logic [7:0] pattern);
    req = pattern;
    #1 $display("req=%b code=%0d valid=%b", req, code, valid);
  endtask
  initial begin
    show(8'b0000_0100);
    show(8'b0010_0100);            // two requests
    show(8'b1111_1111);            // all eight
    show(8'b0000_0001);
    show(8'b0000_0000);            // none
    show(8'b0001_0011);
  end
endmodule

Check Yourself

Spot the bugEach option is the body of an always_comb block of a 4-input priority encoder (highest wins, valid = 1 when any input is active). The bench tries all 16 rows. Which body fails?
ConceptAn 8-input priority encoder (highest wins) sees 0100_1010. What are code and valid?
ConceptHow many outputs, counting valid, does a priority encoder with 16 inputs have?
ConceptWhy is casez safer than casex for a priority encoder?
Predict the outputA plain 4-to-2 OR encoder sees 1001. Predict the exact line.
module tb;
  logic [3:0] d = 4'b1001;
  initial $display("%b", {d[3] | d[2], d[3] | d[1]});
endmodule

Common Mistakes

Wrong Use a plain OR encoder where more than one input can be active.

The code bits of two inputs are ORed together. Requests 1 and 2 give code 3, a device that never asked.

Fix Use a priority encoder whenever the inputs are not guaranteed to be one-hot.

Wrong Leave out the valid output.

Without it, "input 0 is active" and "nothing is active" both give code 0.

Fix Add valid = 1 when any input is active, and read the code only when valid is 1.

Wrong Write the priority in the wrong direction.

An if chain tests in order, so the first test wins. Starting from bit 0 makes the lowest input win.

Fix Put the input with the highest priority first in the chain or the casez list.

Wrong Use casex to get don't-cares.

casex treats an x on the input as a don't-care, as well as z. An unknown input line then matches an arm and hides the fault.

Fix Use casez with ?. It ignores the bits you mark and any z, but an x on the input matches no 0 or 1.

Before
casex (req)
  8'b1xxxxxxx: code = 3'd7;
After
casez (req)
  8'b1???????: code = 3'd7;

Remember

  • An encoder outputs the number of its one active input; each code bit is an OR.
  • Two active inputs make a plain encoder OR their codes together.
  • A priority encoder outputs the highest-priority active input, with valid = OR of all inputs.
  • casez with ? and an if chain both express priority; avoid casex.
  • A priority encoder over a word finds its leading 1.

Practice

Report a problem with this page