基4 Booth编码：补码乘法的硬件实现
Booth算法是补码乘法的经典硬件实现，Radix-4版本每步处理2位，只需N/2步：
| 方法 | 步骤数 | 部分积数 | 硬件成本 |
|---|---|---|---|
| 移位加法 | 2N | N | 最低 |
| Radix-2 Booth | 2N | N | 低 |
| Radix-4 Booth | N | N/2 | 中等 |
| Wallace Tree | 1 | N/2→合并 | 高 |
| Baugh-Wooley | N | N/2 | 中等 |
// Lesson 13: Booth Multiplier — Radix-4 Booth Encoding
module booth_multiplier(
input wire clk, rst_n,
input wire start,
input wire [7:0] multiplicand, multiplier,
output reg [15:0] product,
output reg done
);
reg [7:0] M, M_neg; reg [16:0] P; reg [2:0] step;
always @(posedge clk or negedge rst_n) begin
if(!rst_n) begin product<=0; done<=0; step<=0; P<=0; M<=0; M_neg<=0; end
else if(start && step==0) begin
M<=multiplicand; M_neg<=~multiplicand+1;
P<={8'd0, multiplier, 1'b0}; step<=1; done<=0;
end else if(step>=1 && step<=4) begin
case({P[1],P[0]})
2'b01: P<=P+{M,9'd0};
2'b10: P<=P+{M_neg,9'd0};
default:;
endcase
P<=$signed(P)>>>2; step<=step+1;
end else if(step==5) begin product<=P[15:0]; done<=1; step<=0; end
end
endmoduleRISC-V M扩展定义了5条乘法指令，需要处理有符号/无符号组合：
| 指令 | 操作 | 结果 |
|---|---|---|
| MUL | x[rd] = (x[rs1] × x[rs2])[31:0] | 低32位 |
| MULH | x[rd] = (x[rs1] × x[rs2])[63:32] | 高32位(有符号×有符号) |
| MULHSU | x[rd] = (x[rs1] × x[rs2])[63:32] | 高32位(有符号×无符号) |
| MULHU | x[rd] = (x[rs1] × x[rs2])[63:32] | 高32位(无符号×无符号) |
MULHSU是有符号×无符号，这在计算地址偏移时很有用（基址有符号，偏移无符号）。Booth算法自然处理了这种混合情况。
| 变体 | 基数 | 部分积数 | 额外硬件 |
|---|---|---|---|
| Radix-2 | 2 | N | 无 |
| Radix-4 | 4 | N/2 | -M预计算 |
| Radix-8 | 8 | N/3 | ±M, ±2M, ±3M |
| Radix-16 | 16 | N/4 | ±M到±7M |
Radix-4是最佳平衡点：部分积减半，额外硬件仅需取反加1。更高基数需要更多预计算（如±3M需要加法器），面积开销不值得。
| 资料 | 内容 | 链接 |
|---|---|---|
| RISC-V特权规范 | CSR、Trap、中断完整定义 | riscv.org/specifications |
| RISC-V手册 | 中文版免费教材 | crva.ict.ac.cn |
| OpenSBI源码 | M-mode固件参考实现 | github.com/riscv/opensbi |
| Linux RISC-V | 内核移植与驱动 | kernel.org |
| BOOM处理器 | UC Berkeley开源OoO核心 | github.com/riscv-boom/riscv-boom |
| 香山处理器 | 中科院开源高性能核心 | github.com/OpenXiangShan |
| 课程范围 | 课程号 | 主题 |
|---|---|---|
| 特权架构 | 01-06 | 特权级→CSR→ecall→mret→trap→中断 |
| 内存系统 | 07-12 | PLIC→CLINT→SV39→TLB→直接映射→组相联 |
| 算术单元 | 13-14 | Booth乘法器→恢复余数除法 |
| 乱序执行 | 15-19 | OoO→ROB→寄存器重命名→记分牌→Tomasulo |
| 分支预测 | 20-21 | 2位预测器→BTB |
| RISC-V扩展 | 22-26 | RVC→RVM→RVA→RVF→RVD |
| 系统集成 | 27-30 | PMP→解码器→SoC→启动流程 |
建议使用以下环境进行实验：
| 实现 | 32×32延迟 | 面积(K gates) | 功耗 |
|---|---|---|---|
| 移位加法 | 32 cycles | 2 | 最低 |
| Radix-4 Booth | 16 cycles | 5 | 低 |
| Radix-4 + Wallace | 3-5 cycles | 15 | 中 |
| Radix-8 + Dadda | 2-3 cycles | 25 | 高 |
| 阵列乘法器 | 1 cycle | 50+ | 最高 |
Wallace Tree和Dadda Tree是两种经典的并行压缩器，将N个部分积压缩为2个（Sum和Carry），最后用一个快速加法器求和。它们的区别在于压缩策略：Wallace从最宽处开始压缩，Dadda尽量推迟压缩以减少硬件。
高性能处理器通常将乘法器流水化：
这样虽然单次乘法仍需4个周期，但每周期可以启动新的乘法，吞吐量提升4倍。
Wallace Tree是将Booth编码产生的部分积快速压缩的经典结构：
Dadda Tree与Wallace Tree类似，但采用更激进的压缩策略：只在必要时压缩，减少全加器数量。Dadda通常面积更小但深度可能略大。
为什么Radix-4 Booth编码能正确处理补码乘法？
Booth编码的关键洞察：补码表示中的连续1串可以替换为一次加法和一次减法。例如01110 = 10000 - 00010，减少部分积数量。Radix-4利用这种冗余将部分积数减半。