From Nand to Tetris week 2

这次回顾第二章的内容,这部分主要介绍了布尔运算,讲解了如何实现二进制加法,负数的表示以及算数逻辑单元(ALU)。

课程官网:

https://www.nand2tetris.org/

视频地址:

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

Chapter 2 布尔运算

Part 1:课程回顾

这部分回顾一些重点内容。

二进制加法

来看一个二进制加法的例子:

从上述例子不难看出,最后一位只要考虑两个数相加的问题,处理这部分使用HalfAdder,接口如下:

除最后一位以外,其余每一位还要考虑前一位的进位问题,所以要处理三个数相加的问题,处理这部分使用FullAdder,接口如下:

最后要注意计算机存储数字的位数是固定的,如果超过这个范围,就会产生溢出:

处理方法是直接不考虑溢出位。假设计算机存储的位数为$n$,那么$x+y$的结果为

负数

一个比较关键的问题是如何在计算机中表示负数,一个直接的想法是用第一位表示符号,$0$表示正数,$1$表示负数,但是这样$0$会有两个表示:

并且

实际中使用的是补码表示,即

现在考虑

由定义可得

所以这样定义的表示方式满足常见的负数加法运算,例如

因为

所以如果我们能计算出$-y$,那么减法运算可以直接获得。现在给定$x$,由定义可得

所以$(2^n-1)-x$表示对每一位取反的操作,因此$-x$可以通过对每一位取反然后加$1$得到。

算数逻辑单元(ALU)

首先回顾冯诺依曼结构计算机的基本组成部分:

这一部分介绍算数逻辑单元(ALU),一般的ALU输入输出如下:

其中$f$为一族事先定义好的算数和逻辑函数。该课程中编写的计算机名为Hack,其ALU的形式稍有不同:

其接口如下

通过真值表,不难验证其输出如下:

Part 2:项目

这一次的项目实现加法器以及算数逻辑单元(ALU)

HalfAdder

半加器对两个比特位进行加法,输入为$a,b​$,输出为和sum以及进位carry:

$a$ $b$ $\text{sum}$ $\text{carry}$
$0$ $0$ $0$ $0$
$0$ $1$ $1$ $0$
$1$ $0$ $1$ $0$
$1$ $1$ $0$ $1$

由上述真值表,不难看出

FullAdder

全加器对三个比特位进行加法,输入为$a,b,c$,实现思路很简单,先对$a,b$使用使用半加器,得到

然后对$c,d$使用半加器,得到

最后不难看出

Add16

计算16个比特位的加法,输入为$a[16], b[16]$,输出为$\text{out}[16]$。对$a[0],b[0]$使用半加器,得到$\text{sum}=\text{out}[0]$,记录进位$\text{carry}$,然后从第二位开始,使用全加器,计算$a[i],b[i]$和前一位的进位的和,以此类推。

Inc16

对16个比特位加$1$,第一位使用半加器加$1$,其余每位和上一位的进位相加即可。

ALU

根据提示即可,这里需要注意的一点是可以有多个输出:

1
Mux16 (a=out1, b=out2, sel=no, out=out, out[0..7]=o1, out[8..15]=o2, out[15]=ng);

本文标题:From Nand to Tetris week 2

文章作者:Doraemonzzz

发布时间:2019年04月30日 - 13:54:00

最后更新:2019年04月30日 - 14:02:11

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

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