Booth算法与Wallace树

本文

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

版本	说明
0.1	初版发布

参考

百度百科-Booth算法

背景

在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。

Booth算法与Wallace树