What & How & Why

Boolean Arithmetic and the ALU

Week 2 notes


Binary Numbers

二进制数以 01 的组合表示各式各样的数据:n 位二级制数拥有 $2^n$ 的组合数量。

二进制表示数字

Binary to Decimal

二级制按照如下的规则转化为十进制:

  • 从左到右,从 0 开始,每一位的权为 $2^n$
  • 十进制的结果等于二进制数的带权和

比如下面的例子, 101 转化的的结果是 5



也就是如果有 k 位 Bit,最大能表达的数字为:

$$ 1 + 2 + 4 +...+2^{k-1} = 2^k - 1 $$

Fixed word size

计算机中字的长度是有限的,因此表示的范围也是有限的。理想情况下,一个 8 位的字可以表示 $2^8 = 256$ 个数字;但实际上,如果需要表示负数,那么 8 位的其中一位就会作为符号位,这样 8 bit 只能表示 0-127

Decimal to Binary

按之前转化的逆顺序:

  • 找出当前 10 进制中最大的,可以通过 2^n 计算出的数
  • 从当前数中减去该数
  • 重复上面两步,直到只剩 1($2^0$)

这个过程相当于是在还原二级制构造十进制的过程。因此,之前能找出来的数证明其对应的 Bit 上都是 1,反之都是 0。以 87 位例:



Binary Addition

二进制的加法与十进制类似,按位相加:



如果遇到 1+1 的情况,则进位。进位是逢 21

overflow

如果最后一位相加也需要进位,此时结果长度超出了字的长度。我们称该情况为加法溢出(overflow)。解决的方式是:忽略所有额外的进位。从计算机的角度来考虑,如果加法超出了字长的限制,那么我们做的加法,就不再是真正的加法了。

Adder 的设计

从这个思路出发,Adder 的设计分为:

  • Half Adder:负责两个 Bit 的相加
  • Full Adder:负责三个 Bit,即两个 Bit 与 carry 的相加
Half Adder

Half Adder 完成的工作是将两个 Bits 相加。那么:

  • 输入:两个 bits x, y
  • 输出:一个 bit (和),一个 carry(进位)

需要注意的是,两个 Bits 相加只和当前的 Bit 有关。只要是 1 + 1,那么进位就是 1,结果就是 0。因此,我们可以得到如下的真值表:

Full Adder

Full Adder 完成的工作是将两个 Bits 与 carry 位相加:

  • 输入:bit a, b, c
  • 输出:sum, carry

其真值表也非常容易得到:

Multi-bit Adder(16bits)

这个 adder 由一系列的 half adder 和 full adder 组成。准确的来说,是 15 个 full adder 与 1 个(最右边的)half adder 组合在一起,组成了 16 bits 的,带进位的加法计算器。

Negative Numbers

表示负数的方式有三种:

  • signbit(原码)
  • Complement (补码)

Signed Bit(原码)

这种方式使用二进制的最高位作为符号位,以此来区分正负数。其他位不变,比如:

000 -> 0 100 -> -0
001 -> 1 101 -> -1
010 -> 2 110 -> -2
011 -> 3 111 -> -3
这种方法通常不会采用,有几个大的缺点:

  • -0 的定义,它与 0 的区别无法解释
  • 加减法无法处理。比如 1 + (-1),也就是 001 + 101, 结果是 110,为 -2, 不是 0

2's Complement(补码)

这种方式下,所有的负数都用 bits 可以表示数字的总数来减去负数对应的整数,即: $$2^n-x$$ 比如:

// 4 bits, total numbers: 2^4 = 16
 3 -> 0011
// decimal
-3 -> 16 - 3 = 13 -> 2^3 + 2^2 + 2^0 -> 1101
这种情况下,正数的表达范围为 $[0, 2^{n-1} - 1]$,负数的表达范围为 $[-1, -2^{n-1}]$

补码的优势

使用补码表示负数可以将负数的加法(减法)转化为加法:

, 根据上面的例子,这个过程分为了三步:

  1. 求出负数的补码结果(正数,比如 $-2 = 16 - 2 = 14$)
  2. 将得到的正数转换为二级制相加
  3. 当存在 overflow 时,溢出位将被自动丢弃,比如此处 $14+13=27$,丢弃溢出位后结果为 $27-16 = 11$
  4. $11$ 是以补码形式,根据公式,负数的表现形式为:$2^4 - positiveNumber = 11$。可以得到正数的值为 $5$,因此 $11$ 对应的负数为 $-5$

计算 -x

上面计算负数的过程是将二进制转化为十进制来进行的。实际上,利用补码公式的变形,就可以很轻松的用二进制直接计算负数: $$ 2^n-x = 1 +(2^n-1) -x $$ 观察一下上面的变形,可以发现:

1 -> 1
2^n - 1 -> 11111....1111
那么也就是说,$-x$ 的实际结果,等于所有 bits 都是 $1$ 的数减去 $x$ 对应的二进制,再加上一。比如 $-2$,如果以 4 bits 的 二进制表示,就是:
16 - 2
-> 15 - 2 + 1
-> 1111 - 0010 + 1
-> 1101 + 1
-> 1110
从形式上来看,$x$ 的负数结果实际上是直接将 $x$ 的二进制按位翻转后再加上一得到的。

Arithmetic Logic Unit

Arithmetic Logic Unit (ALU) 在冯诺依曼架构中充当了很重要的角色。具体的来说:

  • ALU 扮演的是函数的角色,也就是接受输入,然后按指定的方法计算结果的的计算单元。
  • ALU 对应的函数是提前定义的,算术逻辑运算的一种(或是这两者的组合)

ALU 的设计在硬件和软件中均可实现。硬件实现下,ALU 的速度会更快,但成本会更高。

实例:Hack ALU

本课例子(HACK ALU):

  • 接收两个 16 bits 的输入
  • 得到一个 16 bits 的输出和两个 1 bits 的输出。
  • 实现了一系列的(总共18个)基础函数
  • 调用哪个函数通过结构图正上方的 6 个 1 bit 的输入来决定。

其结构图如下:


控制位与 16bits 输出位的真值表

Hack ALU 常用的 18 种运算的真值表如下:


上面 6 个控制位均在 0 和 1 时代表了两种不同的运算:



整个计算过程从左到右进行运算,前面的运算结果会作为下一次的算子参与新的运算。比如下面的例子:

// input
x = 0010
y = 1011

// calculation: y - x
// control bits sequence from the turth table
0 0 0 1 1 1

// compute process

zx = 0 // do nothing
x = 0010
y = 1011

zy = 0 // do nothing 
x = 0010
y = 1011

zy  = 0 // do nothing
x = 0010
y = 1011

ny = 1 // y = !y
x = 0010
y = 0100

f = 1 // out = x + y
x = 0010
y = 0100
out = 0110

no  = 1 // out  = !out
out = 1001

Add16:串行实现
  • 0 bit 使用 half adder 计算
  • 之后只需要将前一位计算的 carry 交给下一个Full adder 即可
Add16:Carry-ahead

之前的方法非常慢,必须等到前一个 adder 的结果出来之后才能下一步。我们可以通过 Carry-ahead 的方法进行 carry 位的并行计算。 可以观察到的是,当前 adder 中送到下一个 carry 位是可以根据如下的情况来判断的:

  • 如果参与计算的 bits a, b 都是 1,那么无论前一个 adder 传递来的 carry 位是什么,当前 adder 的 carry 位一定是 1,也就是 a and b
  • 如果参与计算的 bits 中存在一个 1,且前一位的 carry bit ci 是 1,那么当前 adder 的 carry 位是 1。判断条件为 (a or b) and ci

这里的第一部分(a and b)被称为 Generate 位(G),第二部分(a or b)被称为 Propagate 位(P)。也就是说当前 carry 位的值实际上取决于以下的表达式: $$C_{i+1} = G_{i}∨(P_{i} ∧C_{i})$$ 利用这个公式,我们可以对每一位的 $C_i$ 进行展开。也就是说,只要已知所有的 a, b,以及 0 位的 carry,那么所有的 adder 都可以直接对本位的 carry 进行计算, 比如第二位的 carry 公式就可以展开为: $$C_2=G_1​∨(P_1∧G_0)​∨(P_1∧P_0​∧C_0))$$

其他实现上的一些细节
  • Mux16if / else 的硬件实现,使用 sel 位来作为条件输入
  • 验证某个输出是否小于 0 只需验证其最高位,比如 out[15] 为 1 则该数为负
  • 验证某个输出是否等于 0 需要使用 OrNWay 对所有 bits 进行按位 Or。这样计算后:
    • 如果有任意 bit 为 1,那么 Or 的结果都为 1。此时输出是不等于 0 的,如果再将其翻转(Not)再输出至是否相等的 bit,此时为 0,也就是不相等。
    • 反之,按位 Or 全为 0,翻转后结果为 1,说明相等。