algorithm - 修改布斯算法中 LSB 添加的额外 0 有何作用？

Question

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

为什么修改布斯算法中需要在LSB右侧额外加0？

它到底有什么作用以及为什么它需要为 0 而不是 1？

我知道在 Radix-4 Modified Booth 算法(或一般的 iirc)中，您的输入需要偶数位，并且它使用 3 位来决定必须执行什么操作，例如添加 2*被乘数。

但是添加的 0 不能只存在，这样我们就有了一个可以被 3 整除的位长度，对吗？

Answer 1

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

让我们看看更简单的标准展位。
如果重写后 B 的值保持不变，则重写是正确的。
如果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 的负号的特殊情况，其中所有位都被相同地处理独立于我。
事实上，在设计电路时，仅复制一个运算符比根据位位置考虑特定条件要容易得多。因此，最好的解决方案是在 LSB 处添加一个额外的位。

对于 retrofit 展位，情况类似。
我们尝试用数字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 的值无法保持不变。这对于确保乘法算法的正确性至关重要。