第二十七课:ALU 没有 OR 部件,为什么能做 OR

从按位或的需求出发,推导输入取反、按位与和输出取反怎样协同工作,理解 no 控制位。

本章目录CONTENTS ↓

前两课已经接好了输入预处理,以及由 f 选择的 And16、Add16。但 Hack ALU 还需要计算 x | y,也就是按位或:每一位只要有一个输入是 1,输出就应为 1。

一个直接的方案是再接一颗 Or16,然后从 AND、加法、OR 三种结果中选择。这当然可行。现在换一个设计问题:利用已有的输入取反和 AND,能否得到 OR,少接一条独立的 OR 运算通路?

答案需要最后一个控制位 no:它决定是否对运算结果做按位取反(bitwise NOT)。先推导为什么需要这一步,再把它接进 ALU。

从 OR 的要求反推电路

先只看某一位,记两个输入为 a、b。OR 的要求可以换个角度表达:只有两者都为 0,输出才为 0;其余情况都输出 1。

我们已有的 AND 擅长判断“两者都为 1”。如果先把 a、b 各自取反,原本的“都为 0”就变成了“都为 1”。因此,(~a) & (~b) 恰好判断原始输入是否都为 0。

但它的输出方向与 OR 相反:

  • 原始输入都为 0:取反后都是 1,AND 得到 1;OR 需要的是 0。
  • 原始输入至少一个为 1:取反后至少一个为 0,AND 得到 0;OR 需要的是 1。

所以,再把 AND 的结果取反,就得到 OR:

a | b = ~((~a) & (~b))

这就是一条德摩根定律(De Morgan’s law)。上面的两种情况覆盖了全部输入,不是只靠某一个例子猜出规律。Not16、And16 都逐位工作,因此同样的推导适用于 16 位总线的每一位:x | y = ~((~x) & (~y))。这里的 ~ 始终表示对指定宽度内的每一位取反。组合逻辑:德摩根定律

现在每一步都有了对应的控制位:

控制位 取值 为了计算 OR,这一步要做什么
zx、zy 都为 0 保留原始输入,不置零
nx、ny 都为 1 得到 ~x 和 ~y
f 0 选择两者按位与的结果
no 1 对这个结果取反,得到 `x

按官方顺序 zx nx zy ny f no 写,就是 0 1 0 1 0 1。这组控制值是沿着公式推出来的;不需要先背下来。官方 Chapter 2:ALU 函数表

no 应该接在哪里

nx、ny 在运算之前处理输入;no 则在 f 选出结果之后处理输出:

x、y → 输入预处理 → AND / 加法 → f 选择结果 → no 决定是否取反 → out

设 f 选出的 16 位结果仍叫作 selected。no=0 时,out=selected;no=1 时,out=~selected。无论 f 选的是 AND 还是加法,都遵守这条规则。官方 ALU.hdl:输出处理规格

“保留还是取反”仍然是一次选择。保留上一课的六行输入预处理,将末尾三行扩展为下面五行即可:

And16(a=xReady, b=yReady, out=andResult);
Add16(a=xReady, b=yReady, out=sumResult);
Mux16(a=andResult, b=sumResult, sel=f, out=selected);
Not16(in=selected, out=invertedResult);
Mux16(a=selected, b=invertedResult, sel=no, out=out);

invertedResult 是我们自取的内部连线名。Not16 产生取反结果,最后的 Mux16 决定输出哪一路;no=0 并不表示 Not16 停止工作。

这里的取反不会自动加 1。例如 selected=0000 0000 0000 0110(6),no=1 得到 1111 1111 1111 1001(补码 −7),而不是 −6。no 的作用与 nx/ny 一样,都是按位取反,只是作用位置不同。

用完整的 16 位追踪一次 OR

取 x=6、y=3,设置刚才推导出的 zx=0、nx=1、zy=0、ny=1、f=0、no=1。

x = 0000 0000 0000 0110
y = 0000 0000 0000 0011
xReady=~x = 1111 1111 1111 1001
yReady=~y = 1111 1111 1111 1100
selected = 1111 1111 1111 1000 // xReady & yReady
out = 0000 0000 0000 0111 // ~selected

直接逐位 OR,0110 | 0011 = 0111,与最终结果一致。高十二位也符合规格:原始两侧都为 0,输入取反后都为 1,AND 得到 1,再由输出取反恢复为 0。

如果只把 no 改成 0,输出就会停在 1111 1111 1111 1000,得不到 OR。输出取反是在把“原始输入都为 0”的判断,变成“原始输入至少一个为 1”的判断。

这个设计带来了什么

我们已经有 nx/ny 和 AND;增加输出端的一颗 Not16 与一颗 Mux16 后,就能完成 OR,而且同一套输出处理也能用于加法结果。直接增加 Or16 的方案同样合理;这里的收益是复用现有运算部件,代价是需要推导各个功能对应的控制组合,信号还要经过额外的取反与选择部件。这是对当前电路的设计分析,不是对所有 ALU 的最优性结论。

在 Project 2 中,这一步补齐了主输出的六个控制位。后面学习 Hack CPU 时,指令需要执行按位或,就会由相应的控制组合驱动这些部件;电路中的 AND 不会因此变成 OR,而是前后变换让整个 ALU 完成了 OR 的功能。

本课先理解这一条信号链,不展开整张函数表。把接线补入官方 ALU.hdl 后,可以先用 ALU-nostat.tst 检查主输出;状态输出 zr、ng 留到下一课,补齐后再做完整测试。官方 Project 2:分阶段实现与测试

阅读或模拟时,重点核对 selected 和最终 out 的区别。学完告诉我,我们再按一次一题的方式练习。

这一页,先记到这里。