第二十七课: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 0110y = 0000 0000 0000 0011
xReady=~x = 1111 1111 1111 1001yReady=~y = 1111 1111 1111 1100
selected = 1111 1111 1111 1000 // xReady & yReadyout = 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 的区别。学完告诉我,我们再按一次一题的方式练习。
这一页,先记到这里。