Что делает дополнительный 0, добавленный к LSB в Модифицированном Алгоритме Кабины?

Question

Я пытался найти ответ на этот вопрос, но единственная другая ветка об этом не дала столько подробностей, сколько я хотел.

Может кто-нибудь сказать мне, почему дополнительный 0 справа от LSB необходим в Модифицированном Алгоритме Кабины?

Что именно он делает и почему он должен быть 0, а не 1?

Я знаю, что вам нужно четное количество бит для ввода в Radix-4 Modified Booth Algorithm (или вообще iirc) и что он использует 3 бита, чтобы решить, какую операцию необходимо выполнить, например, добавив 2 * multiplicand.

Но добавленный 0 не может быть только там, так что у нас есть длина в битах, которая может быть разделена на 3, верно?

Любая помощь, объясняющая, почему нам нужны дополнительные 0 и почемуэто должно быть 0 будет принята с благодарностью.

Answer 1

Предположим, мы должны умножить A & times; B , где B = (b _n-1 ... b ₁ b ₀ )
Бут в своей стандартной или модифицированной версии работает, переписывая термины b _i .

Давайте посмотрим на стандартный стенд, который проще.
Перезапись правильна, если оставить значение из B без изменений.
Если B кодируется в виде дополнения до двух, его значение равно
B = & минус; б _п-1 & времена; 2 ^{N-1 * тысяча тридцать один * + & сумма; _{= 0 * тысяча тридцать-три ** +1034 * п-1 * 1 035 * б * 1 036 * г} & времена; 2 * 1 038 * г} * * 1 041 Обратите внимание на минус при весе n-1 из-за кодировки дополнения до двух.

Теперь перезапись состоит в том, чтобы изменять каждый b _i на b ' _i = b _i & минус; b _я-1
Если мы теперь скажем, что
B = & сумма; * 1 061 * = 0 * 1 062 * ^п-1 б ' _{я * +1066 * & времена; 2 ^{я * ** 1069 тысяча шестьдесят-восемь *
это легко увидеть, заменив b ' i на b i & минус b i-1 in Это выражение означает, что значение B не изменяется, при условии, что для i = 0 мы добавляем дополнительный бит b i-1 = 0}}

Конечно, мы могли бы добавить специальное правило для i = 0 :
если i & ne; 0 , b ' _i = b _i & min; b _i-1
в противном случае b ' _i = b _i
Но основная начальная мотивация для алгоритма Бута состояла в том, чтобы заменить частный случай минуса при весе n-1 в дополнении до двух регулярным выражением, где все биты обрабатываются одинаково независимо от я .
Действительно, при проектировании схемы гораздо проще просто дублировать оператор, чем учитывать конкретные условия в зависимости от положения бита. По этой причине наилучшим решением является добавление дополнительного бита в LSB.

Для модифицированного Бута ситуация аналогична.
Мы пытаемся переписать b цифрами b '' _2i таким образом, чтобы
B = & sum; _{i = 0} ^{n / 2-1} b '' _2i & times; 2 ²ⁱ
Перезапись выполняется на основе 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

Можно доказать, что таким образом числовое значение B не изменяется, при условии мы добавляем бит в 0 при весе -1 b _{- 1} = 0 . На самом деле, b '' _2i = & plusmn; 2 & times; b _{2i + 1} + b _2i + b _2i-1 и можно заменить, если выражение B = & sum; _{i = 0} ^{n / 2-1} b '' _2i & times; 2 ²ⁱ , чтобы найти значение B в дополнении до двух.
Опять же, мы могли бы по-другому рассмотреть ситуацию, когда i = 0 и сказать, что b '' ₀ = & minus; 2 & times; b ₁ + b ₀ , но это добавит дополнительную сложность.

Итак, чтобы ответить на ваши вопросы:

Может кто-нибудь сказать мне, почему дополнительные 0 справа от LSB необходимы в Модифицированном Алгоритме Кабины?

Этот дополнительный бит упрощает алгоритм перезаписи и позволяет избежать особого случая, когда i = 0

Что именно он делает и почему он должен быть 0, а не 1?

Если этот бит был равен единице, мы не могли бы иметь значение B без изменений после перезаписи. Это важно для обеспечения правильности алгоритма умножения.