从Booth1到Booth4：深入理解乘法器编码进化史（附性能对比测试）

从Booth1到Booth4：深入理解乘法器编码进化史（附性能对比测试）

在计算机体系结构中，乘法运算是最基础也是最关键的操作之一。从早期的Booth1算法到如今广泛应用的Booth4编码，乘法器设计经历了一段令人着迷的技术演进历程。本文将带您穿越这段历史，揭示不同Booth编码背后的优化思想，并通过Python实现和性能对比，帮助您深入理解这些算法在实际芯片设计中的应用价值。

1. 乘法器编码基础与Booth1算法

任何数字系统的乘法运算都可以分解为三个核心步骤：乘数编码、部分积生成和部分积累加。早期的Booth1算法（也称为基2 Booth编码）正是基于这一流程设计的经典解决方案。

Booth1算法的核心思想是通过观察乘数中连续的1或0来减少部分积的数量。具体来说：

• 在乘数的最低有效位（LSB）右侧补一个0
• 从右向左，每次检查两位（当前位和上一位）
• 根据这两位的变化情况决定操作：
  • 00或11：不做任何操作
  • 01：加被乘数
  • 10：减被乘数

def booth1_encoder(multiplier, multiplicand): # 补0 extended_mult = multiplier << 1 n = multiplier.bit_length() partial_products = [] for i in range(n): # 取两位 bits = (extended_mult >> i) & 0b11 if bits == 0b01: partial_products.append(multiplicand << i) elif bits == 0b10: partial_products.append(-(multiplicand << i)) return partial_products

虽然Booth1算法简单直观，但它存在明显的局限性：

1. 部分积数量：对于n位乘法，平均需要n/2个部分积
2. 编码效率：无法有效处理连续的1或0，导致部分积减少效果有限
3. 硬件实现：需要较多的加法器和控制逻辑

下表对比了Booth1算法与传统阵列乘法器的部分特性：

2. Booth2（基4 Booth）算法的突破

为了克服Booth1的局限性，计算机科学家们提出了Booth2算法（也称为基4 Booth编码）。这种算法通过一次检查3位乘数，将部分积数量进一步减少到约n/2。

Booth2算法的编码规则如下：

1. 在乘数末尾补一个0
2. 从右向左，每次检查3位（重叠1位）
3. 根据3位组合决定操作：

def booth2_encoder(multiplier, multiplicand): extended_mult = multiplier << 1 n = multiplier.bit_length() partial_products = [] for i in range(0, n, 2): # 取三位 bits = (extended_mult >> i) & 0b111 if bits == 0b000 or bits == 0b111: continue elif bits == 0b001 or bits == 0b010: partial_products.append(multiplicand << i) elif bits == 0b011: partial_products.append(multiplicand << (i+1)) elif bits == 0b100: partial_products.append(-(multiplicand << (i+1))) elif bits == 0b101 or bits == 0b110: partial_products.append(-(multiplicand << i)) return partial_products

Booth2算法的关键改进在于：

• 部分积减少：平均部分积数量降至n/2
• 操作多样性：支持±A、±2A操作
• 硬件友好：编码规则简单，易于硬件实现

提示：Booth2算法中，当遇到011或100时需要进行移位操作，这在实际硬件中可以通过简单的连线实现，不需要额外的移位器。

3. Booth3与Booth4算法的进阶优化

随着处理器对乘法性能要求的提高，更高基数的Booth算法应运而生。Booth3（基8）和Booth4（基16）算法通过检查更多位数，进一步减少了部分积数量。

3.1 Booth3算法特点

Booth3算法每次检查4位乘数，可以产生以下操作：

• 0、±A、±2A、±3A、±4A

def booth3_encoder(multiplier, multiplicand): extended_mult = multiplier << 1 n = multiplier.bit_length() partial_products = [] # 预计算常用值 A = multiplicand twoA = A << 1 threeA = twoA + A fourA = twoA << 1 for i in range(0, n, 3): bits = (extended_mult >> i) & 0b1111 if bits == 0b0000 or bits == 0b1111: continue elif bits == 0b0001 or bits == 0b0010: partial_products.append(A << i) elif bits == 0b0011 or bits == 0b0100: partial_products.append(twoA << i) elif bits == 0b0101 or bits == 0b0110: partial_products.append(threeA << i) elif bits == 0b0111: partial_products.append(fourA << i) elif bits == 0b1000: partial_products.append(-(fourA << i)) elif bits == 0b1001 or bits == 0b1010: partial_products.append(-(threeA << i)) elif bits == 0b1011 or bits == 0b1100: partial_products.append(-(twoA << i)) elif bits == 0b1101 or bits == 0b1110: partial_products.append(-(A << i)) return partial_products

3.2 Booth4算法特点

Booth4算法将这一思路推向极致，每次检查5位乘数，支持的操作更多样：

• 0、±A、±2A、±3A、±4A、±5A、±6A、±7A、±8A

下表对比了不同Booth算法的关键指标：

注意：虽然高基数Booth算法减少了部分积数量，但所需的预计算值和选择逻辑会显著增加硬件复杂度。设计时需要权衡面积和性能。

4. 性能对比与实际应用

为了直观展示不同Booth算法的性能差异，我们使用Python实现了完整的测试框架，并在模拟环境中运行了多种测试用例。

4.1 测试环境配置

import time import random def test_performance(encoder_func, bit_width=16, test_count=1000): total_time = 0 for _ in range(test_count): a = random.randint(0, (1 << bit_width) - 1) b = random.randint(0, (1 << bit_width) - 1) start = time.perf_counter() encoder_func(a, b) total_time += time.perf_counter() - start return total_time / test_count * 1e6 # 微秒

4.2 性能测试结果

我们对16位乘法器进行了全面测试，结果如下：

4.3 RISC-V处理器中的应用案例

在现代RISC-V处理器设计中，Booth算法的选择需要综合考虑多种因素：

1. 低功耗场景：通常选择Booth2算法，在性能和功耗间取得平衡
2. 高性能场景：可能采用Booth3或定制混合方案
3. 可配置设计：一些现代处理器支持动态切换编码方案

# RISC-V乘法器示例配置 class MultiplierConfig: def __init__(self, booth_type="Booth2", width=32): self.booth_type = booth_type self.width = width def get_encoder(self): if self.booth_type == "Booth1": return booth1_encoder elif self.booth_type == "Booth2": return booth2_encoder elif self.booth_type == "Booth3": return booth3_encoder else: raise ValueError("Unsupported Booth type")

在实际项目中，我曾遇到一个有趣的现象：当使用Booth3算法处理特定数据模式时，由于频繁的±3A操作，反而导致整体延迟增加。这提醒我们，算法选择不能仅看理论指标，还需要结合实际工作负载进行优化。