G3.8.1 NAND2 Only, Fewest Gates

MediumOptimizeIcarus · browser samples / server checksReview the topic

Build the borrow output of a full subtractor from two-input NAND cells only, with the fewest cells any circuit can use.

Hardware context: A lamp function built from two-input unit-delay cells, flat and factored. Build a full subtractor's borrow from the fewest NAND2 cells.

A full subtractor computes a - b - c, where c is the borrow from the bit below. Its borrow out is y = a'b + a'c + bc. The gate array for this block offers one cell only: a two-input NAND.

This is an Optimize problem. The starter converts the flat sum of products gate by gate. It is correct and uses seven NAND2 cells. Rewrite it with as few cells as any NAND2 circuit can use.

Write the module as a netlist of NAND2 instances from cells.sv. The check tests all eight input 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 borrow (input wire a, b, c, output wire y);
  // your NAND2 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 NAND2 (output wire y, input wire a, b);              nand #1 (y, a, b);           initial tb.cells++; endmodule

a b c000001010011100101110111
y01110001
RuleDetail
Functiony = a'b + a'c + bc, the borrow out of a - b - c, on all eight rows.
CellsOnly NAND2 instances. A NAND2 with both inputs tied together is an inverter, and it counts as a cell.
CostThe number of NAND2 cells. It must equal the fewest that any NAND2 circuit for y can use.
NetsDeclare each internal net as a wire. Connect by position, output first, or by name: .y, .a, .b.

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

Examples

Example 1

Borrow in Only
Input
a b c = 0 0 1
Output
value = 1

With a = b = 0 and c = 1, the bit must borrow: y = 1.

Example 2

A = 1, Nothing to Subtract
Input
a b c = 1 0 0
Output
value = 0

With a = 1 and b = c = 0, no borrow is needed: y = 0.

Example 3

Everything Is 1
Input
a b c = 1 1 1
Output
value = 1

With a = b = c = 1, 1 - 1 - 1 borrows: y = 1.

Constraints and Contract

  • Inputs are known 0/1 values, held for 8 ns before y is read.
  • Keep the module name and the ports. Use no assign statements, operators or other cells.

Hints

Hint 1

The starter needs an inverter for a and a three-input OR built from NAND2 cells. Both cost cells. Look for a form with fewer levels of inversion.

Hint 2

Factor the function: y = (b + c)(a' + bc). Check it on the table.

Hint 3

NAND(a, NAND(b, c)) is a' + bc. Then y is (a' + bc) ANDed with b + c. Write that AND-OR as NAND gates that share the signal a' + bc.

What the grader checks: The check tests y on all eight rows and counts the cells through the bench counter. An exhaustive search over NAND2 circuits proves that 5 cells is the minimum. The judge accepts only NAND2 instances connected by plain nets: assign statements, gate primitives and expressions are refused.

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

Borrow in Only

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

With a = b = 0 and c = 1, the bit must borrow: y = 1.

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

Icarus · browser samples / server checks