Booth 乘法算法

Booth 算法是一种乘法算法，允许我们分别用 2 的补码形式来计算两个带符号二进制整数的乘法。它还可以用于提高乘法过程的性能。它也非常高效。它基于乘数中的 0 位串，不需要额外的位，只需将最右边的位串右移；乘数中的 1 位串从权重 2^k 到权重 2^m 可以被认为是 2^{k+ 1} - 2^m。

Booth 算法的图示表示如下

在上面的流程图中，最初，AC 和 Q_{n + 1} 位被设置为 0，SC 是一个序列计数器，表示总的位数 n，等于乘数的位数。BR 表示被乘数位，QR 表示乘数位。之后，我们检查乘数的两位，即 Q_n 和 Q_{n + 1}，其中 Qn 表示 QR 的最后一位，Q_{n + 1} 表示 Qn 加 1 的位。假设乘数的两位为 10，这意味着我们需要从累加器 AC 中的部分积中减去乘数，然后执行算术右移操作 (ashr)。如果乘数的两位等于 01，这意味着我们需要将乘法器加到累加器 AC 中的部分积，然后执行算术右移操作 (ashr)，包括 Q_{n + 1}。算术右移操作在 Booth 算法中用于将 AC 和 QR 的位向右移一位，并保持 AC 的符号位不变。序列计数器持续递减，直到计算循环重复，等于位数 (n)。

Booth 算法的工作原理

1. 将乘数和乘数的二进制位分别设置为 M 和 Q。
2. 最初，我们将 AC 和 Q_{n + 1} 寄存器的值设置为 0。
3. SC 表示乘数 (Q) 的位数，它是一个序列计数器，持续递减，直到等于位数 (n) 或达到 0。
4. Qn 表示 Q 的最后一位，Q_n+1 表示 Qn 加 1 的位。
5. 在 Booth 算法的每个周期，将根据以下参数检查 Q_n 和 Q_{n + 1} 位：
   1. 当两位 Q_n 和 Q_{n + 1} 为 00 或 11 时，我们只需对累加器 AC 的部分积执行算术右移操作 (ashr)。Qn 和 Q_{n + 1} 的位会增加 1 位。
   2. 如果 Q_n 和 Q_{n + 1} 的位显示为 01，则将乘数位 (M) 添加到 AC (累加器寄存器)。之后，我们将 AC 和 QR 的位向右移动一位。
   3. 如果 Q_n 和 Q_{n + 1} 的位显示为 10，则将乘数位 (M) 从 AC (累加器寄存器) 中减去。之后，我们将 AC 和 QR 的位向右移动一位。
6. 操作将持续进行，直到我们在 Booth 算法中达到 n - 1 位。
7. 乘法二进制结果将存储在 AC 和 QR 寄存器中。

Booth 算法中使用两种方法

1. RSC (循环右移)

它将二进制数的右边最一位移出，然后添加到二进制位的开头。

2. RSA (算术右移)

它将两个二进制位相加，然后将结果向右移动 1 位。

示例：0100 + 0110 => 1010，将二进制数相加后，将每位向右移动 1 位，并将结果的第一位放到新位的前面。

示例：使用 Booth 乘法算法计算 7 和 3 的乘法。

答案。这里有两个数字，7 和 3。首先，我们需要将 7 和 3 转换为二进制数，例如 7 = (0111) 和 3 = (0011)。现在将 7 (二进制 0111) 设置为乘数 (M)，将 3 (二进制 0011) 设置为乘数 (Q)。SC (序列计数) 表示位数，这里我们有 4 位，所以设置 SC = 4。它还表示 Booth 算法的迭代次数，然后循环运行 SC = SC - 1 次。

Booth 乘法算法的数值示例是 7 x 3 = 21，21 的二进制表示是 10101。在这里，我们得到二进制结果 00010101。现在我们将其转换为十进制，(000010101)₁₀ = 2*4 + 2*3 + 2*2 + 2*1 + 2*0 => 21。

示例：使用 Booth 乘法算法计算 23 和 -9 的乘法。

这里，M = 23 = (010111) 和 Q = -9 = (110111)

Q_{n + 1} = 1，表示结果为负。

因此，23 * -9 = 111100110001 的 2 的补码 => (00001100111)