老铁们，大家好，相信还有很多朋友对于booth算法和booth算法的证明的相关问题不太懂，没关系，今天就由我来为大家分享分享booth算法以及booth算法的证明的问题，文章篇幅可能偏长，希望可以帮助到大家，下面一起来看看吧！
画出实现Booth算法的运算器框图,
http://wenku.baidu.com/link?url=TuFWEqHNPdbiVZfilSAKmm2FkqJwmKv3R28IpXIqKQpcZGkCPjoGQPQXkvz81e7UOMjFbABbaS5FsceFntPxfLSRPk47KEMkfhwKuI7eE-G###
第25页自己看吧
用加减交替法计算x/y
不恢复余数法，又称加减交替法。
其特点是运算过程中如出现不够减，则不必恢复余数，根据余数符号，可以继续往下运算，
因此步数固定，控制简单。
原码加减交替法的规则是：
当余数为正时，商“1”，余数左移一位减除数；
当余数为负时，商“0”，余数左移一位，加除数。
[x]原
=
[x]补
=
0.1001，[y]原
=
[y]补
=
0.1011，[-
y]补
=
1.0101
被除数x/余数r
商数q
说明
0
0.1
0
0
1
+[-y]补
1
1.0
1
0
1
x减y
----------------------------------------------------------------
1
1.1
1
1
0
余数r0＜0，商0
←
1
1.1
1
0
0
0
商0，r和q左移一位
+[y]补
0
0.1
0
1
1
加y
----------------------------------------------------------------
0
0.0
1
1
1
余数r1＞0，商1
←
0
0.1
1
1
0
0.1
商1，r和q左移一位
+[-y]补
1
1.0
1
0
1
减y
----------------------------------------------------------------
0
0.0
0
1
1
余数r2＞0，商1
←
0
0.0
1
1
0
0.1
1
商1，r和q左移一位
+[-y]补
1
1.0
1
0
1
减y
----------------------------------------------------------------
1
1.1
0
1
1
余数r3＜0，商0
←
1
1.0
1
1
0
0.1
1
0
商0，r和q左移一位
+[y]补
0
0.1
0
1
1
加y
----------------------------------------------------------------
0
0.0
0
0
1
余数r4＞0，商1
1
1
0
1
商1，仅q左移一位
所以
x
/
y
的商
[q]原
=
0.1101，余数[r]原
=
0.00000001
这就是加减交替法的基本步骤，希望对你有帮助。
booth算法的证明
比较好的带符号数乘法的方法是布斯(Booth)算法。它采用相加和相减的操作计算补码数据的乘积。Booth算法对乘数从低位开始判断，根据两个数据位的情况决定进行加法、减法还是仅仅移位操作。判断的两个数据位为当前位及其右边的位(初始时需要增加一个辅助位0)，移位操作是向右移动。在上例中，第一次判断被乘数0110中的最低位0以及右边的位(辅助位0)，得00；所以只进行移位操作；第二次判断0110中的低两位，得10，所以作减法操作并移位，这个减法操作相当于减去2a的值；第三次判断被乘数的中间两位，得11，于是只作移位操作；第四次判断0110中的最高两位，得01，于是作加法操作和移位，这个加法相当于加上8a的值，因为a的值已经左移了三次。
一般而言，设y=y0,yly2…yn为被乘数，x为乘数，yi是a中的第i位(当前位)。根据yj与yi+1的值，Booth算法表示如下表所示，其操作流程如下图所示。在Booth算法中，操作的方式取决于表达式(yi+1-yi)的值，这个表达式的值所代表的操作为：
0无操作
+1加x
-1减x
Booth算法操作表示
yiyi+1操作说明
00无处于0串中，不需要操作
01加x1串的结尾
10减x1串的开始
11无处于1串中，不需要操作
乘法过程中，被乘数相对于乘积的左移操作可表示为乘以2，每次循环中的运算可表示为对于x(yi+1-yi)2^31-i项的加法运算(i=3l，30，…，1，0)。这样，Booth算法所计算的结果可表示为：
x×(0-y31)×2^0
+x×(y31-y30)×2^1
+x×(y30-y29)×2^2
…
[1]+x×(y1-y0)×2^31
=x×(-y0×231+y1×2^30+y2×2^29+y31×2^0)
=x×y
例：用Booth算法计算2×(-3)。
解：[2]补=0010，[-3]补=1101，在乘法开始之前，R0和R1中的初始值为0000和1101，R2中的值为0010。
在乘法的第一个循环中，判断R1的最低位和辅助位为10，所以进入步骤1c，将R0的值减去R2的值，结果1110送人R0，然后进入第二步，将R0和Rl右移一位，R0和R1的结果为11110110，辅助位为l。
在第二个循环中，首先判断Rl的最低位和辅助位为0l，所以进入步骤1b，作加法，R0+R2=1111+0010，结果0001送入R0，这时R0R1的内容为00010110，在第二步右移后变为00001011，辅助位为0。
在第三次循环中，判断位为10，进入步骤lc，R0减去R2，结果1110送入R0，R1不变；步骤2移位后R0和R1的内容为111101011，辅助位为1。
第四次循环时，因两个判断位为11，所以不作加减运算，向右移位后的结果为11111010，这就是运算结果(—6)。
这个乘法的过程描述如下表所示，表中乘积一栏表示的是R0、R1的内容以及一个辅助位P，黑体字表示对两个判断位的判断。
用Booth补码一位乘法计算2×(-3)的过程
循环
步骤
乘积（R0,R1,P）
0
初始值
000011010
第一次循环
1c：减0010
111011010
2：右移1位
111101101
第二次循环
1b：加0010
000101101
2：右移1位
000010110
第三次循环
1c：减0010
111010110
2：右移1位
111101011
第四次循环
1a：无操作
111101011
2：右移1位
111110101
4．补码两位乘
补码两位乘运算规则是根据补码一位乘的规则，把比较yiyi+1的状态应执行的操作和比较yi-1yi的状态应执行的操作合并成一步，便可得出补码两位乘的运算方法。
补码两位乘法运算规则如下
判断位yi-1yiyi+1
操作内容
000
[zi+1]补=2-2[zi]补
001
[zi+1]补=2-2{[zi]补+[x]补}
010
[zi+1]补=2-2{[zi]补+[x]补}
011
[zi+1]补=2-2{[zi]补+2[x]补}
100
[zi+1]补=2-2{[zi]补+2[-x]补}
101
[zi+1]补=2-2{[zi]补+[-x]补}
110
[zi+1]补=2-2{[zi]补+-x}补}
111
[zi+1]补=2-2[zi]补
由上表可见，操作中出现加2[x]补和加2[-x]补，故除右移两位的操作外，还有被乘数左移一位的操作；而加2[x]补和加2[-x]补，都可能因溢出而侵占双符号位，故部分积和被乘数采用三位符号位。
例：[x]补=0.0101，[y]补=1.0101求：[x�6�1y]补。
解：求解过程如下表所示。其中乘数取两位符号位即11.0101,[-x]补=1.1011取三符号位为111.1011。
部分积
乘数
说明
000.0000
+000.0101
1101010
判断位为010，加[x]补
000.0101
000.0001
+000.0101
0111010
→2位
判断位为010，加[x]补
000.0110
000.0001
+111.1011
01
1001110
→2位
判断位为110，加[-x]补
111.1100
1001
最后一步不移位，得[x�6�1y]补
故[x�6�1y]补=1.11001001
可见，与补码一位乘相比，补码两位乘的部分积多取一位符号位（共3位），乘数也多取一位符号位（共2位），这是由于乘数每次右移2位，且用3位判断，故采用双符号位更便于硬件实现。可见，当乘数数值位为偶数时，乘数取2位符号位，共需作n/2次移位，最多作n/2+1次加法，最后一步不移位；当n为奇数时，可补0变为偶数位，以简化逻辑操作。也可对乘数取1位符号位，此时共作n/2+1次加法和n/2+1次移位（最后一步移一位）。
对于整数补码乘法，其过程与小数乘法完全相同。为了区别于小数乘法，在书写上可将符号位和数值位中间的“.”改为“，”即可。
再补充一道例子，增加一下理解。呵呵
例1.37设被乘数M=0111（7），乘数Q=0011（3），相乘过程如下：(其中的①②……是我自己加上去的)
AQQ-1
①００００００１１０初始值
②１００１００１１０A=A-M
③１１００１００１１右移（第1次循环）
④１１１００１００１右移（第2次循环）
⑤０１０１０１００１A=A+M
⑥００１０１０１００右移（第3次循环）
⑦０００１０１０１０右移（第4次循环）
乘法运算结束后，所得结果共8位，A寄存器中是乘积的高位部分，Q寄存器中是乘积的低位部分，即乘积=0010101=(21)(十进制）
例１.38设被乘数M=0111(7),乘数Q＝１１０１（－３），相乘过程如下：
AＱＱ－１
００００１１０１０初始值
１００１１１０１０Ａ＝Ａ－Ｍ
１１００１１１０１右移（第１次循环）
００１１１１１０１Ａ＝Ａ＋Ｍ
０００１１１１１０右移（第２次循环）
１０１０１１１１０Ａ＝Ａ－Ｍ
１１０１０１１１１右移（第３次循环）
１１１０１０１１１右移（第４次循环）
乘积=11101011=(-21)(十进制)
OK，关于booth算法和booth算法的证明的内容到此结束了，希望对大家有所帮助。
