G4.2.2 A 16:1 Mux from 4:1 Muxes

EasyImplementIcarus · browser samples / server checksReview the topic

Build a 16:1 mux of W-bit words from five 4:1 mux cells in two levels, with W as a parameter.

Hardware context: A pump controller and a logic analyser, each built from multiplexer cells. Build a parameterized 16:1 mux of words from five 4:1 mux cells.

A logic analyser routes one of sixteen probe buses to its capture memory. One board uses 1-bit probes and another uses 6-bit probes. The same mux16 module must serve both, so the word width is a parameter W.

This is an Implement problem. Write mux16 as a tree of 4:1 mux cells from the read-only library, five cells in two levels. Pass W on to every cell.

The check builds two copies, one with W = 1 and one with W = 6. It applies eight select values to both, one every 6 ns, and records both outputs.

Signals in the Timeline

SignalWidthRole
script144input of each check
Full specification
The module (keep the name, the parameter and the ports)
module mux16 #(parameter int W = 8) (
  input  logic [16*W-1:0] d,            // sixteen words: word k is d[k*W +: W]
  input  logic [3:0]      s,            // which word to pass
  output wire  [W-1:0]    y
);
  // your netlist
endmodule
mux4w.sv: the cell library (read-only). Ports are (y, d0, d1, d2, d3, s)
// mux4w.sv: the cell library (read-only). One 4:1 mux of W-bit words, 2 ns.
// Every copy adds 1 to tb.n_mux4 when the simulation starts, and reports its output to the bench.
module MUX4 #(parameter int W = 1) (
  output wire [W-1:0] y,
  input  wire [W-1:0] d0, d1, d2, d3,
  input  wire [1:0]   s                 // s = 2'd2 passes d2
);
  int idx;
  assign #2 y = s[1] ? (s[0] ? d3 : d2) : (s[0] ? d1 : d0);
  initial begin
    idx = tb.n_mux4++;
    tb.cell_w[idx] = W;
  end
  always @(y) tb.cell_y[idx] = 6'(y);
endmodule

RuleDetail
Functiony is word s of d: y = d[s*W +: W].
StructureFive 4:1 mux cells in two levels: ten cells over the two copies.
TimingEach cell takes 2 ns, so y must not change in the first nanosecond after a select change.
WidthEvery cell gets the module's W through #(W).
Names to avoidcell and bit are reserved words; do not use them as names.

The result shows the 1-bit and 6-bit outputs after each select (y1_stepK and y6_stepK). It also flags a wrong cell count, a y that changed too soon, and a y that no cell drives.

Examples

Example 1

Word k Holds k: Selects 0 to 7
Input
1-bit words 1010101010101010 (word 15 first); 6-bit words 00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f (word 0 first); selects 0, 1, 2, 3, 4, 5, 6, 7
Output
y6_step0 = 0x0, y1_step0 = no, y6_step1 = 0x1, y1_step1 = yes, y6_step2 = 0x2, y1_step2 = no, y6_step3 = 0x3, y1_step3 = yes, y6_step4 = 0x4, y1_step4 = no, y6_step5 = 0x5, y1_step5 = yes, y6_step6 = 0x6, y1_step6 = no, y6_step7 = 0x7, y1_step7 = yes, cell_count_wrong = no, output_changed_too_soon = no, output_not_from_a_cell = no

Each 6-bit word holds its own number, so y6 equals the select. The 1-bit words alternate, starting with word 0 = 0.

Example 2

Word k Holds k: Selects 8 to 15
Input
1-bit words 0101010101010101 (word 15 first); 6-bit words 00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f (word 0 first); selects 8, 9, 10, 11, 12, 13, 14, 15
Output
y6_step0 = 0x8, y1_step0 = yes, y6_step1 = 0x9, y1_step1 = no, y6_step2 = 0xa, y1_step2 = yes, y6_step3 = 0xb, y1_step3 = no, y6_step4 = 0xc, y1_step4 = yes, y6_step5 = 0xd, y1_step5 = no, y6_step6 = 0xe, y1_step6 = yes, y6_step7 = 0xf, y1_step7 = no, cell_count_wrong = no, output_changed_too_soon = no, output_not_from_a_cell = no

The same words with the selects 8 to 15. These pass through the two upper groups of the tree.

Example 3

One 1 in Each Copy
Input
1-bit words 0000010000000000 (word 15 first); 6-bit words 00 00 00 00 00 00 3f 00 00 00 00 00 00 00 00 00 (word 0 first); selects 10, 6, 0, 15, 6, 10, 5, 9
Output
y6_step0 = 0x0, y1_step0 = yes, y6_step1 = 0x3f, y1_step1 = no, y6_step2 = 0x0, y1_step2 = no, y6_step3 = 0x0, y1_step3 = no, y6_step4 = 0x3f, y1_step4 = no, y6_step5 = 0x0, y1_step5 = yes, y6_step6 = 0x0, y1_step6 = no, y6_step7 = 0x0, y1_step7 = no, cell_count_wrong = no, output_changed_too_soon = no, output_not_from_a_cell = no

Only 1-bit word 10 and 6-bit word 6 are not zero. Each output is non-zero only when the select names that word.

Constraints and Contract

  • Inputs are known 0/1 values. The sixteen words are set once per case; each select is held for 6 ns.
  • Keep the module name, the parameter W and the ports.

Hints

Hint 1

Split the sixteen words into four groups: words 0 to 3, 4 to 7, 8 to 11 and 12 to 15. One cell picks inside each group.

Hint 2

Inside a group the word number differs only in its two low bits, so the first level uses s[1:0]. The last cell picks a group with s[3:2].

Hint 3

Word k starts at bit kW of d. Write it as d[kW +: W], and give every cell #(W) so that the same code works for any width.

What the grader checks: Six directed and eight seeded cases set sixteen words in each copy and apply eight selects. Both outputs are compared with a model written in JavaScript after every select. The cell count must be ten over the two copies. Every cell reports its output, and y must equal the output of one of them.

14 checks on Icarus · browser samples / server checks. 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

Word k Holds k: Selects 0 to 7

Input
1-bit words 1010101010101010 (word 15 first); 6-bit words 00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f (word 0 first); selects 0, 1, 2, 3, 4, 5, 6, 7
Expected output
y6_step0 = 0x0, y1_step0 = no, y6_step1 = 0x1, y1_step1 = yes, y6_step2 = 0x2, y1_step2 = no, y6_step3 = 0x3, y1_step3 = yes, y6_step4 = 0x4, y1_step4 = no, y6_step5 = 0x5, y1_step5 = yes, y6_step6 = 0x6, y1_step6 = no, y6_step7 = 0x7, y1_step7 = yes, cell_count_wrong = no, output_changed_too_soon = no, output_not_from_a_cell = no

Each 6-bit word holds its own number, so y6 equals the select. The 1-bit words alternate, starting with word 0 = 0.

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

Icarus · browser samples / server checks