G4.4.1 Four-Input Priority Encoder

EasyImplementIcarus Verilog + Yosys · serverReview the topic

Encode four active-low request lines: the highest request wins, valid says any request, more says several.

Hardware context: An interrupt line shared by four sensors, and a box of old priority encoders to sort. Encode four active-low request lines with valid and more outputs.

Four sensors share one interrupt line to a small processor. Each sensor pulls its own request line low when it needs service. Several may ask at once. The processor serves the highest-numbered sensor first and must know when others are still waiting.

This is an Implement problem. Write prio4n. code is the number of the highest-numbered device that asks, and 0 when nobody asks. valid is 1 when any device asks. more is 1 when two or more devices ask at once.

The check applies eight request patterns, one per nanosecond, and records code, valid and more after each. The check also synthesizes the module on the site's flow and rejects any latch.

Signals in the Timeline

SignalWidthRole
script32input of each check
Full specification
The module (keep the name and the ports)
module prio4n (
  input  logic [3:0] req_n,     // active-low requests: req_n[k] = 0 means device k asks
  output logic [1:0] code,      // the highest-numbered device that asks; 0 when none asks
  output logic       valid,     // 1 when at least one device asks
  output logic       more       // 1 when two or more devices ask at once
);
  // your design
endmodule
Devices askingcodevalidmore
none000
exactly one, device kk10
two or more; the highest is device kk11

The result fields are code_stepK, valid_stepK and more_stepK for the steps 0 to 7. Device k asks when req_n[k] is 0.

Examples

Example 1

One Device at a Time, and Nobody
Input
req_n=1110 (devices 0 ask); req_n=1101 (devices 1 ask); req_n=1011 (devices 2 ask); req_n=0111 (devices 3 ask); req_n=1111 (nobody asks); req_n=0111 (devices 3 ask); req_n=1011 (devices 2 ask); req_n=1111 (nobody asks)
Output
code_step0 = 0, valid_step0 = yes, more_step0 = no, code_step1 = 1, valid_step1 = yes, more_step1 = no, code_step2 = 2, valid_step2 = yes, more_step2 = no, code_step3 = 3, valid_step3 = yes, more_step3 = no, code_step4 = 0, valid_step4 = no, more_step4 = no, code_step5 = 3, valid_step5 = yes, more_step5 = no, code_step6 = 2, valid_step6 = yes, more_step6 = no, code_step7 = 0, valid_step7 = no, more_step7 = no

A single request gives its own number, valid 1 and more 0. With nobody asking, all three outputs are 0.

Example 2

Two Devices at Once
Input
req_n=1100 (devices 0, 1 ask); req_n=1010 (devices 0, 2 ask); req_n=1001 (devices 1, 2 ask); req_n=0110 (devices 0, 3 ask); req_n=0101 (devices 1, 3 ask); req_n=0011 (devices 2, 3 ask); req_n=1111 (nobody asks); req_n=1110 (devices 0 ask)
Output
code_step0 = 1, valid_step0 = yes, more_step0 = yes, code_step1 = 2, valid_step1 = yes, more_step1 = yes, code_step2 = 2, valid_step2 = yes, more_step2 = yes, code_step3 = 3, valid_step3 = yes, more_step3 = yes, code_step4 = 3, valid_step4 = yes, more_step4 = yes, code_step5 = 3, valid_step5 = yes, more_step5 = yes, code_step6 = 0, valid_step6 = no, more_step6 = no, code_step7 = 0, valid_step7 = yes, more_step7 = no

The higher-numbered device wins, and more is 1 because another device is still waiting.

Example 3

Three and Four Devices at Once
Input
req_n=1000 (devices 0, 1, 2 ask); req_n=0100 (devices 0, 1, 3 ask); req_n=0010 (devices 0, 2, 3 ask); req_n=0001 (devices 1, 2, 3 ask); req_n=0000 (devices 0, 1, 2, 3 ask); req_n=1111 (nobody asks); req_n=0000 (devices 0, 1, 2, 3 ask); req_n=1101 (devices 1 ask)
Output
code_step0 = 2, valid_step0 = yes, more_step0 = yes, code_step1 = 3, valid_step1 = yes, more_step1 = yes, code_step2 = 3, valid_step2 = yes, more_step2 = yes, code_step3 = 3, valid_step3 = yes, more_step3 = yes, code_step4 = 3, valid_step4 = yes, more_step4 = yes, code_step5 = 0, valid_step5 = no, more_step5 = no, code_step6 = 3, valid_step6 = yes, more_step6 = yes, code_step7 = 1, valid_step7 = yes, more_step7 = no

With devices 0, 1 and 2 asking, device 2 wins. With all four asking, device 3 wins.

Constraints and Contract

  • Inputs are known 0/1 values. Each pattern is held for one nanosecond and the outputs are sampled at its end.
  • Keep the module name and the ports. The design is combinational: no clock and no stored value.

Hints

Hint 1

Invert the request lines first, so that a 1 means "asks". Then the rest is an ordinary priority encoder.

Hint 2

Test device 3 first, then 2, then 1. Give code a value on every path, including the one where only device 0 asks or nobody does.

Hint 3

more needs a count of at least two. One way: clear the lowest 1 of the active-high requests, with r & (r - 1), and see if anything is left.

What the grader checks: Seven directed and eight seeded cases of eight steps each cover all sixteen request patterns. code, valid and more are compared with a model written in JavaScript after every step. The synthesis check rejects a latch.

The submitted design must synthesize with 0 latches and no combinational loop. Counts come from the pinned open-source synthesis flow. They are proxies for logic size and depth, not physical area or timing.

15 checks on Icarus Verilog + Yosys · server. Run the examples first, then check the full regression. Full checks use the server judge. Downloads contain public samples only. A passing result establishes the tested cases, not a proof for all possible inputs.

See all 2 steps and the final capstone

Report a problem with this page

Your code SystemVerilogSaved locally
Ln 1, Col 1Tab indents · Ctrl/⌘ + Enter runs samples
Not run yet

One Device at a Time, and Nobody

Input
req_n=1110 (devices 0 ask); req_n=1101 (devices 1 ask); req_n=1011 (devices 2 ask); req_n=0111 (devices 3 ask); req_n=1111 (nobody asks); req_n=0111 (devices 3 ask); req_n=1011 (devices 2 ask); req_n=1111 (nobody asks)
Expected output
code_step0 = 0, valid_step0 = yes, more_step0 = no, code_step1 = 1, valid_step1 = yes, more_step1 = no, code_step2 = 2, valid_step2 = yes, more_step2 = no, code_step3 = 3, valid_step3 = yes, more_step3 = no, code_step4 = 0, valid_step4 = no, more_step4 = no, code_step5 = 3, valid_step5 = yes, more_step5 = no, code_step6 = 2, valid_step6 = yes, more_step6 = no, code_step7 = 0, valid_step7 = no, more_step7 = no

A single request gives its own number, valid 1 and more 0. With nobody asking, all three outputs are 0.

Run samples executes all 3 public checks. Check all tests runs 15 checks on the server.

Icarus Verilog + Yosys · server