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
| Signal | Width | Role |
|---|---|---|
abc | 3 | input of each check |
Full specification
module borrow (input wire a, b, c, output wire y);
// your NAND2 cells
endmodule
// 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 c | 000 | 001 | 010 | 011 | 100 | 101 | 110 | 111 |
|---|---|---|---|---|---|---|---|---|
| y | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 1 |
| Rule | Detail |
|---|---|
| Function | y = a'b + a'c + bc, the borrow out of a - b - c, on all eight rows. |
| Cells | Only NAND2 instances. A NAND2 with both inputs tied together is an inverter, and it counts as a cell. |
| Cost | The number of NAND2 cells. It must equal the fewest that any NAND2 circuit for y can use. |
| Nets | Declare 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