案例介绍

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

作者[Author]:Hongjiang Yu 验证[Verified]:No 浏览次数 [Views]:1021
字体大小 [Fonts]: 14px 16px 18px

概要[Abstract]

首先介绍几个概念

①改进的booth编码:

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

1.png

       简单点来说,当考虑算法时,上表中仅有重编码值对我们有研究意义,将8位被乘数最后补一个零,将9位被乘数b7b6b5b4b3b2b1b00分为四组编码进行编码:b7b6b5、b5b4b3、b3b2b1、b1b00。每一组对应一个重编码值,如不考虑重编码值对于部分积的影响,四个部分积(均为十六位)应该表示为: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,所以高位不确定,但补位时低位一定为零,把可能为非零的数用*表示)

2.png

3.png

4.png

 

 经过图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

     结果如下所示:

6.png    结果显示:10100111*01101101=DA1B即(-89*109=-9701

              11111011*11111011=19即(-5*-5=25

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

 

    部分积经验证全部正确;

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

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

 

 

 

 

 

 

 

 


 
Copyright © Robei | | 鲁ICP备14018662号 |