From Nand to Tetris week 1

这周开始学习From Nand to Tetris,中文名为“依据基本原理构建现代计算机:从与非门到俄罗斯方块”,课程介绍了计算机的工作原理,每周有一个项目,完成课程之后,可以真正构建出一个可以运行的计算机,课程也没有太多的先修课程,只要学过任何一门编程语言即可。

课程官网:

https://www.nand2tetris.org/

视频地址:

https://www.coursera.org/learn/build-a-computer

Chapter 1 布尔逻辑

Part 1:课程回顾

第一讲的内容比较基础,下面回顾几个重点部分:

Bool逻辑与Bool函数

课程首先介绍Bool逻辑的常用性质,这里假设我们只使用$\text{And,Not,Or}$操作。比较关键的一点是Bool表达式对应了真值表,例如

对应了

$x$ $y$ $z$ $f$
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 0
1 1 0 1
1 1 1 1

这部分表示Bool表达式$\Rightarrow$真值表,一个比较自然的问题是如何从真值表推出Bool表达式?

考虑如下例子:
| $x$ | $y$ | $z$ | $f$ |
| —— | —— | —— | —— |
| 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 0 |

构造方法很简单,首先考虑只在$f$取$1$的点处取$1$的表达式,例如此处为

然后将上述三个表达式取$\text{Or}$即得到目标表达式:

不难将上述方法推广到任意Bool表达式的构造,注意每个Bool函数可以用真值表表示,所以我们得到如下引理:

引理1

因为

所以实际上我们有更强的结论:

引理2

我们能否做的更好呢?不难看出在使用$\text{And,Not,Or}$的要求下,我们已经达到最优情形,因为$\text{Not}$无法表达$\text{And}$,反过来也是如此。但是如果可以使用别的逻辑操作,那么可以减少基础逻辑操作符的数量,考虑如下逻辑操作符$\text{Nand}$。

Nand门输入输出关系如下

$x$ $y$ $\text{Nand}(x,y)$
$0$ $0$ $1$
$0$ $1$ $1$
$1$ $0$ $1$
$1$ $1$ $0$

不难验证

所以有如下定理:

定理

本课程中使用的基础逻辑操作为$\text{Nand}$。

HDL(Hardware description language)

本课程使用HDL编程语言来设计逻辑电路,具体的形式如下:

1
2
3
4
5
6
7
/** Xor gate: out = (a And Not(b)) Or (Not(a) And b)) */
CHIP Xor {
IN a, b;
OUT out;
PARTS:
// Implementation missing
}

具体的使用方法可以参考课本附录以及官网,注意HDL无法编译运行,但是可以使用老师提供的模拟器查看输入输出,这部分在视频中有详细介绍。

Part 2:项目

第一次项目使用Nand门构造常用的逻辑单元。

Nand

Nand门输入输出关系如下

$a$ $b$ $\text{Nand}(a,b)$
$0$ $0$ $1$
$0$ $1$ $1$
$1$ $0$ $1$
$1$ $1$ $0$

Not

考虑$\text{Nand}(a,a)$

$a$ $a$ $\text{Nand}(a,a)$
$0$ $0$ $1$
$0$ $0$ $1$
$1$ $1$ $0$
$1$ $1$ $0$

说明

And

$\text{Nand}(a,b)$的特点,不难发现有

Or

XOR

XOR门输入输出关系如下

$a$ $b$ $\text{XOR}(a,b)$
$0$ $0$ $0$
$0$ $1$ $1$
$1$ $0$ $1$
$1$ $1$ $0$

所以有如下逻辑关系

Mux

Mux是选择器,输入为$a,b,\text{sel}$

$\text{sel}$ $\text{out}$
$0$ $a$
$1$ $b$

第一行相当于

第二行相当于

合并起来即为

DMux

DMux的作用如下:

  • if (sel==0)
    • {a,b}={in,0}
  • else
    • {a,b}={0,in}

真值表为

$\text{in}$ $\text{sel}$ $\text{Not}(\text{sel})$ $a$ $b$
$0$ $0$ $1$ $0$ $0$
$0$ $1$ $0$ $0$ $0$
$1$ $0$ $1$ $1$ $0$
$1$ $1$ $0$ $0$ $1$

从真值表中,不难看出我们有

Not16

这个比较简单,只要对每一位取$\text{Not}$即可,注意这里没有循环。

And16

对$a[16]$与$b[16]$每一位取$\text{And}$即可。

OR16

利用

Mux16

根据$\text{sel}$对$a[16]$与$b[16]$每一位取$\text{Mux}$即可。

Or8Way

逐步计算下式即可

Mux4Way16

Mux4Way16的作用如下

  • out = a if sel == 00
    • b if sel == 01
    • c if sel == 10
    • d if sel == 11

所以可以根据$\text{sel}[0]$在$a,b$之间以及$c,d$之间做选择,然后根据$\text{sel}[1]$在第一步的结果之间做选择。

(备注,$\text{sel}[0]$为最右边的数字)

Mux8Way16

Mux8Way16和Mux4Way16作用类似,是对$8$个输入做选择,先根据$\text{sel}[0..1]$对前四个以及后四个做选择,然后根据$\text{sel}[2]$在第一步的结果之间做选择。

DMux4Way

  • 4-way demultiplexor:
  • {a, b, c, d} =
    • {in, 0, 0, 0} if sel == 00
    • {0, in, 0, 0} if sel == 01
    • {0, 0, in, 0} if sel == 10
    • {0, 0, 0, in} if sel == 11

第一步只考虑$\text{sel}[0]$,使用DMux产生如下效果

{a1, b1, c1, d1} =

  • {in, 0, in, 0} if sel == 00
  • {0, in, 0, in} if sel == 01
  • {in, 0, in, 0} if sel == 10
  • {0, in, 0, in} if sel == 11

对应代码如下

1
2
DMux (in=in, sel=sel[0], a=a1, b=b1);
DMux (in=in, sel=sel[0], a=c1, b=d1);

第二步考虑$\text{sel}[1]$,使用Mux产生如下效果

{a, b, c, d} =

  • {in, 0, 0, 0} if sel == 00
  • {0, in, 0, 0} if sel == 01
  • {0, 0, in, 0} if sel == 10
  • {0, 0, 0, in} if sel == 11

对应代码如下:

1
2
3
4
5
Not (in=sel[1], out=notsel1);
Mux (a=a1, b=notsel1, sel=sel[1], out=a);
Mux (a=b1, b=notsel1, sel=sel[1], out=b);
Mux (a=sel[1], b=c1, sel=sel[1], out=c);
Mux (a=sel[1], b=d1, sel=sel[1], out=d);

DMux8Way

和DMux4Way一样的思路,分两步操作,根据$\text{sel}[0..1]$对$a,b,c,d$以及$e,f,g,h$用DMux4Way分别处理,然后利用根据$\text{sel}[2]$使用Mux处理。

本文标题:From Nand to Tetris week 1

文章作者:Doraemonzzz

发布时间:2019年04月24日 - 16:03:00

最后更新:2019年09月04日 - 23:58:47

原始链接:http://doraemonzzz.com/2019/04/24/From Nand to Tetris week 1/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。