Модифицированный алгоритм Бута (умножение на 3 разряда)

  • Автор темы McLarenfan
  • Дата начала
M

McLarenfan

Гость
#1
Всем привет!
У меня есть вопрос не по программированию как таковому, а по алгоритмам, может кто поможет...

Я пишу на языке Verilog кусок АЛУ, который в частности должен умножать целые знаковые\беззнаковые 32-разрядные числа.
Для ускорения выполнения операции знакового\беззнакового умножения использую модифицированный алгоритм Бута с анализом за цикл 3 бит множителя, вроде бы разобрался с ним, а стал рассматривать на примере и получаемый результат не совпадает с теоретическим...

Взял 2 числа:
101 - 01100101
78 - 01001110

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

анализирую множитель...расширяю его: 0010011100
получаю 3 группы:
1100 - соответствует множимому, умноженному на -2
0011 - соответствует множимому, умноженному на 2
0010 - соответствует множимому

получается 3 частичных произведения, смещенных относительно друг друга на разряда влево соответственно:

11111100110110
00011001010
01100101
_______________
01111011000110 - что соответствует нужному результату в 7878 (пары операндов выбрал случайным образом)

А вот для остальных комбинаций знаков почему то не сходится, хотя делаю всё также...

-101 - 10011011
-78 - 10110010

анализирую множитель...расширяю его: 0101100100
получаю 3 группы:
0100 - соответствует множимому, умноженному на 2
1100 - соответствует множимому, умноженному на -2
0101 - соответствует множимому, умноженному на 3

получается 3 частичных произведения, смещенных относительно друг друга на разряда влево соответственно:

11111100110110
00011001010
11010001
_______________
11010111000110 - неверный результат

-101 - 10011011
78 - 01001110

анализирую множитель...расширяю его: 0010011100
получаю 3 группы:
1100 - соответствует множимому, умноженному на -2
0011 - соответствует множимому, умноженному на 2
0010 - соответствует множимому

00000011001010
11100110110
10011011
_______________
10000000111010 - неверный результат

101 - 01100101
-78 - 10110010

анализирую множитель...расширяю его: 0101100100
получаю 3 группы:
0100 - соответствует множимому, умноженному на 2
1100 - соответствует множимому, умноженному на -2
0101 - соответствует множимому, умноженному на 3

000000011001010
111100110110
100101111
________________
100010100111010 - неверный результат

Просьба объяснить в чем я ошибаюсь, на каком этапе...а то уже отчаялся...

Всем заранее спасибо и удачи! ;)