Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 49
Текст из файла (страница 49)
Пусть, например, необходимо синтезировать арифметическое устройство, реализующее четырехместную операцию суммирования. В зависимости от выбора алгоритма, реализующего это задание, получаем определенную блок-схему синтезируемого устройства, характеризующуюся аппаратурными затратами и быстродействием. В данном случае можно предложить, например, три варианта алгоритма.
1-й вариант. Суммируем два первых числа, к полученной сумме прибавляем третье число и к вновь полученной сумме прибавляем последнее число. Этот вариант алгоритма характеризуется временем выполнения операции т1 и аппаратурными затратами в виде одного сумматора, четырех регистров, устройства управления и необходимых каналов связи. Этому алгоритму соответствует блоксхема, изображенная на рис. 4.7, а. 2-й в а ри а нт.
Суммируем одновременно первое число со вторым, третье — с четвертым, результаты записываем соответственно в первый и третий регистры, затем суммируем их на первом сумматоре. Окончательный результат записываем в первом регистре. Этот вариант выполнения задания А характеризуется временем выполнения тт и аппаратурными затратами, представленными на блок-схеме этого варианта (рис.
4.7, б). 3-й вариант. Суммируем первые два числа на одном сумматоре, вторые два — на втором сумматоре, полученные суммы— на третьем сумматоре, результат записываем в первый регистр. Этот вариант характеризуется временем выполнения операции тз и аппаратурными затратами, приведенными на рис. 4.7, в. Тот или иной вариант алгоритма, реализующего задание А, выбирается исходя из конкретных ограничений на аппаратурные затраты и на время выполнения заданных операций. Каждая висячая вершина дерева поиска оценивается временем выполнения данного преобразования и сложностью аппаратуры (сложностью операционного и управляющего автоматов).
Сложность операционного автомата оценивается непосредственным подсчетом аппаратурных затрат. Сложность управляющего автомата можно оценить с помощью понятия производной от модели. На абстрактном этапе решается залача минимизации объема памяти автомата. На этапе кодирования (размещения) внутренних состояний автомата каждому внутреннему состоянию авто- е Рис.
4.7 мата сопоставляется код, т. е. определенная совокупность состояний (значений) элементов памяти. В результате выполнения двух рассмотренных этапов составляют системы выходных функций и функций возбуждения автомата — строят автоматный оператор. После построения автоматного оператора переходят к структурному синтезу. Н. Этап структурного синтеза автомата. Этап структурного синтеза автомата заключается в построении из заданных элементов логической (функциональной) схемы автомата, реализующей полученный автоматный оператор. Более подробно структурный синтез рассмотрим ниже. 34.3.
Алгоритмический этвц цраектираваиия Проектирование автоматного оператора заключается в построении автоматного отображения по заданному словесному описанию, включающему цель проектирования, назначение синтезируемого автомата и свойства поведения (функционирования) управляемого 84.3. Алгоритмический этап проектирования 272 Гл. 4.
Теория формальных грамматик и автоматов 273 Лед Рз Лед Рз Рис. 4.8 объекта, в контуре, с которым проектируемый автомат реализуех поставленную цель. Автоматное отображение, как правило, задают в виде графа переходов. Граф переходил — это граф сх = (Ъ", (Х, г')), каждая вершина которого взаимно однозначно соответствует внутреннему состоянию автомата, и если из состояния 51 автомат переходих в состоЯние Ят, то соохвехствУющие им веРшины и1, и соединЯ- ются дугой (и;, и ) б с(, взвешенной парой векторов (Х, г'), при которых этот переход осуществляется. На алгоритмическом этапе неформально заданная информация преобразуется в формальную систему в виде авхомахного оператора. При этом используется принцип аналогий. Формально этот переход может быть основан на применении грамматик, в которых правила подсхановки формализуют данные свойства управляемого объекта. В реэульхахе применения грамматик порождаются композиции графов переходов, удовлетворяющие заданному словесному описанию.
Эта композиция часто предсхавляет собой двухуровневую иерархию. Первый уровень представляех собой графы переходов, реакцией кохорых является непосредственно управляющее воздействие на управляемый объект. Второй уровень представляет собой граф переходов, реакция которого соответствует возбуждению инициальных вершин графов первого уровня. Рассмотрим построение графов переходов автоматов, реализующих устройства вычислительной техники и промышленной автоматики.
Пусть аадан операкнонный автомат в виде арифметического устройства последовательного действия, изобравеиного на рис. 4.8. Это устройство содервнт четыре регистра: Р1, РЗ, Р9, Р4, и одноразрядный сумматор коыбинапиониого типа, которые свяваны менку собой соединительными каналамн и управляеыыыи вентилями. Четырекраарядные числа представлякяся в устройстве в двоичном коде 8421. Синтеанруем автомат, упрввляюший вычислением мантиссы частного. До выполнения операпии делимое а находится в регистре Р1, делитель Ь вЂ” в регистре Рл, числа а и Ь нормализованы, а састное формируется в регистре РЗ.
При выполнении оперении деления вычитание заменяем словеннем в дополнительном коде и испольауеы следуюший алгоритм. 1. Вычитаем в дополнительном коде содервиыое регистра РЯ(Ь) из содервиыого регистра Р1(о), одновременно переписывая содервиыое регистра Р1 в репютр Р4. 2. Если а — Ь > О, то выполняем и. 3, в противном случае — и, 4. 3. Разность а — Ь записываем в регистр Р1, регистр Р4 устанавливаем в "нуль", а в регистр Р9 ааписываеы 1, сдвигаем на один разряд вправо делитель, регистр результата — влево и переходим к д. 5. 4.
Записываем содервиыое регистра Р4 в регистр Р1, в регистр РЗ записываем О, сдвигаем на один разряд делитель вправо, регистр результата — влево и переходим к и. 5 5. Если и. 1 был выполнен менее пяти рав, то переходим к п. 1, в противном случае — к и. б. б. Конек (в общем случае адесь осушествляется передача управления в блок иорыализалии частного). Для простоты считаем, что в регистр РЗ предварительно записан код нуля.
Зная операционный автомах и реализуемый алгоритм, составляем временную диаграмму функционирования управляющего автомата, которая представляет собой алгоритм выполнения данной операции в терминах управляющих точек — микраопераций, Каждой микрооперации соответствует выходной канал управляющего автомата. Отсюда число выходных каналов синхезируемого автомата равно числу всех микроопераций. Мновество микрооперакий рассматриваемого устройства таково: СВР!— сдвиг регистра Р1; Сдрд — сдвиг регистра Рй ПСВПЗ вЂ” правый сдвиг регистра РЗ; ЛСЭРЗ вЂ” левый сдвиг регистра РЗ; СЗР4 — сдвиг регистра Р4 (наличие репютра Р4 позволяет ие производить восстановления остатка); ПК1— прямой код содервимого регистра Р1; ПКЗ вЂ” прямой код содервимого регистра Рй, ОК1 — обратный код содервимого регистра Р1 ОК8 — обратный код содервимого регистра Р2; ВхР1 — вход репютра Р1; ВхРЛ вЂ” вход регистра Рй, У "О "Р1 — установка регистра Р1 в "нуль"; ВхЛРЗ вЂ” вход регистра РЗ слева; ВхПРЗ вЂ” вход регистра РЗ справа; ЦР1 — пикк регистра Р1; ЦРЗ— дякл регистра Рз; +1 Я вЂ” подача едиииды в пень переноса сумматора; Д4— рабата с векторами длйны 4; ДЗ вЂ” работа с вектораьш длины 5; Дб — работа с вектораын длины 6; Д7 — работа с вектораыи длины 7; Р4-ь Р1 — передача содервимого регистра Р4 в регистр Р1.
Строка временной диаграммы взаимно однозначно соответствует микрооперации. Множество микроопераций, выполняемых одновременно, называется микрокомандой, а множество последовательностей микрокоманд, соотвехствующее выполняемой операции — микропрограммой. Каждая микропрограмма взаимно однозначно соответствует значению входного вектора Х. Следовательно, число различных значений входного вектора Х равно числу выполняемых 275 нсел Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
