andrey

Путь к Файлу: /Организация ЭВМ / Лекции ВМ-91 / Глава2.4 (Мельниченко, Гапонов).doc

Ознакомиться или скачать весь учебный материал данного пользователя
Скачиваний:   0
Пользователь:   andrey
Добавлен:   13.01.2015
Размер:   673.0 КБ
СКАЧАТЬ

Министерство Образования Российской  Федерации

Хабаровский Государственный Технический Университет

 

 

 

 

 

Лекция

«Арифметические схемы»

 

 

 

Выполнили: ст. гр. ВМ-91

                        Гапонов Е.В.

                        Мельниченко Д.

Проверил: Бурдинский И.Н.

 

 

 

 

 

Хабаровск

2004

2.4    Арифметические схемы

Мы используем три разновидности сумматоров: сумматоры с цепным переносом, сумматоры условной суммы, и сумматоры с параллельным переносом.

2.4.1    Сумматоры с цепью переноса

Полный сумматор- схема со входами а, b, с и выходами c',s удовлетворяющими

Глава2.4 (Мельниченко, Гапонов)

(c' s) = a + b + c.

 Рисунок 2.11 Схема n-битного сумматора с цепным переносом CCA

. Таблица 2.5 Функциональность полусумматора.

а    с

 

c'     s

 

0    0

 

0     0

 

0    1

 

0     1

 

1    0

 

0     1

 

1    1

 

1     0

 

 

Полные сумматоры осуществляют один шаг основного алгоритма сложения для двоичных чисел, как показано в таблице 2.3 раздела 2.2. Схема на рисунке 2.2 раздела 2.1 – полный сумматор со следующими ценой и задержкой

CFA = 2*Cxor + 2*Cand + Cor

DFA = Dxor + max{Dxor, Dand+Dor}.

n-adder (сумматор) – схема со входами a[n— 1 : 0], b[n— 1 : 0], сin и выходами s[n: 0] удовлетворяющими

(а) + (b)+cin = (s).

Наиболее очевидная конструкция сумматора непосредственно осуществляет основной алгоритм сложения: каскадированием n полных сумматоров, как показано на рисунке 2.11, получаются carry chain adders (сумматоры с цепным переносом). Такие сумматоры дешевые, но медленные, следовательно, мы их не используем.

Полусумматор (half adder) – схема со входами a,c и выходами c', s удовлетворяющими

(c' s) = a + c.

Поведение полусумматора иллюстрируется в таблице 2.5. Поскольку мы имеем

Глава2.4 (Мельниченко, Гапонов)Глава2.4 (Мельниченко, Гапонов)

Рисунок 2.12 Схема полусумматора HA


Глава2.4 (Мельниченко, Гапонов)

Рисунок 2.13 Схема n-carry chain incrementer CCI (n-разрядный инкрементер с цепью переноса)

очевидная реализация пулусумматоров состоит из одного вентиля and и одного вентиля OR, как показано на рисунке 2.12.

n-incrementer – схема со входами a[n— 1 : 0], cin и выходами s[n : 0] удовлетворяющая

(a) + cin = (s).

Каскадируя n полусумматоров, как показано на рисунке 2.13 (b), получаем инкрементер с цепью переноса со следующей ценой и задержкой:

CCCI(n) = n*(Cxor+Cand)

DCCI(n) = (n-1)*Dand+max{Dxor, Dand}.

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

2.4.2    Сумматоры условной суммы

Простейшая конструкция сумматоров условной суммы показана на рисунке 2.14. Пусть m= [n/2] и k = [n/2] и запись

s[n:0]=s[n:m]s[m-1 :0],


Глава2.4 (Мельниченко, Гапонов)

 


Рисунок 2.14 Простейшая версия n-битного сумматора условной суммы; т = [n/2] и k=[n/2].

тогда

Глава2.4 (Мельниченко, Гапонов)

Таким образом, старшие биты суммы на рисунке 2.14 вычисляются дважды: биты суммы s°[n : m] для случая cm-1 = 0 и биты s1 [n : m] для случая cm-1 = 1. Окончательный выбор делается, как только cm-1 становится известен.

Эта конструкция не должна повторяться рекурсивно, поскольку уменьшение вдвое проблемного размера требует 3 копий аппаратуры для полуразмерной проблемы и мультиплексоров. Игнорируя мультиплексоры и приняв, что n = 2V – степень двойки, получаем для цены c(n) созданного этим способом n-adder оценку

с(n)  >3*c(n/2)

>3V-c(1) - 2v * log 3c(1)

=          nlog 3-c(l)  > n1.57-с(1)

Это слишком дорого.

Для инкрементеров же это смотрится лучше. Старшие биты суммы инкрементера

Глава2.4 (Мельниченко, Гапонов)

Это приводит к очень простой конструкции на рисунке 2. 15. Наш инкрементер будет создан путем использования инкрементеров с цепью переноса


Глава2.4 (Мельниченко, Гапонов)

 


Рисунок 2.15 n-битный инкрементер условной суммы; m= [n/2] и k= [n/2].

для решения подзадач размера k и m. Такой n-incrementer тогда имеет следующую цена и задержку

Cinc(n)    =   Ccci(m)+Ccci(k)+Cmux(k+1) Dinc(n)    =   Dcci(m)+Dmux.

Обратите внимание, что на рисунке 2.15 первоначальная проблема уменьшена до только двух проблем половинного размера от первоначальной проблемы. Таким образом, эта конструкция может быть применена рекурсивно с разумной ценой (смотри упражнение 2.1). Тогда получаем очень быстрый инкрементер условной суммы CSI (conditional sum incrementer).

Действительно, рекурсивная конструкция простых сумматоров условной суммы оказывается настолько дорогой поскольку непересекающиеся цепи используются для вычисления кандидатов старших бит суммы s°[n : m] и s1[n : m]. Этот недостаток может быть исправлен, если создать сумматоры, которые вычисляют и сумму, и сумму + 1 операндов a и b.

n-compound adder (n-составной сумматор)  – схема со входами a[n— 1 :0], b[n—1 : 0] и выходами s°[n : 0], s1[n : 0] удовлетворяющими

(s0)    =    (а) + (b) (s1)    =    (a) + (b) + 1.

Рекурсивная конструкция n-составных сумматоров показана на рисунке 2.16. Он станет полезен в rounders блоках вычислений с плавающей точкой. Обратите внимание, что только две копии аппаратуры используются для полуразмерной проблемы. Цена и задержка конструкции


Cadd2(1) = Cxor+Cxnor+Cand+Cor

Cadd2(n) = Cadd2(k)+Cadd2(m)+2*Cmux(k+1)

Dadd2(1) = max{Dxor, Dxnor, Dand, Dor}

Dadd2(n) = Dadd2(m) + Dmux(k+1)

 


Глава2.4 (Мельниченко, Гапонов)

 


Рисунок 2.16 n-составной сумматор add2(n);m= [n/2],k = [n/2]


Глава2.4 (Мельниченко, Гапонов)

 


Рисунок 2.17 Рекурсивное определение n-fold parallel prefix circuit функции о для четного n

2.4.3    Параллельные префиксные вычисления

Пусть о : M x M —> M ассоциативная бинарная функция, ее n-fold parallel prefix function (параллельная префиксная функция) PPo(n) : Mn -> Mn отображает n входов x1, ... , хn в n результатов y1, ... , yп с yi = x1 o ... o xi.

Рекурсивная конструкция эффективных схем параллельного префикса основана на схеме o-gates, показанной на рисунке 2.17 для случая четного n. Если n - нечетное, тогда реализуется PP0 (n — 1) конструкция на рисунка 2.17 и вычисляется уn-1 = Xn-1 о Уn-2 простейшим путем, используя один дополнительный o-gate.

Правильность конструкции может быть легко рассмотрена. Из


Глава2.4 (Мельниченко, Гапонов)

 


следует

 


Глава2.4 (Мельниченко, Гапонов)

Вычисление выходов


Глава2.4 (Мельниченко, Гапонов)

 


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

CPPo(1)            =          0

CPPo(n}            =          CPPo([n/2]) + (n-1)*C0

DPPo(1)            =          0

DPPo(n)            <=       DPP0([n/2]) + 2*D0.


2.4.4    Сумматоры параллельного переноса

Для a[n - 1 : 0], b[n - 1:0] и индексов i, j с i <= j определим pi,j(a,b) = 1 <-> (a[j:i])+(b[j:i]) = (1j-i+1)

Это случай, когда cj = ci-1, другими словами, когда перенос ci-1 - распространяется (propagated) от позиций i … j операндов до позиции j.  Аналогично, определим для 0 < i <=  j:

gi,j(a,b) = 1 <-> (a[j:i])+(b[j:i])>=(10j-i+1),

т.е., если позиции i … j операндов генерируют (generate) перенос cj независимо от ci-1. Таким образом, для i = 0, принимая во внимание cin , определим

g0,j(a,b,cin) = 1 <-> (a[j:0])+(b[j:0])+cin >= (10j-i+1).

В следующих вычислениях мы просто пишем gi,j и pi,j, соответственно. Очевидно, мы имеем


Глава2.4 (Мельниченко, Гапонов)

 


Предположим, что уже вычислены сигналы генерации и распространения для смежных интервалов индексов [i: j] и [j + 1 : k], где i <= j < k. Тогда сигналы для объединенного интервала [i: k] могут быть вычислены как


Глава2.4 (Мельниченко, Гапонов)

 


Очевидно, это вычисление может быть выполнено схемой на рисунке 2.18, которая берет входы (g1,p1) и (g2,p2) из M = {0,1}2 для выхода


Глава2.4 (Мельниченко, Гапонов)

 


Глава2.4 (Мельниченко, Гапонов)

 


Рисунок 2.18 Схема °, используемая в сумматорах параллельного переноса

Глава2.4 (Мельниченко, Гапонов)

Рисунок 2.19 Схема n-битного сумматора параллельного переноса

Простое упражнение показывает, что операция о, определенная таким образом - ассоциативная (подробнее смотри, например, [KP95]).

Следовательно, рисунок 2.18 может быть заменен на o-gate в схемах параллельного префикса предыдущего подраздела. Фишка этой конструкции в том, что i-й вывод параллельной префиксной схемы вычисляется

(Ci,Pi) = (gi,pi) ° ...° (g0,P0) = (gi,0,Pi,o) = (ci,Pi,o).

Из этого следует, что схема на рисунке 2.19 - сумматор. Он называется сумматор параллельного переноса.

Схема на рисунке 2.18 имеет цена 6 и задержку 4. Мы изменим вычисление выхода g, используя

Глава2.4 (Мельниченко, Гапонов)

Для цены и задержки операции о это дает

 

C0 = Cand + Cnand + Cnor + Cinv = 7

D0 = max{Dand, Dnand + max{Dnor, Dinv}} = 2.


Глава2.4 (Мельниченко, Гапонов)

 

Рисунок 2.20 Схема n-битного арифметического устройства AU

Цена и задержка всего сумматора CLA

ccla (n)    =   CPPo(n) + 2n • Cxor + (n+1)• Cand + Cor dcla (n)   =   Dppo (n) + 2 • Dxor + Dand + Dor.

2.4.5    Арифметический модуль

n-битный арифметический блок – схема со входами a[n - 1 :0], b[n— 1 :0], sub и выходами s[n : 0],neg,ovf. Он выполняет операции

Глава2.4 (Мельниченко, Гапонов)

Выходы суммы s удовлетворяют

Глава2.4 (Мельниченко, Гапонов)

Флаг ovf указывает, что [a] op [b] !€ (не принадлежит) Tn , тогда как neg указывает, что [a] op [b] < 0. Этот флаг должен быть верным даже при переполнении. С помощью этого флага, например, выполняются команды вида "переход, если a< b". В этом случае команда хочет знать знак a – b, даже если a - b не представляют из себя n бит.

Рисунок 2.20 показывает реализацию n-битного арифметического блока. Уравнение           

-[b] = Глава2.4 (Мельниченко, Гапонов) + 1

транслируется в

b’ = b Глава2.4 (Мельниченко, Гапонов) sub  и          Глава2.4 (Мельниченко, Гапонов).

Флаг neg – знаковый бит суммы [a] + [b] € Tn+1. По аргументации из конца раздела 2.2, желаемый флаг – сумма бит sn сложения

(an-1a) + (bn-1b)+Cin = (s[n+1:0]).

Глава2.4 (Мельниченко, Гапонов)

Он может быть вычислен как

 


По теореме 2.4, мы имеем

Глава2.4 (Мельниченко, Гапонов)

 

В сумматорах с ускоренным переносом, все биты переноса доступны, в то время как сумматоры условной суммы производят только финальный бит переноса cn-1. Так как наиболее значительный бит суммы равняется Глава2.4 (Мельниченко, Гапонов), переполнение может быть проверено как


Глава2.4 (Мельниченко, Гапонов)

Пусть add означает двоичный сумматор выбора; тогда цена и задержка арифметического модуля выражается как

СAU(п)   =   (n + 2) - cxor + Cadd(n) DAU(n)    =   3*Dxor + Dadd(n).

2.4.6    Устройство сдвига

Для строк a[n— 1 : 0] и натуральных чисел i € {0,... ,n— 1} мы рассматриваем функции

cls(a,i) =          (a[n-i-1]...a[0]a[n-1]...a[n-1])

crs(a,i) =          (a[i- 1] ...a[0]a[n- 1]...a[i])

lrs(a,i) =          (0ia[n-1]...a[i]).

Функция cls называется циклический сдвиг влево, функция crs называется циклический сдвиг вправо, и функция Irs называется логический сдвиг вправо. Очевидно, мы имеем

crs(a,i) = cls(a,n— i mod n).

Устройство циклического сдвига влево (n,i)-cyclic left shifter – схема со входами a[n - 1 : 0], входом выбора s € {0,1} и выходами r[n - 1 : 0] удовлетворяющими

Глава2.4 (Мельниченко, Гапонов)

Как показано на рисунке 2.21 такие сдвигающие устройства могут быть построены на n muxes.

Пусть n = 2m - степень двойки. n-cyclic left shifter – схема со входами a[n— 1 : 0], входами выбора b[m - 1 : 0] и выводами r[n - 1 : 0] удовлетворяющими

r = cls(a,(b)).

 

Глава2.4 (Мельниченко, Гапонов)

 


Рисунок 2.21 (n,i)-Cyclic left shifter (устройство циклического сдвига влево)

Глава2.4 (Мельниченко, Гапонов)

Рисунок 2,22 Схема n-cyclic left shifter CLS(n)

Глава2.4 (Мельниченко, Гапонов)

Рисунок 2.23 Схема n-cyclic right shifter CRS(n)

Глава2.4 (Мельниченко, Гапонов)

Рисунок 2.24 (n, i)-Logic right shifter (устройство логического сдвига вправо)

Такие сдвигающие устройства могут быть сформированы каскадированием (n, i)-cyclic left shifters для i € { 0, 1,2,4, ...,2m-1} как показано на рисунке 2.22.

Индукцией по i легко показать, что выход r(i) из (n,2i)-cyclic left shifter на рисунке 2.22 удовлетворяет

ri=cls(a,(b[i:0])).

Устройство циклического сдвига вправо  n-cyclic right shifter – схема со входами a[n—1 : 0], выбираемыми входами b[m— 1 : 0] и выходами r[n—1 : 0] удовлетворяющими

 

r = crs(a,(b}). 

 

Это может быть полученная из n-cyclic left shifter конструкция, показанная на рисунке 2.23. Она работает, поскольку

Глава2.4 (Мельниченко, Гапонов)

Устройство логического сдвига вправо  (n,i)-logic right shifter – схема со входами a[n— 1 : 0], входом выбора s € {0, 1} и выходами r[n— 1 : 0] удовлетворяющими

Глава2.4 (Мельниченко, Гапонов)

Оно может быть построено из n muxes, как показано на рисунке 2.24.

Пусть n = 2m степень двойки. n-logic right shifter – схема со входами a[n-1 : 0], входами выбора b[m -1:0] и выходами r[n-1 : 0] удовлетворяющими

r = lrs(a, (b)).

По аналогии с устройством циклического сдвига влево, n-logic right shifter может быть построен каскадированием (n,i)-logic right shifters для i € { 0, 1, 2, 4, . ..,2m-1}.

 

Наверх страницы

Внимание! Не забудьте ознакомиться с остальными документами данного пользователя!

Соседние файлы в текущем каталоге:

На сайте уже 21970 файлов общим размером 9.9 ГБ.

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

Не нашли нужный документ? Воспользуйтесь поиском по содержимому всех файлов сайта:



Каждый день, проснувшись по утру, заходи на obmendoc.ru

Товарищ, не ленись - делись файлами и новому учись!

Яндекс.Метрика