硬件乘法器

玻尔百科

关键要点

硬件中二进制乘法的基础包括使用与门生成部分积，并用加法器网络将它们相加。
乘法器设计涉及面积和延迟之间的关键权衡，这体现在大型、快速的并行阵列乘法器与小型、较慢的时序移位加法设计之间的对比上。
像 Booth 算法和华莱士树架构这样的先进技术通过减少部分积的数量或并行求和来显著提高性能。
硬件乘法器对数字信号处理（DSP）至关重要，它们通过定点运算对小数进行计算，以实现数字滤波等现实世界应用。

引言

乘法是计算的基石，但这个基本操作是如何在处理器核心的硅片中执行的，则是一个复杂的数字工程故事。硬件乘法器的实现虽然看似简单，却展现了在速度、物理尺寸和功耗之间进行关键设计权衡的图景。本文旨在弥合乘法的抽象概念与其具体的硬件实现之间的鸿沟。旅程始于第一章“原理与机制”，我们将从原子级的逻辑门开始解构乘法器，探索基础架构，并考察如 Booth 算法和华莱士树等高级优化技术。随后，“应用与跨学科联系”一章将展示这些数字引擎如何为从计算机体系结构、可编程逻辑到数字信号处理核心的广阔领域提供动力。通过探索“如何实现”和“为何如此”，读者将对计算领域最关键的组件之一获得全面的理解。

原理与机制

一块硅片，作为计算机的心脏，是如何执行像乘法这样基本的操作的？我们在小学时用纸和笔学习过乘法，这是一个有条不紊的移位和相加过程。事实证明，处理器几乎完全是这样做的，只是速度快得惊人，并且用的是微观晶体管而非铅笔芯。从这个简单的想法到现代芯片内部复杂的乘法器，其发展历程是一段精彩的数字工程故事，揭示了在速度、尺寸和巧妙设计之间的权衡。

乘法的原子：与门和加法

让我们回到基础。当你在纸上计算 $13 \times 11$ 时，你首先计算 $13 \times 1$ ，然后计算 $13 \times 10$ （也就是将 13 左移一位），最后将两个结果相加。二进制乘法甚至更简单。被乘数是一个数，比如 1101（十进制 13），乘数是另一个数，比如 1011（十进制 11）。

仔细观察每一行中间结果，即部分积，是如何形成的。第一行是 1101，因为乘数的最后一位是 1。第二行也是 1101，因为下一位是 1。第三行全是零，因为第三位是 0。在二进制中，一个数乘以 1 得到它本身，乘以 0 得到零。

这正是逻辑与门（AND gate）的功能！一个与门只有在它的两个输入都为 1 时才会输出 1。因此，要生成一个部分积的各位，我们只需将被乘数的每一位与乘数的某一位进行与运算。对于一个 $m$ 位的被乘数和一个 $n$ 位的乘数，第一步总共需要 $m \times n$ 个与门，对应每一对可能的位组合。

生成所有部分积之后，我们只需将它们相加。这是半加器（相加两个比特）和全加器（相加三个比特：两个输入比特和一个来自前一列的进位）的工作。

让我们从头开始构建一个微小的 2x2 乘法器，将 $A = A_1A_0$ 乘以 $B = B_1B_0$ 得到一个 4 位乘积 $P = P_3P_2P_1P_0$ 。四个部分积的位是 $A_0B_0$ 、 $A_1B_0$ 、 $A_0B_1$ 和 $A_1B_1$ 。我们按照它们的位权排列并相加：

从这个布局中，我们可以看出逻辑：

乘积的最低位 $P_0$ 就是输入最低位的与运算结果： $P_0 = A_0B_0$ 。
下一位 $P_1$ 是 $A_1B_0$ 和 $A_0B_1$ 的和。这需要一个半加器。
$P_2$ 是 $A_1B_1$ 和 $P_1$ 加法产生的进位的和。这需要另一个加法器。
$P_3$ 仅仅是 $P_2$ 加法产生的进位。

通过推导逻辑，我们可以为每个输出位导出布尔表达式，从而用数字逻辑的最基本原子构建我们的乘法器。

规模扩展：暴力阵列

一个 2x2 乘法器很简单。那么现代 CPU 的 64x64 乘法器呢？最直接的方法就是简单地扩展我们的设计。这就产生了阵列乘法器，一种优美的网格状结构，是纸笔计算方法的直接物理体现。它由一个生成所有部分积的与门网格，以及一个用于将它们相加的全加器和半加器网格组成。

虽然概念上简单而优雅，但这种“暴力”方法代价高昂。对于一个 $n \times n$ 的乘法，你需要 $n^2$ 个与门和大约 $n(n-1)$ 个加法器的组合。基本元件的总数随位数目的平方增长，即 $O(n^2)$ 。将位宽从 32 位加倍到 64 位，硬件不只是翻倍，而是翻了四倍！这种面积的二次方增长意味着对于大数，一个简单的阵列乘法器可能会变得过大，并消耗大量功率。

另一条路：用时间换硬件

如果我们在设计一个小型、低功耗的设备，无法承担庞大阵列乘法器所需的硅片面积怎么办？我们可以做出一个经典的工程权衡：牺牲速度以节省空间。这就产生了时序移位加法乘法器。

与使用一个巨大的加法器网格并行执行所有加法不同，这种设计使用单个加法器并随时间重复该过程。算法很简单：

将一个累加器寄存器初始化为零。
检查乘数的最低有效位（LSB）。如果为 1，则将被乘数加到累加器中。
将累加器和乘数右移一个位置。
对乘数的每一位重复此过程。

经过 $n$ 个步骤后，最终的乘积就存放在累加器中。这种设计比阵列乘法器小得多，但速度也更慢。正如我们的一个设计练习中所述，一个 8 位时序乘法器需要 1 个时钟周期进行初始化，然后需要 8 个周期进行迭代计算，总共需要 9 个周期才能完成。这完美地说明了硬件设计者不断权衡的面积（硬件复杂度）和延迟（时间）之间的基本矛盾。

负数的麻烦

到目前为止，我们的世界是简单而积极的。但现实中，我们需要处理负数。大多数计算机为此使用二进制补码表示法。在这个系统中，一个数的最高有效位（MSB）具有负权重。例如，在 4 位二进制补码中，数字 1011 不是 $8+2+1=11$ ，而是 $-8+2+1 = -5$ 。

如果我们将二进制补码数输入到一个为无符号数设计的乘法器中会发生什么？让我们尝试计算 $-1 \times -1$ 。-1 的 4 位二进制补码表示是 1111。如果我们将 1111 和 1111 输入到我们的无符号乘法器中，它会将它们解释为十进制数 15。硬件会愉快地计算 $15 \times 15 = 225$ ，在 8 位二进制中是 11100001。当然，正确答案是 $+1$ ，即 00000001。结果错得离谱！

失败的原因是硬件没有我们“二进制补码”解释的概念。它将 MSB 视为具有正权重（ $+2^3$ ），而不是我们有符号系统所要求的负权重（ $-2^3$ ）。它忠实地乘以它认为被赋予的那些大的正数。

为了解决这个问题，在累加部分积时我们需要小心。当一个部分积由一个负数生成时，在相加之前必须进行符号位扩展。这意味着将其符号位（MSB）复制到其左侧所有新的比特位上，以在扩展到位宽更大的数时保持其负值。这确保了最终的和能正确反映原始输入的符号。

更巧，而非更繁：优化算法

我们已经看到，我们可以构建大而快的乘法器，也可以构建小而慢的乘法器。但我们能否更聪明一些，设计出既快又高效的乘法器呢？乘法的主要瓶颈是累加大量的部分积。最有效的提速方法是减少我们必须相加的东西的数量。

这就是 Booth 算法的精妙之处。Booth 算法不是机械地为乘数中的每一个 1 生成一个部分积，而是巧妙地将它们分组。考虑乘以数字 30，其二进制表示为 011110。一个简单的乘法器会执行四次加法。但我们知道 $30 = 32 - 2$ ，即 $2^5 - 2^1$ 。因此，我们只需一次加法（对于 $+32$ ）和一次减法（对于 $-2$ ）就可以得到相同的结果，而不是四次加法。

Booth 算法通过将乘数从数字集合 $\{0, 1\}$ 重新编码为一个新的数字集合 $\{-1, 0, +1\}$ 来自动化这个过程。它从右到左扫描乘数位，对于每一位 $m_i$ ，它会查看前一位 $m_{i-1}$ 来决定新的数字：重新编码的值就是 $m_{i-1} - m_i$ 。这个简单的规则自动识别出一串 1 的开始和结束，用一次加法和一次减法代替了多次加法。

这个想法可以通过规范有符号数字（CSD）表示法进一步发展。CSD 是一种独特的有符号数字形式，其中没有两个连续的数字是非零的。这个属性保证了它用绝对最少的非零数字来表示一个数。对于创建乘以固定常数（数字信号处理中的常见任务）的电路的硬件设计者来说，将该常数转换为 CSD 可以最大限度地减少所需的加法器和减法器数量，从而得到更小、更快、更节能的电路。

并行求和的艺术：华莱士树

Booth 算法减少了部分积的行数。但是，最快的方法来累加剩下的行是什么呢？阵列乘法器是顺序相加的，进位从一列缓慢地传递到下一列。一个快得多的方法是并行地将它们全部相加，就像一个数字的淘汰赛。这就是华莱士树（Wallace Tree）的哲学。

华莱士树的关键构建块是全加器，但我们必须重新想象它的用途。不要只把它看作一个加法器，而应把它看作一个 3:2 压缩器。它接收三个具有相同位权的输入位（即它们在同一列中），并将它们“压缩”成两个输出位：一个和位，留在同一列；一个进位位，移动到下一个更高的列。

想象一下，在我们的部分积矩阵中，某一列有 11 个位需要求和。我们不能一次将它们全部相加。但我们可以并行使用三个全加器。每个全加器接收 3 个位，并将它们减少到 2 个（1 个和，1 个进位）。经过这一阶段后，我们处理了 11 个位中的 9 个，剩下 3 个和位在我们的列中，以及 2 个未处理的原始位。列的高度在一步之内就从 11 减少到了 5！我们重复这个过程：5 个位被压缩成 3 个，3 个位被压缩成 2 个。这种缩减速度极快。

通过在所有列上同时应用这种压缩技术，华莱士树可以缩减整个部分积行矩阵。每个阶段的行数呈对数级减少。例如，一组 9 行的初始行可以在四个阶段内压缩到 6 行，然后到 4 行，再到 3 行，最后只剩下 2 行。

华莱士树的输出是最后两行。然后可以将这两个数送入一个单一的、高度优化的加法器（如超前进位加法器）来产生最终的乘积。通过在最终加法之前进行这种大规模的并行压缩，华莱士树架构避免了阵列乘法器中缓慢的、涟漪式的进位链，使其成为大数乘法可能的最快设计之一。这是并行思维在数字设计中力量的证明。

应用与跨学科联系

在上一章中，我们深入探讨了硬件乘法器的内部工作原理。我们将其逐一拆解，从构成部分积的基本与门到将它们相加的复杂加法器树。在某种意义上，我们已经学会了用硅的语言来表达乘法的语法。现在，我们准备好成为诗人了。我们能用这种语法讲述什么样的故事？我们能谱写什么样的交响乐？

事实证明，一旦你教会一块硅片如何做乘法，你不仅仅是创造了一个计算器。你锻造了一把钥匙，可以打开科学和工程领域的无数扇门。本章就是一次穿越这些门的旅程。我们将看到这个单一的基本操作如何成为从可编程逻辑、计算机体系结构到广阔而充满活力的数字信号处理世界的一切的基石。我们会发现，我们实现乘法的方式——我们做出的架构选择——不仅仅是一个技术细节，而是工程创造力和权衡的深刻体现。

逻辑与存储器的二元性

让我们从一个看似哲学的问题开始：乘法是一个计算的过程，还是一个回忆的行为？在硬件的世界里，答案奇妙地是“两者都是！”

思考乘法器最直接的方式是将其视为一个巨大的逻辑函数。对于任何一组输入位，都有一组唯一确定的输出位。我们可以将其写成一组布尔表达式。对于一个简单的 2 位乘 2 位乘法器，输入为 $A_1A_0$ 和 $B_1B_0$ ，产生一个 4 位乘积 $P_3P_2P_1P_0$ ，其逻辑可以被提炼成最纯粹的形式——一个由与门和或门（或者更准确地说，是积之和）组成的集合。例如，乘积的最低有效位 $P_0$ 仅仅是 $A_0 \land B_0$ 。最高有效位 $P_3$ 则更为复杂，涉及到项 $A_1 \land A_0 \land B_1 \land B_0$ 。虽然对于更大的乘法器，这些表达式会变得异常复杂，但原理依旧：在其核心，乘法器只是一个巨大、相互连接的逻辑门网络。正是这种观点，使我们能够在像 FPGA 这样的可编程设备上构建乘法器，这些设备本质上就是等待蓝图的、由可配置门组成的海洋。

但还有另一种完全不同且同样优美的方式来思考它。与其每次都计算乘积，不如我们预先计算出所有可能的乘积并将结果存储在一个表中？这就是查找表（LUT）方法。想象一下，我们想构建一个 4 位乘 4 位的乘法器。两个 4 位输入可以连接起来形成一个 8 位数，可以表示 $2^8 = 256$ 个唯一的值。我们可以用这个 8 位数作为只读存储器（ROM）的地址。在 256 个内存位置的每一个位置，我们简单地存储与该地址对应的 8 位乘法结果。当我们想计算，比如说， $13 \times 11$ 时，我们通过组合它们的二进制表示（ $1101_2$ 和 $1011_2$ ）来形成地址，然后简单地读取存储在那里的值。“计算”在 ROM 制造时就已经完成了！

在这里我们看到了计算中一个经典而深刻的权衡：空间与时间。逻辑门方法动态地计算答案，使用许多门但存储很少。ROM 方法使用大量存储但几乎瞬间完成“计算”。现代硬件设计就是在这两种哲学之间不断地舞蹈。

节俭的艺术：行业技巧

有时候，一个拥有数千个门的全功能乘法器是小题大做了。它对于一个小型嵌入式芯片来说可能太大，功耗太高，或者仅仅比一个更量身定制的解决方案要慢。在这些时刻，工程师们就变成了艺术家，利用他们对二进制的深刻理解来寻找巧妙的捷径。

其中最优雅的一个是认识到乘以一个常数通常可以分解为一系列的移位和加法，这在硅片中是远为“廉价”的操作。一个 $k$ 位的算术左移等同于乘以 $2^k$ 。考虑将一个数 $N$ 乘以 18 的任务。与其使用一个通用乘法器，我们可以注意到 $18 = 16 + 2 = 2^4 + 2^1$ 。因此，操作 $18 \times N$ 等同于 $(N \times 2^4) + (N \times 2^1)$ ，这在硬件中可以实现为 (N 4) + (N 1)。这只需要两个移位器和一个加法器。这种技术，被称为强度折减，是优化编译器和设计高性能、特定应用电路的基石。这是一个美丽的例子，说明了了解问题的数学特性如何能导致硬件效率的大幅提升。

从蓝图到都市：构建乘法器架构

随着规模的扩大，我们需要更系统化的方法来构建这些数字引擎。对布尔方程进行暴力转换变得笨拙。于是，我们转向架构。

最直观的架构之一模仿了我们手算长乘法的方式。这就是移位加法算法。这个过程是顺序的，被分解为由控制器——一个有限状态机（FSM）——管理的简单步骤。在每一步中，控制器查看乘数的一位。如果该位是 '1'，它将被乘数加到一个累加和中；如果是 '0'，则什么也不做。然后，它将部分积右移，并移至下一位。这种多周期方法用尺寸换取速度；它反复使用单个加法器，从而形成一个非常紧凑的设计。这正是中央处理单元（CPU）工作方式的精髓：一个简单的数据通路（寄存器、ALU）在控制器的指令下执行原始操作，控制器则按程序步骤执行。

但如果我们希望硬件更灵活呢？如果我们有时需要将两个大的 8 位数相乘，但在其他时候更愿意并行执行两个 4 位乘法呢？这就引出了可重构硬件的强大思想。考虑一个 $8 \times 8$ 的乘法器。 $X \times Y$ 的完整乘积，其中 $X = X_H \cdot 2^4 + X_L$ 和 $Y = Y_H \cdot 2^4 + Y_L$ ，是 $(X_H Y_H)2^8 + (X_H Y_L + X_L Y_H)2^4 + X_L Y_L$ 。项 $X_H Y_L$ 和 $X_L Y_H$ 是连接上半部分和下半部分的“交叉积”。如果我们能以某种方式强制这些交叉积为零，结果将简化为 $(X_H Y_H)2^8 + X_L Y_L$ 。这意味着高位输入的乘积出现在高位输出位上，低位输入的乘积出现在低位输出位上，彼此之间没有干扰！这可以通过策略性地放置由单个 MODE 信号控制的多路复用器来实现，以选择性地使构成这些交叉项的部分积无效。这是一种简单但深刻的单指令多数据流（SIMD）处理形式，正是这种技术赋予了现代 GPU 在图形和科学计算方面的巨大能力。

这些架构思想在现代硬件描述语言（HDLs）如 VHDL 和 Verilog 中得到了终极体现。设计师不再绘制单个门电路；他们在高层次上描述行为和结构。他们可以创建一个通用的 ALU，并使用一个参数，比如 LIGHTWEIGHT_BUILD，通过 if-generate 语句有条件地包含或排除乘法器模块。这使得一个单一、经过验证的设计可以被合成为不同的形式：一个带有耗电乘法器的全功能版本，或者一个没有乘法器的精简版本，用于要求不高的应用。这是创建可重用知识产权（IP）核的基础，这些 IP 核是现代芯片设计的乐高积木。

通往现实世界的桥梁：数字信号处理

到目前为止，我们的讨论仅限于干净、离散的整数世界。但我们所体验的世界——声音、光、温度和压力——是模拟和连续的。我们的整数乘法器如何能在这里帮助我们呢？答案在于一个优美而实用的抽象：定点运算。

我们可以约定一个惯例：在一个 16 位字中，也许第一位是符号位，接下来的 6 位是整数部分，最后的 9 位是小数部分。这被称为 Q7.9 格式。这种格式的数只是一个 16 位的有符号整数，我们将其解释为被缩放了 $2^{-9}$ 。当我们乘以两个这样的 Q7.9 数时，我们可以将它们原始的 16 位整数模式输入到我们的标准整数乘法器中。结果是一个 32 位的整数。奇妙之处在于理解这个 32 位整数代表什么。如果我们乘以 $A = I_A \cdot 2^{-9}$ 和 $B = I_B \cdot 2^{-9}$ ，硬件会给我们 $P = I_A \cdot I_B$ 。真正的乘积是 $A \cdot B = (I_A \cdot I_B) \cdot 2^{-18} = P \cdot 2^{-18}$ 。为了让我们的结果回到一个熟悉的格式，我们只需要考虑这个新的缩放因子，这通常只需要从 32 位乘积中选择正确的比特片段即可。

这个使用整数乘法器处理小数的简单技巧几乎是所有数字信号处理（DSP）的主力。它使我们能够构建数字滤波器来消除音频噪音、锐化医学图像或调谐到广播电台。有限冲激响应（FIR）滤波器，最常见的类型之一，本质上是一长串的乘法累加（MAC）操作。

在这里，架构再次变得至关重要。一个需要处理高频信号的滤波器的简单实现可能需要每秒进行大量的乘法运算，要求多个硬件乘法器并行工作。但通过应用信号处理理论的深层结果，我们可以做得更聪明。对于一个后跟抽取（即减慢信号）的滤波器，可以使用多相实现。这种架构巧妙地重新排列了计算，将抽取移到滤波之前。这极大地降低了乘法器必须工作的速率，通常允许单个分时复用的乘法器完成多个乘法器的工作。这不仅仅是一个小小的调整；这是计算负载的一个因子为 $M$ 的减少，其中 $M$ 是抽取因子——这是一个直接源于一个名为 Noble 恒等式的美丽数学成果所带来的功耗和面积的巨大节省。

这个兔子洞还可以挖得更深。对于给定的滤波器，还有完全不同的结构，比如格梯结构实现，它有不同的权衡。虽然对于相同的滤波器长度，它通常比标准的直接形式需要更多的乘法器和加法器，但它具有优越的数值稳定性，其系数在语音建模和自适应滤波等应用中具有物理意义。架构的选择不仅仅是关于成本；它是关于为手头的工作找到合适的工具，具备适合问题的正确属性。

从一个简单的逻辑函数到 CPU 的核心，从一个巧妙的编译器技巧到塑造我们现代世界的数字信号处理引擎，硬件乘法器远不止一个简单的算术单元。它是抽象力量的证明，是数学、计算机科学和电气工程的美丽交汇点。理解它的发展历程，就是一窥驱动数字时代的独创性。