booth算法

1、booth算法定义

将乘数看作从最低位开始的一串二进制数字。Booth算法的基本思路是：对于具有连续0和1的组，需要产生的部分积较少。对于乘数中每个0，仅需要将前面的累加的部分积向右移动一位。
布斯编码采用相加和相减的操作计算补码数据的乘积，可以减少部分积的数目，用来计算有符号乘法，提高乘法运算的速度。

2、二进制乘法过程

3、二进制乘法转换成 booth乘法运算

例如假设有一个8位乘数（Multiplier）：0011_1110，它将产生6行非零的部分积。如果把该数字记成另一种形式，0100_00(-1)0（可以验证是同一个数字，-1是负1）

二进制化为十进制 0011_1110 = 0*2^7 + 0*2^6 + 1*2^5 + 1*2^4 + 1*2^3 + 1*2^2 + 1*2^1 + 0*2^0 = 62 0100_00(-1)0 = 0*2^7 + 1*2^6 + 0*2^5 + 0*2^4 + 0*2^3 + 0*2^2 + (-1)*2^1 + 0*2^0 = 64 -2 = 62 注:64=2^6 2=2^1 0011_1110 = 0100_00(-1)0 = 2^6-2^1=0100_0000 - 0000_0010 

计算0010_0001×0011_1110，在这里可以首先将乘数0011_1110改写为0100_0000 – 0000_0010，即根据乘法分配律得:

 0010_0001×0011_1110 = 0010_0001×(0100_0000 - 0000_0010) 

此时，对于乘数，我们需要计算6次的部分积，变成了计算两次部分积。

4、Radix-2 Booth乘法器

Radix-2 Booth乘法器，即是基2 Booth乘法器，基为2的一次方。

2 = 2^1 

相邻两个数据位，进行公式（第0位）-（第1位）计算，得到两位的编码（相邻居两位，从后面像前面减） 00 0-0= 0 转化成二进制编码 0 01 1-0= 1 转化成二进制编码 1 10 0-1=-1 转化成二进制编码-1 11 1-1= 0 转化成二进制编码 0 根据两个数据位的编码决定进行加法、减法还是仅仅移位操作。 

5、Radix-4 Booth乘法器

Radix-4 Booth乘法器，即是基4 Booth乘法器。基为2的二次方。

4 = 2^2 

相邻3位数，进行公式-2*（第3位）+（第2位）+（第1位）计算，得到两位的编码（相邻居两位，从后面像前面减） 000 (-2)*0+0+0= 0 转化成二进制编码 00，即 +0 001 (-2)*0+0+1= 1 转化成二进制编码 01，即 +1 010 (-2)*0+1+0= 1 转化成二进制编码 01，即 +1 011 (-2)*0+1+1= 2 转化成二进制编码 10，即 +2 100 (-2)*1+0+0=-2 转化成二进制编码-10，即 -2 101 (-2)*1+0+1=-1 转化成二进制编码-01，即 -1 110 (-2)*1+1+0=-1 转化成二进制编码-01，即 -1 111 (-2)*1+1+1= 0 转化成二进制编码 00，即 -0 

6、Booth乘法器计算实例

下面展示一些 内联代码片。

从二进制看9：（共6步） 9 = 0*2^5 + 0*2^4 + 1*2^3 + 0*2^2 + 0*2^1 + 1*2^0 从基2看9：（共6步） 9 = 0*2^4 + 1*2^4 + (-1)*2^3 + 0*2^2 + 1*2^1 + (-1)*2^0 从基4看9：（共3步） 9 = 1*4^2 + (-2)*4^1 + 1*4^0 = 1*2^4 + (-2)*2^2 + 1*2^0 

注意：算式绿色部分的计算

(-2)*A*4^1 步骤1 4^1 = 2^2(转化成2的偶次方)表示结果算术左移两位 步骤2 (-2)*A=[(-1)*A]*2^1 步骤2.1 2^1表示在基2中表示结果向左移1位 步骤2.2 (-1)*A表示加上(-A)；此例题中A=000111,(-A)=~()+1=+1= 所以将结果11_1001在基2中表示结果向左移1位，得到111_0010，乘积的位数为2*6位，前面符号位补齐 

此处引用 https://zhuanlan.zhihu.com/p/.

例如第2章节的例题：计算0010_0001×0011_1110(即为33×62=2046)，分别按照基2和基4展开运算

在这里可以首先将乘数0011_1110按照基2展开为 0011_1110——0 相邻两位 首位分组为 0(0)*2^0 + 1(0)*2^1 + 1(1)*2^2 + 1(1)*2^3 + 1(1)*2^4 + 1(1)*2^5 + 0(1)*2^6 + 0(0)*2^7 括号中的后一位减去前一位 0011_1110 = (0-0)*2^0 + (0-1)*2^1 + (1-1)*2^2 + (1-1)*2^3 + (1-1)*2^4 + (1-1)*2^5 + (1-0)*2^6 + (0-0)*2^7 = (-1)*2^1 + 1*2^6 //= (-2) + 64 = 62 = (-1)*0000_0010 + 0100_0000 0010_0001*0011_1110 = 0010_0001*(0100_0000 - 0000_0010) = 0010_0001*0100_0000 -0010_0001*0000_0010 //进行移位计算,-0010_0001的补码为1101_1111,8*8位宽度为16位，前面符号为补齐 = 00_0010_0001_000000 + 1101_1111*0000_0010 //进行移位计算 = 0000_1000_0100_0000 + 1111_111_1101_1111_0 = 0000_1000_0100_0000 + 1111_1111_1011_1110 = 1_0000_0111_1111_1110 //因为两个8位数相乘，结果为16位，超出位舍去 所以，最后结果为： 111_1111_1110=2046 

在这里可以首先将乘数0011_1110按照基4展开为 0011_1110——0 相邻三位 首位分组为 10(0)*4^0 + 11(1)*4^1 + 11(1)*4^2 + 00(1)*4^3 相邻3位数，进行公式-2*（第3位）+（第2位）+（第1位）计算 0011_1110 = (-2)*4^0 + (-0)*4^1 + (-0)*4^2 + (1)*4^3 = (-2)*4^0 + (1)*4^3 = (-1)*2^1 + 1*2^6 //= (-2) + 64 = 62  = (-1)*0000_0010 + 0100_0000 0010_0001*0011_1110 = 0010_0001*(0100_0000 - 0000_0010) = 0010_0001*0100_0000 -0010_0001*0000_0010 //进行移位计算,-0010_0001的补码为1101_1111,8*8位宽度为16位，前面符号为补齐 = 00_0010_0001_000000 + 1101_1111*0000_0010 //进行移位计算 = 0000_1000_0100_0000 + 1111_111_1101_1111_0 = 0000_1000_0100_0000 + 1111_1111_1011_1110 = 1_0000_0111_1111_1110 //因为两个8位数相乘，结果为16位，超出位舍去 所以，最后结果为： 111_1111_1110=2046 

Verilog编程之乘法器的实现： https://blog.csdn.net/weixin_/article/details/.

备注：该内容为读书笔记，部分内容与图片收集来源于网络，如有侵权或错误，请联系我整改，谢谢！