基4布斯算法

对任何计算设备而言，大数相乘是一项基本操作，但重复相加的朴素方法效率低下且速度缓慢。为了追求速度和效率，计算机架构师们开发了复杂的技术来更快地执行这项关键任务。这不仅仅是为了让数学运算更快，更是为了支持从高性能计算到高能效移动设备的一切。

设计乘法器的一个关键挑战在于管理必须生成和求和的大量中间步骤，即“部分积”。我们如何在不影响精度的情况下减少工作量？答案在于一种巧妙的视角转换，这体现在布斯算法及其强大的后继者——基4布斯算法中。

本文将深入探讨基4布斯算法的精妙世界。首先，在“原理与机制”部分，我们将揭示该算法背后的数学技巧，它能将二进制数重新编码为一种更高效的形式，用几次简单的移位和加/减操作代替大量的加法。随后，在“应用与跨学科联系”部分，我们将探讨该方法对硬件设计的深远影响，揭示它如何催生出更小、更快、更节能的乘法器电路，而这些电路是现代电子学的基础。

想象一下，你是一位生活在计算器诞生之前的会计。你的工作是日复一日地计算大数乘法。你很快就会意识到，乘法不过是重复加法的一个花哨说法。例如，将一个数 $M$ 乘以 13，意味着将 $M$ 自身相加 13 次。这个过程既繁琐又缓慢。然而，一个聪明的会计可能会注意到 $13 = 10 + 3$，从而计算 $(M \times 10) + (M \times 3)$。这要快得多。计算机的算术逻辑单元（ALU）面临着同样的挑战，只不过处理的是二进制数。通往基4布斯算法的历程，就是一个不断寻找更巧妙方法来实现“懒惰”与高效的故事。

让我们用二进制来思考。假设我们想将某个数，即​​被乘数​​ $M$，乘以 7。在二进制中，7 是 $\text{0111}$。一个直接的“移位-加法”乘法器会从右到左查看 $\text{0111}$ 的比特位：

• 第0位是1：加 $M$ (移0位)。
• 第1位是1：加 $M$ (移1位)，即 $2M$。
• 第2位是1：加 $M$ (移2位)，即 $4M$。
• 第3位是0：什么都不做。

结果是 $M + 2M + 4M = 7M$。这需要三次独立的加法操作。这个方法可行，但我们能做得更好吗？

如果我们注意到 $7 = 8 - 1$ 会怎么样？在二进制中，这相当于 $\text{1000} - \text{0001}$。乘以 7 的操作可以转变为一次减法：$(8M) - (1M)$。在计算机中，乘以 8 并非一次真正的乘法，而是一次简单且快如闪电的向左​​移位​​三位。因此，我们用一次移位和一次减法代替了三次加法。这是一次巨大的胜利！

这个简单的技巧是布斯算法的灵魂。它认识到，当从右到左扫描时，一长串的 1 可以被替换为：在串的开始处（0→1转变处）进行一次减法，并在串的结束之后的位置（1→0转变处）进行一次加法。例如，数字 $\text{00111100}$（即 60）可以看作是 $\text{01000000} - \text{00000100}$（即 $64 - 4$）。我们用一次减法和一次加法代替了四次加法。该算法通过扫描乘数的比特位，寻找这些 1 串的起点和终点，从而将这个技巧形式化。

最初的布斯算法（基2）是逐个（以重叠对的形式）查看比特位的。它很巧妙，但问题很快就出现了：既然可以大步前进，为何要迈小步呢？这就是​​基4布斯算法​​的用武之地。我们不再一次处理一个乘数比特，而是一次处理两个比特。

通过每步检查两位，我们有效地将操作次数减半。对于一个 $n$ 位乘数，我们只需要 $n/2$ 步而不是 $n$ 步。这意味着需要计算和相加的部分积更少，这直接转化为更小、更快、更节能的乘法器电路。但这是如何实现的呢？如果我们只看两位，比如 $\text{11}$（即 3），我们就需要计算 $3M$。这似乎使问题复杂化了，因为计算 $3M$ 并不像移位那么简单。我们需要一种更巧妙的方法。

秘诀在于，我们不孤立地看待这对（两位）比特，而是同时窥视前一个比特对的最后一位。这为我们提供了上下文。对于每一步 $i$，我们查看乘数 $Y = (\dots y_{2i+1} y_{2i} y_{2i-1} \dots)$ 中一个重叠的三位比特组。比特 $y_{2i-1}$ 是来自右侧的“进位”，它告诉我们当前是处于一串 1 的开头、中间还是结尾。

基于这个三位比特组，我们从一个出人意料的小集合 $\{-2, -1, 0, +1, +2\}$ 中生成一个“重新编码的数字”。这个数字告诉硬件在当前步骤中应该做什么。转换遵循一个简单的规则，可以用公式或查找表来表示。对于三元组 $(y_{2i+1}, y_{2i}, y_{2i-1})$，重新编码的数字 $d_i$ 的值由以下公式给出：

$d_i = -2y_{2i+1} + y_{2i} + y_{2i-1}$

让我们直观地看看这意味着什么：

• ​​一串零​​：如果三元组是 $\text{000}$，公式给出 $d_i = 0$。这很合理；在全是零的区域，我们不需要做任何加法。
• ​​孤立的 1​​：为了得到 $\text{01}$ 对应的数字，我们看三元组 $\text{010}$（假设前一位是 0）。公式给出 $d_i = -2(0) + 1 + 0 = +1$。我们需要加上 $1 \times M$。
• ​​两个 1​​：对于 $\text{11}$ 这对，三元组是 $\text{011}$。公式给出 $d_i = -2(0) + 1 + 1 = +2$。我们需要加上 $2 \times M$。
• ​​一串 1 的结束​​：当遇到三元组 $\text{110}$ 时，公式给出 $d_i = -2(1) + 1 + 0 = -1$。这表示需要执行一次减法操作。
• ​​一串 1 的开始​​：当遇到三元组 $\text{001}$ 时，公式给出 $d_i = -2(0) + 0 + 1 = +1$。这表示需要执行一次加法操作。
• ​​一串 1 的中间​​：三元组是 $\text{111}$。公式给出 $d_i = -2(1) + 1 + 1 = 0$。这太巧妙了！它告诉我们在长串 1 的中间什么也不做，正如我们的直觉所暗示的那样。

让我们看一个完整的例子。假设我们的乘数是8位数字 $Y = \text{01011011}_2$。为了对其进行重新编码，我们首先在右边附加一个零：$01011011\underline{0}$。现在我们从右到左形成重叠的3位比特组：

1. ​​第0组：​​ $(y_1, y_0, y_{-1}) = (1, 1, 0) \rightarrow \text{110} \rightarrow d_0 = -1$
2. ​​第1组：​​ $(y_3, y_2, y_1) = (1, 0, 1) \rightarrow \text{101} \rightarrow d_1 = -1$
3. ​​第2组：​​ $(y_5, y_4, y_3) = (0, 1, 1) \rightarrow \text{011} \rightarrow d_2 = +2$
4. ​​第3组：​​ $(y_7, y_6, y_5) = (0, 1, 0) \rightarrow \text{010} \rightarrow d_3 = +1$

因此，数字 $Y = \text{01011011}_2$ 被转换成了重新编码数字的序列 $(+1, +2, -1, -1)$。我们把一个8位数字转换成了一个4位数的“秘密编码”。

现在，硬件如何处理这个编码 [+1, +2, -1, -1] 呢？每个数字对应一个对被乘数 $M$ 的简单操作。

• ​​$d_i=0$​​：什么都不做。只需为下一步移位累加器。
• ​​$d_i=+1$​​：将 $M$ 加到部分积上。
• ​​$d_i=-1$​​：减去 $M$（即加上它的补码）。
• ​​$d_i=+2$​​：这是个神奇的操作。要得到 $2M$，我们不需要复杂的计算。硬件只需​​对被乘数 $M$ 进行一位左移​​并加上结果。这是一个极其快速且低成本的操作。
• ​​$d_i=-2$​​：类似地，我们通过对 $M$ 进行一位左移得到 $2M$，然后减去这个值（通过取其补码并相加）。

整个复杂的乘法被简化为四个步骤的简单舞蹈（对于一个8位乘法器）。在每一步中，控制器查看重新编码的数字，并告诉加法器/减法器电路对 $M$ 或 $M$ 的移位版本执行哪种操作。每一步之后，累积的结果向右移位两位，为下一个更重要的数字做准备。一个完整的乘法，如 中所示范的那样，是这些简单步骤的优美编排，与朴素方法相比，大大减少了所需的加法总数。

这里面蕴含着更深层次的数学优雅。重新编码的数字不仅仅是一套任意的编码；它们在不同的数制中表示了乘数。具体来说，这是一种​​基4​​的带符号数字表示法。

一个由基4数字 $(d_k, \dots, d_1, d_0)$ 表示的数 $Y$ 的值为：

$Y = \sum_{i=0}^{k} d_i \cdot 4^i = d_k \cdot 4^k + \dots + d_1 \cdot 4^1 + d_0 \cdot 4^0$

我们来验证一下前面重新编码的数字： $(+1, +2, -1, -1)$。 值 $= (+1) \cdot 4^3 + (+2) \cdot 4^2 + (-1) \cdot 4^1 + (-1) \cdot 4^0$ 值 $= 1 \cdot 64 + 2 \cdot 16 - 1 \cdot 4 - 1 \cdot 1 = 64 + 32 - 4 - 1 = 91$

我们原来的二进制数是多少呢？$\text{01011011}_2 = 64 + 16 + 8 + 2 + 1 = 91$。完全匹配！

该算法本质上是从基2到这个特殊的基4系统的转换。这一洞见也让我们能够反向工作。如果有人给你一个重新编码的字符串，如 $(+2, 0)$，你可以立即算出它的值：$2 \cdot 4^1 + 0 \cdot 4^0 = 8$，在6位二进制中即为 $\text{001000}$。你甚至可以解决一些谜题，比如通过逆向应用重新编码规则找到生成编码 (-1, -1, +1) 的原始6位二进制数，或者找到所有满足其重新编码数字有特定约束的数。我们甚至可以设计出能产生期望的重新编码数字模式的数，比如找到给出 [+,-,+] 数字模式的最小正数。

这揭示了这个概念深刻的统一性：基4布斯算法不仅仅是硬件技巧的集合。它是一种数表示法的根本性改变，之所以选择这种表示法，是因为新的表示法非常适合快速高效的硬件实现。它用一个优雅的系统取代了暴力的二进制算术，在这个系统中，每个“数字”都对应一个微不足道的硬件操作：移位和/或加/减。

我们已经看到了基4布斯算法的巧妙机制，它是一种优美的数学戏法，能将数字重新编码为更高效的形式。但是，一个好的魔术不仅仅是巧妙，它还有其目的。因此，我们必须问：这么做的意义何在？为什么要费力地以重叠的三元组检查比特，并生成像 $M$、$-2M$ 等这样奇特的运算序列？答案，正如在科学和工程领域中常见的那样，在于对速度和效率的不懈追求。在计算机芯片的微观世界里，每秒发生数十亿次计算，乘法是一项常见但代价高昂的任务。让乘法更快、更便宜并非小小的调整；它是一个影响一切的根本性飞跃。

布斯算法从一个抽象概念演变为现代电子学基石的历程，极好地说明了不同知识领域是如何相互联系的。这个故事将我们从纯粹的算术带到了硅晶片的物理布局。

首先，让我们来理解布斯算法所优雅解决的问题。两个 $N$ 位数的标准二进制乘法，其核心是一系列的移位和加法。对于乘数中的每个“1”，你取一个被乘数的移位副本；对于每个“0”，你什么都不取。最终，你会得到一个多达 $N$ 个数的列表，称为“部分积”，然后必须费力地将它们相加。即使对计算机来说，将一长串数字相加也需要时间和硬件。

这正是基4布斯重新编码的魔力所在。通过每次检查乘数的两位（外加一位作为上下文），该算法实际上是在说：“与其相加许多简单的东西，不如相加少数几个稍微复杂一点的东西。”它不再仅仅生成 $0$ 或 $M$，而是生成一小组值中的一个：$0, \pm M, \pm 2M$。关键结果是什么？对于一个 $N$ 位乘数，你不再需要对 $N$ 个部分积求和，而只需要 $N/2$ 个。你将列表缩短了一半。这一个结果是所有其他好处生长的种子。

将部分积的数量减半是一个很好的开始，但这如何转化为更快的芯片呢？想象一下，你必须将一叠高高的纸相加，每张纸上都有一个数字。你可以先把前两张相加，然后把第三张加到结果上，依此类推。这种方法缓慢且是串行的。一个快得多的方法是组织一场“求和竞赛”。你将纸张两两配对，并行相加，得到一叠新的、更短的纸。你重复这个过程，直到只剩下两张纸进行最后的相加。

这种“竞赛”正是被称为华莱士树的硬件结构背后的思想。它是并行计算的一个奇迹，使用多层称为全加器的简单逻辑门，将大量部分积减少到只有两个数，然后这两个数可以由一个快速的常规加法器求和。华莱士树的速度由其深度决定——即我们竞赛中的轮数。

在这里，布斯算法的才华大放异彩。如果你开始时只有一半数量的部分积，那么你只需要更少的轮次就能得到最后两个。例如，在一个经典的8x8乘法中，标准方法生成8个部分积，需要华莱士树中的4个阶段来求和。通过使用基4布斯算法，我们只从4个部分积开始。现在的华莱士树只需要2个阶段。我们将加法器树的深度减半了！在CPU时钟的世界里，纳秒即是永恒，这种逻辑深度的减少是速度上的巨大增益。

速度是硬币的一面；另一面是成本。在数字设计中，成本有多种衡量方式：电路在硅芯片上占用的物理面积、布线的复杂性以及它消耗的功率。每一个逻辑操作——每一次加法，每一次移位——都是由称为逻辑门的物理晶体管集合执行的。用于加法最常见的构建模块是全加器（对3位求和）和半加器（对2位求和）。

布斯算法减少部分积，直接转化为这些物理门数量的减少。工程师可以分析乘法器的结构，并推导出所需硬件的精确公式。对于一个 $N$ 位乘法器，一个基于基4布斯编码器输出构建的最优加法器树总共需要 $N^2 - 4N$ 个全加器单元。与标准乘法器相比，这是一个显著的节省，尤其是在 $N$ 变大时。通过仔细分析部分积矩阵每一列的比特数，设计者可以精确计算华莱士树每个阶段所需的加法器数量，确保没有一个晶体管被浪费。

这不仅仅是学术练习。更少的门意味着芯片上的面积更小，这反过来意味着单个晶圆上可以容纳更多的乘法器，从而降低制造成本。更深刻的是，更少的门意味着每次乘法消耗的功率更少。对于像智能手机这样的电池供电设备，这种效率至关重要。对于拥有数千台服务器的大型数据中心，累积的节能效果是巨大的。因此，布斯算法，一个算术理论，成为了绿色计算的关键参与者。

那么，工程师实际上是如何构建这个的呢？这些关于重新编码和相加的抽象思想是如何变成一个有形的硬件的呢？答案在于数字逻辑设计领域以及硬件描述语言（HDL）如Verilog或VHDL的使用。工程师不再是焊接单个门电路；他们编写代码来描述电路的结构和行为。

布斯乘法器一个阶段的实现是这个过程的一个优美缩影。设计是模块化的。首先，你需要潜在的部分积。你取被乘数 $M$，将其符号扩展到适当的宽度，称之为 $+M$。一个简单的 shifter 模块执行左移以创建 $+2M$。Two's complementer 模块用于生成 $-M$ 和 $-2M$。

现在你有了所有可能的成分：$0, \pm M, \pm 2M$。你选择哪一个呢？这由一个多路选择器处理，它本质上是一个电子选择开关。来自布斯编码器的三位比特 $(y_{2i+1}, y_{2i}, y_{2i-1})$ 被馈送到多路选择器的“选择线”上。就像一个拨盘，这个3位编码告诉多路选择器将其哪个输入传递到输出。如果编码是 $\text{011}$，多路选择器选择 $+2M$ 值。如果是 $\text{101}$，它选择 $-M$。这个输出就是该阶段生成的部分积，准备好被送到华莱士树。

这种结构性描述——连接移位器、补码器和多路选择器——是最终由软件工具综合成最终晶体管级布局的蓝图。这是将算法惊人地直接翻译成物理机器的过程。数学的优雅被保存在电路架构的优雅之中。布斯算法不仅仅是计算机所做的事情；它也是计算机之所是。它被融入到驱动我们数字生活的硅片之中。