УМНОЖЕНИЕ ДВОИЧНЫХ ЧИСЕЛ 

      1. Основные методы выполнения операции умножения в двоичной системе счисления 

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

      1) умножение начиная с младших разрядов множителя:

      1101 -- множимое,

ґ

1101 -- множитель,

      _________________

      1101

                          0000

   +

            1101 -- частные произведения,

          1101

      ________

            10101001-- произведение; 

      2) умножение начиная со старших разрядов множителя:

      1101 -- множимое,

ґ

1101 -- множитель,

      _________________

      1101

                        +    1101 -- частные произведения,

                0000

                       1101   

                 ________

                      10101001-- произведение. 

      В обоих случаях операция умножения состоит из ряда последовательных операций сложения частных произведений. Операциями сложения управляют разряды множителя: если в каком-то разряде множителя находится единица, то к сумме частных произведений добавляется множимое с соответствующим сдвигом; если в разряде множителя -- нуль, то множимое не прибавляется.

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

      Метод 1. Пусть А -- множимое (А>0), В -- множитель (В>0), С -- произведение. Тогда в случае представления чисел в форме с фиксированной запятой получаем:

 

      

      

                       Рис. 1 . Структурные схемы множительного устройства 

      А = 0,   а₁а₂…а_n;

      В = 0,   b₁b₂…b_n = b₁Ч2^-1 + b₂Ч2^-2 +…+ b_nЧ2^-n.

      Отсюда

      С = А Ч В = 0,  а₁а₂…а_n(b₁Ч2^-1 + …+ b_nЧ2^-n) =

      = (2^-1Ч0, а₁а₂…а_n) b₁ + (2^-2Ч0, а₁а₂…а_n) b₂ +…

      …+ (2^-nЧ0, а₁а₂…а_n) b_n.         (1) 

      Множитель 2^-n означает сдвиг на n разрядов вправо числа, которое заключено в скобки, т. е. в данном случае сдвигается вправо множимое и умножение начинается со старших разрядов.

      Структурная схема рассмотренного множительного устройства 
представлена на рис. 1, а.  

      Метод 2. Пусть А=0, а₁а₂…а_n  -- множимое и В=0, b₁b₂…b_n - множитель.

      Множитель можно легко преобразовать, используя метод Горнера:

      В = (…(b_nЧ2^-1 + b_n-1) Ч2^-1 + b_n-2) Ч2^-1 +…+ b₂) Ч2^-1 + b₁) Ч2^-1.

      Тогда

      С = А Ч В = (…((b_nЧ0, а₁а₂…а_n)Ч2^-1 + b_n-1 Ч0, а₁а₂…а_n)Ч2^-1 + …

      …+ b₁ Ч0, а₁а₂…а_n)Ч2^-1.         (2)

      Здесь умножение начинается с младших разрядов и сдвигается вправо сумма частных произведений. Структурная схема множительного устройства, реализующего этот метод, представлена на рис. 1, б. 

      Метод 3. Пусть А=0, а₁а₂…а_n  -- множимое и В=0, b₁b₂…b_n - множитель.

      Множитель, используя метод Горнера, можно записать так:

      B = 2^-n(b₁ Ч2^n-1 + b₂ Ч2^n-2 +…+ b_n-1 Ч2¹ + b_n Ч2⁰) =

         = 2^-n(…((b₁ Ч2¹ + b₂) Ч2¹ +…+ b_n-1) Ч2¹ + b_n). 

      В этом случае

      С = А Ч В = 2^-n (b_nЧ0, а₁а₂…а_n + (2^-1Ч0,  а₁а₂…а_n)Чb_n-1 + …

      …+ (2^n-1Ч0, а₁а₂…а_n)Чb₁),        (3)

      что означает: умножение начинается с младших разрядов, и множимое сдвигается влево на один разряд в каждом такте. Схема множительного устройства представлена на рис. 1, в. 

      Метод 4. Пусть А=0, а₁а₂…а_n  -- множимое и В=0, b₁b₂…b_n - множитель. Если множитель В записать по методу Горнера:

      С = А Ч В = 2^-n (…2¹(b₁Ч0, а₁а₂…а_n) + b₂Ч0,  а₁а₂…а_n)Ч2¹ + …

      …+ b_n-1Ч0, а₁а₂…а_n)Ч2¹ + b_nЧ0, а₁а₂…а_n),      (4)

то умножение начинается со старшего разряда и в каждом такте сдвигается влево сумма частных произведений. Схема множительного устройства представлена на рис. 1, г.

      Таким образом, для реализации операции умножения необходимо иметь сумматор, регистры для хранения множимого и множителя и схему анализа разрядов множителя. Сумматор и регистры должны иметь цепи сдвига содержимого в ту или иную сторону в соответствии с принятым методом умножения.

      Анализ формул (1) ё (4) показывает, что с формальной точки зрения процесс умножения двух чисел может быть представлен:

      при последовательном выполнении -- в виде многократно повторяющегося по количеству разрядов цикла

      S_i = S_i-1 + AЧb_i ,      (5) 

где S_i-1, S_i -- суммы частных произведений на (i-1)-м и i-м шагах соответственно;

      при параллельном выполнении -- суммой членов диагональной матрицы, для которой заданы по строкам AЧ2^-i, а по столбцам -- b_i , где i -- текущий номер разряда. 

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

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

      При ограничении количества разрядов сумматора в произведение вносится погрешность. В случае большого объема вычислений погрешности одного знака накладываются друг на друга, в результате чего общая погрешность сильно возрастает. Поэтому существенное значение имеет округление результатов умножения, что дает возможность сделать погрешность произведения знакопеременной, а математическое ожидание погрешности (при условии, что отброшенные младшие разряды могут с одинаковой вероятностью иметь любое из возможных значений) -- равным нулю. При этом предельное по абсолютной величине значение погрешности будет наименьшим из возможных при заданном количестве значащих цифр, т. е. равным половине младшего разряда.

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

2. Умножение чисел, представленных в форме с фиксированной запятой, на двоичном сумматоре прямого кода 

      Пусть заданы машинные изображения двух чисел:

      [A]_пр = Sg_A , а₁а₂…а_n ;

      [B]_пр = Sg_B , b₁b₂…b_n.

      Тогда их произведение

      [C]_пр = Sg_C , c₁c₂…c_n.

где Sg_C = Sg_A Е Sg_B,  Е -- знак  сложения   по   модулю 2.

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

      Пример 1. Умножить числа

      [A]_пр = 1,11010;

      [B]_пр = 0,11001. 

      При умножении будут использованы метод 2 и устройство, показанное на рис. 2.

      Запись всех действий, выполняемых устройством, осуществляется с помощью условных обозначений, т. е. : = -- оператор присваивания (означает, что блоку, который указан слева от оператора, присваивается значение, указанное справа от оператора; -- сдвиг содержимого регистра   вправо   на   один   разряд; [СМ] -- содержимое сумматора; И. П. -- исходное положение.

      Решение. Знак произведения определяем отдельно от цифровой части в соответствии с уравнением 

      Sg_C = Sg_A Е Sg_B = 1 Е 0 = 1.

      Получение цифровой части можно показать в виде следующей записи. Пусть сумматор имеет 10 разрядов без учета знака, а регистры -- 5 разрядов без знака. Введем обозначения [А'], [В'] -- соответственно изображения цифровой части множимого и цифровой части множителя.