知识点摘要

• 芯片本身由大量布尔门组合构建而成
• 任何布尔算子 (Boolean Operator) 都可以只用 Nand: NOT( x AND y ) 或者 Nor: NOT( x OR y ) 构建而成。
• 可以把门看作是一个黑箱函数：只关心输入和输出，而不需要关注内部的实现。
• 每个复杂的门电路都是很多基础的门组合形成的。
• 只要拥有 转换 和 传导 两个特性的硬件都可以用作门的物理实现。
• 组合门的能力本身是一门逻辑学，之后最好去补一下电路设计和逻辑设计两门教材。

作业纠错

给定一个黑箱 Nand：

CHIP Nand {
  IN a, b;
  OUT out;
}

已知 Nand: if a = b = 1 then out = 0 else out = 1 的情况下，实现 Not 很简单，将输入 a 接到 Nand 的输入 a，常量 1 接到 Nand 的输入 b 就行。

NOT = Nand(a = in, b = true, out = out)

而 Nand 本身的语义，就是在 And 的结果上套了 Not，所以想得到 And 就是在 Nand 上再套一次 Not。

AND = Not(Nand(a = a, b = b))

接下来的 Or 门实现的难度主要在逻辑学上了。 首先需要知道 De Morgan’s laws， 理解 OR = NOT( NOT(a) AND NOT(b) ) 之后，再实现电路就比较简单了。

有了 OR 之后再实现 XOR 也是一样组合逻辑： XOR = (A AND NOT B) OR (NOT A AND B)

Mux 的实现与 XOR 有点相似，只不过多了一个变量 SEL: MUX = (a AND NOT sel) OR (b AND sel)

DMux 稍微有些不同，虽然是组合逻辑，但其有了两个可能的输出，在写 HDL 的时候也会需要写两个 OUT：

IN in, sel
OUT a, b

a = in AND NOT sel
b = in AND sel

Multi-bit gate 很简单，就是对着输入的每一位复制粘贴单 bit 的 gate 操作：

Mux(a = a[0], b = b[0], sel = sel, out = out[0]);
Mux(a = a[1], b = b[1], sel = sel, out = out[1]);
Mux(a = a[2], b = b[2], sel = sel, out = out[2]);
Mux(a = a[3], b = b[3], sel = sel, out = out[3]);
...

但 Multi-way gate 就需要发挥一些想象力了。比方对于一个 4 way 的 Mux 操作，sel 会是 2 bit 的输入，对于不同的 sel 组成，这里列出所有可能的输出:

对于 Multi-way 的 gate 实现，需要用一种淘汰赛的思维方式来 reduce 输出可能性。 在上面的表格中，可以把 sel[0] 分为一组可能输入，把 sel[1] 分为一组可能输入。 将这两组分别 Mux 到一个内部 pin 上：

Mux(a = a, b = b, sel=sel[0], out = tmp0);
Mux(a = c, b = d, sel=sel[0], out = tmp1);

在 sel[1] 为 0 的时候，tmp0 管线就有 a 或者 b 的输出，而在 sel[1] 为 1 的时候，tmp1 就有着 c 或者 d 的输出。 最后再将这两个 tmp 管线 Mux 一下，就能得到最终输出：

Mux(a = tmp0, b = tmp1, sel=sel[1], out = out);

对于一个 N way 的 Mux，我们都可以嵌套套用 N/2 way 的 Mux gate 来组合实现。

DMux 也是类似的思路，只不过相对于 Mux 而言需要采取镜像反转的思考方式： 先将一条输入 DMux 到 Log2n 的管线上，然后将管线分组对应的pin脚，对着不同的管线连线 DMux 门：

// 4-way DMux
DMux(in = in, sel = sel[0], a = ac, b = bd);
DMux(in = ac, sel = sel[1], a = a, b = c);
DMux(in = bd, sel = sel[1], a = b, b = d);