G2.6.2 Majority from NOR Gates Only

MediumOptimizeIcarus · browser samples / server checksReview the topic

Build a three-input majority voter from two-input NOR cells only, within a budget of six cells.

Hardware context: A test chip with NAND cells only and a radiation-tolerant controller with NOR cells only. Build a three-input majority voter from six two-input NOR cells.

A radiation-tolerant controller votes on three copies of each control bit. Its cell library is NOR only. The voter output y is 1 when at least two of a, b and c are 1.

This is an Optimize problem. Build the voter from NOR cells of cells.sv. The starter maps the sum of products ab + ac + bc straight onto NOR cells. It is correct, but it needs ten cells. Your budget is six.

Think about which two-level form maps onto NOR cells without extra inverters.

Signals in the Timeline

SignalWidthRole
row3input of each check
Full specification
cells.sv: the cell library (read-only)
// cells.sv: the cell library (read-only). Every cell takes 2 time units.
// Ports are (y, inputs...): output first. Each cell adds 1 to its own counter in the bench.
// While the bench sets poison to 1, every cell output is x.
module INV   (output wire y, input wire a);               wire g; not #2 (g, a);           assign y = tb.poison ? 1'bx : g; initial tb.n_inv++; always @(tb.recount) tb.n_inv++; endmodule
module NAND2 (output wire y, input wire a, b);            wire g; nand #2 (g, a, b);       assign y = tb.poison ? 1'bx : g; initial tb.n_nand2++; always @(tb.recount) tb.n_nand2++; endmodule
module NOR2  (output wire y, input wire a, b);            wire g; nor #2 (g, a, b);        assign y = tb.poison ? 1'bx : g; initial tb.n_nor2++; always @(tb.recount) tb.n_nor2++; endmodule
module NAND3 (output wire y, input wire a, b, c);         wire g; nand #2 (g, a, b, c);    assign y = tb.poison ? 1'bx : g; initial tb.n_nand3++; always @(tb.recount) tb.n_nand3++; endmodule
module NOR3  (output wire y, input wire a, b, c);         wire g; nor #2 (g, a, b, c);     assign y = tb.poison ? 1'bx : g; initial tb.n_nor3++; always @(tb.recount) tb.n_nor3++; endmodule
module XOR2  (output wire y, input wire a, b);            wire g; xor #2 (g, a, b);        assign y = tb.poison ? 1'bx : g; initial tb.n_xor2++; always @(tb.recount) tb.n_xor2++; endmodule
The module you write (keep the name and the ports)
module maj_nor (
  input  logic a,
  input  logic b,
  input  logic c,
  output wire  y
);
  // your NOR2 cells
endmodule
RuleDetail
CellsUse only two-input NOR cells from cells.sv. The library has other cells; using one fails the check.
BudgetAt most 6 cells. No correct netlist of this kind is smaller.
TimingEvery cell takes 2 ns. The check reads the outputs after each input change and again once they settle.
Cells onlyThe check refuses assign, always, initial, gate primitives, operators and hierarchical names before it runs. It also forces every cell output to x, and y must follow.
WiresDeclare every wire between two cells. Each cell is one line: the cell name, an instance name, then (output, inputs).

The library has a three-input NOR cell. It is not allowed here: the chip has two-input NOR cells only.

Examples

Example 1

Two Votes for 1
Input
abc = 011
Output
y = 1, moved_too_early = no

b and c are 1, so y must be 1.

Example 2

One Vote for 1
Input
abc = 001
Output
y = 0, moved_too_early = no

Only c is 1. Two copies say 0, so y must be 0.

Example 3

Three Votes for 1
Input
abc = 111
Output
y = 1, moved_too_early = no

All three copies agree on 1.

Constraints and Contract

  • Keep the module name maj_nor and its four ports.
  • Use cell instances only: no gate primitives, assign or always blocks.

Hints

Hint 1

A product of sums maps onto NOR-NOR. Majority as a product of sums is (a + b)(a + c)(b + c).

Hint 2

Three NOR cells give the three sums, inverted. The output needs a NOR of all three of them, but your cells have two inputs.

Hint 3

A NOR of three signals equals a NOR of (p + q) and r. Two NOR cells make p + q: one NOR, then one NOR used as an inverter.

What the grader checks: The check applies sixteen input changes and reads y after each one. It counts the cells of each kind, and forces every cell output to x to confirm that y comes from a cell. It checks function, cell kind and count.

19 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

Two Votes for 1

Input
abc = 011
Expected output
y = 1, moved_too_early = no

b and c are 1, so y must be 1.

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

Icarus · browser samples / server checks