1、booth算法定义
将乘数看作从最低位开始的一串二进制数字。Booth算法的基本思路是：对于具有连续0和1的组，需要产生的部分积较少。对于乘数中每个0，仅需要将前面的累加的部分积向右移动一位。
布斯编码采用相加和相减的操作计算补码数据的乘积，可以减少部分积的数目，用来计算有符号乘法，提高乘法运算的速度。
2、二进制乘法过程
二进制乘法过程可仿照十进制数乘法进行。由低位到高位，用乘数的每一位去乘被乘数，若乘数的某一位为1，则该次部分积为被乘数；若乘数的某一位为0，则该次部分积为0。某次部分积的最低位必须和本位乘数对齐，所有部分积相加的结果则为相乘得到的乘积。
上诉例子我们知道乘数和被乘数的位数都是4，那么如果计算结果超过2n(n)为二进制表示位数，那么我们将2n高位的其他位省略。
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
数的表示方法：
N比特数B，将其展开，在N比特数B的最后一位B0后添加一个辅助位B(-1)，且B(-1)=0：
从上式中得出，其基系数为：
将A与B相乘，则：
对于B的第n位和第n-1位，从上式可以发现，B可以通过相邻比特位的减法和2的n次方相乘而得。如果AB两数相乘，从B的-1和0位逐次向高位检查，累积A*B的结果。
根据 基2 Booth乘法器的基系数 表达式，得出以下Booth4编码：
相邻两个数据位，进行公式（第0位）-（第1位）计算，得到两位的编码（相邻居两位，从后面像前面减）
00 0-0= 0 转化成二进制编码 0
01 1-0= 1 转化成二进制编码 1
10 0-1=-1 转化成二进制编码-1
11 1-1= 0 转化成二进制编码 0
根据两个数据位的编码决定进行加法、减法还是仅仅移位操作。
以下是基2 Booth编码表，根据两个数据位的编码决定进行加法、减法还是仅仅移位操作。
5、Radix-4 Booth乘法器
Radix-4 Booth乘法器，即是基4 Booth乘法器。基为2的二次方。
4 = 2^2
数的表示方法：
从上式中得出，基4 Booth乘法器的基系数为：
将A与B相乘，则：
根据 基4 Booth乘法器的基系数 表达式，得出以下Booth4编码：
相邻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
以下是基4 Booth编码表，其中A为被乘数，B为乘数。
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)=~(100111)+1=111000+1=111001
所以将结果11_1001在基2中表示结果向左移1位，得到111_0010，乘积的位数为2*6位，前面符号位补齐
此处引用 https://zhuanlan.zhihu.com/p/143802580.
例如第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实现
booth4与csa4:2等见： https://zhuanlan.zhihu.com/p/127164011.
Verilog编程之乘法器的实现： https://blog.csdn.net/weixin_43074474/article/details/90473709.
备注：该内容为读书笔记，部分内容与图片收集来源于网络，如有侵权或错误，请联系我整改，谢谢！