Схемы ускоренного умножения

<

/b>Как следует из выражения (9.67), при умножении операндов АХ! ВХ основную задержку при получении произведения вносит суммирование частичных произведений Рп = АмВп 2пу число которых определяется разрядность N множителя ВЛ. В дальнейшем операнды будем писать без верхних индексов М и М, означающих их разрядность.

Воспользуемся тождеством.

для преобразования множителя В к виду, позволяющему сократить число частичных произведений Р^п в выражении (9.67). Запишем множитель, выделив члены с четными и нечетными показателями степеней при числе 2:

Выражение (9.69) для нечетных п = 2/ + 1 имеет вид Подставив выражение (9.71) в формулу (9.70), получим.

где коэффициент В _л = 0 (при п = 0) введен для общности записи. Принцип удаления членов с нечетными степенями 2^2и+1 следует из тождества (9.69) и проиллюстрирован на рис. 9.101.

После подстановки равенства (9.72) в формулу (9.67) выражение для произведения приобретает следующий вид:

Таким образом, с помощью тождеств (9.69) и (9.71) в исходном выражении (9.67) для произведения двух операндов исключены члены, содержащие нечетные показатели степени при числе 2, благодаря чему уменьшилось практически в два раза чисто частичных произведений.

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

Составим таблицу (табл. 9.33) для нормированных значений частичных произведений.

при всех возможных комбинациях В_2п+1, В_2п, В_2п__{.

Таблица 933

	к	Вгп-[	руг2" .	Операция для получения Рп/22" .
				Заменить А нулем.
			А	Копировать А
			А	Копировать А
			2 А	Сдвинуть А влево на один разряд.
			-2 А	Сдвинуть А влево на один разряд и преобразовать в дополнительный код.
			-А	Преобразовать А в дополнительный код.
			-А	Преобразовать А в дополнительный код.
				Заменить А нулем.

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

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

• • записать в дополнительном коде множимое [Л]_д и множитель [ В |_л — первые две строки примеров и первая строка пояснения;
• • при необходимости расширить разрядную сетку множителя [В]_д (пример 2 — первая строка пояснения)-,
• • последовательно выбирая тройки В_2п. _{В₂₁₁В_2г1, (см. пояснения) из множителя В (см. формулу (9.73)) для п = 0,1,3,…, по табл. 9.33 определить и выполнить необходимую операцию для нахождения частичного произведения Р^п
• • для получения всего произведения Р = АВ просуммировать полученные частичные произведения с учетом их сдвига влево на к разрядов, определяемого множителем 2^к. Освободившиеся при сдвиге разряды заполняются нулями.

При реализации алгоритма необходимо расширить разрядную сетку частичных произведений до разрядной сетки всего произведения Р = АВ. Для положительных чисел старшие разряды заполняются нулями, для отрицательных — единицами. Для наглядности в примерах знаковые разряды отделены от значащих разрядов точкой.

Частичные произведения (9.73) можно получить с помощью комбинационной схемы. Покажем способ получения структурных формул для комбинационной схемы на примере умножителя 4×2. Правила функционирования умножителя приведены в таблице истинности (табл. 9.34), где р" — старший разряд частичного произведения (введен для расширения разрядной сетки); с"  — коэффициент, используемый для получения дополнительного кода; Р" /2²" — нормированное частичное произведение.

На основании табл. 9.34 составим структурные формулы для отдельных разрядов частичных произведений в СДНФ:

где к = 0,1, 2, 3.

Таблица 9.34

	4(1+1.	К	4л 1.	р	pH.	р'1	р"	Р" о	с" .	/*/22п
				^3.	^3.	А2				А
				Аз.	Лз.		з,.			А
				Л3			Л.	4,.		2 А
					Л2		^0.	4,.		2 (А + с")
					^3.					А + с"
				Л3	^3.					А + с"

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