II. Arithmetic

Numbers

Radix-Based System

• 最高有效位(Most Significant Digit, MSD)：$A_{n-1}$
• 最低有效位(Least Significant Digit, LSD)：$A_{-m}$

Binary Representations

对于正数而言，原码=反码=补码；而对于负数：

• 原码(sign-magnitude)：符号位为 1，其余位和其相反数的表示相同。
• 反码(1’s complement code)：在其相反数的表示的基础上取反。
• 补码(2’s complement code)：在其相反数的表示的基础上取反并 + 1。

另外，一些场合（比如：IEEE754 标准浮点数的指数部分（阶码））还会用到移码：

• 移码(biased notation)：统一加上一个固定常数并用无符号整数的方法表示。

ALU

1-bit ALU

AND 和 OR 的功能可以直接使用对应的电路门。

加法功能通过 一位全加器(1-bit full adder) 实现（后面直接用“方括号内加号”的组合来表示全加器）：

为了实现减法器，多一个 Binvert 输入控制（而不是通过 Operation 控制）是否需要将输入 B 取反并将第一个 CarryIn 设 1，因为减一个数就相当于加上这个数的补码。

这样的 1-bit ALU 已经实现了最基本的 AND、OR、加法、减法四种功能。

Complete ALU

可以直接把 1-bit 连接起来拼成一个 $n$ 位的 ALU。这样的设计虽然简单，但是速度慢。

真实的 ALU 每个部分都应是用更快的电路实现的，最后通过一个 MUX 实现选择。

• Zero detection：给输出加一个或非门，即可作为一个判断结果是否为 0 的输出。

Overflow Detection

两个数的和或差可能超过可以被表示的范围，这种情况下就是发生了 溢出(overflow)，ALU 可以支持溢出检测。

• 对于有符号数运算，正数和正数相加得到负数，或者负数和负数相加得到负数，就可以认为发生了溢出。这里正数包括 $0$。
• 对于无符号数运算，两个数相加的结果小于其中任何一个数，就可以认为发生了溢出。

一般来说，实现上我们需要将结果扩展一位，并和最高位综合进行检测。

Comparison

两个计算时会发生 overflow 的数也可以进行比较，比如 127 减 -128。这时可以通过符号位得到结果，而不用担心减法产生溢出。

Faster Adders

• 所有的组合逻辑都可以通过二级逻辑表示（但是其硬件代价可能极高）。

Carry Lookahead Adder

超前进位加法器(Carry Lookahead Adder, CLA) 通过“超前进位”的方式改进 行波进位加法器(Ripple Carry Adder, RCA) 中后一位必须等待前一位进位结果的问题。关于加法中的进位，可以视为两种条件：

• 生成(generate)：记作 $G_i=A_i \cdot B_i$，即第 $i$ 位两位相加本身是否会产生进位。
• 传播(propagate)：记作 $P_i$，接到低位的 $G_j$ 一起，用来表示进位逐步上传的过程。

CLA 的底层也可以不是 1 bit Adder，而是另一个 CLA，如两层 4 bit CLA 嵌套就可以实现 16 bit 加法器。

Carry Select Adder

进位选择加法器(Carry Select Adder, CSA) 通过在加法器中添加一个选择器，在计算时同时计算两种情况，然后根据进位选择结果。

CSA 和 CLA 没有一定优劣，在实际优劣中，我们可以根据对性能快还是面积小的需求选择合适的加法器。

Multiplier

Unsigned Multiplication

Approach 1

按照竖式乘法的算术法则实现。

具体过程：执行以下步骤 64 次：

1. 判断 Multiplier 寄存器的最低位是否是 1：
2. 如果是，则将 Multiplicand 寄存器的值加到 Product 寄存器里；
3. 如果否，进入下一步；
4. 将 Multiplier 寄存器的值右移一位（这是为了不断拿出每一位，相当于在枚举 Multiplier 的每一位），将 Multiplicand 寄存器的值左移一位（对应于和 Multiplier 的第几位乘得到的位移，具体参考上面的链接内容）；
5. 判断是否做满 64 次，决定是否终止；

Approach 2

只在 Product 的左半部分应用加法，这样 ALU 的大小可以减半。

具体过程：执行以下步骤 64 次：

1. 判断 Multiplier 寄存器的最低位是否是 1：
2. 如果是，则将 Multiplicand 寄存器的值加到 Product 寄存器的左半部分里；
3. 如果否，进入下一步；
4. 将 Multiplier 寄存器的值右移一位，将 Product 寄存器的值右移一位；
5. 判断是否做满 64 次，决定是否终止；

Approach 3

把 Multiplier 寄存器和 Product 寄存器进行合并，每次只有一个寄存器需要右移。

具体过程：先将 Multiplexer 放到 Product 寄存器的低 64 位，然后执行以下步骤 64 次：

1. 判断 Product 寄存器的最低位是否是 1：
2. 如果是，则将 Multiplicand 寄存器的值加到 Product 寄存器的左半部分里；
3. 如果否，进入下一步；
4. 将 Product 寄存器的值右移一位；
5. 判断是否做满 64 次，决定是否终止；

Signed Multiplication

上面的乘法不能用补码，只能先进行绝对值的乘法，再把符号位单独处理并应用到结果上。

使用 Booth’s Algorithm 可以实现基于补码的乘法（仅了解）。

• 注意 算术右移(arithmetic shift right) 时应保持符号位不变，最高位补符号位。

Parallel Multiplier

我觉得这个图放在这里本身就有问题。

（TBD：我不理解！）

Division

TBD

Unsigned Division

Approach 1

Approach 2

Approach 3

Faster Division

与乘法不同，除法不能通过循环展开来并行。一些其它的加速方法如 SRT Division 仍需要多步。

Floating Arithmetic

IEEE 754 Representation

• 符号位：一般来说正数就是 0 负数就是 1。
• 尾数：去除符号位后应被移到 $1.\text{xxxxx}$ 的形式，所以最高位的 1 可以被省略（称为 hidden 1）。
  • 对于一些不使用 hidden 1 策略的表示方式则移到 $0.1\text{xxxxx}$ 的形式，注意不同的方式会影响阶码的值。
• 指数：用移码表示，单精度浮点数的 偏移(bias) 为 $127$，双精度浮点数的偏移为 $1023$（刚好是范围的一半）。

$-0.75$ 的单精度、双精度表示

一些特殊值：

• NaN：Exponent = 111…1, Fraction ≠ 000…0
• Infinity：Exponent = 111…1, Fraction = 000…0

单精度、双精度表示法的范围和精度

Floating Point Addition

• Step 1：对齐(alignment)，即让两个数的指数相同，不能表示的位（被移出的位）将被舍弃。这里还需要补上前面被省略掉的尾数最高位。
• Step 2：将对齐后的小数部分进行相加。
• Step 3：规格化(normalization)，将其移位直到符合标准。
• Step 4：上溢(overflow) 或 下溢(underflow) 检测。
• Step 5：舍入(rounding)，将结果舍入到最接近的值。
• Step 6：还需要再进行一次规格化，因为 rounding 时可能产生了进位。

Round Modes

• guard bit：最低有效位
• round bit：最低有效位右边的第一位
• sticky bit：只要 round bit 右边出现过非零位，就将 sticky bit 置 1。在加法的右移过程中，可以记录是否有 1 被移出，从而能够实现 “round to nearest even”。

Floating Point Multiplication

• Step 1：add exponents
• Step 2：multiply the significands
• Step 3：normalise
• Step 4：over/under-flow detection
• Step 5：rounding
• Step 6：sign（依据输入数的符号确定结果的符号）