Digital Design / Module 2: Combinational building blocks
7. Decoders and priority encoders
Translate between binary codes and one-hot lines.
See it move
The idea
A decoder and an encoder translate between compact binary and lines. A decoder takes an N-bit number and raises exactly one of 2^N outputs. An encoder does the reverse.
Decoders are everywhere: picking one memory row, one register in a register file, or one peripheral on a bus.
Why an encoder needs a valid flag
A plain 8-to-3 encoder gives 000 when input 0 is active, and also when nothing is active. To tell these apart it needs a separate valid output. When valid is 0, the code must be ignored.
Priority encoders
Real request lines can be high together, so a priority encoder defines a winner: usually the highest-numbered active input. and interrupt controllers use this.
always @(*) begin
valid = 1'b1;
casez (req)
8'b1???????: code = 3'd7;
8'b01??????: code = 3'd6;
8'b001?????: code = 3'd5;
8'b0001????: code = 3'd4;
8'b00001???: code = 3'd3;
8'b000001??: code = 3'd2;
8'b0000001?: code = 3'd1;
8'b00000001: code = 3'd0;
default: begin code = 3'd0; valid = 1'b0; end
endcase
endCommon mistake
Using the code output without checking valid. A design may treat "no request" as "request 0" and service a client that never asked. Also note that a fixed priority encoder can starve low-priority inputs. The Arbiters lesson deals with that.
Key ideas
- A decoder raises exactly one of 2^N lines.
- An encoder needs a valid output, because all-zero input is otherwise ambiguous.
- Priority encoders resolve several active requests.
Your exercise
Find the bug
This code has one deliberate bug. Read the symptom, then click the line you think is wrong.
The fix
assign valid = |req;
Why it failed
&req is high only when every bit is high, which answers "all". |req answers "any". The code output was fine, so a test that only checked the code would never notice.
Interview questions
coreWhat does a priority encoder do when no input is active?
It deasserts valid, and the encoded output should be ignored.
basicHow many outputs does a 4-to-16 decoder have, and how many of them are high at once when it is enabled?
It has 2^4 = 16 outputs, one for each input code. Exactly one is high at a time, the one whose index equals the input. With the enable off, all outputs are low.
basicWhat does this one-line decoder produce when a is 5?
wire [2:0] a; wire [7:0] y = 8'b1 << a;
Shifting a single 1 left by 5 places gives 8'b0010_0000: bit 5 is high and every other bit is low. The shift places the one high line at the position named by the code, which is exactly a 3-to-8 decoder.
coreHow can a 3-to-8 decoder plus one OR gate implement any 3-input function? Show it for majority.
Each decoder output is high for exactly one input pattern, so each one is a minterm. ORing the outputs for the rows where the function is 1 gives the function. Majority is 1 for patterns 3, 5, 6 and 7, so OR those four outputs.
coreBuild a 4-to-16 decoder from 2-to-4 decoders that have an enable input. How many do you need, and how are they wired?
Five. One decoder takes the top two address bits and drives the enables of four more. Each of those four takes the bottom two bits and produces four of the sixteen outputs. Only the enabled one has a high output, so exactly one line is up overall.
coreThis 4-input priority encoder uses ? in its patterns, but with req = 1010 it reports valid = 0. Why?
case (req) 4'b1???: code = 2'd3; 4'b01??: code = 2'd2; 4'b001?: code = 2'd1; 4'b0001: code = 2'd0; default: begin code = 2'd0; valid = 1'b0; end endcase
In a plain case, ? is just another way of writing z, and a pattern bit is only matched by a z on the same bit of req. So 1??? matches only a value like 1zzz, and 1010 falls through to the default. Use casez, where z and ? bits in the pattern are treated as don't-cares.
coreIn this loop-based priority encoder, req = 8'b0010_0100. Which index is reported, and why?
always @(*) begin
code = 3'd0; valid = 1'b0;
for (i = 0; i < 8; i = i + 1)
if (req[i]) begin code = i; valid = 1'b1; end
endIt reports 5. The loop unrolls into a chain where every later iteration can overwrite earlier ones, and it runs from 0 to 7, so the highest active index assigned last wins. Bits 2 and 5 are set, and 5 is written after 2. Reversing the loop direction would make the lowest index win instead.
advancedWhat does req & (~req + 1) produce, and where is it useful? Try req = 8'b0110_1000.
wire [7:0] req; wire [7:0] grant = req & (~req + 8'd1);
~req + 1 is the two's complement negative of req. Every bit above the lowest 1 is inverted relative to req, the lowest 1 itself survives, and the bits below it are 0, so the AND keeps only the lowest set bit. For 0110_1000 it gives 0000_1000. It is a compact one-hot grant for a lowest-index-wins priority scheme, and it gives all zeros when nothing is requested.
advancedA plain 8-to-3 encoder is built from OR gates: each code bit is the OR of the input lines whose index has that bit set. What does it output if lines 1 and 2 are both high?
Line 1 sets code bit 0 and line 2 sets code bit 1, so the output is 011, which is 3: a line that is not active at all. A plain encoder assumes its input is one-hot, and when that fails it gives the OR of the codes. That is why real request lines go through a priority encoder.