КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Использование алгоритмов умножения в прямых кодах
Умножение чисел, представленных в дополнительных (обратных) кодах Умножение со старших разрядов множителя со сдвигом множимого вправо Отметим особенности данного алгоритма: 1) Сомножители в процессе умножения должны быть представлены в прямых кодах. 2) Операция выполняется над модулями чисел. 3) Умножение начинается со старших разрядов множителя, так что в первом такте умножения находится первое частное произведение С1 и первая сумма частных произведений S1 = C0 + C1. В каждом такте множитель сдвигается влево. 4) Множимое в каждом такте сдвигается вправо, например, в первом такте оно имеет вид A1 = A0 · 2-1. 5) Знак произведения определяется логическим путем. Выполним числовой пример с целью рассмотрения указанного алгоритма А=3/8=0.011; B=5/8=0.101; C=А*В = 15/64 = 0.001111 A=.011 A0=A B= * .111 Cч сдв=0.000000 С0= S0=0 Cч сдв=1 + .0011 A1= А0*2-1* b1, (b1=1) .001100 S1= С0+ А1 Cч сдв=2 .000000 A2= А1*2-1* b2, (b2=0) .001100 S2= S1+ А2 Cч сдв=3 .000011 A3= А2*2-1* b3, (b3=1) .001111 S3= S2+ А3 S = |C| =.001111 = 15/64. Запишем рекуррентную формулу для нахождения суммы частных произведений на каждом шаге умножения Si= Si-1+ Аi-1*2-1* bi. В тех случаях, когда числа в оперативной памяти хранятся в дополнительном или обратном кодах, возможны несколько способов реализации операции умножения. 1-й способ. Перед началом операции умножения анализируются знаки чисел, принятых в АЛУ из оперативной памяти. Для отрицательных чисел осуществляются преобразования [A]о — [A]п или [A]д — [A]п (см. раздел 1.3). После этого выполняется операция умножения чисел в прямых кодах. Этот способ не требует дополнительных затрат времени, если используется обратный код. 2-й способ. Операнды из оперативной памяти поступают в АЛУ в дополнительном коде и без всяких промежуточных преобразований выполняется операция умножения по алгоритму для прямых кодов, а после окончания умножения выполняется, если необходимо, коррекция.
Рассмотрим возможные варианты знаков сомножителей и необходимую в этих случаях коррекцию результата. Итак выполняется операция С=А*В; |A|<1; |B|<1; A≠0; B≠0. Напомним, что операция умножения в прямых кодах производится над модулями сомножителей, ЗНС= М2(ЗНА,ЗНВ) (1.15) 1) A>0; B>0; |C|=|A|*|B| — результат правильный. 2) A<0; B>0; при использовании алгоритма умножения в прямых кодах вычислется псевдопроизведение модулей: |С|`= [-|A|]д*|B| = (1-|A|)*|B| = |B| - |A|*|B| = |B|-|C|; Чтобы найти правильное значение модуля произведения нужно выполнить следующую коррекцию: C``=|C|`-|B|=C`+[-|B|]д=|B|-|A|*|B|+(1-|B|);c C``=1-|A|*|B|= [-|C|]д, cледовательно, поскольку произведение отрицательно, то после коррекции получается модуль произведения в дополнительном коде. После вычисления ЗНС по выражению (1.15) результат заносится в оперативную память без преобразований. Следовательно, время умножения в прямых кодах увеличивается на время одного сложения. 3) A>0; B<0; Этот случай аналогичен предыдущему. |C|` = |A| * [-|B|]д = |A| * (1 - |B|) = |A| - |A| * |B| = |A| - |C| Очевидно, что после умножения должна быть выполнена следующая коррекция C``=C`+[-|A|]д= |A|-|A|*|B|+(1-|A|) = 1 - |A| * |B| C``=[-|C|]д, 4) A<0; B<0. В регистрах АЛУ оба числа представлены в дополнительном коде. Вычисляем псевдопроизведение, как и в случаях 2) и 3). |C|`=[-|А|]д*[-|B|]д= (1-|A|)*(1-|B|); |C|`= 1-|A|-|B| +|A|*|B| = 1-|A|-|B|+|C|. (1.16) Так как по условию выполняются операции над числами, модуль которых меньше единицы, то ``1`` в выражении (1.16) выйдет за пределы разрядной сетки. Следовательно, это выражение примет вид |C|`= -|A| - |B| + |C| Выполним коррекцию. Будем находить |C|. |C|=|C|`+|B|+|A| Следовательно для получения правильного значения произведения необходимо произвести коррекцию в виде двух сложений. Итак, анализируя все рассмотренные варианты, можно сделать вывод, что при этом способе в среднем необходимо для коррекции одно дополнительное сложение. Поэтому среднее время умножения по 2-му способу
Tумн2 = Tумн.п.к. + tсл
Дата добавления: 2015-05-09; Просмотров: 1084; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |