Меню
Главная
Авторизация/Регистрация
 
Главная arrow Информатика arrow Информатика
Посмотреть оригинал

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

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

Пусть необходимо вычислить произведение 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.

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

 
Посмотреть оригинал
< Предыдущая   СОДЕРЖАНИЕ   Следующая >
 

Популярные страницы