Почему «Серийный бит добавляет необходимость в переносе цепи»?
Умножение выполняется с помощью набора сложений и операций сдвига.
Каждый результат сложения используется в качестве входа для следующего сложения (которое называется накоплением), а другой вход - это множитель, сдвинутый на один бит.
Стандартное двоичное умножение 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) заменяется на сдвиг вправо результата, как показано на рисунке. Таким образом, ни перенос, ни А не требуют сдвига. </p>
Следовательно, для умножения потребуется n шагов (по одному на бит в умножении B), но каждый шаг может быть быстрым, так как для него требуется только обход одного сумматора.
Чтобы быть точным, окончательный результат должен быть полностью добавлен к переносам. Это можно сделать с помощью стандартного сумматора с цепочкой переноса или с помощью N дополнительных последовательных битов сложения с множителем, установленным на ноль.
Я не понимаю, почему блок дополнения первого последовательного бита 2 помещается перед последующими битовыми последовательными сумматорами?
Я думаю, что цифра как-то неверна. Эта схема соответствует беззнаковому умножению. Умножение со знаком требует либо разных шагов, либо перекодировки данных (например, перекодирование Бута). Такое перекодирование объясняется в конце страницы, указанной в вашей ссылке, и на каждом шаге потребуется либо добавление, либо вычитание, но на рисунке используется обычное двоичное кодирование, а не дополнение 2.