В ЭВМ операция умножения чисел с фиксорованной запятой сводится к операциям сложения и сдвига
Числа с фиксированной запятой (ф.з.) – правильная дробь со знаком
Старший разряд является знаковым
n-разрядное число можно представить в виде
С точностью до множителя (*) число с ф.з. неотличимо от целого
Из дробного числа можно получить целое, домножив его на масштабирующий коэффициент 2n-1
Из целого числа можно получить дробное, домножив его на масштабирующий коэффициент 2-(n-1)
Удобнее использовать числа при умножении в дополнительном коде.
Рассмотрим умножение двухразрядных двоичных слов, в результате чего должно получиться четырехразрядное двоичное слово
01. ´ 01. = 0001.
0.1 ´ 0.1 = 0.010
0.1 ´ 01. = 0.100
Алгоритмы умножения в первых двух случаях различаются числом циклов, а умножение числа с фиксированной запятой на целое требует введения специального масштабирующего коэффициента, равного 2n-1 , где n - число разрядов в машинном слове.
Следует отметить, что умножение числа с фиксированной запятой на целое представляет собой особый случай, не позволяющий при выполнении операции однозначно определить признак переполнения (так как непонятно, какой результат должен получиться – меньше или больше единицы), и поэтому, как правило, в вычислительных машинах отсутствует.
P = A ´ B
A – множимое; B – множитель; P – произведение
При умножении двух n-разрядных сомножителей получаем 2n-разрядный результат
Pi = Pi-1 + A·bi ·qi
Pi – i-я сумма частичных произведений
В зависимости от способа формирования суммы частичных произведений различают четыре основных метода выполнения умножения и соответственно четыре структуры АЛУ для этой операции. Для определенности сначала будем считать, что оба сомножителя – положительные числа
1. Умножение, начиная с младших разрядов множителя, со сдвигом суммы частичных произведений вправо и при неподвижном множимом.
Регистр множителя и сумматор частичных произведений при этом должны иметь цепи сдвига вправо. Регистр множимого может не иметь цепей сдвига. Последовательность действий в каждом цикле выполнения умножения определяется младшим разрядом регистра множителя, куда последовательно одна за другой поступают цифры множителя.
Поскольку по мере сдвига множителя вправо старшие разряды множителя освобождаются, он может быть использован для хранения младших разрядов произведения, поступающих из младшего разряда сумматора частичных произведений по мере выполнения умножения. Для этого при выполнении сдвига младший разряд регистра сумматора частичных произведений соединяется со старшим разрядом регистра множителя. После выполнения умножения старшие разряды произведения находятся в регистре сумматора, младшие – в регистре множителя.
При данном методе умножения все три регистра имеют одинаковую длину, равную числу разрядов сомножителей. Этот метод умножения нашел наибольшее применение в ЭВМ.
2. Умножение, начиная с младших разрядов множителя, при сдвиге множимого влево и при неподвижной сумме частичных произведений.
Регистр множителя при этом должен иметь цепи сдвига вправо, регистр множимого – влево, а сумматор частичных произведений не содержит цепей сдвига. Последовательность действий определяется, как и в первом случае, младшим разрядом регистра множителя.
При этом методе регистр множимого и сумматор частичных произведений должны иметь двойную длину. Этот метод требует больше оборудования, но никаких преимуществ не дает, и поэтому его применение не целесообразно.
3. Умножение, начиная со старших разрядов множителя, при сдвиге суммы частичных произведений влево и неподвижном множимом.
Регистр множителя и сумматор частичных произведений должны иметь цепи сдвига влево. Регистр множимого не имеет цепей сдвига. Последовательность действий в каждом цикле выполнения умножения определяется старшим разрядом регистра множителя.
При этом методе сумматор частичных произведений должен иметь двойную длину. Данный метод требует дополнительного по сравнению с первым методом оборудования. Несмотря на это, он применяется в некоторых АЛУ, т.к. позволяет без дополнительных цепей сдвига выполнять и деление.
Для выполнения операции деления в АЛУ, реализующем первый метод умножения, необходимы дополнительные цепи сдвига влево в регистре множимого (частного) и в сумматоре частичных произведений (разностей).
4. Умножение, начиная со старших разрядов множителя, при сдвиге вправо множимого и неподвижной сумме частичных произведений.
Регистр множителя должен иметь цепи сдвига влево, регистр множимого – цепи сдвига вправо. Сумматор частичных произведений не имеет цепей сдвига. Последовательность действий на каждом шаге умножения определяется старшим разрядом регистра множителя.
При этом методе умножения и регистр множимого, и сумматор частичных произведений должны иметь двойную длину. Однако, как и третий метод, он не требует дополнительных цепей сдвига для выполнения деления.
Рассмотрим первый алгоритм умножения:
Умножение, начиная с младших разрядов множителя, со сдвигом суммы частичных произведений вправо и при неподвижном множимом.
начальные установки
Сдвиг вправо двойного
слова
сдвиг короткого слова осуществляется через перенос
После получения результата в формате двойного слова необходимо дополнительно сдвинуть его на один разряд вправо, чтобы правильно расположить произведение в разрядной сетке.
Произведение и множимое хранятся в РЗУ, множитель – в регистре расширения
Умножение чисел со знаком
Умножение чаще всего производится в допонительном коде
1. Перемножаем числа без знака
старший разряд числовой
переполнение перенос
2. Вещественные числа
Признак переноса не является признаком переполнения
V – признак арифметического переполнения (OVR)
V=1
- управляемая инверсия
модифицированный сдвиг
Модифицированный код – под знак отводотся 2 бита; при этом изменяется только младший знаковый разряд, старший остается правильным
B – отрицательное
P = A·Доп(B) = A·(2n – |B| ) = A·2n – A·B = A·2n + Доп(A·|B|)
Pбез bn-1 = A·2n – A·|B| – A·2n-1 = A·2n-1 + Доп(A·|B|) = A (зн. B)· 2n-1 + Доп(A·|B|)
Доп(A·|B|) = Pист = Рбез bn-1 – A·bn-1·2n-1
Умножаем на (n-1) младший разряд множителя с учетом знака множимого.
Из полученного произведения вычитаем множимое, умноженное на знаковый разряд с его весом
P = 0 + A·b0 + A·b1 + … + A·bn-1 + (– A·bn-1)
Деление
Деление – одна из многих обратных операций
Делимое должно быть 2n разрядным; делитель и частное – n-разрядными
Р – делимое
А – делитель
В – частное
Любая обратная операция определяется методом подбора цифр
bn-1·A £ P
(bn-1 + 1)·A > P
bn-1 = 1
P – A ³ 0
P = P n-1 = P n-2 + pn-1
Произведение º Делимое
Частичные суммы º остатки (P i )
P n-2 = P n-1 – pn-1
Если остаток ³ 0, то bn-1 = 1,
иначе bn-1 = 0
bi – очередной разряд частного
1) алгоритм деления с восстановлением остатка
Восстанавливаем остаток, если лн меньше нуля
Если очередной остаток (P i – A)< 0, то восстанавливаем его, т.е. заменяем на P i
Пусть (P i – A) – текущий остаток от деления;
Если он отрицательный, то нужно вернуться к прежнему остатку, т.е.
P i – A + A = P i-1 – следующий остаток,
и осуществляется сдвиг делителя вправо – А/2
P i-1 –A/2 = P i – A + A – A/2 = (P i – A) + A/2
отрицательный остаток
2) алгоритм деления без восстановления остатка
Если текущий остаток отрицательный, то при подборе следующей цифры прибавляется делитель, сдвинутый на один разряд вправо,
P i-1 –A/2 = (P i – A) + A/2
отрицательный остаток
в очередной разряд частного записываем 0;
если текущий остаток положительный, то при подборе следующей цифры вычитается делитель, сдвинутый на один разряд вправо,
P i-1 –A/2 = (P i – A) – A/2
в очередной разряд частного записываем 1;
Если предыдущая цифра 1 – вычитаем делитель
0 – прибавляем делитель
Если хотим осуществить умножение быстрее, чем за n тактов, то существует 2 варианта:
1. Новые алгоритмы
2. Построение специализированных схем
Новые алгоритмы
Умножение 16-ти разрядных чисел
Умножаются за 16 тактов – в двоичной системе
за 8 тактов – в восьмеричной системе
Умножение с анализом двух разрядов
Вычисления в четверичной СС
0 00
1 01
2 10
3 100-001 (3=4-1)
основной алгоритм Бута, не теряется знак
упрощенный алгоритм Бута
qст – признак коррекции предидущего разряда
Рассмотрим один из способов умножения на два разряда множителя, начиная с его младших разрядов (упрощенный алгоритм Бута). В зависимости от результата анализа пары разрядов множителя предусматриваются следующие действия. При 00 производится простой сдвиг на два разряда вправо суммы частичных произведений. При 01 к сумме частичных произведений прибавляется одинарное множимое и сумма частичных произведений сдвигается на два разряда вправо. При 10 прибавляется удвоенное множимое и сумма частичных произведений сдвигается на 2 разряда вправо. При 11 из суммы частичных произведений вычитается одинарное множимое и сумма частичных произведений сдвигается на два разряда вправо. Тогда в первых трех случаях результат получается правильный, а в последнем – неправильный, он должен быть скорректирован на следующем шаге.
Поскольку при 11 из суммы частичных произведений вычитается одинарное множимое вместо прибавления утроенного множимого, для корректировки результата к сумме частичных произведений надо было бы прибавить учетверенное множимое. Но после сдвига на два разряда вправо сумма частичных произведение уменьшается в четыре раза, так что для корректировки его на следующем шаге должно быть прибавлено одинарное множимое.
Это учитывается при обработке следующей пары разрядов. Если следующая пара 00, по она обрабатывается как 01, если 01, то как 10, если 10 то как 11, если 11, то как 00 и фиксируется необходимость коррекции при обработке следующей пары. Удвоенное множимое может быть получено его сдвигом. Признак необходимости коррекции может запоминаться в отдельном триггере коррекции.
Данный метод умножения требует корректировки результата, если старшая пара разрядов множителя 11 или 10 и состояние триггера коррекции является единичным.