04Глава 3 (561021)
Текст из файла
Глава 3. Структурный и абстрактный синтез устройств ВМ.
Структурный синтез операционных устройств ВМ. Операционное устройство ВМ можно представить состоящим как бы из двух частей — комбинационной и памяти. На входы комбинационной части поступают сигналы с выходов элементов памяти (триггеров) Q1, …, Qm, а также сигналы, приходящие по шинам управления x1, …, xm. Назначение шин управления состоит в том, чтобы из всех микроопераций, выполняемых устройством, выбрать одну, требуемую в данный момент. Сигналы с выходов комбинационных схем подаются на входы триггеров. Функция возбуждения входного i-го триггера записывается в следующем виде:
Значения всех переменных в этом выражении определены для одного и того же момента времени t, поэтому функции возбуждения триггеров являются переключательными функциями, которым соответствуют комбинационные схемы, формирующие входные сигналы для триггеров. Следовательно, если известен тип триггера, то задача структурного синтеза устройства заключается в составлении функции возбуждения каждого триггера, функции кодирования выходов заданного устройства и минимизации. При выполнении структурного синтеза используются матрицы переходов триггеров (табл. 3.1), где для каждого типа триггера указаны значения входных сигналов, определяющие переход триггера из одного состояния в другое. Если значение входного сигнала не влияет на данный переход, то в матрице указывается неопределенный коэффициент b. Для триггера D — V–типа дополнительно указан второй коэффициент по управляющему входу.
Таблица 3.1
Алгоритм структурного синтеза
-
Определяется необходимое число независимых шин управления. Число управляющих шин зависит от числа микроопераций, выполняемых устройством, и находится из соотношения
, где L — число микроопераций.
-
По числу различных состояний N устройства определяется необходимое количество триггеров: m
, каждое состояние устройства кодируется m-разрядным двоичным кодом, i-й разряд соответствует выходному сигналу i-го триггера.
-
Кодируется внутреннее состояние синтезируемого автомата.
-
Согласно закону функционирования составляется кодированная таблица выходов устройства и переходов из одного состояния в другое при определенных входных воздействиях. Поскольку устройство представляет совокупность триггеров, такая таблица будет включать функции возбуждения всех входов триггеров возбуждения.
-
Выбирается (или задается) тип каждого триггера, по таблице переходов или матрице переходов составляются таблицы функций возбуждения всех входов каждого триггера.
-
Полученные функции возбуждения и функции выходов минимизируются соответствующим выбором значений неопределенных коэффициентов.
-
Согласно функциям возбуждения и в соответствии с выбранной (заданной) элементной базой строится структурная схема.
Синтез микропрограммных автоматов. Управляющий автомат, реализующий микропрограмму работы дискретного устройства, принято называть микропрограммным автоматом. Его синтез состоит из следующих этапов:
-
Составление частных содержательных микропрограмм выполнения операции автомата.
-
Построения частных микропрограмм с учетом отметок граф-схемы алгоритма символами.
-
Получение отмеченных частных микропрограмм.
-
Построение графов частных управляющих автоматов Мили или Мура.
-
Построения графа многофункционального автомата Мили или автомата Мура путем объединения состояний автоматов и введения настроечного алфавита.
-
Структурный синтез.
Далее составляется таблица переходов микропрограммного автомата. Для автомата Мили таблица содержит четыре столбца: am и as — исходное состояние и состояние перехода; х(am, as) — конъюнкция переменных из множества х, принимающая значение 1 на данном переходе; у(am, as) — подмножество выходных переменных, принимающих значение 1 на данном переходе. Каждая строка таблицы переходов соответствует одному пути перехода, т.е. дуге графа автомата с одним входным и одним выходным сигналами.
Таблица переходов микропрограммного автомата Мура содержит три столбца. В ней выходные сигналы из множества у(am) записываются в столбце am рядом с состоянием, в котором они формируются.
С помощью минимизации числа строк таблицы переходов автомата и методов доопределения функций строится логическая схема автомата, являющаяся совместной реализацией функций возбуждения функций выходов.
Абстрактный синтез автоматов. Задача абстрактного синтеза заключается в составлении таблиц переходов и выходов автомата по заданным условиям его функционирования.
Абстрактный синтез автоматов включает два этапа. Первый этап состоит в получении таблиц переходов и выходов в некоторой исходной форме. На втором этапе проводится минимизация количества внутренних состояний заданного автомата.
Алгоритм абстрактного синтеза заключается в следующем. Фиксируется начальное состояние a0 и для входного слова li, состоящего из r букв, назначается r внутренних состояний автомата ai1, ai2, …, air. Переходы в автомате назначаются так, что первая буква слова li переводит автомат из состояния a0 в состояние ai1, вторая буква — из состояния ai1 в состояние ai2 и т.д. Аналогичные последовательности внутренних состояний назначаются для всех остальных слов. Затем все конечные состояния air, в которые автомат попадает после подачи слов, входящих в событие Sj, отмечаются выходным сигналом уi.
Чтобы система переходов автомата была определенной для всех слов, имеющих одинаковые начальные отрезки, следует назначать одну и ту же последовательность состояний. В состояниях, не отмеченных буквами выходного алфавита у1, …, уk, а также в начальном состоянии автомат должен выдавать пустую букву, соответствующую событию Sk+1. Для запрещенного события последовательность состояний можно не назначать.
При абстрактном синтезе целесообразно использовать следующие соотношения:
Алгоритм минимизации числа внутренних состояний автомата включает следующие действия:
-
Все внутренние состояния разбиваются на группы, количество которых равно количеству выходных сигналов автомата. Если существует такое состояние, в котором автомат выдает пустое слово, то такие состояния также выделяют в общую группу.
-
По таблице переходов автомата определяют, к каким группам принадлежат внутренние состояния, в которые автомат переходит из данного состояния под воздействием каждой буквы входного алфавита.
-
Проводится новое разделение внутренних состояний на группы, при этом объединяются в каждой группе состояния, отмеченные одинаковой последовательностью букв.
-
Пользуясь таблицей переходов автомата, снова отмечаются каждые состояния последовательности букв. Объединение состояний в группы продолжается до тех пор, пока новые группы состояний появляться не будут.
Триггерные устройства. Основными элементами, предназначенными для хранения информации, являются устройства с двумя устойчивыми состояниями — триггеры. Структуру триггера можно представить в виде запоминающего элемента и схемы управления (рис 3.1).
Запоминающий элемент имеет два выхода Q и , разрешенные сигналы на которых всегда противоположны, и два входа s (set – установка) и r (reset – сброс). Переключающий сигнал по входу s устанавливает запоминающий элемент в состояние «1», а по входу r — в состояние «0». В общем случае запоминающий элемент может иметь несколько установочных входов.
Характеристики
Тип файла документ
Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.
Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.
Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.