Пусть необходимо вычислить произведение Z = XY, где множимое X и множитель Y — целые n-разрядные числа:
Представим Y в развернутом виде
Тогда
Произведение множимого на один разряд множителя хЛ = (Ху;)2‘ называется частичным произведением, а сумма к таких произведений — k-й суммой частичных произведений (СЧП). При к = п СЧП превращается в произведение Z. Произведение двух п-разрядных сомножителей имеет длину, равную 2п. Различают 4 схемы последовательного умножения: две с анализом младшего разряда множителя (со сдвигом множимого X либо СЧП) и две с анализом старшего разряда множителя (со сдвигом множимого X либо СЧП).
В любой из четырех схем цикл умножения на один разряд множителя у; в общем случае включает 2 такта:
? такт суммирования тх,
? такт сдвигов
В трех из них такт суммирования является первым. При умножении с анализом старшего разряда Y со сдвигом множимого X первым считается такт сдвига.
Структурная схема такого умножения приведена на рис. 4.64.
Рис. 4.64. Структурная схема
Аналитически умножение описывается выражением
Схема алгоритма умножения приведена на рис. 4.65. Особенность его состоит в том, что анализируется старший разряд множителя Y, выдвинутый из регистра, который может храниться во флажке С — флажке переноса.
Пример умножения 4-разрядных сомножителей (X = 13 = 11012, Y = 10 = 10102) приведен в табл. 4.11.
Рис. 4.65. Схема алгоритма
Таблица. 4.11
Трасса исполнения циклов
Умножение чисел со знаком
Для отрицательных чисел, хранящихся, как правило, в памяти компьютера в дополнительном коде, удобнее использовать один из алгоритмов умножения в ДК, например умножение в ДК с преобразованием, при котором оба сомножителя преобразуются (инвертируются, а затем увеличиваются на единицу младшего разряда: Хпр =|Х|дк+1,
Ynp =| Y | дк +1), если Y отрицательное число, либо остаются неизменными при Y > 0. Схема умножения может быть любой из 4 схем, названных выше.
Пример.
Найти Z = XY, используя схему умножения с анализом младшего разряда Y со сдвигом СЧП, если
Поскольку Y < 0, требуется преобразование сомножителей:
Трасса исполнения циклов приведена в табл. 4.12.
Таблица 4.12
Умножение в ДК с преобразованием
После перехода от кода к числу ([Z]flK —» Z) получим Z = = -000011112 = -15.
Реализация умножения путем последовательного выполнения операций сложения и сдвига в течение п тактов занимает значительное время, что является недопустимым для ряда применений. Поэтому разработаны различные алгоритмы ускоренного умножения, основанные на одновременном анализе нескольких битов множителя, и быстродействующие однотактные умножители, например, матричные, которые выпускаются в виде отдельных микросхем либо входят в состав БИС в качестве операционных узлов.