routing - 串行通过并行展位乘法器

Question

我不明白为什么第一位串行 2 的补码块放在后续位串行加法器之前？

串行通过并行展位乘法器

score 1 · Accepted Answer

为什么“比特串行增加了无需进位链”？

乘法是通过一组加法和移位操作完成的。加法的每个结果都用作下一次加法的输入（称为累加），另一个输入是移位一位的乘数。

标准二进制乘法 A*B，其中 B=2^n-1*b_n-i + ... + 2^1*b_1+2^0*b_0 通过以下算法完成

Res<=0
for i in 0 .. n-1 do
   Res <= Res + A * b_i
   A <= A * 2
done

通常，加法需要将进位从 LSB 传播到 MSB（进位链）。但是对于累加，可以使用“进位保存加法”，这是执行乘法的标准平均值。在这种情况下，不是将输出进位馈送到下一个加法器（进位链）的输入进位，而是保存并在下一次加法中移位使用。

这样，一个加法步骤只需要经过一层加法器，而不是在涉及进位链时需要经过 n 层。请注意，进位保存允许加快内部累加步骤，但加法器的总和输出将保持不完整，直到进位被有效传播。

这就是图中所表示的。输出进位（右下角）被记忆（在蓝色寄存器中）并用作该加法器下一次加法的输入。加法器和输出（在每个加法器的右上角）被存储并移位发送到下一个加法器的一个输入，而将不再修改的 LSB 被移出。

请注意，乘法算法中的左移（A<=A*2）被替换为结果的右移，如图所示。这种方式既不需要进位，也不需要任何移位。

因此，乘法将需要 n 个步骤（被乘数 B 中的每一位一个），但每个步骤都可以很快，因为它只需要遍历单个加法器。

正确地说，最终结果需要完全添加到进位中。这可以通过带有进位链的标准加法器来完成，或者通过 N 个额外的位串行加法步骤将乘数设置为零。

我不明白为什么第一位串行 2 的补码块放在后续位串行加法器之前？

我认为这个数字在某种程度上是不正确的。该示意图对应于无符号乘法。有符号乘法需要不同的步骤或数据重新编码（例如布斯重新编码）。这种重新编码在链接中给出的页面末尾进行了说明，并且在每一步都需要加法或减法，但该图使用常规二进制编码而不是 2 的补码。

1 回答 1