Метод Бута

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

Примечание.

Умножения в дополнительных кодах с применением коррекции.

Правильный результат получается только при положительных операндах.

С = [A_пр.]×[B_пр.]

При А<0, B>0 получаем псевдо-произведение:

С^* = [A_доп.]·[B_пр.] = [2ⁿ - |A|]·[B_пр.] = 2ⁿ ·B_пр. - |A| ·B_пр.

Должно быть: C = 2²ⁿ - |A| · B_пр.

При A>0, B<0: А_пр.· [2ⁿ - |В|] = 2ⁿ · А_пр - А_пр·|В|

Должно быть: C = 2²ⁿ - А_пр·|В|

При A>0, B<0: (2ⁿ - |A|)·(2ⁿ - |В|) = 2²ⁿ - 2ⁿ·|В| - 2ⁿ·|А| + |A| · |В|

Должно быть: C = |A| · |В|

Два вида коррекции

1. Коррекция окончательного результата состоит в вычитании множимого из старших разрядов СЧП, которое может быть заменено на сложение с дополнением множимого. Эта коррекция проводится при отрицательном множителе.

2. При отрицательном множимом коррекция проводится во время умножения и сводится к модифицированному сдвигу СЧП (при сдвиге СЧП вправо в свободный разряд заносится единица).

В случае отрицательного множимого (A<0,B>0) при умножении на младшие нули проводится обычный (не модифицированный) сдвиг – в свободный разряд заносится 0.

Пример. А = 15, В = 13, n = 5.

[A_пр.] = 1.1111 [B_пр.] = 0.1101

[A_доп.] = 1.0001

а) А<0, B>0:

№ шага

Операнды и действия

СЧП (старшие разряды)

СЧП (младшие разряды)

Пояснения

СЧП

Обнуление старших разрядов СЧП.

[A]доп.

Сложение СЧП с множимым.

СЧП

СЧП→

Сдвиг СЧП.

СЧП→

Сдвиг СЧП.

[A]доп.

Сложение СЧП с множимым.

СЧП

СЧП→

Сдвиг СЧП.

[A]доп.

Сложение СЧП с множимым.

СЧП

СЧП→

Сдвиг СЧП.

СЧП

С_доп. = (1.100111101)₂

С_пр. = (1.011000011)₂ = -195

b) А>0, B<0:

[A_пр.] = 0.1111 [B_пр.] = 1.1101

[B_доп.] = 1.0011

№ шага

Операнды и действия

СЧП (старшие разряды)

СЧП (младшие разряды)

Пояснения

СЧП

Обнуление старших разрядов СЧП.

[A]пр.

Сложение СЧП с множимым.

СЧП

СЧП→

Сдвиг СЧП.

[A]пр.

Сложение СЧП с множимым.

СЧП

СЧП→

Сдвиг СЧП.

СЧП→

Сдвиг СЧП.

СЧП→

Сдвиг СЧП.

[A]пр.

Сложение СЧП с множимым.

СЧП

СЧП→

Сдвиг СЧП.

Корр

[-A]доп.

СЧП

С_пр. = (1.011000011)₂ = -195

b) А<0, B<0:

[A_пр.] = 1.1111 [B_пр.] = 1.1101

[B_доп.] = 1.0011

№ шага

Операнды и действия

СЧП (старшие разряды)

СЧП (младшие разряды)

Пояснения

СЧП

Обнуление старших разрядов СЧП.

[A]доп.

Сложение СЧП с множимым.

СЧП

СЧП→

Сдвиг СЧП.

[A]доп.

Сложение СЧП с множимым.

СЧП

СЧП→

Сдвиг СЧП.

СЧП→

Сдвиг СЧП.

СЧП→

Сдвиг СЧП.

[A]доп.

Сложение СЧП с множимым.

СЧП

СЧП→

Сдвиг СЧП.

Корр

[-A]пр.

СЧП

С_пр. = (1.011000011)₂ = -195

Особенности метода.

Сложение или вычитание множимого на каждом шаге зависит от того, как после сдвига вправо меняется младший разряд множителя. Если он поменялся с 0 на 1, то происходит вычитание множимого из СЧП. При изменении младшего разряда множителя с 1 на 0 происходит сложение множимого с СЧП.

Если младший разряд множителя не изменился, то производится только сдвиг. При реализации этого метода происходит чередование сложения и вычитания, поэтому старший разряд СЧП в явном виде представляет его знак. При сдвиге знак СЧП сохраняется.

Эффективность метода Бута по сравнению с обычным методом поразрядного умножения проявляется для тех множителей, в которых имеются длинные последовательности единиц.