ЗНАЕТЕ ЛИ ВЫ?

Алгоритмы реализации арифметических действий с операндами, представленными в форме с фиксированной запятой



 

 

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

 

 

Регистр SR

 

Накапливающий сумматор АС

 

Рис\ 11.1\

В устройство входят:

накапливающий сумматор АС, включающий:

накапливающий регистр АС и параллельный сумматор ;

запоминающий регистр SR;

регистр множителя-частного MQ;

n-разрядный вспомогательный регистр сдвига LR;

6-разрядный регистр RG;

счетчик сдвигов SC;

двухбитовый регистр кода процедуры OPCODE;

однобитовые регистры: SI, Т, ADOV, DVOV.

Все однобитовые регистры, т.е. триггера, чаще всего объединяются в один статусный регистр.

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

В n-разрядных регистрах AC, SR, MQ старший, n-ый, разряд S выделен под знак числа. Остальные n - 1 разряды этих регистров отведены для представления значения числа и обозначаются как AC(M), SR(M), MQ(M). Разряд AC(Q) используется в одном из алгоритмов деления.

В зависимости от структуры регистров АС и MQ можно прямой код содержимого этих регистров преобразовывать в дополнительный или же в обратный код и выполнять также соответствующую обратную процедуру. Возможные варианты структур регистров с такими характеристиками приведены на рис.16а и 16б в разделе 4.

При вычитании содержимого регистра SR из содержимого регистра АС вычитаемое может представляться в дополнительном коде непосредственно на входах параллельного сумматора . Структура одного разряда такого сумматора выглядит следующим образом:

 

SR(i)

 

 

SM S AC(i)

 

P Pi

Pi-1

Сложение

Вычитание

AC(i)

Рис. 11.2\

В младшем разряде сумматора на SM вместо сигнала Pi-1 поступает сигнал "Вычитание", если алгебраическое сложение выполняется в дополнительном коде. Таким образм, параллельный сумматор такой конфигурации позволяет выполнять не только процедуру сложения, но и процедуру вычитания из содержимого регистра АС содержимое регистра SR без предварительного представления последнего в дополнительном коде.

Регистры АС и MQ объединены в один так называемый "касрегистр" для процедуры совместного сдвига их содержимого вправо или влево. Сдвигается содержимое всех разрядов, кроме знакового, т.е. разряды AC(M) и MQ(M). Причем, таким образом, чтобы при каждом таком сдвиге содержимое очередного младшего, 0-го, разряда АС(М) попадало в старший, (n -1)-ый разряд MQ(M) и наоборот. Процедуры сдвига используются при умножении и делении.

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

 

Сложение и вычитание

 

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

Таким образом, при сложении: [AC] + [SR] AC, а при вычитании:

[AC] + [SR] AC. В соответствующем алгоритме можно учесть, отмеченный ранее способ организации процедуры вычитания при помощи параллельного сумматора, включенного в состав АУ, но можно и не использовать эту возможность. Рассмотрим последний вариант как более рациональный в данном случае.

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

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

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

1. Если код процедуры соответствовал вычитанию, то знак операнда, размещенного в регистре SR, изменяется, т.е. выполняется процедура

инвертирования: [SR(S)].

2. Если AC(S) = SR(S), то 1 SI, иначе 0 SI.

3. Если AC(S) = 1, то AC(M) := [AC(M)] + 1, т.е представляется в допол-нительном коде.

4. Если SR(S) = 1, то SR(M) := [SR(M)] + 1.

После инициализации выполняется процедура самого алгебраического сложения: AC:= [AC] add2 [SR]\

5. Если при [SI] = 1 и после сложения AC(S) = SR(S), то переход к пункту 7, иначе вырабатывается сигнал переполнения: ADOV = 1, т.е. 1 ADOV и переход к пункту 9.

6. Если [SI] = 0, то переход к пункту 7.

7. Если значащая часть результата равна 0, т.е. AC(M) = 0, то в знаковый бит регистра АС засылается 0: 0 AC(S) и переход к пункту 9.

8. Если AC(S) =1, то результат получился в дополнительном коде и его преобразуют в прямой код: AC(M) := [AC(M)] + 1\

9. Конец процедуры алгебраического сложения.

Граф-схема этого варианта алгоритма алгебраического сложения приведена на рис.11.3.

 

Умножение

 

При умножении [SR] [MQ] касрегистр {AC-MQ}.

Умножение можно выполнять с анализом одного младшего бита множителя MQ(0) или двух младших битов множителя MQ(1,0).

Процедура инициализации умножения заключается в следующем.

1. Если один из операндов равен 0, то результату умножения при-сваивается значение 0 и тем самым процедура умножения заканчивается:

0 MQ, 0 AC\

2. Если у операндов одинаковые знаки, то результату присваивается положительный знак, т.е.0 AC(S), и 0 MQ(S), 0 SR(S)\

3. Если у операндов разные знаки, то результату присваивается отрицательный знак, т.е 0 AC(S) и 1 MQ(S), 0 SR(S)\

4. Обнуляется регистр АС: 0 AC(M).

Как уже отмечалось, при умножении чисел множимое из регистра SR умножается на множитель из регистра MQ, а произведение помещается в "касрегистр", образованный из регистров АС и MQ. В регистре АС находится старшая часть произведения, а в регистре MQ - младшая часть. Множимое остается в регистре SR, а множитель в регистре MQ теряется.

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

Перед началом процедуры умножения в счетчик SС записывается число

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

На каждом элементарном шаге умножения выполняются следующие действия.

1. Если MQ(0) = 0, то содержимое касрегистра {AС(M)-MQ(M)} сдвигается вправо на один разряд: [AC(M)-MQ(M)]\

2. Если MQ(0) = 1, то содержимое регистра SR складывается с содержимым регистра АС: AC := [AC] + [SR], после чего содержимое касрегистра

{AС(M)-MQ(M)} сдвигается вправо на один разряд.

3. В конце каждого элементарного шага вычитываетя 1 из содержимого счетчика SC, после чего проверяется равно ли 0 содержимое SС, если да, то процедура умножения заканчивается. В противном случае элементарный шаг повторяется.

4. Если по окончании умножения содержимое AС(M) не равно 0 вы-рабатывается сигнал переполнения: 1 ADOV\

Теперь рассмотрим вариант умножения с анализом двух младших разрядов множителя MQ(1,0). Граф-схема соответствующего алгоритма приведена на рис.11.4.

В связи с тем, что в этом случае в процессе выполнения операции умножения на каждом цикле операции анализируется сразу два младших разряда множителя, то таких циклов понадобится (n-1)/2. Это число циклов записывается в счетчик SС. При обнулении содержимого счетчика SС процедура умножения останавливается. В конце каждого цикла производится одновременный сдвиг на два разряда вправо содержимого касрегистра {AС(M)-MQ(M)}. Обозначим эту процедуру условно как ПС. Очевидно, что и в этом случае произведение будет сформировано в разрядной сетке, первоначально отведенной для множителя, т.е. в регитре MQ.

В зависимости от результата анализа разрядов MQ(1,0) предусматриваются следующие действия.

1. Если [MQ(1,0)] = 00= то выполняются только процедуры: ПС и SC = SC-1.

2. Если [MQ(1,0)] = 01, то последовательно выполняются процедуры:

AC := [AC] + [SR], GC и SC = SC-1.

После каждого выполнения процедуры AC := [AC] + [SR] проверяется равно ли 0 содержимое AC(S)! Если нет, то выполняется процедура 1 ADOV и выполнение арифметического действия прекращается.

3. Если [MQ(1,0)] = 10, то выполняются процедуры: сдвиг множимого влево на 1 разряд, т.е. умножение его на два, потом AC := [AC] + [SR], GC и

SC = SC _ 1.

Перед сдвигом множимого, т.е. перед процедурой [SR], проверяется равно ли содержимое разряда SR(n-1) единице, если да, то выполняется процедура 1 ADOV и выполнение арифметического действия прекращается.

4. Если [MQ(1,0)] = 11, то выполняется три раза процедура AC := [AC] + [SR] потом ПС и SC = SC _ 1.

Иногда процедуру трехкратного сложения заменяют однократным вычитанием: AC := [AC] - [SR].

5. Когда [SC] = 0 - операция умножения заканчивается.

Как и в предыдущем случае если содержимое АС(М) после окончания процедуры умножения не равно нулю вырабатывается сигнал переполнения:

1 ADOV.

При умножении и делении необходимо бывает выполнить процедуру AC := [AC] _ [SR]. Как уже отмечалось, в этом случае операнд, размещенный в регистре SR, представляется в дополнительном коде непосредственно на входе сумматора, а не в самом регистре SR. Для этого на входе сумматора предусматривается специальная схема управления.

 

Деление

 

Рассмотрим четыре варианта алгоритма деления. Первые два требуют выравнивания левого края делителя с левым краем делимого. При выполнении этих двух алгоритмов делимое загружается в регистр АС, а делитель в регистр SR регистр MQ обнуляется, частное формируется в регистре MQ:

[{AC-MQ}] / [SR] MQ, а остаток в АС. Делитель после выполнения операции остается в регистре SR, а делимое теряется.

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

1. Если делимое равно 0, то результату присваивается значение 0: 0 MQ и тем самым процедура деления заканчивается.

2. Если делитель равен 0, то вырабатывается сигнал ошибки: 1 DVOV, результату присваивается значение 0: 0 MQ, и тем самым процедура деления заканчивается.

3. Если делимое меньше делителя, то вырабатывается сигнал ошибки:

1 DVOV и процедура деления заканчивается: 0 MQ и 0 AC(S)\

4. Если у операндов одинаковые знаки, то результату присваивается положительнй знак: 0 MQ(S), 0 AC(S), 0 SR(S)\

5. Если у операндов разные знаки, то результату присваивается отрицательный знак: 1 MQ(S), 0 AC(S), 0 SR(S)\

В первых двух вариантах алгоритма деления инициализация завершается процедурой выравнивания.

Выравнивание левого края делителя по отношению к левому краю делимого выполняется путем сдвига влево содержимого SR(M). Тем самым "совмещаются" старшие единицы делимого и делителя. Если число сдвигов было равно, например, m, то число M = m + 1 записывается в счетчик SC, т.е нужно будет повторить М раз элементарные шаги деления.

Рассмотрим вначале эти два варианта алгоритма деления.

На каждом элементарном шаге деления с восстановлением остатка (первый вариант алгоритма) выполняются следующие действия.

1. AC := [AC] _ [SR].

2. Если [AC] < 0= то переход к пункту 3, иначе переход к пункту 4.

3. AC := [AC] + [SR] и сдвиг содержимого касрегистра влево на один разряд: [AC(M) - MQ(M)], потом MQ(0) := 0, далее переход к пункту 5.

4. Сдвиг содержимого касрегистра влево на один разряд и MQ(0) := 1.

5. SC := SC - 1. Если [SC] 0= то переход к пункту 1, иначе переход к пункту 6.

6. Выравнивание остатка: сдвиг содержимого AC(M) вправо на М разрядов.

7. Конец процедуры деления.

Граф-схема этого алгоритма приведена на рис. 11.5.

При делении без восстановления остатка (второй вариант алгоритма) изменяется только пункт 3:

3. Сдвиг содержимого касрегистра влево на один разряд и MQ(0) := 0, далее AC := [AC] + [SR], SC := SC _ 1. Если [SC] 0, то переход к пункту 2, иначе переход к пункту 6.

Процедура выравнивания левого края делителя, алгоритм которой приведен на рис. 11.8, очень часто получается достаточно длительной. Поэтому ускорение самой процедуры деления за счет уменьшения числа элементарных шагов деления не всегда уменьшает суммарное время, необходимое для выполнения всего алгоритма деления. В связи с этим используют также алгоритмы деления, не требующие процедуры выравнивания. Возможные варианты таких алгоритмов приведены на рис. 11.6 и 11.7. Разряд AC(Q) накапливающего сумматора АС используется только в последнем из этих алгоритмов, в котором учитывается специфика структуры используемого в АУ накапливающего сумматора. Этот алгоритм позволяет минимизировать аппаратуру описанного АУ, т.к. не требует применения регистров LR, SC1, T, которые используются в других вариантах алгоритма деления, и упрощает процедуру передачи информации из регистра MQ в регистр АС.

 

[AC] [SR] AC

 

Рис. 11.3. Алгоритм алгебраического сложения чисел в форме с фиксированной запятой.

 

 

[AC] [SR] AC

 

Рис. 11.3а. Алгоритм алгебраического сложения чисел в форме с фиксированной запятой.

 

 

Рис. 11.4. Умножение операндов с фиксированной запятой (вариант 2)

C:= A / B или MQ := {AC-MQ} / [SR], остаток в АС

 

 

Рис. 11.5. Алгоритм деления (вариант 1) операндов с фиксированной запятой с восстановлением остатка.

A / B = C : [{AC-MQ}] / [SR] MQ, остаток в АС

 

 

Рис. 11.6. Деление операндов с фиксированной запятой.

(вариант 3, не требует процедуры выравнивания левого края делителя)

A / B = C : [{AC-MQ}] / [SR] MQ, остаток в АС

 

Рис. 11.7. Деление операндов с фиксированной запятой.

(вариант 4, не требует процедуры выравнивания левого края делителя)

Рис. 11.8. Процедура выравнивания левого края делителя

(дополнение к алгоритму, приведенному на рис. 11.5.)

 





Последнее изменение этой страницы: 2016-06-23; Нарушение авторского права страницы

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.238.107.166 (0.013 с.)