改进的booth编码和wallace树部分积压缩法设计8*8乘法器

首先介绍几个概念

①改进的booth编码：

       booth编码用于乘法计算中对乘数进行重新编码，目的是减少加法的次数，减少程序的运行时间。本设计中，考虑8*8的乘法，对于一个8位的乘数，采用基四编码的思想编码，最终产生4个部分积相加（若不编码则会产生8个部分积），具体的编码规则如下：

       简单点来说，当考虑算法时，上表中仅有重编码值对我们有研究意义，将8位被乘数最后补一个零，将9位被乘数b₇b₆b₅b₄b₃b₂b₁b₀0分为四组编码进行编码：b₇b₆b₅、b₅b₄b₃、b₃b₂b₁、b₁b₀0。每一组对应一个重编码值，如不考虑重编码值对于部分积的影响，四个部分积（均为十六位）应该表示为：xxxxxxxxa、xxxxxxa00、xxxxa0000、xxa000000，其中a为8位被乘数，x为扩展位，x值和a的最高位相同，低位均补零。当考虑重编码值对部分积的影响时，部分积发生变化如下（仅仅用十六位中的a来说明就可以，因为a确定了十六位数就确定了）：

当重编码值为0时，部分积为0；

当重编码值为1时，a不变；

当重编码值为-1时，a变为-a(取反加1)；

当重编码值为2时，a左移一位；

当重编码值为-2时，a左移一位后将a变为-a（取反加1）；

②Wallace树部分积压缩算法：

假设用booth编码后的十六位部分积用P1、P2、P3、P4表示，压缩算法可以减少版图的关键路径和所需加法器的单元数目，具体的压缩算法方法如下图所示：（由于符号位可能为1也可能为0，所以高位不确定，但补位时低位一定为零，把可能为非零的数用*表示）

 经过图a和图b的两次Wallace数部分积压缩，最后的数据呈现图c上，一共需要20个全加器和2个半加器，最后仅需将p1和p2由一个简单的两输入加法器完成加法即可。（注：最后也可以将p1[2]和p2[2]由一个半加器相加，第三位到第十五位由全加器相加，由此完成加法效果相同，此方法的程序也在后面的程序中给出）

 需要注意，无论是半加器还是全加器，和保存在本位，进位保存在下一位。举例说明如下：考虑图b中的p1[5],p2[5],p3[5]相加，其和保存在p1[5],进位保存在p2[6]。图a和图b均为从高位向低位运算。

 本设计中包含两个功能模块：booth编码模块和Wallace数压缩算法模块。booth编码模块根据被乘数或者乘数改变为运行开始的信号，Wallace数压缩算法根据外加的一个时钟信号的上升沿为运行开始的信号。

 验证系统功能时用以下三组数据验证：

          10100111*01101101

          11111011*11111011

          00001010*00000011

     结果如下所示：

    结果显示：10100111*01101101=DA1B即（-89）*109=-9701

              11111011*11111011=19即（-5）*（-5）=25

              00001010*00000011=1E即10*3=30

    部分积经验证全部正确；

    测试数据涵盖了所有的情况（负乘以正，负乘以负，正乘以正），结果均符合实际情况。

    需要注意：运算中涉及到负数用补码表示；