乘法器的实现（阵列、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位一组进行划分，相互重叠一位，编码表：

乘数位编码位编码000000001+被乘数01010+被乘数01011+2×被乘数10100-2×被乘数I0101-被乘数0I110-被乘数0I111000

本质是从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 {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]