умножение в двоичном коде со знаком
Практическая работа №4 операция умножения чисел в ЭВМ
Практическая работа №4
Операция умножения чисел в ЭВМ
Целью работы является изучение умножения чисел как с фиксированной, так и с плавающей точкой в ЭВМ.
2. Теоретическая часть
2.1. Умножение чисел в двоичной системе счисления.
Наиболее просто умножение выполняется в прямом коде, независимо от того, являются ли операнды целыми или дробными числами. В ЭВМ с фиксированной точкой умножение реализуется в два этапа.
Первый этап заключается в определении знака произведения с помощью сложения знаковых цифр сомножителей по модулю два, где 0 – соответствует плюсу, а 1 – минусу (табл. 2.1.1).
Сложение по модулю два
По-другому, это эквивалентно
На втором этапе производится перемножение модулей сомножителей, затем в случае необходимости округления полученного модуля произведения, после чего к модулю результата приписывается его знак, определенный на первом этапе.
Умножение производится по обычным правилам арифметики, согласно двоичной таблицы умножения (табл. 2.1.2).
Традиционная схема умножения похожа на известную из школьного курса процедуру записи «в столбик». Вычисление произведения двух n-разрядных двоичных чисел без знака сводится к формированию частичных произведений (ЧП) по одному на каждую цифру множителя, с последующим суммированием полученных ЧП. Перед суммированием каждое частичное произведение должно быть сдвинуто на один разряд относительно предыдущего.
2.2. Умножение двоичных чисел в ЭВМ. Машинный метод.
Умножение двоичных чисел сводится к операциям сдвига на один двоичный разряд влево и повторения первого сомножителя в тех разрядах, где второй сомножитель содержит 1, и сдвига без повторения в разрядах с 0. Сдвиг всегда чередуется со сложением, поскольку для выполнения операций имеется всего два регистра (два места для записи чисел). Другими словами, реализации отдельной операции умножения в процессоре не требуется.
Как и в операции сложения, при умножении чисел с ограниченной разрядной сеткой может возникнуть переполнение.
Перемножение двух n-разрядных двоичных чисел P=A*B приводит к получению результата, содержащего 2n битов. Таким образом, алгоритм умножения предполагает последовательное выполнение двух операций – сложения и сдвига. Суммирование ЧП обычно производится не на завершающем этапе, а по мере их получения. Это позволяет избежать необходимости хранения всех ЧП, то есть сокращает аппаратурные издержки. Устройство умножения предполагает наличие регистров множимого, множителя и суммы частичных произведений, а также сумматора ЧП и, возможно, схем сдвига (если операция сдвига не реализована иным способом).
Существуют следующие алгоритмы умножения:
Рассмотрим пример умножения двоичных чисел в ЭВМ.
Выполнить умножение чисел A = 101112 и B = 1012 в двоичной системе счисления.
Умножение выполняется в несколько этапов:
1. Впишем множимое A, допустим в 8-ми разрядный регистр, начиная с младших разрядов (нумерация разрядов начинается с нуля). В недостающие разряды записываем нули.
2. Впишем множитель В в 8-ми разрядный регистр, начиная с младших разрядов. В недостающие разряды записываем нули.
3. Подготовим (обнулим) регистр результата C удвоенной разрядности (16 бит). Произведение содержит в два раза больше разрядов чем исходные сомножители.
4. Дальше выполняется следующий цикл:
4.1. Анализируем очередной разряд множителя В (начинаем с младших), если он «1», то прибавляем множимое A к старшим разрядам регистра С, результат снова в С. Если очередной разряд множителя «0», пропускаем данный шаг.
4.2. Сдвигаем содержимое регистра С на один разряд вправо. При этом крайний левый (старший) разряд заполняется нулем. Но если перед этим была операция сложения, во время которой возник перенос из старшего разряда, то тогда крайний левый разряд заполняется единицей.
4.3. Действия, описанные в п. п. 5.1 и 5.2,повторяютсядо тех пор не будут проанализированы все разряды множителя.
В итоге процесс умножения выглядит следующим образом:
5. Определяется знак результата. Если знаки исходных сомножителей одинаковы, то результирующее произведение положительно и наоборот. В данном случае знаки совпадают, следовательно результирующее произведение положительно.
В итоге получается ответ: 
Выполнить умножений и деление чисел согласно варианту задания.
4.1. Выполнить умножение чисел A и B в двоичной системе счисления, используя ручной метод. Показать решение.
4.2. Выполнить умножение чисел A и B двоичной системе счисления, используя машинный метод. Разрядность регистров выбрать самостоятельно. Показать решение.
Умножение чисел с фиксированной запятой в прямом и дополнительном кодах
Умножение чисел с фиксированной запятой имеет несколько вариантов, каждый из которых влияет на те или иные характеристики ЭВМ и, соответственно, должен быть принят во внимание при ее проектировании или анализе ее работы.
Умножение чисел c фиксированной запятой на 2 в степени ±k
Умножение двоичных чисел на целую степень числа два, казалось бы, не представляет существенных сложностей. Но при машинном выполнении этого действия необходимо учитывать ряд моментов, среди которых форма представления числа, разрядность используемой машинной сетки, код, в котором записано данное число и некоторые другие.
Данное действие используется как при выполнении операции умножения, так и деления чисел в различных кодах и с использованием разных алгоритмов.
Умножение чисел c фиксированной запятой на 2 в степени +k
Данное действие соответствует увеличению двоичного числа в k раз, что равносильно его сдвигу влево на k разрядов. При этом необходимо учесть следующие моменты:
Для положительных чисел их представление в прямом, обратном и дополнительном кодах совпадают (Рис.8.1).
Поэтому умножение числа на 2 +k для всех кодов происходит аналогичным образом. Очевидно, что для положительного числа данное действие приведет к переполнению (число превысит единицу) лишь при условии k > s.
Освобождающиеся справа разряды заполняются нулями (Рис.8.2):
Для отрицательных чисел умножения на 2 +k зависит от того, в каком коте это число представлено.
Для чисел, записанных в прямом коде, умножение не приведет к переполнению разрядной сетки в случае, если первые s разрядов числа были единицами, и выполнялось условие s > k (Рис.8.3). При этом освобождающиеся справа разряды заполняются нулями.
Для чисел, заданных в прямом коде, выполняется, так называемый, логический сдвиг, при котором знак числа остается на месте, а освобождающиеся за знаком позиции заполняются нулями. При этом цифры, выходящие за пределы разрядной сетки, теряются (Рис.8.4).
Цифры, выходящие за пределы разрядной сетки, теряются (Рис.8.5).
Умножение чисел, заданных в прямом коде
Рассмотрим вариант умножения операндов, представленных в прямом коде. Числа с фиксированной запятой в прямом коде записываются согласно выражению (7.1). Поэтому запишем множимое как 
, а множитель как 
. Тогда произведение нам необходимо получить в виде
и действие распадается на два самостоятельных действия: получение знака произведения и получение модуля его числовой части.
Знак произведения определяется обычным образом как сумма по модулю 2 знаков сомножителей:
 | ( 8.1) |
Теперь запишем формулу (точнее, формулы) для вычисления модуля произведения.
Преобразуя эту формулу, получим
 | ( 8.2) |
которая приводит к алгоритму умножения со старших разрядов множителя, или к формуле
 | ( 8.3) |
которая показывает последовательность действий при умножении с младших разрядов множителя.
Прежде чем подробно рассматривать примеры, иллюстрирующие каждый из этих алгоритмов, остановимся на некоторых общих для обоих алгоритмов моментах.
Во-первых, отметим, что мы имеем дело с двоичными числами. В связи с этим, yi может принимать только два разных значения: «ноль» либо «единица». В первом случае величина 
не участвует в формировании частичного произведения на соответствующем шаге умножения, а во втором случае – участвует.
Такой сдвиг реализуется на основе сдвигового регистра (см. «Схемотехническая реализация элементов вычислительной техники» ). При этом разряды, выходящие за пределы разрядной сетки, теряются (но в полноразрядной сетке такого произойти не может).
Пример 8.1.
В-третьих, следует сказать о разрядности используемых в операции операндов, произведения и разрядной сетки, в которой необходимо проводить необходимые действия по его получению.
ЭВМ работает с операндами равной длины. Если длины операндов не совпадают, то операнд, имеющий меньшую длину, расширяется знаком до разрядности операнда с большей длиной. Поэтому будем считать, что оба операнда имеют длину в n числовых разрядов. В этом случае мы получим 2n разрядное произведение (не считая одного разряда, отводимого под знак числа).
Получение результата с точностью, превосходящей точность исходных данных, бессмысленно. В литературе показано [. ], что в случае n разрядных операндов необходимая точность получается для чисел в формате с фиксированной запятой для результата в укороченной разрядной сетке, содержащей n + d разрядов, где d ≥ log2n.Так, для чисел, имеющих четыре разряда в цифровой части, можно проводить умножение в разрядной сетке 4 + log24 = 6 разрядов. Но, во-первых, это потребует проведения округления на каждом шаге вычисления произведения. А, во-вторых, возникают вопросы: «Что делать с полученным числом, которое имеет длину больше, чем длина операнда, но меньше, чем удвоенная длина операнда? Как его хранить в памяти? Как использовать в последующих операциях?» В силу этого и ряда других моментов укороченная разрядная сетка при выполнении так называемых «длинных» операций (умножения и деления) в универсальных компьютерах не применяется, и мы при рассмотрении примеров выполнения умножения и деления ею пользоваться не будем.
Умножение чисел с фиксированной запятой в прямом и дополнительном кодах
Умножение со старших разрядов множителя чисел, заданных в прямом коде
Напомним, что при реальной записи числа в памяти ЭВМ какие-либо символы, отделяющие знак от цифровой части числа, отсутствуют. Так что в данном случае мы имеем дела с пятиразрядным числом, включающим знак и четыре цифровых разряда.
Так как в прямом коде знак произведения и его модуль формируются отдельно, то следует обсудить лишь вопросы, касающиеся количества разрядов, отводимых под хранение мантисс сомножителей и мантиссы произведения.
Мы уже отмечали, что произведение следует получать в 2n-разрядной сетке, где n – количество разрядов у операндов.
Умножение со старших разрядов множителя заключается в том, что за время умножения на один разряд множителя происходит два действия:
В силу того, что в операции должны участвовать операнды одинаковой разрядности, а разрядность результата, равна 2n, то и 
изначально должен храниться в регистре длиной 2n, в котором младшие n позиций заполнены нулями. Также изначальное значение СЧП тоже должно быть равно нулю и изначально все ее позиции должны быть заполнены нулями. Для СЧП может быть выбран обычный регистр хранения: исходя из формулы (8.2) его значение сдвигам не подвергается.
Регистр, хранящий 
, в процессе выполнения умножения интересен не как единое целое, а как набор отдельных разрядов, хранящих значения yi, использующихся при формировании очередного СЧП. Получение очередного значения yi в следующем такте формирования СЧП может быть выполнено разнообразными схемотехничекими решениями, наиболее рациональным из которых представляется хранение в n-разрядном регистре сдвига, его сдвиге в сторону старших разрядов после анализа очередного разряда и снятии старшего разряда этого регистра в каждом такте для анализа очередного разряда yi.
Таким образом, мы получаем следующие схемотехнические требования к регистрам, которые хранят модули операндов и результата:
Пример 8.2.
Умножить два числа с фиксированной запятой, заданных в прямом коде, со старших разрядов множителя: Xпк = 1.0110, Yпк = 0.1010.
Исходя из вышесказанного, выполнение данного примера будет складываться из следующих этапов.
Так как в формировании произведения участвует , сдвинутый на соответствующее число разрядов вправо, то для наглядности будем представлять его в виде отдельного столбца значений.
На основе данного примера рассмотрим еще один момент, отражающий связь между используемым при выполнении арифметических действий алгоритмом и особенностями организации ЭВМ. При умножении со старших разрядов множителя чисел, заданных в прямом коде, к значению СЧП, полученному на очередном шаге, в зависимости от значения очередного разряда yi добавляется либо , сдвинутый на соответствующее количество разрядов вправо, либо ноль. Добавления ноля, казалось бы, только замедляет выполнение операции (в половине случаев такое сложение бессмысленно). Однако, и тот, и другой вариант действий может быть использован. Первый вариант носит название варианта без пропуска такта суммирования, а второй, соответственно, с пропуском такта суммирования.
В качестве преимущества первого варианта мы отметили устранение операции суммирования с нулем, которое не приводит к изменению предыдущего значения СЧП. Но при этом у нас изменяется регулярность последовательности тактов выполнения операции умножения, а само значение yi должно быть передано и проанализировано устройством управления компьютера, которое является сложной и нерегулярной схемой. В то же время прибавление нуля к СЧП (при yi = 0) можно осуществить достаточно просто. Фрагмент такого действия показан на Рис. 8.6. Более подробно арифметико-логическое устройство, реализующее такой алгоритм умножения, показано в [ ].
Умножения с младших разрядов множителя чисел, заданных в прямом коде
Данное умножение реализуется согласно формуле (8.3). Суть этой формулы проста: к СЧП, полученной на предыдущем шаге добавляется , умноженный на значение соответствующего разряда yi, а затем полученное новое значение сдвигается вправо на 1 разряд. Нюанс этого алгоритма как раз и заключается в этом сдвиге, завершающем формирование очередного значения СЧП.
Пример 8.3.
Выполнить умножение с младших разрядов множителя следующих чисел с фиксированной запятой, заданных в прямом коде:
Умножение чисел с фиксированной запятой в прямом и дополнительном кодах
Умножение с младших разрядов множителя чисел, заданных в дополнительном коде
При умножении чисел, заданных в дополнительном коде, с младших разрядов множителя, так же как и при умножении со старших разрядов множителя в формировании произведения участвует все число, включая его знак. Произведение также получается в дополнительном коде со знаком. Соответствующая формула умножения выглядит следующим образом:
 | ( 8.4) |
где y0 – знак множителя;
yn+1 – разряд, дополняющий множитель справа; для дополнительного кода yn+1 ≡ 0 при любом значении знака Yдк.
Так же, как и в предыдущем алгоритме, (yi+1-yi) может принимать три разных значения: (-1), (0), (+1), исходя из чего на каждом шаге вычислений к полученному на предыдущем шаге значению СЧП добавляется Xдк, ноль или (-Xдк) соответственно.
Следует отметить, что, в отличие от аналогичного способа умножения модулей сомножителей в прямом коде, здесь на последнем шаге сдвига вправо нет.
Пример 8.5.
Выполнить умножение с младших разрядов множителя следующих чисел с фиксированной запятой, заданных в дополнительном коде: Xдк = 0.1100; Yдк = 0.0111
Решение.
Пример 8.6.
Перемножим с младших разрядов самые большие (по модулю) числа, которые можно представить в дополнительном коде: Xдк = 0.1111; Yдк = 1.0000.
Решение.
Выполним проверку.
Это соответствует ожидаемому результату.
Выполним проверку.
Это соответствует ожидаемому результату.
Краткие итоги
В данной лекции рассмотрены способы умножения чисел с фиксированной запятой, заданных в прямом и дополнительном кодах. Рассмотрено умножение положительных и отрицательных чисел, заданных в прямом и дополнительном кодах, на 2 ±k как арифметический или логический сдвиг соответствующего числа. Показана связь различных алгоритмов умножения с используемой аппаратурой.
Процесс умножения чисел в двоичной системе счисления прост, так как разрядами множителя могут быть либо «0», либо «1», и, следовательно, частичным произведением в каждом такте цикла умножения будет либо «0», либо множимое. Поэтому в цикле умножения двоичных чисел три элементарных операции:
1. анализ цифры очередного разряда множителя;
2. суммирование множимого с накопленной суммой частичных произведений, если цифра множителя «1»;
3. сдвиги в каждом такте умножения.
Умножение можно выполнять как с младших, так и со старших разрядов множителя, со сдвигом, как частичной суммы, так и множимого в процессе умножения. Этим объясняется существование четырех способов умножения чисел.
Следует обратить внимание на то, что множитель сдвигается во всех способах умножения, так как в каждом такте анализируется очередной разряд: при умножении с младших разрядов сдвиг вправо (в сторону младших разрядов), при умножении со старших разрядов множитель сдвигается влево. И еще одна особенность, позволяющая легко запомнить способы умножения: сумма частичных произведений обычно сдвигается в ту же сторону, что и множитель, а множимое сдвигается навстречу множителю, т.е. в противоположную сторону.
|
Знак произведения: 0 + 1 = 1
n
2n