|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[201] сложение с предвычислением переносов (carry-lookahead addition), причем соответствующая схема также имеет размер в (га). Наконец, сложение с запоминанием переносов (carry-save addition) за время 0(1) сводит сложение трёх га-разрядных чисел к сложению га-разрядного и (га + 1)-разрядного чисел. Схема также имеет размер 0(га). 29.2.1. Каскадное сложение Неотрицательное целое число а записывается в двоичной системе как последовательностью га битов (ага-ъ an-2j • • • , ao)j причем га [lg(«+l)l и п-1 а = Е «г2*- г=0 При сложении по двум га-значным числам а = (ara-i, ап-2, ,ао) и Ь = (bn i, bn 2, , bo) строится (га + 1)-значное число s = (sn, sra 2,... , So), равное их сумме (пример на рис. 29.3). Рис. 29.3 29.3 При сложении 8-значных чисел а = (01011110) и Ь = (11010101) получается 9-значное число s = (100110011). В г-м столбце указаны г-е разряды чисел а, Ъ и s, а также бит переноса с,. Входной бит переноса со всегда равен 0. При сложении столбиком (справа налево) мы складываем в г-м разряде bi и входной бит переноса (carry-in bit) сг-. Младший разряд суммы записывается в г-ый разряд ответа (s8), а старший становится выходным битом переноса (carry-out bit) c8 i и используется при сложении в следующем разряде. В младший разряд ничего не переносится, поэтому со = 0. Последний перенос сп становится старшим разрядом суммы sn. Поскольку s4- = parity(сц, bi, сг), а сг 1 = majority(аг, 6г, сг), для каждого шага можно годится описанный выше сумматор. Таким образом, га-разрядный каскадный сумматор состоит из последовательно соединённых простых сумматоров FAq,FA\, ... ,FAn-\, так что выход c8 i сумматора FAi является входом для FAi+i. На входе со фиксировано значение 0, не зависящее от входов (см. рис. 29.4). Рис. 29.4 Каскадный сумматор для п = 8. Ромбик справа означает, что значение на входе фиксировано. Поскольку бит переноса проходит через все сумматоры, глубина каскадного сумматора равна га (а глубина элемента FAi равна г+1). Поэтому время работы составляет в (га). Размер схемы равен в (га). 29.2.2. Сложение с предвычислением переносов В каскадном сумматоре бит переноса сг- вычисляется в момент времени г. Значения аг- и Ьг-, однако, известны с самого начала. В некоторых случаях они определяют бит переноса сг-: •если аг- = Ь{ = 0, то сг- = 0 (перенос «поглощается»(kill)) •если аг- = Ьг- = 1, то сг- = 1 (перенос «порождается»(generate)) Однако если один из битов аг- и Ьг- равен 1, а другой 0, но c8 i существен; именно, •если аг- ф bi, то сг- = сг 1 (перенос распространяется (propagate)) Каждому разряду, следовательно, соответствует один из трёх типов переноса (carry statuses): k, (kill), g (generate) или p (propagate) (см. рис. 29.5). Этот тип известен заранее, что позволяет уменьшить время работы схемы сложения. Рис. 29.5 Выходной бит переноса и тип переноса сумматора FA,-i в зависимости от а, и 6,. Зная типы переноса для соседних сумматоров ((г - 1)-го и г-го), можно определить тип переноса для их соединения, считая c8 i входным битом, a c8 i - выходным: зная, что случается с битом переноса на каждом шаге, можно рассчитать, что произойдёт за два шага, то есть как зависит c8 i от c8 i. Если г-й разряд имеет тип к или g, то соединение имеет тот же тип переноса. Если же г-й разряд имеет тип переноса р, то тип переноса для соединения совпадает с типом (г - 1)-го разряда (см. рис. 29.6). Рис. 29.6 Тип переноса соединения двух сумматоров (таблица операции Сх)). Таблицу на рис. 29.6 можно рассматривать как определение операции (композиции типов переноса) на множестве {k, g, р} ; она будет обозначаться символом <g>. Эта операция ассоциативна (см. упражнение 29.2-2). С помощью этой операции тип переноса для некоторого участка числа выражается через типы переносов отдельных рязрядов. Обозначим через жг- тип переноса в г-м разряде. [ k,ifa8 i = 6г 1 = 0; g,ifa8 i = 6г 1 = 1;(29.3) p,ifa; i ф 6г 1. Тогда зависимость, скажем, бита с7 от с4 определяется композицией ж5 (g) Xq (g) ж7. Поскольку в нулевой разряд переноса от младших разрядов не поступает, условно положим жо = к. Тогда перенос на выходе г -го разряда определяется композицией xq <g> х\ <g> ... <g> xf. С{ = О, если композиция равна к, и с,- = 1, если композиция равна g. (Значение р для композиции невозможно, поскольку для этого все члены должны быть равна р, а это не так для жо-) Более формально это записывается так. Положим уо = к и определим У1,у2,---уп так: Другими словами, уо,...уп называются префиксами (prefixes) выражения жо®Ж1®.. .®хп. (Общая задача о параллельном вычислении префиксов рассмотрена в гл. 30). На рис. 29.7 показаны значения Xi и yi для примера рис. 29.3. Рис. 29.7 29.7. Значения х, и у, для примера рис. 29.3. Теперь сказанное выше запишется так: Лемма 29.1. При всех г = 0,1, 2,... , га: 1.Если yi = к, то Ci = 0. 2.Если yi = g, то Ci = 1 3.Случай yi = р невозможен. Доказательство. Индукция по г. При г = 0 по определению уо = жо = к и со = 0. Пусть утверждение леммы выполнено для г - 1. Возможны три случая. 1.Если yi = к, то либо Xi = к (и тогда сг- = 0), либо жг- = р и жг 1 = к. Тогда по предположению индукции c8 i = 0, а сг- = сг 1 (бит переноса сохраняется), поэтому и в этом случае сг- = 0. 2.Случай yi = g аналогичен. 3.Если yi = р, то обязательно жг- = р и = р, но последнее равенство невозможно по предположению индукции. Лемма доказана. Таким образом, вычисление битов переноса сг- сводится к вычислению префиксов yi. Оставшиеся действия выполняются за время 0(1) -достаточно подать биты переноса на входы сумматоров. 29.2.3. Вычисление типов переноса с помощью параллельной префиксной схемы Здесь мы рассмотрим схему, использующую возможность параллельных вычислений и позволяющую за время О (lgra) вычислить все типы переноса уг-. Она имеет размер О (га). Введём некоторые обозначения. При 0 г j га положим Уг = Xi <g) уг 1 = Ж0 <g> Xi <g) . . . ® Xi (29.3) В частности, [г, г] [г, j] = Xi 0 жг+1 <g) ... <g) Xi. Если 0 г < j /г га, то [i,fc] = [i,i-l]®[i,A;] (29.4) |
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | ||