G3.8.3 NOR2 Only, Fewest Gates

MediumOptimizeIcarus · browser samples / server checksReview the topic

Build a press interlock from two-input NOR cells only, with the fewest cells any NOR2 circuit can use.

Hardware context: A lamp function built from two-input unit-delay cells, flat and factored. Build a press interlock from the fewest NOR2 cells, starting from its 0s.

A press may run unless its guard is open while a light curtain sees a hand. The guard switch is a, and the two curtain sensors are b and c. So run is 0 exactly when a = 1 and b or c is 1.

The gate array for this block offers one cell only: a two-input NOR. The starter converts the product of sums (a' + b')(a' + c') gate by gate. It is correct and uses six NOR2 cells.

This is an Optimize problem. Rewrite the interlock with as few NOR2 cells as any circuit can use. Write a netlist of NOR2 instances only; the check tests all eight rows and counts your cells.

Signals in the Timeline

SignalWidthRole
abc3input of each check
Full specification
The module (keep the name and the ports)
module interlock (input wire a, b, c, output wire run);
  // your NOR2 cells
endmodule
cells.sv: the only cell you may use (read-only). Ports are (y, a, b): output first
// cells.sv: the unit-delay cell library (read-only).
// Every cell takes 1 time unit, whatever its fan-in. Ports are (y, inputs...): output first.
// Each cell adds 1 to the bench's cell counter when the simulation starts.
module NOR2  (output wire y, input wire a, b);              nor #1 (y, a, b);            initial tb.cells++; endmodule

a b c000001010011100101110111
run11111000
RuleDetail
Functionrun = 0 when a = 1 and (b = 1 or c = 1); run = 1 on every other row.
CellsOnly NOR2 instances. A NOR2 with both inputs tied together is an inverter, and it counts as a cell.
CostThe number of NOR2 cells. It must equal the fewest that any NOR2 circuit for run can use.
NetsDeclare each internal net as a wire. Connect by position, output first, or by name: .y, .a, .b.

Each row check reports run for one input row. The cost check reports your number of cells.

Examples

Example 1

Guard Closed, Curtain Clear
Input
a b c = 0 0 0
Output
value = 1

With a = b = c = 0 the press may run: run = 1.

Example 2

Guard Open, Hand Seen
Input
a b c = 1 1 0
Output
value = 0

With a = 1 and b = 1 the press must stop: run = 0.

Example 3

Guard Open, Curtain Clear
Input
a b c = 1 0 0
Output
value = 1

With a = 1 and b = c = 0 nothing is in the way: run = 1.

Constraints and Contract

  • Inputs are known 0/1 values, held for 8 ns before run is read.
  • Keep the module name and the ports. Use only NOR2 instances connected by plain nets: assign statements, gate primitives and expressions are refused.

Hints

Hint 1

Look at the 0s of run instead of the 1s. Write run' as a sum of products.

Hint 2

run' = a(b + c). So run is the complement of an AND of a and an OR. A NOR gives an OR that is already inverted.

Hint 3

NOR(b, c) is (b + c)'. Combine it with a' in one NOR, then invert that result with one more NOR.

What the grader checks: The check tests run on all eight rows and counts the cells through the bench counter. An exhaustive search over NOR2 circuits proves that 4 cells is the minimum. The judge accepts only NOR2 instances connected by plain nets.

9 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 3 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

Guard Closed, Curtain Clear

Input
a b c = 0 0 0
Expected output
value = 1

With a = b = c = 0 the press may run: run = 1.

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

Icarus · browser samples / server checks