乘法器的实现(阵列、Booth、Wallace)


1 乘法器

M和N位宽输入的乘法,采用一个N加法器需要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 。形式上相当于把乘数变换成一个四进制形式。8’b1000_00I0 = (2,0,0,-2)(四进制)

问题:与{0,1}相乘等效于AND,但是与{-2,-1,0,1,2}相乘还需要反向逻辑和移位逻辑,大小不同的部分积阵列对乘法器设计不合理。

2.2 改进的波兹编码

改进的波兹编码(modified Booth’s recoding)乘数由最高有效位(msb)到最低有效位(lsb)进行,按3位一组进行划分,相互重叠一位,编码表:

乘数位编码位编码
000000
001+被乘数01
010+被乘数01
011+2×被乘数10
100-2×被乘数I0
101-被乘数0I
110-被乘数0I
111000

本质是从msb到lsb检查乘数中1的字串,用一个以1开头或以-1结尾的字符串代替他们。
例子:
011 :一串1的开始,所以用一个开头的1代替(100)
110 :一串1的结尾,所以用一个结尾的-1代替(0I0)

8’b0111_1110,从msb到lsb,分成3位一组首尾重叠的4组:01(1),11(1),11(1),10(0)。编码后为10,00,00,I0,这与上述的编码是吻合的。

3 部分积的累加

对部分积相加是一个多操作数的加法,一个直接累加的部分积方法是用许多加法器形成阵列,所以被称为 阵列乘法器(array multiplier)。

一个更为先进的方法与树结构的形式完成加法。

3.1 阵列乘法器

在这里插入图片描述

AND 门产生部分积,加法器阵列实现相加。

在这里插入图片描述

所有关键路径都具有相同的长度。

上述乘法器只能进行无符号数相乘。

3.2 进位保留乘法器

如果进位向下沿而不是向左,可以得到一个更有效的实现。进位不是立即相加,而是传递给下一级加法器,在最后一级在一个快速进位传播(如超前进位)加法器中合并。

代价:需要一个额外的加法器,被称为向量合并(vector-merging)加法器。由此得到的乘法器被称为进位保留乘法器。

优点:在最坏情形下关键路径最短且唯一确定。

拓扑优化后的结构:

在这里插入图片描述

这种结构可以更好的映射到硅片上。

3.3 Wallace 树形乘法器

部分积加法器可以设计成树形,可以减少关键路径和所需的加法器单元数目。

在这里插入图片描述

上面的4个4位部分积,只有第3bit需要加 4 个。

第一步,第3列和低4列引入2个半加器,如图b所示,压缩后得到图c。
第二步,第3、4、5列引入3个全加器,第2列引入1个半加器,得到图d。
第三步,使用简单的两输入加法器。

前两步一共使用了3个全加器、3个半加器。原来的进位保留乘法器结构需要6个全加器、6个半加器。

全加器3个输入两个输出,所以运算过程中又称为压缩器。

优点:

  • 节省了较大乘法器所需硬件,减少了传播延时。

缺点:

  • 不规则,高质量版图设计任务变复杂。

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{I_b[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 编码的思想,因为不是实时乘数的话,预编码之后确实还是节省资源的。

参考

数字集成电路-电路、系统与设计(第二版)