什么是Booth算法介绍
Booth算法是一种适合于通过硬件实现的简便算法。将乘数看作从最低位开始的一串二进制数字。Booth算法的基本思路是:对于具有连续0和1的组,需要产生的部分积较少。对于乘数中每个0,仅需要将前面的累加的部分积向右移动一位。
Booth算法简介
利用移位和加法,可以实现二进制无符号数的乘法,在无符号数乘法的基础上,加上适当的符号处理,很容易得到带符号数的原码乘法器。但是,在计算机中,带符号数都以补码表示,若采用原码乘法器进行带符号数的乘法运算,则首先要将乘数和被乘数转换成原码,相乘后再将负的乘积转换成补码,致使运算过程比较复杂。
不少处理器直接采用补码相乘的方法,以避免运算过程中的码制转换,提高处理器的工作效率。然而,二进制无符号的乘法并不能直接推广到补码的乘法运算,比较普遍采用的是布斯(Booth)补码相乘算法。
Booth算法原理
布斯算法将乘数看作从最低位开始的一串二进制数字。从最低位算起,只要这串数字为“0“,就不执行任何操作;当这串数字遇到第一个“1”时执行一次减法,即减被乘数与该位权值的乘积,而对于其后的“1”不执行任何操作;当这串数字再变为“0”时,则遇到第一个“0”时执行一次加法,即加被乘数与该位权值的乘积,而对其后的“0”则不执行任何操作。如此一直进行到最高位。
举例来说,假设被乘数是5,乘数是7,即进行二进制数00000101与00000111相乘。该算法将7看作为三个“1”后面跟有五个“0”的一串数字。对于第一个”1”,该算法将减去5×2,对于第二和第三个“1”,则不执行任何操作;当遇到第一个“0”时,加5×2,得到最后结果是35。用算式表示为:
Booth算法计算步骤
Booth算法对乘数从低位开始判断,根据两个数据位的情况决定进行加法、减法还是仅仅移位操作。判断的两个数据位为当前位及其右边的位(初始时需要增加一个辅助位0),移位操作是向右移动。
其中booth算法在操作时,需要遵循一个操作表:
Yn |
Yn+1 |
操作 |
0 |
0 |
+0,右移一位 |
0 |
1、 |
+补,右移一位 |
1、 |
0 |
+补,右移一位 |
1、 |
1、 |
+0,右移一位 |
具体步骤如下:
1、被乘数X与乘数Y均以补码的形式参加乘法运算,运算结果是积的补码。
2、部分积和被乘数X采用双符号位,乘数Y采用单符号位。
3、初始部分积为0。运算前,在乘数Y的补码末位添加一位附加位Yn+1,初始值为0。
4、根据YnYn+1的值,按照上表进行累加右移操作,右移时遵循补码的移位规则。
5、累加n+1次,右移n次,最后一次不右移。
Booth算法用途
对于算术四则运算,加减用补码方法、乘除用原码方法无法实现。这样会使同一运算部件做四则算术运算需要进行码制转换,这会非常困难。
原码乘法中的符号位不能参加运算,需要单独用一个异或门产生乘积的符号位。故人们自然地思考能否让符号数字化后也参加乘法运算的问题,补码乘法就可以实现符号位直接参加运算。
补码乘除解决符号位参加运算的问题,但过程比较复杂,人们寻求较好的补码乘法和除法。由Booth(布斯)夫妇首先提出的比较法即Booth算法是一种比较好的带符号数乘法的方法,被广泛采用。
Booth算法采用相加和相减的操作,计算补码数据的乘积。Booth算法对乘数从低位开始判断,根据两个数据位的情况决定进行加法、减法还是仅仅移位操作。判断的两个数据位为当前位及其右边的位(初始时需要增加一个辅助位0),移位操作是向右移动。
Booth算法特点
2、位Booth编码可以将部分积的个数减少1/2,3位或4位的Booth编码可以使部分积的个数减少得更多。但是,在3位或3位以上的Booth编码中,虽然部分积的个数减少了,但是部分积产生电路变复杂了,部分积的产生需要的时间增加了,在一定程度上抵消了部分积的减少带来的好处。因此,在实际的乘法器设计中,常被使用的仍然是2位Booth编码。