G9.5.2 The Fewest Transistors for NOT(ab + Cd)

HardOptimizeIcarus · browser samples / server checksReview the topic

Rebuild a 14-transistor circuit for y = NOT(a AND b OR c AND d) as one compound gate with 8 transistors.

Hardware context: A six-transistor AND-OR-INVERT gate of a standard-cell library. Replace three simple gates by one AOI22 compound gate and count the transistors saved.

A carry circuit computes y = NOT(a AND b OR c AND d). The first version was drawn gate by gate: two NAND gates, then an AND made of a NAND and an inverter. It is correct, and it uses 14 transistors in three stages.

This is an Optimize problem. The starter is that 14-transistor circuit. Rebuild the function with 8 transistors or fewer, using only the nfet and pfet cells.

The check walks the input rows and reads y after each one. Then it counts the transistors against the budget of 8. The output must never float and the supply must never be shorted.

Signals in the Timeline

SignalWidthRole
rows32input of each check
Full specification
The module (keep the name, the ports and the two supply nets)
module aoi4 (
  input  logic a,
  input  logic b,
  input  logic c,
  input  logic d,
  output wire  y
);
  supply1 vdd;   // the positive supply: always 1
  supply0 gnd;   // ground: always 0
  // your transistors
endmodule
a AND bc AND dy
001
010
100
110
switches.sv: the two transistor cells (read-only). The terminals are out, in, ctrl
// switches.sv: the two transistor cells (read-only).
// Terminals are (out, in, ctrl), in the order of the nmos and pmos primitives.
// Each cell adds 1 to the transistor counter of the check when the simulation starts.
module nfet (output wire out, input wire in, input wire ctrl); nmos (out, in, ctrl); initial tb.transistors++; endmodule   // on when ctrl is 1
module pfet (output wire out, input wire in, input wire ctrl); pmos (out, in, ctrl); initial tb.transistors++; endmodule   // on when ctrl is 0

RuleDetail
TransistorsOnly nfet and pfet cells. The budget is 8.
Suppliesvdd is always 1 and gnd is always 0. They are declared for you.
Inner nodesA node between two transistors is a wire that you declare.
Resulty after each of eight input rows, shown as 0, 1, x or z. Then the transistors over the budget, which must be 0.

Examples

Example 1

Rows 0000 to 0111
Input
(a, b, c, d) = 0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111
Output
y_row1 = 1 (1), y_row2 = 1 (1), y_row3 = 1 (1), y_row4 = 0 (0), y_row5 = 1 (1), y_row6 = 1 (1), y_row7 = 1 (1), y_row8 = 0 (0), transistors_over_budget = 0, built_from_switch_cells = yes (1)

With a at 0 the first AND is 0. So y is 0 only where c and d are both 1: rows 0011 and 0111.

Example 2

Only the Pair a, b Changes
Input
(a, b, c, d) = 0000, 1100, 0100, 1100, 1000, 1100, 0000, 1100
Output
y_row1 = 1 (1), y_row2 = 0 (0), y_row3 = 1 (1), y_row4 = 0 (0), y_row5 = 1 (1), y_row6 = 0 (0), y_row7 = 1 (1), y_row8 = 0 (0), transistors_over_budget = 0, built_from_switch_cells = yes (1)

With c and d at 0, y is 0 only in the rows where a and b are both 1. The starter gives the same values, but it is 6 transistors over the budget.

Example 3

Only the Pair c, d Changes
Input
(a, b, c, d) = 0000, 0011, 0001, 0011, 0010, 0011, 0000, 0011
Output
y_row1 = 1 (1), y_row2 = 0 (0), y_row3 = 1 (1), y_row4 = 0 (0), y_row5 = 1 (1), y_row6 = 0 (0), y_row7 = 1 (1), y_row8 = 0 (0), transistors_over_budget = 0, built_from_switch_cells = yes (1)

With a and b at 0, y is 0 only in the rows where c and d are both 1. One input of a pair alone never pulls y down.

Constraints and Contract

  • Inputs are known 0/1 values; each row is held for one nanosecond and y is read at its end.
  • Keep the module name, the ports and the supply nets vdd and gnd.

Hints

Hint 1

Count the stages of the starter. Each stage inverts, and the function already has a NOT in front. Ask whether one stage can do the whole job.

Hint 2

In one stage, the pull-down network builds the part under the NOT. Each AND is a pair of NMOS in series. The OR puts the two pairs in parallel.

Hint 3

The pull-up network is the dual: each series pair becomes a parallel pair, and the two parallel pairs go in series. That is four NMOS and four PMOS.

What the grader checks: Six directed and four seeded scripts apply eight input rows each, and together they cover all sixteen rows. After every row, y is read as 0, 1, x or z and compared with the function computed in JavaScript. The transistor cells are counted against the budget. Voltages, delays and widths are outside this problem.

10 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 0000 to 0111

Input
(a, b, c, d) = 0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111
Expected output
y_row1 = 1 (1), y_row2 = 1 (1), y_row3 = 1 (1), y_row4 = 0 (0), y_row5 = 1 (1), y_row6 = 1 (1), y_row7 = 1 (1), y_row8 = 0 (0), transistors_over_budget = 0, built_from_switch_cells = yes (1)

With a at 0 the first AND is 0. So y is 0 only where c and d are both 1: rows 0011 and 0111.

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

Icarus · browser samples / server checks