计算机基础系列 —— 从 Nand 门到 ALU（2）

"Simplicity is the ultimate sophistication." ― Leonardo da Vinci

文中提到的所有实现都可以参考：nand2tetris_sol，但是最好还是自己学习课程实现一遍，理解更深刻。

冯诺依曼架构

I(键盘)/O（屏幕） 负责指令的输入和结果的展示，Memory(RAM 和 ROM) 用来储存指令，CPU(ALU, Registers) 进行指令的调度和计算。

二进制

莱布尼茨发明了二进制，计算机更习惯使用二进制（因为更容易存储、传输、etc.），而人类更习惯使用十进制。

表示

二进制的每一位称为 1bit。

二进制和十进制的相互转换：

负数的表示：

二进制表示负数要满足：code(x) + code(-x) = code(0)

二进制的位数 n 是固定的，假设 n=4，因为溢出的缘故， 对二进制来说等于 0（n=4，相当于第五位，实际上不存在，所以可以用  (相当于 ，满足上面的要求)表示负数。

计算

• 加法

x+y

• 减法

code(-y) = ()

x+(-y)

乘法和除法可以通过加法和减法实现。

算术逻辑单元 ALU（Arithmetic Logical Unit）

半加器

全加器

/** * Adds two 16-bit values. * The most significant carry bit is ignored. */

16-bit 加法器

/**
 * Adds two 16-bit values.
 * The most significant carry bit is ignored.
 */

16-bit 增量器

/**
 * 16-bit incrementer:
 * out = in + 1 (arithmetic addition)
 */

ALU

/**
 * 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

设计的 ALU 实在是太优雅了，只需要基础的几个组合逻辑单元，就可以实现计算机内部的一切复杂的运算。

我们可以看 x-y、y-1 的证明，确定 ALU 的设计是没有问题的。

• x-y

pre-setting the x input 结果：code(-x -1) (因为 code(-x) = code(1 + !x) = code(1 + 1111 - x) = )

pre-setting the y input 结果：code(y)

select between computing + or & 结果：code(-x - 1 + y)

post-setting the output 结果：code( - (-x - 1 + y) - 1 ) = code(x-y)

y -1

pre-setting the x input 结果： 

pre-setting the y input 结果：code(y)

select between computing + or & 结果： = code (y -1)

post-setting the output 结果：code(y-1)

到这里 ALU 就实现完毕了，接下来我们看寄存器（Register）和 RAM 的实现。