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
casezor anifchain. - 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.
- Cycle 0
Device 1 alone. Code bit 0 is req3 OR req1, so the code is 1. Correct.
- Cycle 1
Device 2 alone. Code bit 1 is req3 OR req2, so the code is 2. Correct.
- Cycle 2
Devices 1 and 2 together. Both code bits are 1, and the CPU reads device 3.
- 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.
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".
- I/O
- Datapath
- Processor
- Interrupt
- Data
- Control
- Two requests
Devices 2 and 1 ask. The encoder ignores device 1 while device 2 asks.
Follow the calls, values and waits
- data 0110: Requests → Priority encoder
- Code and valid
code = 2 and valid = 1. The CPU serves device 2 first; device 1 waits.
Follow the calls, values and waits
- data code 2: code → CPU
- data valid 1: valid → CPU
- No request
With no request, valid = 0. The code is 0, but the CPU does not read it.
Follow the calls, values and waits
- data 0000: Requests → Priority encoder
- 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 d0 | code | valid |
|---|---|---|
| 1 X X X | 3 | 1 |
| 0 1 X X | 2 | 1 |
| 0 0 1 X | 1 | 1 |
| 0 0 0 1 | 0 | 1 |
| 0 0 0 0 | 0 | 0 |
A 4-input priority encoder. X means "either value". Five rows cover all sixteen input patterns.
- Cycle 1
Requests 5 and 2 are both active. The higher one, 5, wins.
- Cycle 2
All eight are active, and the code is 7.
- 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
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.
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.
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.
Synthesize the design to measure its cells and inspect the mapped gates.
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=1Original 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
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.
casex (req)
8'b1xxxxxxx: code = 3'd7;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.