Понимание модифицированного алгоритма умножения Боугли

Question

Для модифицированного алгоритма умножения Боу-Вули, почему это! (A0 * B5) вместо просто (A0 * B5)?

Те же вопросы для! (A1 * B5),! (A2 * B5),! (A3 * B5),! (A4 * B5),! (A5 * B4),! (A5 * 3),! (A5 * B2),! (A5 * B1) и! (A5 * B0)

Кроме того, почему есть два дополнительных «1»?

Answer 1

В знаковых 6-битных двоичных двоичных символах дополнения значения битов:

-32  16   8   4   2   1

Обратите внимание, что старший бит имеет отрицательное значение.Однако, когда сложение, вычитание и умножение выполняются в моде 64, этот знак минус абсолютно не влияет на то, как работают эти операции, потому что 32 = -32 мод 64.

Ваше умножение не выполняется мод 64, однако, так что знак должен быть принят во внимание.

Один способ думать о вашем умножении состоит в том, что 6-битные числа расширяются до 12 битов, и затем умножение выполняется мод 4096.При расширении числа со знаком верхний бит копируется, поэтому -32 становится -2048 + 1024 + 512 ... +32, что в совокупности имеет одинаковое значение -32.Так что расширьте числа со знаком и умножьте.Я сделаю это с 3 битами, умножая мод 64:

Given:         Sign-extended:
A2 A1 A0       A2 A2 A2 A2 A1 A0
B2 B1 B0       B2 B2 B2 B2 B1 B0

Multiply:
A0B2    A0B2    A0B2    A0B2    A0B1   A0B0
A1B2    A1B2    A1B2    A1B1    A1B0        
A2B2    A2B2    A2B1    A2B0
A2B2    A2B1    A2B0
A2B1    A2B0
A2B0

Поскольку мы реплицировали одни и те же биты в нескольких позициях, вы увидите одинаковые битовые продукты в нескольких позициях.

A0B2 появляется 4 раза с общим значением места 60 или 15 << 2 и т. Д.Давайте запишем множители в: </p>

                        A0B2*15 A0B1   A0B0
                A1B2*7  A1B1    A1B0        
        A2B2*5  A2B1*7  A2B0*15

Опять же, из-за модульной арифметики, * 15s и * 7s совпадают с * -1, а * 5 совпадает с * 1:

                       -A0B2    A0B1   A0B0
               -A1B2    A1B1    A1B0        
        A2B2   -A2B1   -A2B0

Эта модель начинает казаться знакомой.Теперь, конечно, -1 не является битовым значением, но ~ A0B2 = 1-A0B2, поэтому мы можем перевести -A0B2 в ~ A0B2 и затем вычесть дополнительный 1, который мы добавили.Если мы сделаем это для всех вычитаемых продуктов:

                       ~A0B2    A0B1   A0B0
               ~A1B2    A1B1    A1B0        
        A2B2   ~A2B1   ~A2B0
                 -2       -2

Если мы сложим значения мест этих -2 и расширим их в эквивалентные биты, мы обнаружим источник дополнительных 1 на вашей диаграмме:

                       ~A0B2    A0B1   A0B0
               ~A1B2    A1B1    A1B0        
        A2B2   ~A2B1   ~A2B0
   1              1

Answer 2

почему два лишних «1»?

См. Некоторые предыдущие объяснения в ответе Мэтта Тиммерманса

Примечание: «-2» в двух дополнениях равно 110, и это способствует переносам, таким образом, два дополнительных «1»

зачем менять значения некоторых битов частичного произведения.

Это связано со знаковым битом в MSB (A5 и B5).

Кроме того, см. Ниже контрмеры для модифицированного алгоритма Боу-Вули в случае A_WIDTH! =B_WIDTH с помощью других .

Я написал аппаратный код verilog для этого алгоритмаНадеюсь, этот пост поможет некоторым читателям.

Answer 3

Короткий ответ заключается в том, как работает представление 2-дополнение : старший бит фактически является знаковым битом, поэтому 1 там означает -.Другими словами, вы должны вычесть

A5*(B4 B3 B2 B1 B0) << 5

и

B5*(A4 A3 A2 A1 A0) << 5

из суммы (обратите внимание, что A5*B5 добавляется снова, поскольку оба имеют один и тот же знак -).И эти два 1 являются результатом замены этих двух вычитаний с добавлением -X.

Если вам нужно больше подробностей, то вам, вероятно, нужно просто перечитать, как работают 2-х дополнения, а затем всю математику, лежащую в основе алгоритма умножения Боуг-Вули.Это не так сложно.