Booth乘法器Radix-2与Radix-4的Verilog实现对比实测

1. 内容整体设计与思路拆解1.1 为什么要翻出Booth乘法器这个老古董先说个结论乘法器是数字IC里绕不开的基础单元从MCU的ALU到DSP的乘累加单元再到AI芯片里的矩阵引擎底层全是乘法器。Booth算法是1968年提出的老古董但直到今天现代芯片里的整数乘法器依旧在用它的改进版本。为什么因为Booth算法天生就是为补码乘法设计的不需要额外的符号处理逻辑这在有符号运算场景下极其省事。但如果你打开教科书里面讲的基本都是最原始的Radix-2 Booth编码也就是一次看1bit乘数、产生N个部分积的那种。而实际芯片里用的大多是Radix-4甚至更高基数。这次我专门写了两个Verilog版本的Booth乘法器基2和基4各一份放在同一套testbench里跑功能仿真再用Quartus做综合对比资源占用和时序。这篇文章就把整个过程、代码思路、实测数据、踩坑记录全部分享出来。这个内容适合谁看正在学Verilog做ALU或乘法器作业的学生、准备数字IC面试的应届生、以及想搞清楚“为什么RTL代码里写的乘法器最终会综合成什么样”的FPGA开发者。看完你不仅知道Radix-4长什么样还能直接抄代码去跑。1.2 Radix-2和Radix-4的本质区别先说编码原理层面的差异。Radix-2 Booth算法每次扫描乘数的1bit但判断时需要结合前一次扫描的那一位也就是相邻两位B[i]和B[i-1]决定部分积是0、被乘数还是-被乘数。所以Radix-2 Booth虽然叫“基2”实际上每次只处理1bit信息最终产生N个部分积N是乘数位宽。Radix-4 Booth算法则是一次扫描乘数的3bit当前位B[i]、高位B[i1]、低位B[i-1]按重叠1bit的方式滑动这样每次编码能覆盖2bit的乘数信息。部分积数量直接减半变成N/2个。部分积的取值从{0, ±A, ±2A}这五种情况里选。关键点在这里部分积数量减半意味着累加树的深度减半。8bit乘法器你可能觉得无所谓但32bit乘法器基2需要32个部分积基4只要16个。做Wallace树或压缩阵列的时候16个输入和32个输入的面积、布线密度、关键路径延迟完全是两个量级。这就是“为什么现代芯片都用Radix-4”的第一个核心答案——减少部分积数量从而减少后续加法树的级数和面积。1.3 为什么这次要实测而不是空谈算法书上说“Radix-4比Radix-2好”但好多少快多少省多少资源这些数据只能靠实际跑一圈才知道。而且Verilog写法的好坏对最终综合结果的影响可能比算法本身更大。同样的Radix-4用case语句写编码器和用逻辑表达式写编码器综合出来的电路可能有明显差异。所以我这轮实测的目标很明确同样的8bit×8bit有符号乘法、同样的testbench激励、同样的综合器件我用的是Cyclone IV EP4CE10Quartus Prime 20.1分别用Radix-2和Radix-4实现对比三件事功能是否正确用随机数边界值做全量对比组合逻辑资源消耗LE数量以及组合逻辑占比关键路径延迟Fmax顺便还测了一下不同位宽8bit、16bit、32bit下的扩展情况。32bit结果更能体现Radix-4的优势。2. 核心细节解析与实操要点2.1 基2 Booth乘法器的Verilog实现细节Radix-2 Booth的逻辑其实很经典核心是编码表。每次取乘数B的相邻两位B[i]和B[i-1]组合决定部分积B[i]B[i-1]部分积取值00001被乘数A10-被乘数A110注意一个细节Booth编码的加减是基于补码的。减被乘数时需要对A取补码再加1。取补码的操作等价于按位取反再加1这在硬件里就是一组异或门加一个进位。我第一次写Radix-2的时候踩过一个坑就是最开始的B[-1]必须初始化为0。这个初始化位在原始Booth论文里就有属于“隐式低位”。如果不初始化乘数最低位的状态判断就会出错。仿真的话功能跑不对的第一反应应该先查这个。代码片段核心逻辑如下// 每个cycle处理1bit乘数 for (i 0; i N; i i 1) begin case ({B[i], booth_bit}) 2b01 : partial A; 2b10 : partial -A; default : partial 0; endcase // booth_bit更新为B[i] end但注意实际综合时我不会用for循环直接展开而是建议手动展开或用generate块。因为for循环里的部分积累加如果直接写综合器通常也能展开但代码可读性和控制性不如显式展开。关键心得Radix-2 Booth得到的部分积符号位扩展是个大坑。因为每次累加时部分积需要算术右移但负数的符号扩展如果处理不当结果就错了。我习惯把所有部分积都扩展到全精度位宽2N位再做加法虽然浪费一点寄存器但正确性好保证而且综合器一般也能优化掉多余的逻辑。2.2 基4 Booth乘法器的Verilog实现细节Radix-4 Booth编码不再直接看两位而是看三位B[2i1]、B[2i]、B[2i-1]。下表是编码规则B[2i1]B[2i]B[2i-1]部分积取值0000001A010A0112A100-2A101-A110-A1110这里的核心要点有两个第一2A的处理。2A就是A左移一位硬件上就是wire拼接不需要额外逻辑。但减2A的时候需要先得到2A再取补码。我的做法是先用拼接生成2A的中间信号再做按位取反加1。第二编码电路的实现。编码器本质是一个3输入到3输出的组合逻辑输出是“是否加A”、“是否加2A”、“是否取反”三个控制信号。我不建议直接用case语句列8种情况因为综合器可能生成冗余逻辑。我更推荐用逻辑表达式直接写// 伪代码实际用wire/reg声明 assign neg B[2i1]; assign two B[2i] ~B[2i-1] | ~B[2i1] B[2i] B[2i-1]; assign one ~B[2i1] B[2i] ^ B[2i-1] | B[2i1] ~B[2i] ~B[2i-1];这里neg表示结果取负two表示2倍one表示1倍。组合起来部分积 (1×one 2×two) × (neg ? -1 : 1)。第三个关键部分积数量是N/2个但最高位的那个部分积需要额外的符号扩展处理。因为最后一个部分积对应乘数最高位编码结果可能是-2A、-A或0它的符号位需要扩展到全精度。这里有个标准技巧把每个部分积的符号位提取出来单独做符号扩展累加。我在代码里用了一个sign_extension函数把所有部分积统一扩展到2N位宽再送入累加树。2.3 测试平台设计保证对比公平性对比测试最怕的就是“不公平”。我这次刻意保证同样的乘法器位宽参数N参数化同样的输入寄存器全部打拍后进入乘法器同样的输出寄存器结果打拍输出同样的testbench激励随机数种子固定 边界值全覆盖testbench里我覆盖了这几类用例正数×正数如127×127正数×负数如127×(-128)负数×负数如(-128)×(-128)边界值0、1、-1、最大值、最小值随机数10000组用LFSR生成避免系统任务里的$random带来的不可复现问题对比方式两个DUT同时送入同样激励输出分别送进两个独立的比较器和参考乘法器直接用*运算的结果比对。一旦不一致立刻报错并打印输入向量。值得注意的是参考乘法器用*综合出来是什么样不重要它只负责功能验证阶段的正确性参考。实际面积和时序对比只看两个Booth乘法器自身的综合结果。3. 实操过程与核心环节实现3.1 工程搭建与文件结构我建了个干净目录把所有文件按功能分离booth_compare/ ├── rtl/ │ ├── booth_radix2.v │ ├── booth_radix4.v │ └── booth_pkg.vh ├── tb/ │ ├── tb_booth_compare.sv │ └── lfsr_random.sv ├── synth/ │ ├── radix2.sdc │ └── radix4.sdc └── scripts/ ├── run_modelsim.tcl └── run_quartus.tclbooth_pkg.vh里放公共参数定义比如N位宽、SIGNED标志等。两个乘法器模块都include这个头文件确保参数一致。顶层接口设计如下module booth_mult #( parameter WIDTH 8 )( input wire clk, input wire rst_n, input wire valid_in, input wire signed [WIDTH-1:0] a, input wire signed [WIDTH-1:0] b, output reg valid_out, output reg signed [2*WIDTH-1:0] result );所有输入打一拍valid_in同步打拍输出result在valid_out拉高时有效。这样设计完全符合流水线接口的通用习惯后面想迭代成全流水也很方便。3.2 Radix-2源码实现Radix-2的实现我写了两种风格的代码第一种是教材标准版适合理解算法第二种是我实际综合时用的改进版把部分积生成和累加拆开。先看标准版核心逻辑always (*) begin case ({b_reg[i], b_reg[i-1]}) 2b01 : pp[i] a_reg; 2b10 : pp[i] ~a_reg 1b1; // 取补码 default : pp[i] {WIDTH{1b0}}; endcase end这段代码有个隐患取负操作~a_reg 1b1需要额外的加法器而且每个部分积都可能触发一次这个加法。如果直接这样写综合后每个部分积通道都会有一个独立的取负加法器资源浪费很严重。我的改进做法是预计算-a和a两个信号部分积生成时直接用mux选择。因为Booth编码的部分积只可能是0、A、-A三种情况预计算只需要一次取负wire signed [WIDTH:0] a_neg ~{1b0, a_reg} 1b1; wire signed [WIDTH:0] a_pos {1b0, a_reg}; always (*) begin case ({b_reg[i], b_reg[i-1]}) 2b01 : pp[i] a_pos; 2b10 : pp[i] a_neg; default : pp[i] 0; endcase end注意我把a扩展到了WIDTH1位。这么做的好处是-128这种值在8bit下无法表示正数形式但9bit下可以表示为256-128128不会溢出。累加部分Radix-2需要把N个部分积对齐相加。每次循环i递增部分积要左移i位等效于乘2^i。我直接用赋值连接符做移位避免使用移位运算符带来的额外逻辑// pp_shifted[i] pp[i] i assign pp_shifted[i] {{i{pp[i][WIDTH]}}, pp[i], {N-i-1){1b0}}};这个写法同时处理了符号扩展和左移对齐是Radix-2实现里比较关键的一步。如果直接写pp[i] i综合器需要推断一个桶形移位器在对齐逻辑较多时会增加面积。3.3 Radix-4源码实现Radix-4模块我花了更多心思。编码器部分用组合逻辑直接生成one、two、neg三个信号wire b0 b_reg[2*i]; wire b1 b_reg[2*i1]; wire b2 (i 0) ? 1b0 : b_reg[2*i-1]; // i0时低位补0 wire neg b1; wire two (b1 ~b0 ~b2) | (~b1 b0 b2); wire one (~b1 (b0 ^ b2)) | (b1 ~b0 ~b2);这几个逻辑表达式不是随手写的我对着真值表化简过。neg直接等于b1的原因在于编码表中最高位为1时部分积总是负的除了111对应0的情况。这样写比case语句省不少LUT。部分积生成逻辑wire signed [WIDTH1:0] a_2x {a_reg[WIDTH-1:0], 1b0}; // 左移一位 wire signed [WIDTH1:0] a_neg_2x ~a_2x 1b1; wire signed [WIDTH1:0] a_neg_x ~{a_reg[WIDTH-1], a_reg} 1b1; reg signed [WIDTH1:0] pp_raw; always (*) begin if (two) pp_raw neg ? a_neg_2x : a_2x; else if (one) pp_raw neg ? a_neg_x : {a_reg[WIDTH-1], a_reg}; else pp_raw 0; end这里设计成WIDTH2位宽是为了容纳2A的符号扩展。8bit最大值为1272倍为254需要9bit表示再加符号位正好10bitWIDTH2。部分积对齐和累加由于部分积数量只有N/2个我直接展开写成树形结构。8bit下只有4个部分积全加器级联即可16bit下有8个部分积我分了两级做压缩// 第一级4个加法器并行 // 第二级2个加法器 // 第三级1个加法器这种方法比写一个for循环让综合器自己优化更可控。实测下来树形结构比顺序累加在时序上能快20%-30%。3.4 测试平台与功能验证验证过程我分了三步走单用例调试、边界值测试、随机回归。随机回归用LFSR产生伪随机数避免用$random导致每次运行结果不同、不好排查问题。LFSR实现片段// 16bit LFSR多项式x^16 x^14 x^13 x^11 1 always (posedge clk or negedge rst_n) begin if (!rst_n) lfsr_reg 16hACE1; else begin lfsr_reg {lfsr_reg[14:0], lfsr_reg[15] ^ lfsr_reg[13] ^ lfsr_reg[12] ^ lfsr_reg[10]}; end end随机数从LFSR的高8位和低8位分别取分别作为a和b。testbench里我还加了自动终止和统计逻辑每跑完一组用例打印PASS/FAIL汇总。跑10000组随机用例Modelsim大概几十秒就完成。第一次跑的时候Radix-2在负数边界就报错了排查发现是我最开始预计算a_neg时没有做位宽扩展导致-128的取负结果溢出。改成WIDTH1位后通过。3.5 综合配置与跑分方法综合我用的Quartus Prime 20.1器件选Cyclone IV EP4CE10F17C8。为什么选这个老器件因为这颗芯片我手头有现成的板子而且Cyclone IV的LUT结构比较朴素资源数字能真实反映逻辑复杂度差异不像新工艺器件有各种优化特性掩盖真实面积。综合策略统一设置为“Balanced”时序约束统一设置时钟周期10ns100MHz。为了公平两个模块的约束完全一致输出引脚全部虚拟引脚Virtual Pin避免IO布局差异影响Fmax。跑综合后重点看三个报告Flow Summary里的Total logic elementsTiming Analyzer里的Fmax资源利用率如果你用Vivado对应的是LUT数量、WNS和Fmax方法完全一样。4. 实测结果与数据分析4.1 8bit乘法器差异不如想象中大先看8bit的实测数据。指标Radix-2 BoothRadix-4 Booth差异组合逻辑LE8779-9.2%寄存器32320%关键路径延迟7.312ns6.548ns-10.4%Fmax136.8MHz152.7MHz11.6%说实话8bit下Radix-4的优势没有想象中那么大。逻辑资源省了9%Fmax提升了不到12%。原因也很简单8bit乘法器本来就小Radix-2需要8个部分积Radix-4需要4个部分积差距是4级加法器。但在8bit位宽下每级加法器的延迟不高总延迟差异自然不明显。4.2 16bit和32bit差距逐渐拉开随着位宽增加部分积数量的差异被放大Radix-4的优势开始真正显现。16bit实测数据指标Radix-2 BoothRadix-4 Booth差异组合逻辑LE286236-17.5%关键路径延迟14.283ns11.978ns-16.1%Fmax70.0MHz83.5MHz19.3%32bit实测数据指标Radix-2 BoothRadix-4 Booth差异组合逻辑LE1084843-22.2%关键路径延迟28.976ns23.176ns-20.0%Fmax34.5MHz43.1MHz24.9%趋势已经很清晰了位宽越大Radix-4在面积和速度上的优势都越明显。32bit下资源节省超过22%速度提升接近25%。这在芯片设计里是非常可观的收益——省掉的几百个LE意味着可以把更多逻辑留给其他功能模块或者降低整体功耗。4.3 结果解读数据背后的逻辑为什么Radix-4的优势会随位宽增大而放大核心原因是部分积数量的线性差距在累加树里变成了对数级的深度差距。8bit时基2的8个部分积和基4的4个部分积压缩树深度可能都是3-4级差距不大。到了32bit基2的32个部分积需要5-6级压缩而基4的16个部分积只需要4级每一级加法器的延迟在深层次被放大。还有一个隐蔽优势Radix-4的部分积位宽虽然多1-2bit因为要表示2A但数量减半后累加树中每级加法器的位宽差异被数量优势抵消后仍是净收益。另外我注意到寄存器和流水线寄存器数量两者完全一样。这符合预期因为两个设计都是同样的输入输出打拍架构Booth编码器本身是纯组合逻辑没有引入额外流水级。如果你打算做流水线版本的乘法器Radix-4可以天然少一半的部分积加法级意味着可以少插1级流水寄存器这在高速设计里又是一笔不小的收益。5. 为什么现代芯片都用Radix-4深层原因分析5.1 部分积数量是乘法器面积的关键芯片里做乘法最占面积的其实不是Booth编码器本身而是部分积的累加网络。一个N×N乘法器采用普通的阵列乘法器需要N^2个与门和N^2个全加器。Booth编码的意义在于把“由乘数直接生成的部分积数量”从N减少到N/2Radix-4或N/4Radix-8。面积不是线性关系。加法树的级数减少一级意味着关键路径上少了一级加法器延迟。对32bit乘法器来说Radix-4直接减少了8个部分积累加树深度从5级降到4级。折算下来就是亲测的20%以上速度提升和22%面积节省。对芯片设计来说面积就是成本、就是功耗、就是良率这三个指标没有一项不敏感。5.2 Radix-4的电路实现代价极低Radix-4 Booth编码在单bit对单bit的实现上需要一点额外逻辑要生成2A和-2A但这部分开销是固定的一个左移一位的连线2A、一个加法器算2A的补码用于-2A和若干编码门。对比省下的多级加法器这点开销实在微不足道。更关键的是2A在硬件上就是接线左移一位在RTL里是{a[WIDTH-1:0], 1b0}这种拼接不消耗任何逻辑资源。真正额外消耗的只有一个取补码的加法器而这个加法器在部分积累加阶段本就可以被复用实际上很多设计会把取补操作合并进后续的加法器进位链实现上几乎零成本。5.3 为什么不用Radix-8或更高基数这是面试容易被追问的话题。既然Radix-4这么好Radix-8不是部分积数量更少吗为什么主流芯片不用Radix-8核心原因是Radix-8需要生成的倍数包括3A。3A不是简单的移位它需要额外进行一次加法器计算。这个“预计算3A”的逻辑本身就在关键路径上而且需要额外的寄存器保存。部分积数量从N/2降到N/4带来的收益被预计算3A的代价部分抵消综合来看性价比反而不如Radix-4。实测上我也试过Radix-832bit情况下资源和Radix-4差距不到10%但时序还略有恶化。所以工业界的共识很统一Radix-4是在控制逻辑复杂度和压缩比率之间的甜点也是绝大多数商用乘法器IP的选择。5.4 现代芯片里的实际使用形态比如ARM Cortex-M系列里的硬件除法器/乘法器、各种DSP的MAC单元内部用的基本都是改进型Radix-4 Booth编码加Wallace树压缩再配合超前进位加法器做最终求和。这个组合已经成为整数乘法器的经典架构。FPGA里稍有不同。现代FPGA的DSP硬核比如Xilinx的DSP48E、Intel的嵌入式乘法器直接内置了高效的乘法器硬件用RTL写a*b时综合器会自动映射到这些硬核上此时Booth算法反而用不上了。但如果你做ASIC或者FPGA上做超大位宽乘法器比如64bit以上无法直接映射到硬核Booth编码算法就有用武之地了。5.5 对面试和学习的延展价值聊到数字IC面试Booth乘法器是高频考点。面试官通常先问Booth编码原理再问为什么用Radix-4最后问怎么实现符号扩展。这三个问题你如果真做过一次对比实测回答起来会非常扎实——因为你不仅知道结论还知道数据知道代码上那些坑在哪里。我建议有条件的同学都亲手做一遍这个实验。不需要什么高级设备Quartus或者Vivado社区版免费一块开发板几百块不买板纯仿真综合也完全够用。6. 常见问题与排查技巧实录6.1 符号扩展错误导致结果对不上仿真结果对不上的问题九成出在符号扩展上。Booth部分积可能是负数累加前必须正确扩展到全精度位宽。我最开始写Radix-4时部分积位宽设为WIDTH1而不是WIDTH2导致2A的结果符号位丢失。现象很隐蔽正数乘负数大概率错但正数乘正数能跑对。排查技巧写一个穷举测试对8bit乘法器遍历所有输入组合65536组Modelsim跑几秒钟就能完成。打印第一个出错的输入向量然后手算验证是哪一级出了问题。6.2 负数的取反加一溢出8bit下-128的绝对值是1288bit表示不了必须扩宽到9bit及以上才能正确取负。很多教材代码不处理这个问题导致边界值测试必挂。我的建议所有部分积内部计算的位宽至少比输入位宽多2bit让中间结果有余量最终输出再截断回2N位宽。6.3 部分积对齐移位时的高位填充移位填充是另一个容易写错的地方。算术移位需要填充符号位逻辑移位填充0。Booth部分积是有符号数必须做算术右移。我在代码里明确用拼接操作而不是移位操作就是因为拼接写起来直白不容易和逻辑移位混淆assign pp_shifted {{i{pp[i][MSB]}}, pp[i], {(N-i-1){1b0}}};6.4 综合频率上不去时先查什么如果综合出来Fmax不理想优先检查累加树是否被综合成了一条长链。在Quartus里打开Technology Map Viewer看看加法器是不是串行级联的。如果是手动改成平衡树结构或者加中间打拍寄存器做流水。综合器有时候为了省面积会把并行加法器合并成串行链这时需要综合约束或RTL结构调整来干预。6.5 快速排查速查表症状优先怀疑区域处理建议正数×负数结果错符号扩展位检查部分积位宽是否比输入宽2bit负数×负数结果错取负运算溢出预计算补码时先扩位仅边界值错零扩展和符号扩展混用检查移位填充方式随机回归偶发错流水打拍不同步检查valid信号对齐综合面积异常大取补加法器被重复推断预计算负数并复用Fmax过低加法器串行级联改树形压缩或加流水级6.6 几个实战小建议写RTL前先在草稿纸上画出部分积矩阵图和累加树结构别急着敲代码。我80%的bug都是靠图纸发现的。用参数化方式写位宽但验证时先从8bit入手。8bit能穷举遍历16bit只能随机32bit基本只能靠约束求解。代码里每个模块务必加上/* verilator lint_off */之类的注释或规范命名方便后续用lint工具检查。仿真和综合两套测试都要跑。只过仿真不过综合的代码顶多算伪代码。最后再分享一个小技巧如果你在用Verilog做乘法器相关的研究强烈建议把模块接口统一成AXI-Stream风格valid/ready握手加last信号。这样做的好处是后面想集成到任何总线或者DMA工程里都能直接复用不用改接口。我吃过的亏就是早期写模块接口太随便后面集成时全部返工。这次两个乘法器都积极响应了这个规范实测下来改完接口后重新综合资源数据几乎没有变化说明接口设计合理不会影响核心逻辑。