移位乘法器设计

本次实验需要理解移位加法乘法器的工作原理，并掌握有符号乘法通过无符号运算实现的方法。

二进制乘法的原理

设被乘数为 A，乘数为 B，且 A、B 都为 16 位无符号数：

\[B = \sum_{i=0}^{15} b_i \cdot 2^i\]

则乘法可以表示为：

\[A \times B = \sum_{i=0}^{15} (b_i \cdot A \cdot 2^i)\]

其中，当 b_i 为 1 时，对应的部分积为 A 左移 i 位； 当 b_i 为 0 时，对应部分积为 0。

阵列乘法器

阵列乘法器

在学习算数运算电路的时候，课堂上介绍了阵列乘法器，通过硬连线的方式实现移位操作， 使用全加器或者其他的加法器将部分积依次相加，得到最后的乘法结果。结构如上图所示。 实现了两个无符号的二进制数相乘。也介绍了阵列乘法器有符号数与无符号数，有符号数与有符号数的乘法实现。

多周期移位乘法器实现

对于两个n位宽的二进制数乘法电路，当n的值比较大时，使用阵列乘法器实现需要大量的门电路， 并且关键路径会非常长，单周期内难以完成乘法计算。

另一种方案是通过一个移位寄存器和一个加法器，通过若干个周期完成乘法计算。 对于16位的乘法器，每个周期完成以下操作：

  1. 判断乘数最低位

  2. 若该位为 1，则将被乘数加到部分积寄存器

  3. 被乘数左移一位

  4. 乘数右移一位

  5. 计数器加 1

当计数器达到 15 时，运算结束，得到乘法最终的结果。 对于移位乘法器，硬件实现结构简单，运算时间与位宽成正比。

移位乘法器

有符号数乘法的问题

如果乘数是补码表示的正数，可以使用和无符号数一致的方法运算。 被乘数可以是补码表示的正数或者负数，当为负数时需要对符号位进行扩展。 而乘数是补码表示的负数时，则需要做额外的处理。

二进制数的补码表示

补码我们已经很熟悉了。

补码表示

对于 N 位二进制补码数，其数值可以表示为：

\[B = -b_{N-1} \cdot 2^{N-1} + \sum_{i=0}^{N-2} b_i \cdot 2^i\]

2的补码表示法

证明上面的 N 位二进制补码数的数值表示公式。若给出一个补码表示的负数，让我们计算表示的值，有两种常见的办法。 第一种对它求2的补码，也就是对它进行取反加一，得到它的绝对值，再加上负号。例如求补码 11111110 表示的值， 取反得到 00000001 ，再加一得到 00000010，也就是2，因此补码 11111110 表示-2。或者直接使用公式计算数值表示， 例如求补码 11000000 表示的值，也就是-128 + 64 = -64。可以根据1的个数，选取合适的方法快速计算出补码表示的负数的值。

其中最高位 b_{N-1} 为符号位，具有负权重。 这意味着补码中的最高位并不能像普通的位一样 通过“移位加法”直接参与部分积计算。

计算有符号数乘法

方法1

有符号数通常使用补码来表示。对于补码表示的负数，我们可以求2的补码，统一转换为正数进行计算。如果乘数和被乘数都是补码表示的负数， 那么结果不需要再进行改变，如果只有乘数或者被乘数是补码表示的负数，则对计算结果也求2的补码，得到最终的结果。

为正确实现有符号乘法，可以采用如下步骤：

  1. 判断输入 A 和 B 的符号位

  2. 若为负数，取其补码，转换为无符号数

  3. 使用无符号移位乘法器计算乘积

  4. 根据 A 和 B 的原始符号，对结果进行符号修正

最终结果的符号由以下关系确定：

result_sign = A_sign ^ B_sign

若 result_sign 为 1，则对无符号乘积求2的补码。

方法2

当然也可以通过另一种办法计算有符号数乘法，被乘数乘以乘数的某一位得到部分积，最后每个部分积之间做加法，补码是可以直接进行加法的。 如果被乘数是补码表示的负数，部分积则需要扩展符号位。一种更好的方式是，相较于上面的“移位加乘法器”的结构，乘数和被乘数的移位方向都反过来。 被乘数A使用算数右移，而乘数B使用左移，先对高位相乘，依次往下计算部分积并相加。 被乘数A则不是放入移位寄存器的最低位，而是放在高位，并在最高位补上符号位，这样算数右移即可实现符号位的扩展。

被乘数算数右移

对于乘数B，如果是补码表示的负数，可以求2的补码，转换为正数进行计算，然后对计算结果也求2的补码，得到最终的结果。 当然也可以根据公式，最高位具有负权重，需要对部分积求2的补码，其余位则保持一致即可。当然也可以最后对结果进行修正， 本来应该乘以 -2^n-1 ，但正常处理就乘以了 2^n-1 ，因此最后减去 A * (2^n) ，就能得到正确的结果。

设计多周期移位乘法器

多周期移位乘法器本身就是适用于两个无符号数计算相乘，通过额外的电路结构，即可计算有符号数乘法，在上面已经讲了一些实现的方法， 需要你去仔细的思考、比较，并选择出一种合理的方案：既可以计算两个无符号数相乘，也可以计算两个补码表示的有符号数相乘， 还能计算一个无符号数和一个补码表示的有符号数相乘。

设计16位多周期移位乘法器

我们的乘法器需要能够完成上述功能，既可以计算两个无符号数相乘，也可以计算两个补码表示的有符号数相乘， 还能计算一个无符号数和一个补码表示的有符号数相乘。我们通过两个输入信号表明乘数和被乘数分别是无符号数， 还是补码表示的有符号数。写出你认为合适的方案，并参照上面给出的移位乘法器的电路结构，画出你的电路结构。

求2的补码

求2的补码有多种方式，最常见的方式就是取反加一（其1的补码加1），或者减一再取反，这两种方式都可以用一个加法器和反相器简单实现。 也可以不使用加法器实现，我们保留从右往左的第一个"1"及其右边的"0"不变，其余位全部取反。 比如对 11100000 求2的补码，保留从右往左的第一个"1"及其右边的"0"，也就是低6位保持不变，高2位取反， 得到 00100000，随便尝试一些数求2的补码，检查是否与取反加一的结果一致。

求2的补码

保留从右往左的第一个"1"及其右边的"0"不变，其余位全部取反，为什么就能求2的补码，尝试给出证明。 如何实现该电路呢？我们可以从低位一直或到最高位，检查最低位是不是1，如果不是，最低为或上次低位，如果为1，则次低位为1，如果不是，将或的结果与更高一位相或... 这样就能得知第一个"1"的位置，并且第一个"1"之后的或会一直传播下去，然后利用异或门可控取反。

输入为 0 的特殊情况

若 A 或 B 任意一个为 0，则乘法结果必然为 0。 在这种情况下，状态机可以直接跳转到完成状态， 无需进入移位计算过程，从而简化计算。

处理输入为 0

如何处理输入为 0 更好呢，实现并分别描述数据A、数据B的输入为 0 ，状态机是如何运行的。

状态机设计

我们可以通过有限状态机控制乘法过程，参考的状态划分如下：

  • IDLE：等待开始信号

  • PREPARE：符号判断与无符号转换、输入是否为 0

  • CALC：移位加法计算

  • SIGN_FIX：结果修正

  • DONE：计算完成，输出结果，标明计算结果已经完成

你可以根据设计情况自由修改状态机。

FSM 状态转移图

完成好乘法器设计之后，画出你的完整的状态转移图。

实现16位多周期移位乘法器

实现多周期移位乘法器的RTL编写，我们本次不给出框架代码，请自行思考。输入两个16位的数，以及指示两个数是有符号数还是无符号数，得到32位的结果。 实现后，编写 testbench 程序，验证你的多周期移位乘法器，需要对计算两个无符号数相乘，计算两个补码表示的有符号数相乘， 计算一个无符号数和一个补码表示的有符号数相乘进行测试。目前不需要上FPGA板，等之后完成了输入输出的部分再进行上板实验。

乘法器输入

我们的乘法器的输入部分设计如下：

FPGA 的 SW0~SW15 作为数据A或者B输入、SW16 用于指示数据A或者数据B是有符号数还是无符号数，当SW16为1时， 为有符号数，0时为无符号数。SW17 作为数据A 输入的标志位，SW18 作为数据B 输入的标志位，SW19作为开始计算的标志位。

我们需要约定如下状态机，在 S0 阶段，先输入数据A，使用SW0~SW15指示数据A的值，SW16 用于指示数据A是有符号数还是无符号数。 当SW17为1，存储数据A的值和数据类型，进入 S1 阶段；输入数据B，同样使用SW0~SW15指示数据B的值，SW16 用于指示数据B是有符号数还是无符号数。 当SW18为1，存储数据B的值和数据类型，进入 S2 阶段；当SW19为1时，进入 S3 阶段； 此时将乘法器的数据输入valid信号置为有效，数据A、B和它们的数据类型传入乘法器，开始进行乘法计算。

在若干个周期乘法器计算完成之后，乘法器会将finish信号置为有效。finish信号用于标志数码管显示的结果， 当finish有效时，数码管上应该显示乘法器的32位结果，否则显示16位的数据A和16位的数据B，以{DataA, DataB}的方式位拼接起来显示。

当我们想要重新输入数据，通过reset信号，将各个状态机恢复如初，然后重新按照上面的方法输入数据。

输入设计的参考状态机如下：

  • S0：等待数据A和数据类型的输入

  • S1：等待数据B和数据类型的输入

  • S2：用于显示数据A和数据B，等待准备开始乘法计算

  • S3：将乘法器的输入valid置为有效，数据A、B和它们的数据类型传入乘法器

输入valid之后，乘法器开始正常工作，直到计算出结果，将结果显示在七段数码管上。

完成16位多周期移位乘法器上板

参照输入设计，完成输入功能，并将结果给七段数码管模块，功能需要按照规定实现， 但如何设计，状态机划分可以自定义实现。完成所有的设计。

下面是代码框架参考：

乘法器代码框架参考
 1   module top (
 2      clk
 3      ,reset
 4      ,data
 5      ,code
 6      ,cs_o
 7   );
 8
 9   input   wire            clk;    // 100 Mhz System Clock
10   input   wire            reset;
11   input   wire   [23:0]   data;
12   output  wire    [7:0]   code;
13   output  wire    [7:0]   cs_o;
14
15   wire    [15:0]  a, b;
16   wire    sign_a, sign_b, valid;
17
18   fsm_input u_fsm_input(
19      .clk             (clk         )  // <<i<<
20      ,.reset          (reset       )  // <<i<<
21      ,.data_in        (data[15:0]  )  // <<i<<
22      ,.sign_in        (data[16]    )  // <<i<<
23      ,.valid_a        (data[17]    )  // <<i<<
24      ,.valid_b        (data[18]    )  // <<i<<
25      ,.ready          (data[19]    )  // <<i<<
26      ,.a              (a           )  // >>o>>
27      ,.b              (b           )  // >>o>>
28      ,.sign_a         (sign_a      )  // >>o>>
29      ,.sign_b         (sign_b      )  // >>o>>
30      ,.valid          (valid       )  // >>o>>
31   );
32
33   wire    [31:0]  result;
34   wire    finish;
35
36   mul u_mul(
37      .clk         (clk    )  // <<i<<
38      ,.reset      (reset  )  // <<i<<
39      ,.a          (a      )  // <<i<<
40      ,.b          (b      )  // <<i<<
41      ,.sign_a     (sign_a )  // <<i<<
42      ,.sign_b     (sign_b )  // <<i<<
43      ,.valid      (valid  )  // <<i<<
44      ,.result     (result )  // >>o>>
45      ,.finish     (finish )  // >>o>>
46   );
47
48   wire    [31:0]  display_data;
49   assign  display_data = finish ? result : {a, b};
50
51   seg_driver u_seg_driver(
52      .clk     (clk           )  // <<i<<
53      ,.data   (display_data  )  // <<i<<
54      ,.reset  (reset         )  // <<i<<
55      ,.code   (code          )  // >>o>>
56      ,.cs_o   (cs_o          )  // >>o>>
57   );
58
59   endmodule