21 NAND 文档 EN

题解精选

TapeOut 电路题的门级做法:10 道题的门数、深度和一句话思路。

规则

10 道题

题号题目门数 / 深度做法
3异或 XOR4 / 3先算 n1 = NAND(A,B),再各和 A、B 做一次 NAND,最后合起来。穷举证明 3 个门做不出。
18半加器5 / 3XOR 的 4 门结构加一门:n1 自己和自己 NAND 就是进位,一门两用。
75二分频1 NAND + 1 LATCH / 1输出取反再存回去。要翻转必须有一位存储和一个取反,2 个元件是下限。
484 位数 1 的个数20 / —一个全加器加一个半加器,两路进位再做异或和与。
83序列检测 10116 NAND + 2 LATCH / —4 状态机,穷举所有状态编码找最省的一种;有一位状态直接等于输入。
10016 位 + 8 位加法108 / —低 8 位用 9 门全加器串起来,高 8 位只剩进位,用 5 门半加器链。
1456 位比较器(<、=、>)71 / —「大于」从最高位往下算前缀链,每低一位 12 个门;「等于」「小于」从链上再接 4 个门。
162、1638 位取大 / 取小70 / —借位链算出 A<B,再用它当选择信号,每位 3 门选 A 或 B。门数 9n−2。
20916-4 优先编码器78 / —递归二分:高半有请求就取高半的编号,否则取低半,每位 3 门合并。
2278 位饱和减法91 / —二补码减法 A + ~B + 1;最高位进位为 0 说明 A<B,用它把结果清零,每位 2 门。

「—」是笔记里没记深度。

9 门全加器

多道加法类题都复用这一个。

9 个 NAND 的全加器:前 4 门算 x = A⊕B,再 4 门算和,最后 1 门出进位
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)

进位那一门复用了 g1 和 g5,不另花反相器。笔记里还穷举证伪了 8 门的全加器。

踩过的坑