Лекции по дисциплине «Теория вычислительных процессов» (стр. 3 )

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

Полученное выражение можно представить в виде схемы Горнера для вычисления полиномов.

С=(((...((О+А+Аbn)2-1+Abn-1)2-1+...+Abn-i)2-i+...+Ab2)2-1+Ab1)2-1

Это выражение может быть сведено к n-кратному выполнению цикла:

Ci+1=(Ci+Abn-i)2-1 при начальных i=0, Со=0.

В каждом цикле множимое либо добавляется к СЧП (если bi=1), либо нет (bi=0), после чего сумма умножается на 2-1, т. е. сдвигается на один разряд вправо. После окончания n-го цикла образуется искомое произведение, т. е. Сn=С=АВ.

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

Реализация данного способа требует 2n разрядного сумматора. Однако, если дополнительные разряды сумматора исключить, то произведение будет вычисляться с тем же количеством разрядом, что и сомножители. Однако для округления результата желательно удлинить сумматор на один дополнительный разряд, чтобы после вычисления произведения прибавить к дополнительному разряду единицу и вывести результат без дополнительного разряда. Количество разрядов сумматора может быть уменьшенного вдвое также при вычислении полноразрядного произведения, если использовать освобождающиеся разряды регистра множителя, соединив при этом младший разряд регистра сумматора со старшим разрядом регистра множителя и объединив их в общий сдвиговый регистр.

2) Умножение младшими разрядами множителя со сдвигом множества влево.

Выражение представим в виде:

С=2-n(Abn+2Abn-1+...+2iAbn-i+...+2n-1Abi).

Вычисление этого выражения сводится к кратному выполнению цикла:

Сi+1=Ci+Aibn-i, где Ai=2ai-1, при начальных значениях i=0, Co=0, Ао=А.

В каждом цикле умножения множимое сдвигается на один разряд влево и либо прибавляется к СЧП (при bi-1), либо нет (bi=0).

3) Умножение старшими разрядами множителя со сдвигом СЧП влево:

Выражение преобразуем к виду:

С=2-(n+1) ((...(...((0+Abi)2+Ab2)2+...+Abi)2+...+Abn-1)2+Abn)2

При этом умножение сводится к n-кратному повторению цикла Сi+1=(Ci+Abi+1)2 с начальными значениями i=0, Co=0.

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

4) Умножение старшими разрядами множителя со сдвигом множимого вправо.

Выражение представим в виде

С=А2-1bi+A-2b2+...+A2-ibi+...+A2-nb и тогда вычисление произведения может быть сведено к n-кратному выполнению цикла:

Ai+1=Ai 2-1

Ci+1=Ci+Ai+1bi+1 при начальных i=0 Ао=А Со=0. Т. е. в каждом числе множимое сдвигается на один разряд вправо и в зависимости от значения управляющего разряда множителя либо прибавляется к СЧГ, либо нет.

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

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

1) В каждом цикле передачи множимого в СМ после которого будут пропадать его младшие разряды. Тогда при условии, что все n-k младших разрядов множимого равны 1, максимальная погрешность произведения составит:

Dmax=2-(n+k+1)-(2-(n+k+1)+2-(n+k+2))-...-(2-(n+k+1)+21-(n+k+2)+...+2-(n+k))=-2-(n+k)[(1-2-1)+(1-2-2)+...(1-2-(n+k))]=-2(n+k)[n-k-(1-2-(n-k))]=2-(n+k)(n-k-1)

2) После окончания умножения отбрасываются все к младших разрядом СЧП. Если все они равны 1, погрешность от этого составит

D2max=2-n(1-2-k)<2-n

Dmax<D2max

(n-k-1) 2-(n+k)<2-n

Отсюда число дополнительных разрядов К>Cog2(n-k-1)

Обе составляющих ошибки имеют отрицательный знак.

Анализ приведенных схем умножения показывает, что

1) Длительность процесса умножения по любой схеме составляет и циклов:

Ту=ntц

Однако длительность циклов в разных схемах неодинакова. Так, во 2 и 4 схемах tц=tсм, и учитывая, что tсм>tсов, эти схемы позволяют ускорить процесс выполнения операции умножения за счет совмещения операции сложения ЧП и сдвигов множимого.

2) По количеству оборудования предпочтение следует отдать первой, а потом 3 схеме. Однако, с учетом, что обычно требуется n-разрядный результат, схема 4 может быть также значительно упрощена.

3) Схемы 3 и 4 легче приспособить для выполнения операции деления.

4) Схемы 2 и 4 позволяют не устанавливать регистр СЧП в 0 перед выполнением следующей операции.

Отсюда можно заключить, что наиболее удобными для применения в ЭВМ являются 1 и 4 схемы умножения.

Деление чисел в ДК

Так же как и при умножении, возможны два пути:

1) Перевод операндов прямой код, получение частного обычным способом и перевод его в ДК перед записью в памяти.

2) Деление операндов в ДК с получением частного в требуемом виде.

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

1) Деление в процессе операции участвует всего лишь один раз, а дальше текущие остатки получаются автоматически;

2) Нетрудно организовать получение цифр ДК отрицательного частного непосредственно в процессе деления путем передачи знаковых цифр остатков в СМ в регистр частного.

Рассмотрим 4 возможных случая:

1) А>0; B>0; Y=A/B>0.

Деление производится как обычно.

2) А<0; B>0; Y=A/B<0

Ход деления обычный с учетом следующих особенностей.

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

Так как знак нулевого остатка имеет инверсное значение, то при продолжении деления обычно путем все другие остатки получаются также с инверсивными знаками. Поэтому, в регистр частного также будут записываться инверсные цифры и в конце деления в нем образуется обратный код отрицательного частного. Для округления результата и него надо вычесть единицу (n+1)-го разряда, а для перевода его в ДК к нему надо прибавить единицу n-й разряд. Тогда прибавление единицы в (n+1) разряд произведет суммарное действие округления и перевода ОК в ДК.

3) А>0; B<0; Y=A/B<0

Псевдознаковая цифра частного получается как обычно путем инверсии знака первого остатка, а для того, чтобы получить инверсные цифры частного, нужно брать их равными знаковым цифрам соответствующих остатков без инвертирования. В конце деления необходимо добавить к (n+1)-му разряду частного единицу для одновременного выполнения округления результата и перевода его в ДК.

4) А<0; B<0; Y=A/B>0.

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

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

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

Алгоритм деления чисел в ДК сводится к следующему.

На каждом шаге деления производится алгебраическое сложение кода текущего остатка и кода делителя, которому присваивается знак, противоположный знаку текущего остатка. При этом, если знаки вновь полученного остатка и делителя одинаковы, то в текущий разряд частного записывается единица, в противном случае - ноль. После этого вновь полученный остаток и частное сдвигаются на один разряд влево. Деление прекращается после вычисления (n+1) разряда частного, в который добавляется единица округления автоматически и код модуля частного соответствует его знаку.

Методы ускорения операции умножения

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

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

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

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

Другим способом является одновременное умножение на два разряда.

Для младшей пары разрядов при умножении с младших разрядов возможны следующие комбинации единиц и нулей в разрядах: 00; 01; 10; 11.

Для первой комбинации не производится ни сложение, ни вычитание, для второй - суммирование множимого, для третьей суммирование сдвинутого на один разряд влево множимого, для четвертой - одно вычитание множимого и одно сложение после сдвига множимого на 2 разряда.

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

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

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