21 NAND Docs 中文

Worked examples

Gate-level designs for TapeOut circuit problems: gate count, depth and a one-line idea for 10 problems.

Rules

10 problems

No.ProblemGates / depthApproach
3XOR4 / 3First compute n1 = NAND(A,B), then NAND it once with A and once with B, then combine. Exhaustive search proves 3 gates cannot do it.
18Half adder5 / 3The 4-gate XOR plus one gate: NAND n1 with itself to get the carry, so one gate does two jobs.
75Divide by two1 NAND + 1 LATCH / 1Invert the output and store it back. Toggling needs one bit of storage and one inverter, so 2 parts is the minimum.
48Count of 1s in a 4-bit number20 / —One full adder plus one half adder, then XOR and AND on the two carries.
83Sequence detector 10116 NAND + 2 LATCH / —A 4-state machine. Try every state encoding and keep the cheapest. One state bit equals the input directly.
10016-bit + 8-bit addition108 / —Chain 9-gate full adders for the low 8 bits. The high 8 bits only carry, so use a chain of 5-gate half adders.
1456-bit comparator (<, =, >)71 / —"Greater than" is a prefix chain from the top bit down, 12 gates per lower bit. "Equal" and "less than" take 4 more gates off the chain.
162, 1638-bit max / min70 / —A borrow chain computes A<B, then use it as the select signal, 3 gates per bit to pick A or B. Gate count 9n−2.
20916-to-4 priority encoder78 / —Split in half recursively: if the high half has a request, take its index, otherwise the low half's. Merge with 3 gates per bit.
2278-bit saturating subtraction91 / —Two's complement subtraction A + ~B + 1. A top carry of 0 means A<B; use it to clear the result, 2 gates per bit.

"—" means the notes did not record the depth.

The 9-gate full adder

Many of the addition problems reuse this one.

A full adder from 9 NANDs: the first 4 gates compute x = A⊕B, 4 more compute the sum, and the last 1 gives the carry
g1 = NAND(A, B)
g2 = NAND(A, g1)
g3 = NAND(B, g1)
x  = NAND(g2, g3)
g5 = NAND(x, Cin)
g6 = NAND(x, g5)
g7 = NAND(Cin, g5)
Sum  = NAND(g6, g7)
Cout = NAND(g1, g5)

The carry gate reuses g1 and g5, so it needs no extra inverter. The notes also used exhaustive search to rule out an 8-gate full adder.

Pitfalls