Booth算法与Wallace树

本文

主要介绍Booth算法与Wallace树结构,并根据其原理实现16x16乘法器,可以实现优化传统乘法器结构,增强并行性提高运算速度。

版本 说明
0.1 初版发布

参考

背景

在DSP和CPU等各类芯片中,乘法器是必不可少的运算单元,由于乘法操作逻辑复杂,乘法器往往处于关键延时路径上,对系统运行速度影响很大,所以优化乘法器是很有必要的。为了优化乘法器,工程师们提出了很多高效的设计思想,BOOTH算法与wallace树最为典型,BOOTH算法可以减少部分乘积项,wallace树可以提高部分乘积相加的并行性。

BOOTH算法

介绍

传统的串行乘法使用的是移位相加的办法,这种方法虽然易于理解与实现,但是速度较慢,并且不能直接对补码进行处理,所以需要额外的符号处理逻辑,最终也就是需要三步:

  • 乘数符号处理:补码转原码
  • 移位相加
  • 乘级积符号处理:补码转原码

以上运算过程显然比较复杂,组合链延时比较长。解决此问题可以使用BOOTH算法,BOOTH算法有两个特点,一是可以实现补码相乘,二是可以减少乘积项。

原理

补码加法运算原理

要想理解BOOTH算法为什么支持补码乘法,首先要理解补码是如何直接进行加法运算的,那就是对和进行了取模。假设现在标准时间为4点整,而有一只表已经到7点了,为了校准时间,可以采用两种方法:一种是将逆时针退(7-3=4)3格;二是顺时针进(7+9-12=4)9格。所以y=a-b可以表示为y=a+(m-b),这里m为模长,(m-b)也就是补码形式。举例说明,因为’b1_0000-‘b10='b1110,这里对16取模,就可以表示为-2,所以’b0111(7)+'b1110(-2)='b1_0101,对16取模后,结果为’b0101(5)。

表达式变换1

补码形式a[n-1:0],其中a[n-1]为符号位,表达式的变换如下:
a[n-1:0] = -a[n-1]*2^(n-1) + a[n-2]*2^(n-2) + a[n-3]*2^(n-3) + … + a[1]*2^1 + a[0]*2^0
a[n-1:0] = (-a[n-1]+a[n-2])*2^(n-1) + (-a[n-2]+a[n-3])*2^(n-2) + … + (-a[1]+a[0])*2^1 + (-a[0]+0)*2^0

举例说明: ‘b1110(-2) = (-1+1)*2^3 + (-1+1)*2^2 + (-1+0)*2^1 + (-0+0)*2^0

所以 ‘b0111(7) * ‘b1110(-2) 有四个乘积项相加:

a[n-1] a[n-2] 乘积项
a[0]=0 a[-1]=0 ‘b0000_0000
a[1]=1 a[0]=0 ‘b1111_0010(-7*2)
a[2]=1 a[1]=1 ‘b0000_0000
a[3]=1 a[2]=1 ‘b0000_0000

由此可判断,基于2位Booth编码的算法,可以直接运算补码形式,但是并没有减少乘积项。

表达式变换2

补码形式a[n-1:0],其中a[n-1]为符号位,表达式的变换如下:
a[n-1:0] = -a[n-1]*2^(n-1) + a[n-2]*2^(n-2) + a[n-3]*2^(n-3) + … + a[1]*2^1 + a[0]*2^0
a[n-1:0] = (-2a[n-1]+a[n-2]+a[n-3])*2^(n-2) + (-2a[n-3]+a[n-4]+a[n-5])*2^(n-4) + … + (-2a[1]+a[0]+0)*2^0

举例说明: ‘b1110(-2) = (-2*1+1+1)*2^2 + (-2*1+0+0)*2^0

所以 ‘b0111(7) * ‘b1110(-2) 有两个乘积项相加:

a[n-1] a[n-2] a[n-3] 乘积项
a[1]=1 a[0]=0 a[-1]=0 ‘b1111_0010(-7*2)
a[3]=1 a[2]=1 a[1]=1 ‘b0000_0000

由此可判断,基于3位Booth编码的算法,可以直接运算补码形式,同时可以将乘积项减少一半。

总结

Booth编码可以使补码直接参与运算,3位Booth编码可以将部分积的个数减少1/2,4位或更多位的Booth编码可以使部分积的个数减少得更多,但是,更多位的Booth编码中,虽然部分积的个数减少了,但是部分积产生电路变复杂了,部分积的产生需要的时间增加了,在一定程度上抵消了部分积的减少带来的好处。综上,使用最多的是基于3位或4位BOOTH编码。

逻辑实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
reg [3:0] data1;
reg [3:0] data2;

reg [7:0] data1p;
reg [7:0] data1p_n;

reg [7:0] p0;
reg [7:0] p1;
reg [7:0] p;

assign data1p = {4{data1[3]},data1[3:0};
assign data1p_n = ~data1p +1;

always@*
    case({data[1:0],1'b0})
        3'b000, 3'b111: p0 = 8'b00000000;
        3'b001, 3'b010: p0 = data1p;
        3'b011        : p0 = {data1p[6:0],1'b0};
        3'b100        : p0 = {data1p_n[6:0],1'b0};
        3'b101, 3'b110: p0 = data1p_n;
    endcase

always@*
    case(data[3:1])
        3'b000, 3'b111: p1 = 8'b00000000;
        3'b001, 3'b010: p1 = {data1p[5:0],2'b00};
        3'b011        : p1 = {data1p[4:0],3'b000};
        3'b100        : p1 = {data1p_n[4:0],3'b000};
        3'b101, 3'b110: p1 = {data1p_n[5:0],2'b00};
    endcase

assign p = p0 + p1;

Wallace树

介绍

Wallace在1964年提出采用树形结构减少多个数累加次数的方法,成为wallace树结构加法器。wallance树充分利用全加器3-2压缩的特性,随时将可利用的所有输入和中间结果及时并行计算,大大节省了计算延时。

原理

Wallace树的原理简单说就是使用全加器把3个n位的数相加转换成2个n+1位的数相加,以此类推,可以用多个全加器把多个数规约成2个数相加,最后用加法器把这两个最终的数相加得到乘积。

什么是全加器3-2压缩的特性?全加器输入cin、a、b,输出为cout,sum,这就是3-2压缩的特性。举个例子:

a+b+c=a^b^c + (a&b|a&c|b&c)<<1

由此可见,通过Wallace树可以并行处理减少加数项,比如8个加数项:

级数 加数个数 结构
1 8->6 (3,3,2)->(2,2,2)
2 6->4 (3,3)->(2,2)
3 4->3 (3,1)->(2,1)
4 3->2 (3)->2
5 2->1 加法器实现两数相加

读到这里可能你会有疑问,直接使用加法器三级就可以实现啊,也就是8->4->2->1,岂不是运算更快?这里需要注意了,这样计算每一级逻辑是多位加法器延时,而采用Wallace树结构每一级逻辑相当于1位全加器延时。


文章原创,可能存在部分错误,欢迎指正,联系邮箱 cao_arvin@163.com。