algorithm - Modified Booth Algorithm 的 LSB 中额外添加的 0 有什么作用？

Question

我试图找到这个问题的答案，但关于它的唯一其他线程没有提供我希望的那么多细节。

为什么 Modified Booth Algorithm 需要 LSB 右边额外的 0？

它到底做了什么，为什么它需要是 0 而不是 1？

我知道您在 Radix-4 Modified Booth Algorithm(或一般的 iirc)中需要偶数位用于输入，并且它使用 3 位来决定必须完成什么操作，例如添加 2*multiplicand .

但是添加的 0 不能只在那里，所以我们有一个可以被 3 整除的 Bit-length，对吧？

Answer 1

假设我们必须乘以 A×B，其中 B=(b_n-1 ... b₁ b ₀)
Booth 的标准版或修改版通过重写术语 b_i 来工作。

让我们看看更简单的标准Booth。
如果保持 B 的 value 不变，则重写是正确的。
如果B用二进制补码编码，则其值为
B=−b_n-1×2^n-1+∑_i=0^n-1b_i×2ⁱ
由于二进制补码编码，请注意权重 n-1 处的负号。

现在重写包括将每个 b_i 更改为 b'_i=b_i- b_i-1
如果我们现在这么说
B=∑_i=0^n-1b'_i×2ⁱ
将 b'_i 替换为 b_i−b_i-1 在这个表达式中 B 的值不变，前提是对于 i=0，我们添加一个额外的位 b_i-1 =0

当然，我们可以为 i=0 添加一个特殊规则:
如果i≠0，b'_i=b_i−b_i-1
否则 b'_i=b_i
但是 Booth 算法的主要初始动机是用一个正则表达式替换二进制补码中权重 n-1 的负号的特殊情况，其中所有位都被相同地处理独立于i。
事实上，在设计电路时，复制一个运算符比必须根据位位置考虑特定条件要容易得多。因此，最好的解决方案是在 LSB 处添加一个额外的位。

对于修改后的展位，情况类似。
我们尝试用数字 b''_2i 重写 b
B=∑_i=0^n/2-1b''_2i×2 ²ⁱ重写以 4 为基，表达式更复杂，要生成数字 b''，我们需要考虑位 b_2i+1，b< sub>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

可以这样证明，B的数值是不变的，假设我们在权重-1处在0处加了一位b_-1=0。实际上，b''_2i=−2×b_2i+1+b_2i+b_2i-1 和一个可以替换 if 表达式 B=∑_i=0^n/2-1b''_2i×2 ²ⁱ 以二进制补码求 B 的值。
同样，我们可以不同地考虑 i=0 的情况，并说 b''₀=−2×b₁+ b₀，但这会增加额外的复杂性。

所以回答你的问题:

Could anyone tell me why the extra 0 to the right of the LSB is needed in Modified Booth Algorithm?

这个额外的位简化了重写算法并避免了在i=0时需要处理的特殊情况

What exactly does it do and why does it need to be 0 and not 1?

如果该位为 1，则重写后我们不能让 B 的值不变。这对于确保乘法算法的正确性至关重要。