04Глава 3 (Полезная книга)
Описание файла
Файл "04Глава 3" внутри архива находится в папке "Полезная книга". Документ из архива "Полезная книга", который расположен в категории "". Всё это находится в предмете "схемотехника" из 6 семестр, которые можно найти в файловом архиве МАИ. Не смотря на прямую связь этого архива с МАИ, его также можно найти и в других разделах. Архив можно найти в разделе "книги и методические указания", в предмете "схемотехника" в общих файлах.
Онлайн просмотр документа "04Глава 3"
Текст из документа "04Глава 3"
Глава 3. Структурный и абстрактный синтез устройств ВМ.
Структурный синтез операционных устройств ВМ. Операционное устройство ВМ можно представить состоящим как бы из двух частей — комбинационной и памяти. На входы комбинационной части поступают сигналы с выходов элементов памяти (триггеров) Q1, …, Qm, а также сигналы, приходящие по шинам управления x1, …, xm. Назначение шин управления состоит в том, чтобы из всех микроопераций, выполняемых устройством, выбрать одну, требуемую в данный момент. Сигналы с выходов комбинационных схем подаются на входы триггеров. Функция возбуждения входного i-го триггера записывается в следующем виде:
Значения всех переменных в этом выражении определены для одного и того же момента времени t, поэтому функции возбуждения триггеров являются переключательными функциями, которым соответствуют комбинационные схемы, формирующие входные сигналы для триггеров. Следовательно, если известен тип триггера, то задача структурного синтеза устройства заключается в составлении функции возбуждения каждого триггера, функции кодирования выходов заданного устройства и минимизации. При выполнении структурного синтеза используются матрицы переходов триггеров (табл. 3.1), где для каждого типа триггера указаны значения входных сигналов, определяющие переход триггера из одного состояния в другое. Если значение входного сигнала не влияет на данный переход, то в матрице указывается неопределенный коэффициент b. Для триггера D — V–типа дополнительно указан второй коэффициент по управляющему входу.
Таблица 3.1
Переходы | Тип триггера | ||||||||
0 – 0 | 0 | b | 0 | b | b a | b | 1 | b | 0 |
0 – 1 | 1 | b | 1 | 1 | 1 | 1 | 0 | 0 | 1 |
1 – 0 | b | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 0 |
1 – 1 | b | 0 | 1 | b | b a | 1 | b | 0 | b |
Алгоритм структурного синтеза
-
Определяется необходимое число независимых шин управления. Число управляющих шин зависит от числа микроопераций, выполняемых устройством, и находится из соотношения , где 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». В общем случае запоминающий элемент может иметь несколько установочных входов.