The Road Ahead week2 Boolean Arithmetic and the ALU

“The great wall is made by blocks”

二进制加法

半加器

我们考虑最基本的二进制加法,两位相加,然后再扩展到高位上。对于一个对a, b两位相加的加法器,我们称其为半加器,输入是a, b两位,输出为和sum以及进位carry

图片名称

半加器实际上就是不考虑输入进位的加法器

全加器

现在我们考虑进位,引入全加器,即在输入端考虑有进位的情况,全加器的真值表如下:

c b a sum(out) carry(out)
0 0 0 0 0
0 0 1 1 0
0 1 0 1 0
0 1 1 0 1
1 0 0 1 0
1 0 1 0 1
1 1 0 0 1
1 1 1 1 1

实际上全加器就是计算( a + b + carry),可以用两个半加器实现,实现方式如下:

图片名称

多位加法器

现在我们来考虑如何实现多位加法,一样的道理,对于每一位运算,我们可以使用一个全加器,对于第一位,输入的carry设置为0即可,也不难,这里来直接给出HDL实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
// 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:
HalfAdder(a = a[0], b = b[0], sum = out[0], carry = c0); // The first bit not have a carry, use a half adder
FullAdder(a = a[1], b = b[1], c = c0, sum = out[1], carry = c1);
FullAdder(a = a[2], b = b[2], c = c1, sum = out[2], carry = c2);
FullAdder(a = a[3], b = b[3], c = c2, sum = out[3], carry = c3);

FullAdder(a = a[4], b = b[4], c = c3, sum = out[4], carry = c4);
FullAdder(a = a[5], b = b[5], c = c4, sum = out[5], carry = c5);
FullAdder(a = a[6], b = b[6], c = c5, sum = out[6], carry = c6);
FullAdder(a = a[7], b = b[7], c = c6, sum = out[7], carry = c7);

FullAdder(a = a[8], b = b[8], c = c7, sum = out[8], carry = c8);
FullAdder(a = a[9], b = b[9], c = c8, sum = out[9], carry = c9);
FullAdder(a = a[10], b = b[10], c = c9, sum = out[10], carry = c10);
FullAdder(a = a[11], b = b[11], c = c10, sum = out[11], carry = c11);

FullAdder(a = a[12], b = b[12], c = c11, sum = out[12], carry = c12);
FullAdder(a = a[13], b = b[13], c = c12, sum = out[13], carry = c13);
FullAdder(a = a[14], b = b[14], c = c13, sum = out[14], carry = c14);
FullAdder(a = a[15], b = b[15], c = c14, sum = out[15], carry = c15); // Omit the carry when do last bit add
}

这个加法器的一个问题是进位信号在16个门之间传递,效率比较低,有一种方法叫做carry look ahead,即超前进位加法器,优点是速度快,缺点是器件会增加很多:

图片名称

负数

如果我们用最高位表示符号,即可得到负数,$-x$可以使用如下公式进行计算:

例如对于二进制1001 (9),对应的负数为$-(2^{4}-9) = (-7)$,我们称$9$为$-7$的补数,此处我们给出一个重要结论,两个负数相加可以表示为它们的补数相加:

由于我们抛弃了最高位,因此得到的补数和所需的负数结果相同。现在我们需要考虑给定一个数$x$,如何获取他的负数$-x$?这样我们就可以将减法转化为加法:$y-x=y+(-x)$。即我们需要如下芯片:

$\textrm{Input}: x$

$\textrm{Output}: -x$

这里我们运用一个小技巧:为了计算$(2^{n}-x)$,我们可以计算$2^n-x=1+(2^{n}-1)-x$,这样做的好处是$2^{n}-1$全部为1,做减法不需要借位,只需要将被减数按位翻转即可,所以这里我们得到了最终的结论,很重要,记住:一个负数等于其正数按位翻转后+1

算数逻辑单元(ALU)

现在我们来构造CPU中最重要的模块:ALU,其模块图如下所示:

图片名称

ALU:输入两个操作数和待执行的函数(算数或逻辑运算),给出指定结果,对于本课程的Hack ALU,其结构如下所示:

图片名称

根据六个输入控制位zx, nx, zy, ny, f, no,可以选择不同的操作,Hack ALU支持的操作如下:

输出立即数 一元逻辑运算 二元逻辑运算 数学运算
0 x x & y -x
1 y x \ y -y
-1 !x x+1
!y y+1
x-1
y-1
x+y
x-y
y-x

同时,该ALU还有两个输出控制位zr, ng,表示输出是否为0或者为负数,ALU的HDL代码框架如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Chip name: ALU
Inputs: x[16], y[16], // Two 16-bit data inputs
// Your ALU should first deal with zx, then nx
zx, // Zero the x input
nx, // Negate the x input
zy, // Zero the y input
ny, // Negate the y input
f, // Function code: 1 for Add, 0 for And
no // Negate the out output
Outputs: out[16], // 16-bit output
zr, // True iff out=0
ng // True iff out<0
Function: if zx then x = 0 // 16-bit zero constant
if nx then x = !x // Bit-wise negation
if zy then y = 0 // 16-bit zero constant
if ny then y = !y // Bit-wise negation
if f then out = x + y // Integer 2's complement addition
else out = x & y // Bit-wise And
if no then out = !out // Bit-wise negation
if out=0 then zr = 1 else zr = 0 // 16-bit eq. comparison
if out<0 then ng = 1 else ng = 0 // 16-bit neg. comparison
Comment: Overflow is neither detected nor handled

控制位的真值表如下:

图片名称

参考文献

0%