12. Алгоритм Бута для умножения чисел в форме с фикс. Точкой.

Алгоритм Бута удобно рассмотреть с помощью упрощенной схемы множительного устройства, имеющего вид:

На данной схеме символами R₁, R₂ и R₃ обозначены функциональные узлы называемые регистрами. Каждый такой регистр содержит определенное количество разрядов, которые могут устанавливаться в одно из двух состояний 0 или 1. Таким образом, в регистре можно помещать многоразрядные двоичные числа, служебные разряды С1 и С0 также могут рассматриваться как один двухразрядный регистр. Регистры R₂, R₃ и служебные разряды С1 и С0 объединены между собой так, что можно одновременно сдвигать содержимое всех их разрядов вправо, при этом в старший регистр R₃ поступает содержимое младшего регистра R₂, а в С1 поступает содержимое младшего разряда R₃. Таким образом, при проведении операции сдвига R₂, R₃, С1 и С0 можно рассматривать как один общий сдвиговый регистр. В регистре R₁ и R₃ предварительно помещают множимое и множитель, причем отрицательные сомножители должны представляться в дополнительном коде и если результат операции умножения является отрицательным числом (1 в старшем разряде регистра R₂), то она так же оказывается представленным в дополнительном коде. В регистре R₂ периодически записывается текущая сумма частичных произведений и формируются старшие разряды результата произведения в сумматоре выполняется алгебраическое сложение двух двоичных чисел поступающих на два его кода. Счетчик циклов предназначен для фиксации необходимого количества сдвиговых и суммирующих операций. Порядок проведения операции умножения по алгоритму Бута рассмотрим на алгоритмической блок-схеме имеющей вид:

На первом этапе в регистре R₁ и R₃ заносятся соответственно множимое и множитель, во все разряды регистра R₂ и разряды С1 и С0 заносятся 0. в счетчик циклов заносится целое число n, равное количеству разрядов в сомножителях.

Следующий этап состоит в арифметическом сдвиге вправо содержимого регистров R₂, R₃ и разрядов С1 и С0 на один разряд. Причем, при арифметическом сдвиге остается неизменным содержимое старшего знакового разряда регистра R₂. Далее выполняются операции по определению содержимого служебных разрядов С1 и С0. В зависимости от содержания С1 и С0 производятся соответствующие операции алгебраического сложения над содержимым регистров R₂ и R₁ со значением результата обратно в регистре R₂, причем если С1=1, а С0=0, то множимое складывается с содержимым регистра R₂, как отрицательное число в дополнительном коде. Если С1=0, а С0=1, то множимое складывается с содержимым регистра R₂ как положительное число в прямом коде. Количество повторений операций сдвига и количество операций алгебраического сложения контролируется счетчиком циклов. В каждом цикле выполняется вычитание 1 из содержимого счетчика и при достижении им нулевого значения происходит выход из вычислительного сдвига.

Рассмотрим использование алгоритма Бута на примере умножения чисел Х= +11₁₀= +1011₂ и У= -7₁₀= - 0111₂.

Представим числа в формате байта (8 разрядов):

Х= (00001011)_пр

У= (10000111)_пр

У= (11111000)_обр

У= (11111001)_доп

Изменим знак числа Х и представим его в дополнительном коде:

-Х= (10001011)_пр

-Х= (11110100)_обр

-Х= (11110101)_доп

Выполняемые при умножении операции представим в виде таблицы:

	R2	R3	C1 C0	Сч	Выполняемая операция
[-X]доп. [X]доп. Отбрасыв [-X]доп.	00000000 0 0000000 11110101 11110101 11111010 00001011 100000101 00000010 00000001 11110101 11110110 11111011 11111101 11111110 11111111	11111001 01111100 01111100 10111110 10111110 11011111 01101111 01101111 00110111 10011011 11001101 01100110	0 0 1 0 1 0 0 1 0 1 0 0 1 0 1 0 1 1 1 1 1 1 1 1	8 8 8 7 7 6 5 5 4 3 2 1 0	Исходное состояние Арифметический сдвиг Сумма Арифметический сдвиг Сумма Арифметический сдвиг Арифметический сдвиг Сумма Арифметический сдвиг Арифметический сдвиг Арифметический сдвиг Арифметический сдвиг Выход из вычислитель-ного цикла
	Результат в дополнительном коде

После перевода результата в прямой код будем иметь:

(111111110110011)_доп

(100000001001100) провели инверсию

(100000001001101)_пр → -77₁₀.