计算机补码一位乘法

补码乘法由英国人布斯（Booth）于 1950 年发明，又称为布斯（Booth）算法。

1、Booth 算法的推导

设 \([x]_{补} = x_0.x_1x_2...x_n\)，\([y]_{补} = y_0.y_1y_2...y_n\)。下面分两种情况来推导 Booth 算法。

1. 设被乘数 \(x\) 符号任意，乘数 \(y\) 符号为正，则：

\[ [x]_{补} = x_0.x_1x_2...x_n \quad [y]_{补} = 0.y_1y_2...y_n \]

根据补码的定义：

\[ \begin{equation} \begin{split} &[x]_{补} = (2 + x) \; mod \; 2 = (2^{n + 1} + x) \; mod \; 2（注 1） \\ &[y]_{补} = y \end{split} \end{equation} \]

\[ \begin{equation} \begin{split} [x]_{补} \times [y]_{补} &= [(2^{n + 1} + x) \; mod \; 2] \times y \\ &= [(2^{n + 1} + x) \times y] \; mod \; 2 \\ &= (2^{n + 1} \times y + x \times y) \; mod \; 2 \\ &= (2 \times y_1y_2...y_n + x \times y) \; mod \; 2 \\ &（这一块的证明见注 2） \end{split} \end{equation} \]

所以，

\[ \begin{matrix} [x]_{补} \times [y]_{补} = (2 + x \times y) \; mod \; 2 = [x \times y]_{补} \\ [x \times y]_{补} = [x]_{补} \times y \qquad \qquad (1) \end{matrix} \]

2. 被乘数 \(x\) 符号任意，乘数 \(y\) 符号为负，则根据补码定义：

\[ [x]_{补} = x_0.x_1x_2...x_n \quad [y]_{补} = 1.y_1y_2...y_n = 2 + y \]

所以：

\[ \begin{matrix} y = [y]_{补} - 2 = 1.y_1y_2...y_n - 2 = 0.y_1y_2...y_n - 1 \\ x \times y = x \times (0.y_1y_2...y_n - 1) = x \times 0.y_1y_2...y_n - x \qquad \qquad (2) \end{matrix} \]

对式 (2) 两边同时求补，并利用补码减法公式展开等式右边项可得：

\[ [x \times y]_{补} = [x \times 0.y_1y_2...y_n]_{补} - [x]_{补} \qquad \qquad (3) \]

根据式 (1) 可得：

\[ [x \times y]_{补} = [x]_{补} \times 0.y_1y_2...y_n - [x]_{补} \qquad \qquad (4) \]

将式 (1) 和式 (4) 综合起来，引入 \(y_0\) 位，即可得补码一位乘法的统一算式，即：

\[ [x \times y]_{补} = [x]_{补} \times 0.y_1y_2...y_n - [x]_{补} \times y_0 \qquad \qquad (5) \]

对于式 (5) 右边第二项 \([x]_{补} \times y_0\)，存在如下结论：

当 \(y\) 为正时，\(y_0 = 0\)，该项不存在；当 \(y\) 为负时 \(y_0 = 1\)，该项为 \([x]_{补}\)。

总结下来，就是以下的式子：

\[ \begin{equation} \begin{split} &[x \times y]_{补} = [x]_{补} \times y & \quad y \; 符号为正 \\ &[x \times y]_{补} = [x]_{补} \times 0.y_1y_2...y_n - [x]_{补} & \quad y 符号为负 \end{split} \end{equation} \]

\[ [x \times y]_{补} = [x]_{补} \times 0.y_1y_2...y_n - [x]_{补} \times y_0 \quad 不考虑 \; y \; 的符号 \]

接下来是推导从式 (5) 演变成适合计算机计算的迭代公式。

为了方便，我们把上面的式 (5) 放在这里：

\[ [x \times y]_{补} = [x]_{补} \times 0.y_1y_2...y_n - [x]_{补} \times y_0 \]

上面的式子可以展开成下面的形式：

\[ [x \times y]_{补} = [x]_{补} \times [(y_1 - y_0) + 2^{-1}(y_2 - y_1) + 2^{-2}(y_3 - y_2) + \cdots + 2^{-(n - 1)}(y_n - y_{n - 1}) + 2^{-n}(0 - y_n)] \]

然后，设 \([z_0]_{补} = 0\)，接着，

\[ \begin{equation} \begin{split} [z_1]_{补} &= 2^{-1} \{ [z_0]_{补} + (y_{n + 1} - y_n)[x]_{补} \} \\ [z_2]_{补} &= 2^{-1} \{ [z_1]_{补} + (y_{n} - y_{n - 1})[x]_{补} \} \\ \cdots &\cdots \\ [z_n]_{补} &= 2^{-1} \{ [z_{n - 1}]_{补} + (y_{2} - y_1)[x]_{补} \} \\ [x \times y]_{补} &= [z_{n + 1}]_{补} = 2^{-1} \{ [z_n]_{补} + (y_1 - y_0)[x]_{补} \} \\ \end{split} \end{equation} \]

上面的推导可以类比于高中时候学过的二项式：

\[ \begin{aligned} f(x) &= a_0 + a_1x + a_2x^2 + a_3x^3 \\ &= a_0 + x(a_1 + x(a_2 + x(a_3 + 0))) \end{aligned} \]

\[ \begin{aligned} S_0 &= 0 \\ S_1 &= x(S_0 + a_3) \\ S_2 &= x(S_1 + a_2) \\ S_3 &= x(S_2 + a_1) \\ S_4 &= S_3 + a_0 \end{aligned} \]

当然，其中有一点差异，就是我们的式子中，比如说

\[ [z_1]_{补} = 2^{-1} \{ [z_0]_{补} + (y_{n + 1} - y_n)[x]_{补} \} \]

有一项 \((y_{n + 1} - y_n)\) 的后面还乘上了一个 \([x]_{补}\)，这个我一开始也不理解，后来经同学点拨，我决定将推导过程中的前几个式子给展开看一下，结果发现每一个式子都可以把 \([x]_{补}\) 给提出来，那么，这个问题自然就解决了。

算法描述

• 在 \([y]_{补}\) 后添一个 \(0\) 作为 \(y_{n + 1}\)，令部分积为 \(0\)
• 如果 \(y_{n + 1} = y_n\)，部分积 \(+ \; 0\)，并将结果右移一位
• 如果 \(y_{n + 1} < y_n\)，部分积 \(+ \; [-x]_{补}\)，并将结果右移一位
• 如果 \(y_{n + 1} > y_n\)，部分积 \(+ \; [x]_{补}\)，并将结果右移一位

2、举例应用

已知 \(X = +0..1101\)，\(Y = +0.1011\)，用补码一位乘法求 \(X \times Y\).

\[ 解：[X]_{补} = 0.1101 \quad [Y]_{补} = 0.1011 \quad [-X]_{补} = 1.0011 \]

\[ \begin{equation} \begin{split} &部分积 \qquad & 乘数 \qquad \quad & 说明 \\ &00.0000 \qquad & 0.10110 & \\ {+} \; &11.0011 \qquad & & Y_{n + 1} < Y_n, 部分积 +[-X]_{补} \\ ···& ········& & \\ &11.0011 \qquad & & \\ \rightarrow \; &11.1001 \qquad & 1001011 & 将结果右移一位 \\ {+} \; &00.0000 \qquad & & Y_{n + 1} = Y_n, 部分积 + 0 \\ ···& ········ & & \\ &11.1001 \qquad & & \\ \rightarrow \; &11.1100 \qquad & 11.0101 & 将结果右移一位 \\ {+} \; &00.1101 \qquad & & Y_{n + 1} > Y_n, 部分积 + [X]_{补} \\ ···& ········ & & \\ &00.1001 \qquad & & \\ \rightarrow \; &00.0100 \qquad & 111.010 & 将结果右移一位 \\ {+} \; &11.0011 \qquad & & Y_{n + 1} < Y_n, 部分积 + [-X]_{补} \\ ···& ········ & & \\ &11.0111 \qquad & & \\ \rightarrow \; &11.1011 \qquad & 1111.01 & 将结果右移一位 \\ {+} \; &00.1101 \qquad & & Y_{n + 1} > Y_n, 部分积 + [X]_{补} \\ ···& ········ & & \\ &00.1000 \qquad & & \end{split} \end{equation} \]

所以

\[ \begin{equation} \begin{split} [XY]_{补} &= 0.10001111 \\ XY &= 0.10001111 \end{split} \end{equation} \]

---

注释：

1、小数的补码，按照定义应该是：

设二进制小数 \(X = \pm 0.x_{-1}x_{-2}...x_{-m}\)，则其补码定义为

\[ [X]_{补} = \left\{\begin{matrix} \begin{aligned} &X & 0 & \leqslant X < 1 \\ &2 + X & -1 & \leqslant X < 0 \\ \end{aligned} \end{matrix}\right. \]

上面的式子可以归结成一个式子：

\[ [X]_{补} = (2 + X) \; mod \; 2 \qquad -1 \leqslant X < 1 \]

2、在上面的推导过程中，隐含地用了下面的关系：

设 $ -1 < x, y < 1 $，则有

\[ [(2^{n + 1} + x) \; mod \; 2] \times y = [(2^{n + 1} + x) \times y] \; mod \; 2 \]

下面我门来证明这个式子。

1. \(x \in (0, 1)\)，

\[ 左式 = x \times y \]

对于模运算，有这样的运算法则：

\[ (a \times b) \; mod \; p = [(a \; mod \; p) \times (b \; mod \; p)] \; mod \; p \]

所以有

\[ [(2^{n + 1} + x) \; mod \; 2 \times y \; mod \; 2] \; mod \; 2 = (x \times y) \; mod \; 2 = x \times y \]

所以有 \(左式 = 右式\)。

2. \(x \in (-1, 0)\)，

\[ 左式 = (2 + x) \times y \]

\[ 右式 = [(2 + x) \times y] \; mod \; 2 = (2 + x) \times y \]

所以有 \(左式 = 右式\)。

综上，原式的正确性得证。

对于边界情况，即 \(x = 0 \; or \; 1 \; or \; -1\) 时候，我想，计算机应该有更好的方法直接就把结果给计算出来了，这里就不再赘述。

3、电路图逻辑实现

首先说明一下正方形方框充当的是缓冲器的角色。

然后，解释一下下面的部分：

• 左边，当 \(y_{n + 1} > y_n\) 时，与门输出为 1，这时，X 直接送上去；
• 右边，当 \(y_{n + 1} < y_n\) 时。与门输出为 1，这时，X 按位取反加一，利用的是：\([-X]_{补} = [X]_{补}\) 先按位取反然后在末尾加一。

然后，图中的 \(R_0, \; R_1\) 表示的寄存器（Register），在实际运作过程中，P 和 Y 都要移位。

最后，这个图仅仅是逻辑实现的示意图，其中还是隐藏了一些具体的细节的。