我试图找到这个问题的答案，但是关于它的唯一其他线程并没有提供我希望的那么多细节。
LSB为什么在 Modified Booth Algorithm中需要的右侧多余的 0 ？
它到底做了什么，为什么它需要为 0 而不是 1？
我知道您在 Radix-4 Modified Booth Algorithm（或一般的 iirc）中的输入需要偶数位，并且它使用 3 位来决定必须完成的操作，例如添加 2*multiplicand。
但是添加的 0 不能只在那里，所以我们有一个可以除以 3 的位长，对吧？
问问题
174 次
1 回答
3
假设我们必须乘以A×B，其中B=(b n-1 ... b 1 b 0 )
Booth 在其标准或修改版本中通过重写术语b i来工作。
让我们看看更简单的标准展位。如果B的值保持不变
，则重写是正确的。
如果B以二进制补码编码，则其值为B=-b n-1 ×2 n-1 +∑ i=0 n-1 b i ×2 i注意由于二进制补码编码，权重n-1
处的减号。
现在重写包括将每个b i更改为b' i = bi -b i-1
如果我们现在说
B=∑ i=0 n-1 b' i ×2 i
很容易通过替换b' i由b i -b i-1在这个表达式中B的值不变，前提是对于i=0，我们添加一个额外的位 b i-1 =0
当然，我们可以为i=0添加一个特殊规则：
如果i≠0，则b' i = bi -b i-1
否则b' i =b i
但布斯算法的主要初始动机是替换特定的通过正则表达式在二进制补码中权重n-1处的减号的情况，其中所有位都以独立于i的方式进行相同处理。
实际上，在设计电路时，仅仅复制一个运算符要比必须根据位位置考虑特定条件要容易得多。出于这个原因，最好的解决方案是在 LSB 处添加一个额外的位。
对于修改后的 Booth，情况类似。
我们尝试用数字b'' 2i重写b使得B=∑ i=0 n/2-1 b'' 2i ×2 2i
重写以 4 为基数，表达式更复杂，并且生成一个数字b''我们需要考虑位 b 2i+1、 b 2i和 b 2i-1。
这是对应的真值表。
b_2i+1 b_2i b_2i-1 | b''_2i
-----------------------------------
0 0 0 | 0
0 0 1 | 1
0 1 0 | 1
0 1 1 | 2
1 0 0 | -2
1 0 1 | -1
1 1 0 | -1
1 1 1 | 0
可以证明，如果我们在权重 -1 b -1 =0时在 0 处加一点，那么B的数值是不变的。实际上，b'' 2i =−2×b 2i+1 +b 2i +b 2i-1并且如果表达式B=∑ i=0 n/2-1 b'' 2i ×2 2i可以替换以求值二进制补码中的B。同样，我们可以不同地考虑i=0
的情况，并说b'' 0 =−2×b 1 +b 0
，但这会增加额外的复杂性。
所以回答你的问题：
谁能告诉我为什么在修改布斯算法中需要 LSB 右侧的额外 0？
这个额外的位简化了重写算法，避免了当i=0时有特殊情况需要处理
它到底做了什么，为什么它需要为 0 而不是 1？
如果该位为 1，则我们无法在重写后保持B的值不变。这对于确保乘法算法的正确性至关重要。
于 2019-06-30T20:59:56.010 回答