Booth 乘法器详解（含示例）

说明基数 2 与基数 4 Booth 重编码，逐步跟踪 -3 × 5，并分析迭代硬件乘法器中的有符号位宽问题。

Denny

2026年5月7日阅读约需 8 分钟

Chalkboard feature illustration for “Booth 乘法器详解（含示例）”

简述： Booth 重编码将乘数中连续的 1 改写为有符号数字。基数 2 Booth 在每次迭代检查 $(Q_0,Q_{-1})$ ：01 加被乘数，10 减被乘数，00 或 11 保持不变，随后执行算术右移。位宽安全的 $n$ 位实现会对被乘数进行符号扩展，并使用 $(n+1)$ 位累加器，以正确处理最小负值。基数 4 改进 Booth 从 $0,\pm M,\pm2M$ 中选择，使部分积数量约减半。

二进制乘法可由移位和加法构建。挑战不在于二进制补码操作数不能不用 Booth 相乘——它们可以——而在于必须正确设计符号处理和部分积生成。

Booth 方法提供统一的有符号重编码并压缩连续的 1 。它在两种不同架构中有用：

迭代乘法器，在多个周期复用一个加法器
并行乘法器，生成重编码部分积，并使用加法器/压缩器树归约

两种架构共享重编码思想，但延迟、面积和时序不同。

连续一的恒等式

考虑从位 $j$ 到位 $k$ 的一段二进制 1，其中 $k\ge j$ ：

2^j + 2^{j+1} + \cdots + 2^k = 2^{k+1} - 2^j

例如：

001111_2 = 010000_2 - 000001_2

普通无符号移位加法会为 1111 加上被乘数的四个移位副本。Booth 重编码在该连续段的低边界减法，在高边界之上一位加法。

这并不保证所有位模式都能减少非零操作。较长连续段可以受益；孤立或交替的 1 可能不会减少操作，甚至可能增加加/减决策数。固定延迟的基数 2 迭代乘法器仍执行 $n$ 次迭代：重编码只改变每次迭代中的算术动作，并不会自动改变周期数。

基数 2 Booth 重编码

在乘数下方附加隐含零：

Q_{-1}=0

第 $i$ 次迭代时，检查当前最低有效乘数位 $Q_0$ 和保存的前一位 $Q_{-1}$ ：

$Q_0$	$Q_{-1}$	累加器动作
0	0	不变
0	1	加 $M$
1	0	减 $M$
1	1	不变

随后将组合的累加器、乘数和保存位算术右移一位。

该位对检测边界：

10 标记连续一的低端，因此减法
01 标记移过连续段后的高端，因此加法
相邻位相等时，处在恒定连续段内，不需要算术动作

表中位顺序很重要。有些文本印作 $(Q_{-1},Q_0)$ ；那会反转行标签。务必说明所用约定。

位宽安全的迭代数据通路

令两个输入操作数均为有符号 $n$ 位二进制补码值：

$M$ ：被乘数
$Q$ ：乘数

使用：

$M_e$ ：符号扩展到 $n+1$ 位的 $M$
$A$ ：初始为零的 $n+1$ 位累加器
$Q$ ： $n$ 位乘数寄存器
$Q_{-1}$ ：初始为零的一个保存位
从 0 到 $n-1$ 的迭代计数器

在 $n$ 次迭代中的每次：

检查 $(Q_0,Q_{-1})$
若为 01，置 $A \leftarrow A+M_e$
若为 10，置 $A \leftarrow A-M_e$
若为 00 或 11， $A$ 保持不变
将拼接 $\{A,Q,Q_{-1}\}$ 算术右移一位

完成 $n$ 次迭代后，舍弃 $A$ 冗余的顶部符号扩展位。 $A$ 剩余的 $n$ 位与 $Q$ 拼接，构成有符号 $2n$ 位乘积。

为什么额外的累加器位很重要

对于 $n$ 位二进制补码数，可表示范围为：

-2^{n-1} \le x \le 2^{n-1}-1

$-2^{n-1}$ 的正幅值无法装入 $n$ 位。因此，若设计仅在 $n$ 位预先计算 -M，当 $M$ 是最负值时便可能失败。对 $M$ 符号扩展并使用 $(n+1)$ 位累加器，使算法中 $M_e$ 与 $-M_e$ 均可表示。

算例： $-3 \times 5$

使用四位操作数：

M=-3=1101_2,\qquad Q=5=0101_2

将被乘数符号扩展至五位：

M_e=11101_2

初始化：

A=00000,\quad Q=0101,\quad Q_{-1}=0

表中展示位对和算术动作，随后展示组合算术右移之后的状态：

迭代	位对 $(Q_0,Q_{-1})$	移位前动作	移位后 $A$	移位后 $Q$	$Q_{-1}$
初始	—	—	`00000`	`0101`	`0`
1	`10`	$A-M_e=00011$	`00001`	`1010`	`1`
2	`01`	$A+M_e=11110$	`11111`	`0101`	`0`
3	`10`	$A-M_e=00010$	`00001`	`0010`	`1`
4	`01`	$A+M_e=11110$	`11111`	`0001`	`0`

四次迭代后，舍弃 $A$ 冗余的高符号位：

A[3:0]\;||\;Q = 1111\;0001_2

作为八位二进制补码值：

11110001_2=-15

与 $-3\times5$ 一致。

跟踪一次组合移位

第一次减法后：

\{A,Q,Q_{-1}\} = \{00011,\ 0101,\ 0\}

算术右移将累加器符号位复制到新的最高位，并将其余每一位移动一处：

\{00001,\ 1010,\ 1\}

移位必须作用于整个拼接寄存器。分别移位 $A$ 和 $Q$ 会丢失其边界间的位传递。

硬件模块

可复用的迭代 Booth 乘法器包含：

一个 $(n+1)$ 位被乘数寄存器或输入路径
一个 $(n+1)$ 位累加器
一个 $n$ 位乘数寄存器以及 $Q_{-1}$
一个 $(n+1)$ 位加/减法器
用于 add 、 subtract 或 hold 的位对译码控制
组合算术移位器
迭代计数器和 busy/done 控制

加法器在全部迭代中复用，相较完全并行乘法器节省面积，但付出延迟。一次迭代需一个时钟还是多个微步骤取决于控制器和数据通路。

ALU 元件可在教学电路中提供加/减行为，但应确认其位宽及有符号溢出行为。移位寄存器说明串行移动；Booth 数据通路需要一个更宽的组合寄存器，其顶部位进行符号填充。

基数 4 改进 Booth 编码

基数 4 改进 Booth 检查重叠的三位窗口，并每个数字重编码两个乘数位。在低端附加零，并按需在高端对乘数进行符号扩展。

对于窗口 $(Q_{2i+1},Q_{2i},Q_{2i-1})$ ：

窗口	重编码倍数
`000`	$0$
`001`	$+M$
`010`	$+M$
`011`	$+2M$
`100`	$-2M$
`101`	$-M$
`110`	$-M$
`111`	$0$

可用倍数为：

\{0,\ +M,\ -M,\ +2M,\ -2M\}

$2M$ 是左移，因此这些部分积生成相对经济。对 $n$ 位乘数，基数 4 产生约 $\lceil n/2\rceil$ 个重编码数字，而非 $n$ 个基数 2 数字。

这种减少可以：

在迭代基数 4 设计中将迭代次数减半
在并行设计中减少部分积行数

但它不会自动使完整乘法器快一倍。重编码、符号校正、部分积生成、归约、布线、最终加法和流水线都会影响时序。

并行归约：Wallace、Dadda 与最终加法器

高吞吐量乘法器可并行生成部分积，用进位保存压缩器归约其列，并以进位传播加法器完成计算。

Wallace 树和 Dadda 树是两种经典归约调度方法。改进 Booth 重编码可置于归约树之前以减少部分积行数。最终加法器可采用超前进位、并行前缀、选择进位或其他适合目标技术的结构。

“组合”并不必然表示“一个处理器周期”。宽乘法器可能跨多个级流水化以满足目标时钟周期，一些处理器也因面积或功耗原因使用迭代单元。架构是一种实现选择。

Booth 与其他乘法器结构

方法	有符号运算	部分积或周期数	典型权衡
基本迭代移位/加法	通过正确符号处理可实现	通常为 $n$ 次迭代	数据通路小，控制直接
基数 2 迭代 Booth	原生二进制补码重编码	$n$ 次迭代	统一有符号算法；加/减/跳过
基数 4 迭代 Booth	原生二进制补码重编码	约 $\lceil n/2\rceil$ 次迭代	需要更多译码/倍数选择
并行部分积阵列/树	有符号或无符号变体	行并发处理	硬件更多；可流水化
基数 4 Booth 加归约树	原生有符号重编码	初始行数约减半	常见高性能设计选项

不存在适用于所有场景的单一结构。操作数宽度、目标单元或 FPGA 资源、吞吐量、时延、面积、功耗和验证工作量共同决定结构选择。

在 DigiSim 中构建

对于四位教学实现：

用可见存储元件创建五位累加器。
将四位被乘数符号扩展到五位。
使用五位加/减路径。
存储四位乘数和单独的 $Q_{-1}$ 位。
将 (Q0, Q−1) 译码为加、减和保持。
对完整的 {A,Q,Q−1} 状态实现算术移位。
精确计数四次迭代。
暴露 busy 、 done 和最终八位乘积。

逐步执行 $-3\times5$ 表，并比较每个移位后状态。第一次迭代不匹配通常指向位对顺序反转或减法极性错误；负累加器移位后的不匹配通常指向使用了逻辑移位而非算术移位。

验证清单

对于小型 $n$ 位乘法器的穷举验证，应测试全部：

2^n \times 2^n = 2^{2n}

输入对，并与按 $2n$ 位表示的有符号参考乘积比较。

至少包括：

$0\times x$ 和 $1\times x$
正数 × 正数
正数 × 负数
负数 × 正数
负数 × 负数
最大正值
最负值 $-2^{n-1}$
$-2^{n-1}\times -1$
乘数模式 0000 、 1111 、 0101 和 1010
忙碌期间的复位或重新启动

还应断言：

恰好发生 $n$ 次基数 2 迭代
每次接受的操作只发出一次 done
输入要么被锁存，要么按契约要求保持稳定
结果在有效前不被使用
组合移位保留累加器符号

理想功能仿真证明算术排序，并不证明最大硬件时钟频率。将设计映射到目标后，应使用静态时序分析。

继续学习

复习二进制补码算术以了解符号扩展和范围，再比较行波进位加法与超前进位结构。

Andrew D. Booth 在其 1951 年论文“一种有符号二进制乘法技术”中提出了该统一有符号方法。核心重编码至今仍有意义，但专业实现仍需显式位宽、定义明确的延迟契约、穷举有符号测试和目标特定时序分析。