y 7 y 6 y 5 y 4 y 3 y 2 y 1 y 0 y -1
booth编码
Y8
Y8 Y8 y 7 y 6 y 5 y 4 y 3 y 2 y 1 y 0 y -1 booth2编码
2016-11-27
Fudan University, Jinmei Lai
乘法实现
归纳为： 1. 部分积产生？ 2. 部分积压缩？ 3. 将Sum和Carry相加产生最终结果
CMOS Subsystem Design（2）
来金梅
2016-11-27
jmlai
Booth 乘法器

Why booth Multiplier ？ 编码方法 拓扑结构
2016-11-27
Fudan University, Jinmei Lai
Basic Mathematics
2016-11-27
Fudan University, Jinmei Lai
提高运算速度
为了进一步提高运算速度，通常采用: 根据0/1结构的特征，对于成串的1，利用 减少部分积的数目。


变长位数移位方式： 充分考虑了乘数中不同长度的“1”串 算法的速度强烈依赖于0/1的结构 难以进行统一时序控制和阵列化设计 固定位数移位方式：booth算法
1.反码运算时，其符号位与数值一起参加运算。 2.反码的符号位相加后，如果有进位出现，则要把它送回到最低 位去相加（循环进位）。 3.用反码运算，其运算结果亦为反码。
2016-11-27
Fudan University, Jinmei Lai
补码
补码可表示为(X为符号数) ：
1.补码运算时，其符号位与数值部分一起参加运算。 2.补码的符号位相加后，如果有进位出现，要把这个进位舍去 （自然丢失）。 3.用补码运算，其运算结果亦为补码。
n1
i0even n2
i i y 2 y 2 i i y1 i1odd n3
n2
n3
i0even
y 2 y 2
i i i1odd i i0even i y 2 i i n2 n2
i1
2 yi 2 y1
i1 i1odd n4
n3
2 y(n2)1 2n2
i2even
i i y 2 2 y 2 i1 y1 i1 i0even
i0even
(y
n2
i1
yi 2yi1) 2
2016-11-27
i取偶数 Fudan University, Jinmei Lai
2016-11-27
Fudan University, Jinmei Lai
Booth乘法实现步骤
第一步：根据输入的被乘数与乘数，产生部分积 Booth编码：部分积无减少，但解决了符号位问题 Booth2编码：部分积减少一半，同时解决了符号位问题 Booth4，Booth8，Booth32，Booth64。。。：通过增 加预计算和Booth编码器的复杂度，部分积更少（自学） 第二步：将生成的部分积压缩得到和(Sum)和进位(Carry) 多个部分积进行压缩，需选择合理的并行方案，即选择 合理拓扑结构。 第三步：将Sum和Carry相加产生最终结果
2016-11-27
Fudan University, Jinmei Lai
经典booth算法
X被乘数,Y乘数 PPi= (-Yi+1+ Yi)X
yi+1 yi 0 1 0 1 PPi +0 +X -X +0
y7 y6 y5 y4 y3 y2 y1 y0 y-1
0 0 1 1
Booth算法取数操作
2016-11-27
Fudan University, Jinmei Lai
编码中的符号位处理


第一步正数乘法器情况：假定乘数和被乘数的 符号位是0（正数） 首先讨论：部分积全部为负 其次讨论：部分积可正可负 第二步推广到有符号乘法器：乘数和被乘数的 符号位或是0或是1的情况 部分积可正、可负
Fudan University, Jinmei Lai
2016-11-27
有符号数乘法 又如何呢？
2016-11-27
Fudan University, Jinmei Lai
符号位的处理
机器数

符号数：在数的绝对值前加上正负号，就成了符号 数，例:+1101，-1101 机器数:正号用0表示、负号用1表示，称为机器数。 如“01101”“11101”。 机器数分为:
i
i
i取偶数
部分积的个数为 [(n+1)/2]
Fudan University, Jinmei Lai
PP i (yi1 yi 2yi1)X
Booth2算法



每次交叠检验三位,每个部分积 对应2比特数, 使部分积减少一 半，从而提高了运算速度并降 低了硬件复杂度 2X:左移X一位 -X：取反加 1 -2X：左移X一位，再取反加 1 电路实现时，先对补码形式的n 位乘数Y = yn-1 yn-2 ··· y1 y0扩 充附加位y-1=0 若n是奇数，还需扩充一位附加 符号位yn = yn-1 继续扩充有必要么？ Fudan University, Jinmei Lai 2016-11-27
2016-11-27
Fudan University, Jinmei Lai
反码和补码

为了减少设备，解决机器内负数的符号位参加 运算的问题，将减法运算变成加法运算，就引 进了反码和补码这两种机器数。
2016-11-27
Fudan University, Jinmei Lai
反码
反码可表示为(X为符号数) ：
Fudan University, Jinmei Lai
Booth 算法:免去特殊操作(减)
X被乘数,Y乘数
XY (Yi Y(i1) )2 X PP i2
i i0 i0
N 1Βιβλιοθήκη N 1i(3-5)
部分积
PP i (Y i Y (i1) ) X
式(3-5)、式(3-12)表达形式是相同的， 无符号数与符号数的乘法就统一起来了 Fudan University, Jinmei Lai 2016-11-27
2016-11-27
Fudan University, Jinmei Lai
Booth 乘法器

Why booth Multiplier ？ 编码方法 拓扑结构
2016-11-27
Fudan University, Jinmei Lai
编码方法：如何有效地获得部分积呢？

采用booth编码方法:
2016-11-27
Fudan University, Jinmei Lai
A为符号数
若
A 补 A N 1 2 N 1 A 0 2 0
A （符号数）可表示为：
2016-11-27
Fudan University, Jinmei Lai
Booth 算法:免去特殊操作(减)
2016-11-27
经典booth算法

经典的Booth算法（1951，A.D. Booth ）主要是 为了解决有符号运算中复杂的符号修正问题而研 究的 对于补码表示的两数相乘无需进行符号位特殊 操作 经典Booth算法通过每次在乘数中交叠地取两 位(Yi+1, Yi)来产生部分积PPi= (-Yi+1+ Yi)X，X是 被乘数
部分积均为负时成立！
s 1，s ss 011
2016-11-27
Fudan University, Jinmei Lai
编码中的符号位处理


第一步假定：乘数和被乘数的符号位是0（正 数） 首先讨论：部分积为负 其次讨论：部分积可正可负 第二步推广到乘数和被乘数符号位或是0或是1 的情况
G.Bewick，“Fast Multiplication：Algorithms and Implementation”, Ph.D. Dissertation, E.E. Dept. of Stanford Univ., 1994. Fudan University, Jinmei Lai 2016-11-27
表1.1：Booth算法规则
其中：Y-1=0是附加考察位,帮助分析Y0 X是被乘数 Fudan University, Jinmei Lai 2016-11-27
Booth2算法
Y yn1 2 yi 2 y1
n1 i i0 n2
yn1 2n1 yn1 2
2016-11-27
Fudan University, Jinmei Lai
Complete 16 bit Booth 2 multiplication
2016-11-27
Fudan University, Jinmei Lai
编码中的符号位处理


第一步假定：乘数和被乘数的符号位是0（正 数） 首先讨论：部分积为负 其次讨论：部分积可正可负 第二步推广到乘数和被乘数符号位或是0或是1 的情况
2016-11-27
Fudan University, Jinmei Lai
编码中的符号位处理


第一步假定：乘数和被乘数的符号位是0（正 数） 首先讨论：部分积全部为负 其次讨论：部分积可正可负 第二步推广到乘数和被乘数符号位或是0或是1 的情况
2016-11-27
Fudan University, Jinmei Lai
Booth2算法 乘上被乘数得到 X Y