XNOR Gate from NAND Gates Only
XNOR (exclusive-NOR) is the logical complement of XOR. It outputs 1 when both inputs are equal and 0 when they differ. XNOR is the gate behind digital equality checking — 4-bit comparators use a cascade of XNOR gates to detect whether two buses carry the same value. In CMOS, XNOR is just as expensive as XOR and must also be built from NAND primitives.
Your task is to implement Y = A XNOR B = NOT(A XOR B) using only NAND2 gates, achieving the minimum gate count. The truth table is:
| A | B | Y | |---|---|---| | 0 | 0 | 1 | | 0 | 1 | 0 | | 1 | 0 | 0 | | 1 | 1 | 1 |
The minimum NAND-only XNOR requires 5 gates. The key observation is that XNOR = NOT(XOR). You already know that XOR requires 4 NAND gates (from the classic shared-node construction). Adding a single NAND gate wired as an inverter (NAND(X, X) = NOT(X)) at the output of the 4-gate XOR gives you XNOR in 5 gates total. However, you must verify that this 5th gate does not alias with an existing intermediate node in the XOR network — it connects to the XOR output, not to any internal node.
| Signal | Direction | Width | Description | |--------|-----------|-------|-------------| | A | input | 1 | First input bit | | B | input | 1 | Second input bit | | Y | output | 1 | A XNOR B: 1 when A and B are equal, 0 when they differ |
Constraints
- Only NAND2 gates are allowed. No AND, OR, NOT, XOR, NOR, or XNOR gates.
- The optimal solution uses exactly 5 NAND2 gates.
- Connecting both inputs of a NAND gate to the same signal is allowed and produces NOT of that signal.
- A solution using 6 or more NAND gates is accepted but will not earn the efficiency bonus.
Topics
Solve this problem
Place the gates, wire them up and watch the signals settle. Every submission runs on the same simulation engine that grades it.
This problem is part of Codiode Pro. The statement above is free to read.
The circuit builder and code editor need a desktop screen. On a phone, read the problem here and open it on a laptop to solve.