Умножение целых двоичных чисел

Умножение чисел без знака

Пусть необходимо вычислить произведение 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 = 1101₂, Y = 10 = 1010₂) приведен в табл. 4.11.

Рис. 4.65. Схема алгоритма

Таблица. 4.11

Трасса исполнения циклов

Умножение чисел со знаком

Для отрицательных чисел, хранящихся, как правило, в памяти компьютера в дополнительном коде, удобнее использовать один из алгоритмов умножения в ДК, например умножение в ДК с преобразованием, при котором оба сомножителя преобразуются (инвертируются, а затем увеличиваются на единицу младшего разряда: Х_пр =|Х|_дк+1,

Y_np =| Y | _дк +1), если Y отрицательное число, либо остаются неизменными при Y > 0. Схема умножения может быть любой из 4 схем, названных выше.

Пример.

Найти Z = XY, используя схему умножения с анализом младшего разряда Y со сдвигом СЧП, если

Поскольку Y < 0, требуется преобразование сомножителей:

Трасса исполнения циклов приведена в табл. 4.12.

Таблица 4.12

Умножение в ДК с преобразованием

После перехода от кода к числу ([Z]_flK —» Z) получим Z = = -00001111₂ = -15.

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