6 / 63 · 概念

通用逻辑门：只用 NAND 构造电路

通过具体结构说明 NAND、NOR 的功能完备性，验证 XOR 的中间信号。

“所有电路”的含义范围

仅用 NAND 就能构造 NOT、AND、OR，而任意有限输入的组合逻辑函数都能用这些运算表示。在这个意义上，NAND 是通用逻辑门^{通用逻辑门若重复使用一种门就能构造任意布尔函数，则称其为通用逻辑门。NAND 与 NOR 是典型例子。}。这不意味着一个 NAND 就能解决存储、时钟、布线和功耗条件。

\overline a=\operatorname{NAND}(a,a)

ab=\operatorname{NAND}(n,n),\quad n=\operatorname{NAND}(a,b)

a+b=\operatorname{NAND}(\operatorname{NAND}(a,a),\operatorname{NAND}(b,b))

将同一输入连接到 NAND 的两个输入端，便得到 NOT。在 NAND 后再取反^{取反将 0 变为 1、1 变为 0 的 NOT 运算。表达式上方的横线表示对其覆盖的整个表达式应用 NOT。了解更多}一次得到 AND；利用德摩根^{德摩根定律对 AND 结果取反，等价于分别将输入取反后做 OR；对 OR 结果取反，等价于分别将输入取反后做 AND。了解更多}定律则得到 OR。NOR 也能通过并接输入构造 NOT，并可用类似结构证明其通用性。

用四个 NAND 构造 XOR

按以下顺序定义中间信号。

n_0=\overline{ab},\quad n_1=\overline{a n_0},\quad n_2=\overline{b n_0},\quad y=\overline{n_1n_2}

a	b	n0	n1	n2	y
0	0	1	1	1	0
0	1	1	1	0	1
1	0	1	0	1	1
1	1	0	1	1	0

利用共享中间信号构造 XOR

第一个 NAND: n0 = NAND(a, b)
中间的两个 NAND: n1 = NAND(a, n0); n2 = NAND(b, n0)
最后一个 NAND: y = NAND(n1, n2)

第二级的两个 NAND 并行工作。总门数为 4，但最长逻辑路径只有 3 级。在每个门最大延迟为 2 ns 的简化模型中，最大路径延迟和为 6 ns。实际负载与布线带来的变化需另行考虑。

将四个 NAND 的结果与 XOR 比较

XOR · 真值表
a	b	y
0	0	0
0	1	1
1	0	1
1	1	0

亲自填完表中的四行，再与上面的 XOR 比较。功能等价是指所有输入对应的输出相同，并不是说门数或传播延迟^{传播延迟从输入变化到输出稳定为正确值所需的时间。逻辑表达式等价与时间特性是两回事。了解更多}相同。

自己试试

写出只用 NOR 构造 NOT 和 AND 的表达式。AND 结构的门数与最长路径级数分别是多少？

阅读解释

NOT a=NOR(a,a)。AND 为 NOR(NOR(a,a), NOR(b,b))。两个输入反相加最后一个 NOR，共 3 个门，最长路径为 2 级。