G4.2.1 Any Function from One Mux

MediumImplementIcarus · browser samples / server checksReview the topic

Build a four-variable function from one 8:1 mux and one inverter, by Shannon expansion on the last variable.

Hardware context: A pump controller and a logic analyser, each built from multiplexer cells. Build a four-variable function from one 8:1 mux and one inverter.

A pump controller reads four float sensors a, b, c and d, with a the most significant. The pump runs when f = 1, and f = Σm(0, 2, 3, 7, 10, 13, 14, 15). The board has room for one 8:1 multiplexer chip and one inverter, and nothing else.

This is an Implement problem. Write pump as a netlist of cells from the read-only library. Use exactly one mux cell and at most one inverter. The constants 1'b0 and 1'b1 may drive data inputs.

The check applies eight input rows per case, one every 4 ns, and records f after each. It also counts your cells.

Signals in the Timeline

SignalWidthRole
script32input of each check
Full specification
The module (keep the name and the ports)
module pump (
  input  logic a, b, c, d,     // the four sensors; a is the most significant
  output wire  f               // 1: run the pump
);
  // your netlist
endmodule
muxcells.sv: the cell library (read-only). Ports are (y, inputs...): the output comes first
// muxcells.sv: the cell library (read-only). Every cell takes 1 ns. Ports: output first.
// The cells count themselves: tb.n_mux for every mux cell, tb.n_inv for every inverter.
module INV  (output wire y, input wire a);                                   not #1 (y, a);                                  initial tb.n_inv++; endmodule
module MUX2 (output wire y, input wire d0, d1, s);                           assign #1 y = s ? d1 : d0;                      initial tb.n_mux++; endmodule
module MUX4 (output wire y, input wire d0, d1, d2, d3, s1, s0);              assign #1 y = s1 ? (s0 ? d3 : d2) : (s0 ? d1 : d0); initial tb.n_mux++; endmodule
module MUX8 (output wire y, input wire d0, d1, d2, d3, d4, d5, d6, d7, s2, s1, s0);
  wire [7:0] d = {d7, d6, d5, d4, d3, d2, d1, d0};
  assign #1 y = d[{s2, s1, s0}];
  initial tb.n_mux++;
endmodule

RuleDetail
Functionf = 1 exactly in the rows 0, 2, 3, 7, 10, 13, 14 and 15. The row number is abcd read as binary.
CostOne mux cell of any size, and at most one inverter.
Data inputsEach may be a variable, the inverter output, 1'b0 or 1'b1.
NetsDeclare each internal net as a wire. The output f is a wire.

The result shows f after each of the eight rows, f_row0 to f_row7, in the order the case applies them. It also shows whether the cell count is over the budget.

Examples

Example 1

Rows 0 to 7
Input
0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111 (abcd)
Output
f_row0 = yes, f_row1 = no, f_row2 = yes, f_row3 = yes, f_row4 = no, f_row5 = no, f_row6 = no, f_row7 = yes, over_budget = no

The first half of the table: a = 0. f is 1 in the rows 0, 2, 3 and 7. The cell count is within the budget.

Example 2

Rows 8 to 15
Input
1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111 (abcd)
Output
f_row0 = no, f_row1 = no, f_row2 = yes, f_row3 = no, f_row4 = no, f_row5 = yes, f_row6 = yes, f_row7 = yes, over_budget = no

The second half: a = 1. f is 1 in the rows 10, 13, 14 and 15.

Example 3

Pairs That Differ in d Only
Input
0010, 0011, 1100, 1101, 0110, 0111, 0000, 0001 (abcd)
Output
f_row0 = yes, f_row1 = yes, f_row2 = no, f_row3 = yes, f_row4 = no, f_row5 = yes, f_row6 = yes, f_row7 = no, over_budget = no

Rows 2 and 3 are both 1, so their data input is a constant 1. Rows 0 and 1 give 1 then 0, so their data input is d inverted.

Constraints and Contract

  • Inputs are known 0/1 values. Each row is held for 4 ns before f is read.
  • Keep the module name and the ports.

Hints

Hint 1

Put a, b and c on the three select lines. Then each data input sees two rows of the table: one with d = 0 and one with d = 1.

Hint 2

For each pair of rows, f is 0 in both, 1 in both, equal to d, or equal to d inverted. That value is the data input.

Hint 3

Data input k of the mux is chosen when abc = k. So the rows 2k and 2k + 1 set data input k. Mind which select pin is the most significant.

What the grader checks: Nine directed and six seeded cases apply eight rows each, covering all sixteen rows several times. f is compared with the truth table, computed in JavaScript, after every row. The cell count must be one mux and at most one inverter. The source may hold only cell instances: no assign, no always block and no operator.

15 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

Rows 0 to 7

Input
0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111 (abcd)
Expected output
f_row0 = yes, f_row1 = no, f_row2 = yes, f_row3 = yes, f_row4 = no, f_row5 = no, f_row6 = no, f_row7 = yes, over_budget = no

The first half of the table: a = 0. f is 1 in the rows 0, 2, 3 and 7. The cell count is within the budget.

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

Icarus · browser samples / server checks