|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[205] Выходные значения этой схемы поступают на входы регистров, но не воспринимаются ими до следующего тактового импульса. Схема, изображённая на рис. 29.17, называется устройством побитового сложения (bit-serial adder). Чтобы схема работала правильно, период между импульсами должен быть не меньше задержки сумматора (иначе к следующему тику не будет готов выходной бит переноса). Значения на входы подаются с интервалом в один период. В момент первого тактового импульса на входы сумматора подаются значения ао, &о и 0 (рис. 29.17 (а); мы предполагаем, в начальном состоянии на выходе регистра имеется значение 0). На выходе через некоторое время появляются бит суммы so (который выдаётся наружу) и бит переноса с\. Бит переноса поступает (по проводу) на вход регистра, но лишь после второго импульса появляется на выходе регистра. Вместе со значениями а\ и Ь\ он даёт на выходе s\ и с2 (рис. 29.17(b)) и т. д. Так продолжается, пока не будут обработаны все разряды слагаемых, после чего на входы подаются нули (ап = 0, Ьп = 0), и на выход подаётся старший разряд суммы (совпадающий с последним битом переноса; sn = сп) см. рис. 29.17(e). 29.4.2.Характеристики схемы Как мы говорили, тактовая частота зависит от задержки в схеме из функциональных элементов (в данном случае - задержки в элементе суммирования FA), поскольку все вычисления должны закончиться до начала следующего тактового импульса. В данном случае сумматор имеет глубину 0(1), а для получения всех выходов необходимо га+1 периодов, так что общее время работы составляет (п + 1)0(1) = 0(га). Размер схемы равен 0(1). 29.4.3.Каскадное сложение и побитовое сложение Каскадный сумматор можно рассматривать как развёрнутую схему устройства побитового сложения: теперь за каждый период между импульсами отвечает свой сумматор. Такое развёртывание, заменяющее время пространством, можно сделать для любой тактированной схемы, соединяя несколько экзмепляров схемы (столько, сколько тактов требует её работа). Конечно, при этом увеличивается число элементов - зато не нужны синхронизирующие импульсы от тактового генератора. Такая схема на практике работает несколько быстрее, поскольку в тактированной схеме на каждом такте нужно оставлять некоторый запас времени (чтобы вычисления успели произойти), а после развёртывания выходы каскада сразу же попадают на входы следующего, ничего не ожидая. 29.4.4.Одномерный умножитель Матричный умножитель, рассмотренный в разделе 29.3, имеет размер ©(га2). В этом разделе мы рассмотрим два тактированных умножителя, использующих одномерный массив элементов (размера в (га)) вместо двумерного. Более быстный из них имеет время работы в (га) (как и матричный умножитель) Оба этих умножителя используют алгоритм, который в Америке называют русским народным алгоритмом умножения (Russian peasants algorithm). Он показан на рис. 29.18 (а). Сомножители а и Ь записываются рядом, и под каждым из них пишется колонка чисел. В левой колонке число на каждом шаге делится на 2 (остаток отбрасывается); в правой - умножается на 2. Так продолжается до тех пор, пока в левой колонке не будет 1. После этого складываются числа из правой колонки, стоящие напротив нечётных чисел в левой. На первый взгляд этот алгоритм кажется удивительным, но он становится понятным, если записать все числа в двоичной системе: при этом становится ясным, что он представляет собой вариант умножения в столбик. Строки, в которых слева появляется нечётное число, соответствуют единичным разрядам в а, их вклад в сумму есть умноженное на соответствующую степень двойки число Ь (см. рис. 29.18 (Ь)). Рис. 29.18 29.18 Умножение 19 на 29 с помощью русского народного алгоритма. В колонке а каждое следующее число получается из предыдущего делением на 2 (остаток отбрасывается), а в колонке Ъ -умножением на 2. Складываются числа из правой колонки, напротив которых стоят нечётные числа в левой (выделены серым цветом), (а) Сложение в десятичной системе. (Ь) То же в двоичной системе. 29.4.5.Простая реализация Простой вариант реализации русского народного алгоритма в виде тактированной схемы умножения га-битовых чисел показан на рис. 29.19 (а). В нём используется 2га групп по 3 регистра. Верхние регистры хранят биты сомножителя а, средние отвечают за сомножитель Ь, а в нижных постепенно формируется произведение р. Содержимое г-го а-регистра перед j-м шагом обозначается а\ , аналогично для Ь и р. Вместе все биты в а-регистрах образуют двоичную запись числа, которогое обозначется (по состоянию &(°) = Ъ и = 0. Поддерживается инвариант aU) . ьО) + ptt) = а-Ь(29.6) (см. упражнение 29.4-2). На j-m шаге производятся следующие действия: 1.Если а0 = 1 (т. е. а) нечётно), то p+1) = + &(•?), иначе р(з+1) - р(]) 2.Число а сдвигается вправо на одну позицию (делится на 2 с остатком): (j+i) { а\1 если 0 г 2га - 2 [ 0 если г = 2га - 1 3.Число Ь сдвигается влево на одну позицию (умножается на 2): (j+i) \ а\-\ если 1 i 2га - 1 [ 0 если i = О После га шагов получаем ап) = 0, поэтому инвариант гарантирует, что р(п) = а Ь. Наш алгоритм требует га шагов. Если на каждом шаге использовать для сложения каскадный сумматор, то каждый шаг занимает время О(га), поэтому общее время работы составляет 0(га2). Схема состоит из Зга регистров, каскадного сумматора размера О(га) и О (га) элементов, формирующих частичные произведения (операция AND над а0 и 6-битами). Общий размер схемы равен О (га). Рис. 29.19 29.19 Два одномерных умножителя. Показано умножение 5-битовых чисел а = 19 = (10011) на Ъ = 29 = (11101) и содержимое регистров перед каждым шагом; значащие биты выделены серым цветом, (а) Простой умножитель (время работы 0(п2)). На каждом шаге используется каскадный сумматор, поэтому интервал между тактами должен быть не меньше Q(n). (Ь) Быстрый умножитель, использующий сложение с запоминанием переносов. Каждый шаг требует времени 0(1). Всего требуется 2п - 1 = 9 шагов, показаны первые 5. (После этого остаются сложить и и v, для чего достаточно продолжить тот же процесс сложения с запоминанием переносов.) 29.4.6. Быстрая реализация Уменьшения времени работы можно добиться, используя вместо каскадного сложения сложение с запоминанием переносов (см. рис. 29.19 (Ь)). Теперь вместо трёх регистров на каждый разряд будут четыре; в двух из них по-прежнему хранятся цифры чисел а и Ь, а вместо числа р будт храниться два числа и и v, причём поддерживается инвариант а(з) . ь0) + и(Л + VU) = а 6едгао(29.7) так что роль р играет сумма и + v (см. упражнение 29.4-2). Вначале = г>(°) = 0. (Это соответствует использованию алгоритма |
Среды: 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 | ||