15、P1 W2 U2.6 总结、作业2答案
视频：
如果本次课程对应的 Coursera 的视频打不开，可以点击下面链接
P1W2U2.6 - Perspectives
软件：
全课程所需软件项目包官方下载：
https://www.nand2tetris.org/software
备了一份软件项目包放在CSDN了，版本2.6支持Mac、Linux、Windows：
https://download.csdn.net/download/shazizm/11268147
常见问题：
- 第二周做的这些芯片（逻辑单元）是标准的吗？
大部分是，但ALU是经过简化的。 - 为什么ALU没有设计更多的操作？
优化为了至简，这样就能在硬件模拟器中实现。 - 这些芯片（逻辑单元）是高效的吗？
大部分是。但比如加法器，就会有更优化的设计。 - 为什么建议每周先使用硬件模拟器里内建的芯片（逻辑单元）？
方便定位每周的设计错误。
求：
HalfAdder
FullAdder
Add16
Inc16（自加1）
ALU
一、HalfAdder （半加器）
已知下图：
完成 HalfAdder.hdl
提示：可以用两个基础逻辑门组成
1、真值表
已知 Half Adder
2、布尔函数
两个输出 sum 、carry 。老师貌似没提怎么处理这种情况。和上周作业DMux类似,就写两个试试吧。
提醒：真值表转布尔函数，我总结了一个
假设输出是单项的，先看输出项(例如上图sum)有1的行。
在这行(例如上图第2行)看输入项为0加Not（例如上图2行的a项就写成Nota），多项输入间用And（Nota And b）。
多行输出有1的（例如上图第2行 和 第3行），用Or连接。
如果输出是多项的（sum 和 carry），自己写自己的。。。
//sum
(Not(a) And b) Or ( a And Not(b) ) // 如果你不知道这是怎么来的，回忆一下上周作业吧
//carry
a And b
3、HDL
根据运算优先级：（）> not > and > or 写硬件语言
// This file is part of www.nand2tetris.org
// and the book "The Elements of Computing Systems"
// by Nisan and Schocken, MIT Press.
// File name: projects/02/HalfAdder.hdl
/**
* Computes the sum of two bits.
*/
CHIP HalfAdder {
IN a, b; // 1-bit inputs
OUT sum, // Right bit of a + b
carry; // Left bit of a + b
PARTS:
// Put you code here:
Not(in = a, out = nota);
Not(in = b, out = notb);
And( a = nota, b = b, out = notaandb);
And( a = a, b = notb , out = aandnotb);
And( a = a , b = b, out = carry);
Or(a = notaandb, b = aandnotb, out = sum);
}
4、测试
测试成功。
PS：第一周作业详情说了如何用 Hardware Simulator 硬件模拟器 进行测试。这里就贴一张图
Hardware_Simulator 本文最开始 软件处下载
二、FullAdder（带进位 全加器）
已知下图：
完成 FullAdder.hdl
提示：可以用两个半加器组成
1、真值表
已知 Full Adder
2、布尔函数
那上一个Half Adder 测试没问题。多输出(sum、carry)也可以按照机械的公式转换。
a、b、c 为输入
sum、carry 为输出
// sum
(Nota And Notb And c) Or
(Nota And b And Notc) Or
(a And Notb And Notc) Or
(a And b And c)
// 公式貌似东西有点多
// 转写成(~a)(~b)c + (~a)b(~c) + a(~b)(~c) + (abc)
// 用http://tma.main.jp/logic/index_en.html 简化一下。结果还是这个。。。HDL写起来就累一点了。
// carry
(Nota And b And c) Or
(a And Notb And c) Or
(a And b And Notc) Or
(a And b And c)
3、HDL
// This file is part of www.nand2tetris.org
// and the book "The Elements of Computing Systems"
// by Nisan and Schocken, MIT Press.
// File name: projects/02/FullAdder.hdl
/**
* Computes the sum of three bits.
*/
CHIP FullAdder {
IN a, b, c; // 1-bit inputs
OUT sum, // Right bit of a + b + c
carry; // Left bit of a + b + c
PARTS:
// Put you code here:
Not(in = a, out = nota);
Not(in = b, out = notb);
Not(in = c, out = notc);
//挑几个sum和carry复用的And
And(a = notb, b = c, out = notbc);
And(a = a, b = notc, out = anotc); //
And(a = b, b = notc, out = bnotc);
And(a = nota, b = b, out = notab);
And(a = a, b = b, out = ab);
And(a = ab, b = c, out = abc);
// sum
And(a = nota, b = notbc, out = notanotbc);
And(a = nota, b = bnotc, out = notabnotc);
And(a = anotc, b = notb, out = anotbnotc);
// carry
And(a = notab, b = c , out = notabc);
And(a = a, b = notbc , out = anotbc);
And(a = a, b = bnotc , out = abnotc);
// sum
Or(a = notanotbc, b = notabnotc, out = or1);
Or(a = anotbnotc, b = abc, out = or2);
Or(a = or1, b = or2,out = sum);
// carry
Or(a = notabc, b = anotbc, out = or3);
Or(a = abnotc, b = abc, out = or4);
Or(a = or3, b = or4,out = carry);
}
4、测试
测试成功
三、Add16
已知下图：
完成 Add16.hdl
貌似很简单，这个参考 And16，Or16 之类的，就是考虑一下进位怎么搞。
提示：可以由16个全加器组成。进位可以一个接一个。最后的进位忽略。
1、真值表
无
2、布尔函数
无
3、HDL
// This file is part of www.nand2tetris.org
// and the book "The Elements of Computing Systems"
// by Nisan and Schocken, MIT Press.
// File name: projects/02/Adder16.hdl
/**
* Adds two 16-bit values.
* The most significant carry bit is ignored.
*/
CHIP Add16 {
IN a[16], b[16];
OUT out[16];
PARTS:
// Put you code here:
FullAdder(c=false, a=a[0], b=b[0], sum=out[0], carry=c0); //最低位没有进位
FullAdder(c=c0, a=a[1], b=b[1], sum=out[1], carry=c1);
FullAdder(c=c1, a=a[2], b=b[2], sum=out[2], carry=c2);
FullAdder(c=c2, a=a[3], b=b[3], sum=out[3], carry=c3);
FullAdder(c=c3, a=a[4], b=b[4], sum=out[4], carry=c4);
FullAdder(c=c4, a=a[5], b=b[5], sum=out[5], carry=c5);
FullAdder(c=c5, a=a[6], b=b[6], sum=out[6], carry=c6);
FullAdder(c=c6, a=a[7], b=b[7], sum=out[7], carry=c7);
FullAdder(c=c7, a=a[8], b=b[8], sum=out[8], carry=c8);
FullAdder(c=c8, a=a[9], b=b[9], sum=out[9], carry=c9);
FullAdder(c=c9, a=a[10], b=b[10], sum=out[10], carry=c10);
FullAdder(c=c10, a=a[11], b=b[11], sum=out[11], carry=c11);
FullAdder(c=c11, a=a[12], b=b[12], sum=out[12], carry=c12);
FullAdder(c=c12, a=a[13], b=b[13], sum=out[13], carry=c13);
FullAdder(c=c13, a=a[14], b=b[14], sum=out[14], carry=c14);
FullAdder(c=c14, a=a[15], b=b[15], sum=out[15], carry=c15); //c15 一般就舍弃不考虑了
}
4、测试
测试成功
四、Inc16
已知下图：
完成 Inc16.hdl
注：这个本周貌似没有提到，应该是 一个 16bit的二进制数，加1。
提示：在HDL里 1位的0 或 1位的1，可以对应用 false 和 true 来代替。最后的进位忽略
1、真值表
无
2、布尔函数
无
3、HDL
// This file is part of www.nand2tetris.org
// and the book "The Elements of Computing Systems"
// by Nisan and Schocken, MIT Press.
// File name: projects/02/Inc16.hdl
/**
* 16-bit incrementer:
* out = in + 1 (arithmetic addition)
*/
CHIP Inc16 {
IN in[16];
OUT out[16];
PARTS:
// Put you code here:
Add16(a[0]=true, b=in, out=out); //老师这里给了提示，1bit = true 就可以代表一个二进制 “1”。
}
4、测试
测试成功
五、ALU
在写ALU这个作业时，还是很有感慨的，小时候有许多好奇和“魔术”，在成长的过程中一一被破解，生活中“原来如此”的惊喜越来越少。
记得小时候第一次接触电脑的时候，就种了一个“好奇”的草。叛逆
高中
姑娘
工作
辞职
喜悦
低谷
平静时隔20年，也许只有当平静时，初心才有机会闪耀。
已知下图：
完成 ALU.hdl
提示：会用到Add16和第一周做的逻辑门组成。HDL的代码可以少于20行。
1、真值表
无
2、布尔函数
无
3、HDL
貌似 zx、nx、zy、ny、f、no 6个输入。有一个输出用来选择不同公式。（如下图），但这个选择貌似跟 之前的真值表不是一个意思，没用吧。不能推导用。
再思考下图的处理顺序：
X[16] 先要 zx 处理后，再nx 处理。
Y[16] 先要 zy 处理后，再 ny 处理。
X[16] 和 Y[16] ，再f处理。
最后f的输出，no再后处理一下。
先按上面顺序写个“伪代码”吧
//X 预处理
zx = true, outzx = false //置零
zx = false, outzx = X
nx = true, outnx = Not16(outzx) //取反
nx = false, outnx = outzx
//Y 预处理
zy = true, outzy = false
zy = false, outzy = Y
ny = true, outny = Not16(outzy)
ny = false, outny = outzy
// 选择 function
f = true，outf = outnx Add16 outny //Add 运算
f = false，outf = outnx And16 outny // And 运算
// out 最后处理
no = true，out = Not16(outf) //取反
no = false, out = outf
用来选择的，有Mux,仔细思考，上面的伪代码"X预处理"部分再进一步转化一下，看起来“真HDL”了
Mux16(a = X, b = false, sel = zx，out = outzx )
Not16(in = outzx, out = notoutzx)
Mux16(a = outzx, b = notoutzx, sel = nx，out = outnx)
同理类似的都这么处理就行了。
另外有两个 zr 和 ng 输出标志位，需要琢磨搜索搜索。
“HDL真码”
// This file is part of www.nand2tetris.org
// and the book "The Elements of Computing Systems"
// by Nisan and Schocken, MIT Press.
// File name: projects/02/ALU.hdl
/**
* The ALU (Arithmetic Logic Unit).
* Computes one of the following functions:
* x+y, x-y, y-x, 0, 1, -1, x, y, -x, -y, !x, !y,
* x+1, y+1, x-1, y-1, x&y, x|y on two 16-bit inputs,
* according to 6 input bits denoted zx,nx,zy,ny,f,no.
* In addition, the ALU computes two 1-bit outputs:
* if the ALU output == 0, zr is set to 1; otherwise zr is set to 0;
* if the ALU output < 0, ng is set to 1; otherwise ng is set to 0.
*/
// Implementation: the ALU logic manipulates the x and y inputs
// and operates on the resulting values, as follows:
// if (zx == 1) set x = 0 // 16-bit constant
// if (nx == 1) set x = !x // bitwise not
// if (zy == 1) set y = 0 // 16-bit constant
// if (ny == 1) set y = !y // bitwise not
// if (f == 1) set out = x + y // integer 2's complement addition
// if (f == 0) set out = x & y // bitwise and
// if (no == 1) set out = !out // bitwise not
// if (out == 0) set zr = 1
// if (out < 0) set ng = 1
CHIP ALU {
IN
x[16], y[16], // 16-bit inputs
zx, // zero the x input?
nx, // negate the x input?
zy, // zero the y input?
ny, // negate the y input?
f, // compute out = x + y (if 1) or x & y (if 0)
no; // negate the out output?
OUT
out[16], // 16-bit output
zr, // 1 if (out == 0), 0 otherwise
ng; // 1 if (out < 0), 0 otherwise
PARTS:
// Put you code here:
// X预处理
// X预处理
Mux16(a = x, b = false, sel = zx, out = outzx);
Not16(in = outzx, out = notoutzx);
Mux16(a = outzx, b = notoutzx, sel = nx, out = outnx);
// Y预处理
Mux16(a = y, b = false, sel = zy, out = outzy);
Not16(in = outzy, out = notoutzy);
Mux16(a = outzy, b = notoutzy, sel = ny, out = outny);
// 选择 function
Add16(a = outnx, b = outny, out = outaddf);
And16(a = outnx, b = outny, out = outandf);
Mux16(a = outandf, b = outaddf,sel = f, out=outf);
// no 后处理
Not16(in = outf, out = notoutf);
// 这里out的多种表达方式，老师有提到吗？
// out[0..7] = outlow ... 出其不意的操作，不说谁知道啊？
Mux16(a = outf, b = notoutf,sel = no, out=out, out[0..7]=outlow, out[8..15]=outhigh, out[15]=ng);
// zr outno = 0时，zr = 1
Or8Way(in = outlow,out = outor8waylow);
Or8Way(in = outhigh,out = outor8wayhigh);
Or(a = outor8waylow,b = outor8wayhigh, out = nzr);
Not(in = nzr,out = zr);
//ng outno < 0时，ng = 1
//参考 https://www.jianshu.com/p/e15d757b1623 里观察，貌似out[15] 为1 就是负数。
}
4、测试
测试成功
太棒了，我们实现了CPU里最核心的部件了。不过别忘了我们是在老师已经设计好的蓝图下完成的。那蓝图又应该怎么思考得来呢？
下周就要进行存储相关的探索了，尤其软件程序的可存储化，在计算机历史上还是很重要的一个节点。标志着通用计算机的诞生。
另外 下周还会引入 时序逻辑。不准确、形象的解释一下就是之前两周学习的逻辑门电路，都是没有时序控制的。有点像“静”的。加入时序脉冲（电脑里常说的CPU频率就是在说明这个脉冲的快慢），特定的逻辑组合会有不同的特性，各个电路有了一个协调有序的节奏，这种在统一节奏下工作的逻辑电路，就叫时序电路了。时序的引入才使CPU“脉动”起来，不过遗憾的时，老师将这部分实现时序的电路省略了（可能无法用逻辑电路实现），在硬件模拟器里默认提供了。
换一种看法：如果我们到现在做好的ALU，比做一个静止机械的机器。那么只有通过引入脉冲来体现“时间”的流动，它才能看起来是运动的。
