文章目录
- 1 乘法器
- 2 产生部分积
-
- 2.1 波兹（Booth）编码
- 2.2 改进波兹编码
- 3 积累部分
-
- 3.1 阵列乘法器
- 3.2 进位保留乘法器
- 3.3 Wallace 树形乘法器
- 4 Verilog 实现
-
- 4.1 普通阵列乘法器
- 4.2 Booth 乘法器
- 4.3 Wallace 乘法器
- 5 总结
- 参考
1 乘法器
MN位宽输入乘法需要M个周期。
利用移位和相加积累M部分（partial product）加在一起。部分积的计算位相乘本质上是逻辑的。
101010 被乘数 × 1011 乘数 ——————————— 101010 \ 101010 | 部分积 000000 | 101010 / ————————————— 111001110 2 产生部分积
2.1 波兹（Booth）编码
乘数 8’b0111_1110 可以转换成 8’b1000_0000 - 8’b0000_0010 。这里用8’b1000_00I0 表示（I表示 -1 ）。
这可以减少非0行的数量，使部分积的数量至少减少原来的一半。减少部分积数意味着减少相加次数，从而加快计算速度，减少面积。
保证每两个连续位最多只有一个 1 或者 -1 。形式上相当于把乘数变成四进制。b1000_00I0 = (2,0,0,-2)(四进制)
问题：与{0，1}相乘AND，但与{-2、-1、0、1、2}相乘也需要反向逻辑和移位逻辑，不同尺寸的积阵列对乘法器设计不合理。
2.2 改进波兹编码
改进波兹编码（modified Booth’s recoding）乘数由最高有效位决定（msb）最低有效位（lsb）按三位一组划分，重叠一位，编码表：
| 乘数位 | 编码位 | 编码 |
|---|---|---|
| 000 | 0 | 00 |
| 001 | 被乘数 | 01 |
| 010 | 被乘数 | 01 |
| 011 | 2×被乘数 | 10 |
| 100 | -2×被乘数 | I0 |
| 101 | -被乘数 | 0I |
| 110 | -被乘数 | 0I |
| 111 | 0 | 00 |
本质是从msb到lsb检查乘数中的1字串，用1开头或1结尾的字符串代替。 例子： 011 ：一串1的开始，所以用一开始的1代替(100) 110 ：一串1的结尾，所以用结尾-1代替(0I0）
8’b0111_1110，从msb到lsb，分为：01(1)，11(1)，11(1)，11(1)，10(0)。编码后、00，I这与上述编码一致。
3 积累部分
部分积相加是多操作数的加法，直接积累的部分积方法是用多个加法器形成阵列，因此被称为 阵列乘法器（array multiplier）。
以树结构的形式完成加法是一种更先进的方法。
3.1 阵列乘法器
AND 门产生部分积，加法器阵列相加。
所有关键路径都有相同的长度。
上述乘法器只能乘以无符号数。
3.2 进位保留乘法器
如果进位向下而不是向左，则可以更有效地实现。进位不是立即添加，而是传输给下一级加法器，并在最后一级加法器中合并快速进位传输（如先进进位）。
成本:需要额外的加法器，称为向量合并（vector-merging）加法器。由此获得的乘法器称为进位保留乘法器。
优点:关键路径最短，最坏情况下唯一确定。
拓扑优化后的结构：
这种结构可以更好地映射到硅片上。
3.3 Wallace 树形乘法器
一些积加法器可以设计成树形，减少关键路径和所需加法器单元的数量。
以上四个四位部分的积累只有第三个bit需要加 4 个。
第一步是引入第三列和低4列的两个半加器，如图b所示，压缩后得到图c。 第二步，第三、四、五列引入三个全加器，第二列引入一个半加器d。 第三步，使用简单的两输入加法器。
前两步使用了3个全加器和3个半加器。原来的进位保留乘法器结构需要6个全加器和6个半加器。
三个全加器输入两个输出，因此在运行过程中也称为压缩器。
优点：
- 节省了大乘法器所需的硬件，减少了传播延迟。
缺点：
- 不规则，高质量的地图设计任务变得复杂。
4 Verilog 实现
4.1 普通阵列乘法器
以 8bit 以无符号数相乘为例，注意这里的设计不考虑性能。
array_multiplier.v：
`timescale 1ns/1ps module array_multiplier ( input I_sys_clk, input I_reset_n, input I_valid, input [7:0] I_a, input [7:0] I_b, output reg O_valid, output reg [15:0] O_c ); //--- Main body of code --- always @(posedge I_sys_clk or negedge I_reset_n) begin if(~I_reset_n) begin O_valid <= 1'b0; O_c <= 16'b0; end else begin O_valid <= I_valid; O_c <= (({8{I_b[0]}} & I_a) ) (({8{I_b[1]}} & I_a) << 1) (({8{I_b[2]}} & I_a) << 2) (({8{I_b[3]}} & I_a) << 3) (({8{I_b[4]}} & I_a) << 4) (({8{I_b[5]}} & I_a) << 5) (({8{Ib[6]}} & I_a) << 6) +
(({8{I_b[7]}} & I_a) << 7)
;
end
end
endmodule
testbench array_multiplier_tb.sv:
`timescale 1ns/1ps
module array_multiplier_tb();
parameter T = 5;
reg I_sys_clk;
reg I_reset_n;
reg I_valid ;
reg [7:0] I_a ;
reg [7:0] I_b ;
wire O_valid ;
wire [15:0] O_c ;
initial begin
I_sys_clk <= 'b0;
I_reset_n <= 'b0;
I_valid <= 'b0;
I_a <= 'b0;
I_b <= 'b0;
#(T*20)
I_reset_n <= 'b1;
#(T*20)
data_gen();
$finish();
end
always #(T/2) I_sys_clk <= ~I_sys_clk;
array_multiplier array_multiplier_u (
.I_sys_clk(I_sys_clk),
.I_reset_n(I_reset_n),
.I_valid (I_valid ),
.I_a (I_a ),
.I_b (I_b ),
.O_valid (O_valid ),
.O_c (O_c )
);
task data_gen();
for (int i = 0; i < 256; i++) begin
I_valid <= 'b1;
I_a <= i;
I_b <= i;
$display("%d x %d = %d", i, i, i*i);
@(posedge I_sys_clk);
I_valid <= 'b0;
end
endtask
endmodule
sim.do 文件：
cd D:/prj/modelsim_prj/multiplier/array_multiplier/
vlib work
vlog array_multiplier.v array_multiplier_tb.sv
vsim -novopt work.array_multiplier_tb
sim.bat 文件：
vsim -do sim.do
所有文件放在相同路径下，双击批处理文件即可开始Modelsim仿真。
仿真结果：
4.2 Booth 乘法器
Verilog 设计，注意，这个代码只是描述算法，需要进行符号位拓展、乘换成与逻辑、以及将乘2的幂转换为移位处理。
`timescale 1ns/1ps
module booth_multiplier (
input I_sys_clk,
input I_reset_n,
input I_valid ,
input [7:0] I_a ,
input [7:0] I_b ,
output reg O_valid ,
output reg [15:0] O_c
);
//--- Main body of code ---
wire [8:0] W_b;
wire [15:0] W_a_n;
wire [2:0] W_booth_code_pre [0:3];
reg R_valid ;
reg signed [15:0] R_partial_product [0:3];
assign W_b = {I_b, 1'b0};
assign W_a_n = -{
{8{I_a[7]}}, I_a};
genvar gen_i;
for (gen_i = 0; gen_i < 4; gen_i = gen_i + 1) begin
assign W_booth_code_pre[gen_i] = W_b[gen_i*2 +: 3];
always @(posedge I_sys_clk or negedge I_reset_n)
begin
if(~I_reset_n)
begin
R_partial_product[gen_i] <= 1'b0;
end
else
begin
case (W_booth_code_pre[gen_i])
3'b000: R_partial_product[gen_i] <= 9'b0;
3'b001: R_partial_product[gen_i] <= $signed(I_a) * 1 * 2**(gen_i*2) ;
3'b010: R_partial_product[gen_i] <= $signed(I_a) * 1 * 2**(gen_i*2) ;
3'b011: R_partial_product[gen_i] <= $signed(I_a) * 2 * 2**(gen_i*2) ;
3'b100: R_partial_product[gen_i] <= $signed(I_a) * -2 * 2**(gen_i*2) ;
3'b101: R_partial_product[gen_i] <= $signed(I_a) * -1 * 2**(gen_i*2) ;
3'b110: R_partial_product[gen_i] <= $signed(I_a) * -1 * 2**(gen_i*2) ;
3'b111: R_partial_product[gen_i] <= 9'b0;
default: R_partial_product[gen_i] <= 9'b0;
endcase
end
end
end
always @(posedge I_sys_clk or negedge I_reset_n)
begin
if(~I_reset_n)
begin
R_valid <= 1'b0;
end
else
begin
R_valid <= I_valid;
end
end
always @(posedge I_sys_clk or negedge I_reset_n)
begin
if(~I_reset_n)
begin
O_valid <= 1'b0;
O_c <= 16'b0;
end
else
begin
O_valid <= R_valid;
O_c <= R_partial_product[0] +
R_partial_product[1] +
R_partial_product[2] +
R_partial_product[3]
;
end
end
endmodule
testchech：
`timescale 1ns/1ps
module booth_multiplier_tb();
parameter T = 5;
reg I_sys_clk;
reg I_reset_n;
reg I_valid ;
reg [7:0] I_a ;
reg [7:0] I_b ;
wire O_valid ;
wire [15:0] O_c ;
// reference model signal
reg [7:0] R_i ;
reg [7:0] R1_i ;
reg [7:0] R2_i ;
initial begin
I_sys_clk <= 'b0;
I_reset_n <= 'b0;
I_valid <= 'b0;
I_a <= 'b0;
I_b <= 'b0;
#(T*20)
I_reset_n <= 'b1;
#(T*20)
data_gen();
$finish();
end
always #(T/2) I_sys_clk <= ~I_sys_clk;
booth_multiplier booth_multiplier_u (
.I_sys_clk(I_sys_clk),
.I_reset_n(I_reset_n),
.I_valid (I_valid ),
.I_a (I_a ),
.I_b (I_b ),
.O_valid (O_valid ),
.O_c (O_c )
);
task data_gen();
for (int i = 0; i < 256; i++) begin
I_valid <= 'b1;
I_a <= i;
I_b <= i;
R_i <= i;
R1_i <= R_i;
R2_i <= R1_i;
// reference model
if (O_valid)
begin
$display("i=%d, O_c=%d, check=%d", $signed(R2_i), $signed(O_c), $signed(O_c) == $signed(R2_i) * $signed(R2_i));
end
@(posedge I_sys_clk);
I_valid <= 'b0;
end
endtask
endmodule
Modilsim do文件做对应修改，sim.do：
cd D:/prj/modelsim_prj/multiplier/booth_multiplier/
vlib work
vlog booth_multiplier.v booth_multiplier_tb.sv
vsim -novopt work.booth_multiplier_tb
仿真结果：
4.3 Wallace 乘法器
以4bit×4bit为例，按照结构把线连起来就行： wallace_multiplier.v:
`timescale 1ns/1ps
module wallace_multiplier (
input I_sys_clk,
input I_reset_n,
input I_valid ,
input [3:0] I_a ,
input [3:0] I_b ,
output reg O_valid ,
output reg [7:0] O_c
);
reg R_valid ;
reg [3:0] R_partial_product [0:3];
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];
genvar gen_i;
generate
for (gen_i = 0; gen_i < 4; gen_i = gen_i + 1) begin
always @(posedge I_sys_clk or negedge I_reset_n)
begin
if(~I_reset_n)
begin
R_partial_product[gen_i] = 4'd0;
end
else
begin
R_partial_product[gen_i] = {4{I_b[gen_i]}} & I_a;
end
end
end
endgenerate
// level1
adder_half adder_half_u1 (
.I_a (R_partial_product[2][1]),
.I_b (R_partial_product[3][0]),
.O_c (W_level1_c[0]),
.O_carry(W_level1_carry[0])
);
adder_half adder_half_u2 (
.I_a (R_partial_product[1][3]),
.I_b (R_partial_product[2][2]),
.O_c (W_level1_c[1]),
.O_carry(W_level1_carry[1])
);
// level2
adder_half adder_half_u3 (
.I_a (R_partial_product[1][1]),
.I_b (R_partial_product[2][0]),
.O_c (W_level2_c[0] ),
.O_carry(W_level2_carry[0])
);
adder adder_u1 (
.I_a (R_partial_product[0][3]),
.I_b (R_partial_product[1][2]),
.I_carry (W_level1_c[0] ),
.O_c (W_level2_c[1] ),
.O_carry (W_level2_carry[1] )
);
adder adder_u2 (
.I_a (R_partial_product[1][3]),
.I_b (W_level1_c[1] ),
.I_carry (W_level1_carry[0] ),
.O_c (W_level2_c[2] ),
.O_carry (W_level2_carry[2] )
);
adder adder_u3 (
.I_a (R_partial_product[2][3]),
.I_b (R_partial_product[3][2]),
.I_carry (W_level1_carry[1] ),
.O_c (W_level2_c[3] ),
.O_carry (W_level2_carry[3] )
);
assign W_level3[0] = {R_partial_product[3][3], W_level2_c[3:1], R_partial_product[0][2:0]};
assign W_level3[1] = {W_level2_carry[3:0], W_level2_c[0], R_partial_product[1][0], 1'b0};
always @(posedge I_sys_clk or negedge I_reset_n)
begin
if(~I_reset_n)
begin
R_valid <= 1'b0;
O_valid <= 1'd0;
O_c <= 8'd0;
end
else
begin
R_valid <= I_valid;
O_valid <= R_valid;
O_c <= W_level3[0] + W_level3[1];
end
end
endmodule
module adder_half (
input I_a,
input I_b,
output O_c,
output O_carry
);
assign O_c = I_a ^ I_b;
assign O_carry = I_a & I_b;
endmodule
module adder (
input I_a,
input I_b,
input I_carry,
output O_c,
output O_carry
);
assign O_c = I_a ^ I_b ^ I_carry;
assign O_carry = (I_a & I_b) | ((I_a ^ I_b) & I_carry);
endmodule
仿真结果：
5 总结
数字集成电路设计可能对加法器的面积和版图有较高的要求。对于FPGA设计，可能基本阵列加法器用着还更简单顺手。主要看的的题目可能问的是与一个常数相乘的设计，这个时候要参考 Booth 编码的思想，因为不是实时乘数的话，预编码之后确实还是节省资源的。
参考
数字集成电路-电路、系统与设计（第二版）