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
| Signal | Width | Role |
|---|---|---|
rows | 32 | input of each check |
Full specification
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 b | c AND d | y |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |
// 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
| Rule | Detail |
|---|---|
| Transistors | Only nfet and pfet cells. The budget is 8. |
| Supplies | vdd is always 1 and gnd is always 0. They are declared for you. |
| Inner nodes | A node between two transistors is a wire that you declare. |
| Result | y 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