题解精选
TapeOut 电路题的门级做法:10 道题的门数、深度和一句话思路。
规则
- 只用两输入 NAND;时序题另有 LATCH(每拍把输入存一位)。
- 门数 = NAND 个数,时序题另记 LATCH 个数。深度 = 从输入到输出最长要过几层门。
- 每题都在本地用仿真核过:小题全部输入跑一遍,大题跑全部或大量随机输入。
10 道题
| 题号 | 题目 | 门数 / 深度 | 做法 |
|---|---|---|---|
| 3 | 异或 XOR | 4 / 3 | 先算 n1 = NAND(A,B),再各和 A、B 做一次 NAND,最后合起来。穷举证明 3 个门做不出。 |
| 18 | 半加器 | 5 / 3 | XOR 的 4 门结构加一门:n1 自己和自己 NAND 就是进位,一门两用。 |
| 75 | 二分频 | 1 NAND + 1 LATCH / 1 | 输出取反再存回去。要翻转必须有一位存储和一个取反,2 个元件是下限。 |
| 48 | 4 位数 1 的个数 | 20 / — | 一个全加器加一个半加器,两路进位再做异或和与。 |
| 83 | 序列检测 1011 | 6 NAND + 2 LATCH / — | 4 状态机,穷举所有状态编码找最省的一种;有一位状态直接等于输入。 |
| 100 | 16 位 + 8 位加法 | 108 / — | 低 8 位用 9 门全加器串起来,高 8 位只剩进位,用 5 门半加器链。 |
| 145 | 6 位比较器(<、=、>) | 71 / — | 「大于」从最高位往下算前缀链,每低一位 12 个门;「等于」「小于」从链上再接 4 个门。 |
| 162、163 | 8 位取大 / 取小 | 70 / — | 借位链算出 A<B,再用它当选择信号,每位 3 门选 A 或 B。门数 9n−2。 |
| 209 | 16-4 优先编码器 | 78 / — | 递归二分:高半有请求就取高半的编号,否则取低半,每位 3 门合并。 |
| 227 | 8 位饱和减法 | 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 门的全加器。
踩过的坑
NAND(x, ~x)恒等于 1,不是 0。要常 0 得再取反。- 二补码减法的最高位进位为 1 表示没借位,可以直接当使能。
- 要得到 d 与 c:先
x = NAND(d, c),再NAND(x, x)。只用一个 NAND 得到的是反的。