Chapter 9 Arithmetic(6)

这一章是很难的，不过我打的就是精锐。😎

Booth algorithm Directly handle the multiplication with signed numbers

因为可以处理有符号数，因此相比上一节的算法有了更加洋气的名字吗？

引言

直接的乘法方法在负操作数或两个负操作数的情况下不起作用。
示例: $M = 1001, Q = 0011$，计算 $P = M × Q $
- 直接的乘法，$P = 00011011 $
- 如果将 M, Q 和 P 视为无符号非负数，$M = 9，Q = 3，P = 27 $
- 如果将 M, Q 和 P 视为带符号的 2 的补码数，$M = 7，Q = 3，P = 27 $

不起作用

为什么直接的乘法不适用？
- 示例: $M = 1001, Q = 0011 $

进行符号拓展后的计算才是对的，因此，直接的乘法是不可以的。

转换为无符号数，进行乘法运算，然后再转换回带符号数
- 这种方法可行，但较慢且有些繁琐。
布斯算法可以直接处理带符号数的乘法
- 通过重新编码乘数的位
- 直接与 2 的补码数一起工作

布斯算法通过优化乘法的处理方式，尤其是对于带符号数，能显著提高效率。

Booth算法

1. Booth 算法简介

Booth 算法是一个有效的二进制乘法算法，可以减少部分积的数量。其主要思想是通过对乘数的位进行分组，来减少乘法运算中的加法次数。

减少部分积的数量：

对于乘数中的连续$ 0$ 的组，不会产生新的部分积，只需要将部分积右移一位即可。
对于乘数中连续的 $m$ 个 1 的组，生成的部分积数量少于 $m $个。

2. 乘数的重新编码

Booth 算法通过重新编码乘数来优化计算，具体步骤如下：

对于每一组连续的 1 或 0，将其重新编码为更简洁的部分积。

示例： 对于乘数$ 0011110$，重新编码为 $0100000 和 0000010$。这种方法减少了需要计算的部分积。

3. Booth 算法的操作示例

步骤如下：

将被乘数$ M$ 和乘数 $Q $放入寄存器 $A$ 和 $Q $中。
用控制逻辑逐位扫描乘数 $Q$，同时检查其右侧的$ Q₀ $位。
根据扫描结果调整 $A $和 $Q$ 的值，完成必要的加法和右移操作。

通过这种方式，能够有效减少需要计算的部分积。

4. 硬件组织

在硬件实现时，Booth 算法要求：

将被乘数 M 和乘数 $Q$ 分别放入寄存器$ A$ 和 $Q $中。
需要一个额外的 1 位寄存器 $Q₁ $来记录乘数$ Q$ 的右侧位。
控制逻辑逐位扫描乘数 $Q $和 $Q₁$，通过加法、移位等操作得出最终结果。

5. Booth 算法流程图

算术右移（Arithmetic Shift Right）

算术右移是一种移位操作，它不仅会将二进制数向右移动，而且会考虑符号位的处理，以确保结果的符号不发生错误。在算术右移操作中，最左侧的符号位（也就是 A 的最高位）会保持不变，从而维持数值的符号。

操作说明：

对于一个二进制数 A，如果进行算术右移，则：

A 中的每一位都将向右移动一位。
最左侧的位（即符号位）会复制到移位后的空位中，确保符号位保持不变。
右侧空出的位用零填充。

假设有一个 4 位的二进制数 A = 1101，表示十进制数 -3（假设使用补码表示法）。

算术右移后，A 的移位过程如下：

1 2	原数： 1101 (-3，补码表示) 算术右移1位： 1110 (-2，补码表示)

在这里，最左侧的符号位 1 保持不变，因此即使进行移位，符号也保持一致。

6. Booth 算法的优点

统一处理正负数的乘法：无论是正数还是负数，Booth 算法都能有效处理。
减少加法次数：当乘数中存在较长的 1 区间时，能够减少部分积的数量，优化计算效率。
运算速度：与普通的乘法算法相比，Booth 算法在平均情况下的速度是相同的，但能有效减少部分积的数量，提高计算效率。

7. Booth 算法的例子

好乘数（Good multiplier）:

1	000011111100001111

普通乘数（Ordinary multiplier）:

1	1100101101111100

最坏乘数（Worst case multiplier）:

1	0101010101010101

精华

Booth 算法通过对乘数进行优化编码，减少部分积的数量，能够提高乘法运算的效率，尤其是在处理有较多连续 1 的情况下。它在硬件实现中采用了简单的加法、移位操作，能够有效地处理带符号数的乘法运算。

Quiz

题目1：

在实现 Booth 算法的硬件电路中，乘数放在 Q 寄存器中，且在 Q 寄存器的最低有效位（Q₀）右侧，逻辑上放置一个 1 位寄存器 Q₁。乘法运算的结果会出现在 A 和 Q 寄存器中。在每个计算周期结束时，A、Q 和 Q₁ 会 ______ 1 位。

选项： A. 向左移位
B. 向右移位
C. 算术向左移位
D. 算术向右移位

正确答案：

D. 算术向右移位

解析：

在 Booth 算法的每个计算周期结束时，需要对 A、Q 和 Q₁ 进行 算术右移 操作。这是因为在 Booth 算法中，我们需要保持符号位（最左边的位）不变，因此是算术右移而不是逻辑右移。

算术右移的特点：

在算术右移过程中，符号位（即 A 的最高位）会被复制到新移位空出来的位置，以保持数值的符号正确。
这与逻辑右移不同，后者是简单地将所有位右移并填充零。

Booth 算法的右移操作：

A 和 Q 寄存器中的每一位向右移动一位。
最左侧的符号位（Aₙ₋₁）会被复制到移位后的空位，以确保符号位的正确性。
Q₁ 会进入 Q₀ 的位置，而 Q₀ 会被新的值替换。

题目 2：

关于 Booth 算法，下列哪项不正确？

选项：
A. 它可以统一处理正负乘数。
B. 当乘数有几个大的 1 区块时，它在所需加法数量上实现了一些效率。
C. 它的乘法速度总是比普通算法更快。
D. 乘数 111100110 会生成三个部分积。

正确答案：

C. 它的乘法速度总是比普通算法更快。

解析：

A 选项： Booth 算法确实能够统一处理正负数的乘法，使用补码表示法来处理符号，因此这项说法是正确的。
B 选项： Booth 算法能在乘数中有长的 1 区块时减少部分积的数量，从而提高效率，这项说法也是正确的。
C 选项： Booth 算法并不总是比普通算法更快。在乘数较小或没有连续 1 区块的情况下，Booth 算法可能不会比普通的乘法算法更快，反而可能更慢。因此这项说法是不准确的。
D 选项： 乘数 111100110 的确会生成三个部分积，这项说法是正确的，因为连续的 1 可以减少部分积的生成数量。

总结： 选项 C 是不正确的，Booth 算法的速度并不总是比普通算法更快。