Booth算法：二进制乘法的高效优化技术
在计算机体系结构中，二进制乘法的效率直接影响处理器的性能。传统乘法方法在处理有符号数时需频繁处理符号位，计算复杂度较高。1951年，英国数学家Andrew Donald Booth提出Booth算法，通过独特的编码策略减少计算步骤，成为现代计算机处理有符号数乘法的核心技术之一。
一、算法设计背景
传统二进制乘法通过逐位相乘和累加实现，例如计算(3 times 5)时需执行3次加法（(3 times 1 + 3 times 4)）。然而，当乘数中存在连续多个”1″时（如(0111_2 = 7)），传统方法需多次累加被乘数，效率低下。Booth算法通过将连续”1″转换为减法-移位操作，显著减少计算次数。例如，(0111_2)可视为(1000_2 – 0001_2)，从而将三次加法优化为一次减法和两次移位。
二、算法原理与步骤
Booth算法的核心思想是乘数重编码，通过检查乘数相邻位的组合（当前位(Q_i)与前一位(Q_{i-1})）动态调整操作：
1. 初始化
– 寄存器配置：将累加器（A）、乘数（Q）扩展为双倍字长，并添加额外位(Q_{-1}=0)。
– 被乘数（M）存入寄存器，符号位需扩展至与累加器等长。
2. 操作规则
– (Q_0 Q_{-1} = 01) → 累加器A = A + M
– (Q_0 Q_{-1} = 10) → 累加器A = A – M
– (Q_0 Q_{-1} = 00/11) → 仅移位，不运算
3. 迭代过程
每次操作后，对（A, Q, (Q_{-1})）执行算术右移一位，保持符号位不变。重复n次（n为乘数字长）。
4. 结果输出
最终结果存储在A与Q寄存器组成的联合空间中。
三、实例演示：计算(-5)×7
假设用4位补码表示，被乘数(M = -5 = 1011_2)，乘数(Q = 7 = 0111_2)，操作流程如下：
| 步骤 | A | Q | Q?? | 操作 |
||||–|-|
| 0 | 0000 | 0111 | 0 | 初始状态 |
| 1 | 0000+0101=0101 | 0111 | 0 | Q?Q??=10，A=A-M（M=+5补码为0101） |
| | 0010 | 1011 | 1 | 右移 |
| 2 | 0010+0101=0111 | 1011 | 1 | Q?Q??=11，仅移位 |
| | 0011 | 1101 | 1 | 右移 |
| 3 | 0011+0101=1000 | 1101 | 1 | Q?Q??=01，A=A+M |
| | 1100 | 0110 | 1 | 右移（结果溢出需处理）|
| 4 | 1110 | 0011 | 0 | 右移 |
最终结果(11100011_2 = -35)，验证正确。
四、算法优化与局限性
– 优点：
1. 减少部分积数量，尤其擅长处理连续1/0的乘数。
2. 统一处理有符号/无符号数，硬件实现简洁。
– 缺点：
1. 乘数无连续相同位时效率不显著。
2. 需预计算被乘数补码，增加初始化开销。
改进方案如基4 Booth编码（一次检查3位）可进一步提升速度，适用于高性能ALU设计。
五、应用场景
Booth算法广泛应用于低功耗嵌入式芯片（如ARM处理器）和GPU的整数单元中。其变种算法（如Radix-4）在RISC-V开源架构中也被采用，充分体现了其在平衡效率与硬件成本方面的价值。
通过将乘数转换为特定操作序列，Booth算法以巧妙的数学重构突破了传统乘法的效率瓶颈，成为计算机算术单元设计的经典范例。