相关阅读数字IC前端https://blog.csdn.net/weixin_45791458/category_12173698.html?spm1001.2014.3001.5482华莱士树虽然能够显著缩短乘法器的关键路径但它本质上仍是一种较为规则的结构。这种规则性一方面使树结构更容易生成另一方面也带来了一个问题它所使用的全加器和半加器数量并不一定是最少的。为了解决这个问题Dadda提出了一种对华莱士树的改进方法后来被称为Dadda Tree。这种结构在不增加树深度的前提下尽可能减少全加器和半加器的使用数量从而在节省硬件资源的同时仍然保持与华莱士树相近的性能。Dadda树的核心思想不是像华莱士树那样尽可能早地压缩所有列而是控制每一阶段各列的最大高度使压缩过程“刚好够用”从而减少加法器数量。其压缩策略可概括为如下过程1、先定义一个目标高度序列且其中表示向下取整。然后找到最大的j使得房钱部分积中至少有一列的深度大于。2、对所有深度超过的列进行压缩压缩时使用全加器或半加器使这些列的深度最终不超过。在这一过程中还需要同时考虑来自低位列压缩后产生的进位并尽可能减少所使用的器件数量。3、重复执行上述两个步骤直到部分积最终被压缩为两行。换句话说当压缩过程进行到时压缩阶段结束随后即可进入最后的向量合并阶段。根据这一算法可以得到Dadda树的结构如图1所示。图中的斜杠/表示全加器其输出分别连接到右上方的本位和以及左下方送往高位的进位带反斜杠\的/表示半加器。以四乘四Dadda Tree乘法器为例其压缩过程如下。首先按照Dadda的规则找到最大的。此时第四列从右往左计数有四个部分积因此需要使用一个半加器进行压缩第五列再加上来自第四列的进位后同样达到四个部分积所以这里也需要使用一个半加器进行压缩。之后继续重复该过程找到最大的。这时第三列有三个部分积因此使用一个半加器压缩第四列由于接收了第三列传来的进位变为四个部分积因此需要使用全加器压缩第五列和第六列的情况与此类似也都需要使用全加器进行压缩。经过这一轮处理后部分积最终被压缩为两行。最后再通过一个向量合并器完成最终求和。这个向量合并器既可以使用普通传播进位加法器也可以使用超前进位加法器。图1 dadda树乘法器的覆盖过程具体的Verilog实现见附录使用Modelsim进行仿真的结果如图2所示。采用Synopsys的综合工具Design Compiler并基于0.13 μm工艺库进行综合综合结果如图3所示。图2 dadda树乘法器仿真结果​​​​​​图3 dadda树乘法器综合结果在Design Compiler中使用report_timing命令可以得到关键路径延迟如图4所示。可以看到该结构的关键路径延迟为1.54ns略差于华莱士树乘法器。这主要是因为Dadda树在最后一级向量合并时需要处理的数据位宽相对更大因此末级加法器的延迟会稍高一些。图4 dadda树乘法器关键路径报告在Design Compiler中使用report_area命令可以得到电路面积报告如图5所示。可以看出Dadda树乘法器在面积方面优于华莱士树乘法器。若不考虑最后的向量合并器仅从部分积压缩网络来看Dadda树完成四位乘法部分积累加只使用了三个全加器和三个半加器相比之下华莱士树则使用了五个全加器和三个半加器。随着数据位宽增加华莱士树对加法器数量的需求增长速度通常也快于Dadda树因此可以认为Dadda树是华莱士树的一种资源优化版本。不过Dadda树也有其不足之处。与华莱士树相比它的结构没有那么规则设计和实现时往往更复杂需要投入更多时间和人力。图5 dadda树乘法器面积报告下面给出四乘四Dadda Tree乘法器的Verilog代码实现。module Dadda_Multiplier( input [3:0] A, input [3:0] B, output [7:0] Sum ); wire [3:0] partial_product [3:0]; wire [1:0] W_level1_c, W_level1_carry; wire [3:0] W_level2_c, W_level2_carry; wire [6:0] W_level3[0:1]; //产生部分积 assign partial_product[0] B[0]?A:0; assign partial_product[1] B[1]?A:0; assign partial_product[2] B[2]?A:0; assign partial_product[3] B[3]?A:0; // 阶段1 // *************************************************** Adder_half adder_half_u1 ( .Add1 (partial_product[2][1]), .Add2 (partial_product[3][0]), .Res (W_level1_c[0]), .Carry (W_level1_carry[0]) ); Adder_half adder_half_u2 ( .Add1 (partial_product[3][1]), .Add2 (partial_product[2][2]), .Res (W_level1_c[1]), .Carry (W_level1_carry[1]) ); // *************************************************** // 阶段2 // *************************************************** Adder_half adder_half_u3 ( .Add1 (partial_product[1][1]), .Add2 (partial_product[2][0]), .Res (W_level2_c[0]), .Carry (W_level2_carry[0]) ); Adder adder_u1 ( .Add1 (partial_product[0][3]), .Add2 (partial_product[1][2]), .I_carry (W_level1_c[0]), .Res (W_level2_c[1]), .Carry (W_level2_carry[1]) ); Adder adder_u2 ( .Add1 (partial_product[1][3]), .Add2 (W_level1_c[1]), .I_carry (W_level1_carry[0]), .Res (W_level2_c[2]), .Carry (W_level2_carry[2]) ); Adder adder_u3 ( .Mult1 (partial_product[2][3]), .Mult2 (partial_product[3][2]), .I_carry (W_level1_carry[1]), .Res (W_level2_c[3]), .Carry (W_level2_carry[3]) ); // *************************************************** // 向量合并 // *************************************************** assign W_level3[0] {partial_product[3][3], W_level2_c[3:1], partial_product[0][2:0]}; assign W_level3[1] {W_level2_carry[3:0], W_level2_c[0], partial_product[1][0], 1b0}; assign Sum W_level3[0] W_level3[1]; // *************************************************** endmodule // 半加器 module Adder_half( input Add1, input Add2, output Res, output Carry ); assign Res Add1 ^ Add2; assign Carry Add1 Add2; endmodule // 全加器 module Adder( input Add1, input Add2, input I_carry, output Res, output Carry ); assign Res Add1 ^ Add2 ^ I_carry; assign Carry (Add1 Add2) | ((Add1 ^ Add2) I_carry); endmodule