Лекция
Привет, сегодня поговорим про построение абстрактных автоматов по граф-схеме микропрограммы, обещаю рассказать все что знаю. Для того чтобы лучше понимать что такое построение абстрактных автоматов по граф-схеме микропрограммы , настоятельно рекомендую прочитать все из категории Теория цифровых автоматов.
Любое цифровое устройство можно рассматривать как устройство, состоящее из двух частей: операционного и управляющего блоков. Операционный блок, например АЛУ, характеризуется совокупностью определенных в нем микроопераций, каждая из которых представляет собой некоторый выполняемый в данном операционном блоке акт передачи или преобразования информации. Часть цифрового вычислительного устройства, предназначенного для выработки последовательности управляющих функциональных сигналов, называется управляющим блоком или управляющим устройством (УУ). 545i86cf
Формально УУ можно рассматривать как конечный автомат, определяемый:
1) множеством двоичных выходных сигналов,
2) множеством входных сигналов,
3) множеством подлежащих реализации программ,
4) множеством внутренних состояний.
Управляющие блоки называются управляющими автоматами. Поскольку эти автоматы задаются микропрограммами, они часто именуются микропрограммными автоматами.
Существуют два метода построения логики управляющих автоматов:
Управляющие автоматы с "жесткой" логикой представляют собой логические схемы, вырабатывающие распределенные во времени управляющие функциональные сигналы. В отличие от управляющих устройств, с хранимой в памяти логикой, у этих автоматов можно изменить логику работы только путем переделок схем автомата.
ЭВМ высокой производительности управляются автоматами с "жесткой" логикой. Типичным применением такого автомата является устройство управления АЛУ.
Произведем синтез цифрового автомата, заданного микропрограммой (рис. 1). По микропрограмме строится соответствующий управляющий автомат Мили или Мура. Синтезируем автомат Мили, так как он имеет число состояний, как правило, меньше, чем число состояний эквивалентного ему автомата Мура. С этой точки зрения автомат Мили предпочтительнее.
Переход от микропрограммы к автомату Мили иллюстрируется рис. 2, на котором показаны микропрограмма и граф интерпретирующего ее автомата Мили. Начало и конец микропрограммы представляются начальным состоянием автомата Q0.
Каждая дуга, выходящая из прямоугольника, представляющего микрокоманду, отмечается меткой X и символом состояния автомата. Исключение составляют дуги, идущие к конечной вершине, которые не отмечаются. Если несколько дуг с меткой X входят в один блок графа программы, то все они отмечаются одинаковым символом состояния. Условия перехода по микропрограмме от одной метки состояния к другой задают функции переходов. Эти условия записываются в виде конъюнкции осведомительных сигналов. Для каждого перехода фиксируется также набор выходных переменных, принимающих при переходе единичное значение (задание функции выходов).
От графа, интерпретирующего микропрограмму, можно перейти к ее технической реализации. Зная число состояний автомата m, определим число триггеров, необходимых для реализации его памяти, K=log2m.
Для приведенного примера m=3 => K=log23 º2 требуется два триггера. Выберем для определенности D-триггера. Для триггеров составим таблицы состояний и истинности (табл. 1-2). Схема дешифрации состояний состоит из элементов D3.1, D3.2, D3.3 (рис. 3).
Примечание. Состояние триггера D1=1, D2=1 является запрещенным.
|
Таблица 1 |
|
Таблица 2 |
||||||||
|
№ |
Q |
D1 |
D2 |
|
№ |
D1 |
D2 |
Q0 |
Q1 |
Q2 |
|
1 |
0 |
0 |
0 |
|
1 |
0 |
0 |
1 |
0 |
0 |
|
2 |
1 |
0 |
1 |
|
2 |
0 |
1 |
0 |
1 |
0 |
|
3 |
2 |
1
|
0 |
|
3 |
1 |
0 |
0 |
0 |
1 |
На элементах D1.3, D4 собрана схема, вырабатывающая управляющие сигналы состояний Q0, Q1, Q2 и множество входных сигналов . Схема функционирует так, что на ее выходах только одно логическое значение "0", все остальные - "1". Зная этот выход (в разные моменты времени он разный) и граф микропрограммы, можно точно определить текущие и следующие состояния автомата, выходные управляющие сигналы.
Поэтому тем, на какие элементы D1.1 или D1.2 заведен этот вывод (провод), и определяются следующие состояния автомата.
Объединение по "п" некоторых выводов этих элементов (D1.3, D4) согласно графу функционирования автомата дает множество управляющих выходных сигналов.
Элементы D1.1, D1.2 служат для формирования функций возбуждения триггеров.
Переход осуществляется в два этапа.
На первом этапе производится определение числа состояний путем разметки и отметки граф-схемы;
на втором - определение графа автомата.
Правила разметки:
помечаем вход вершины следующей за начальным оператором в ГСА и вход конечной вершины. (рис.4.1,а).
- входы вершин, следующих за операторными вершинами (рис.4.1,б).
Рис. 4.1.
Если в результате разметки оказалось, что в одну и ту же вершину граф-схемы входит несколько размеченных стрелок, то им присваивается один и тот же символ. В дальнейшем символ рассматривается как начальное состояние автомата, а символы 
- как промежуточные состояния автомата. Таким образом, число состояний автомата определяется числом различающихся символов 
Переход от отмеченных граф-схем к графу автомата осуществ-ляется в следующем порядке.
Вершинами графа изображаются все состояния автомата и внутри кружков записываются символы 
, то есть существующие метки на ГСА.
На граф-схеме микропрограммы отыскивается путь между двумя соседними состояниями 
и 
. Пути отображаются дугами. Возможно существование путей трех видов:
и графа автомата, отмечаетсялогической функцией 
, значение которой определяет переход автомата из состояния в состояние и оператором 
находящимся на пути между и (рис.4.2).
и графа автомата, отмечаетсялогической функцией, значение которой определяет переход автомата из состояния в состояние as и если на пути между и отсутствует операторная вершина, то этот факт отмечается символом '-' или символом 
( пустой оператор, пропуск такта) (рис.4.3);
находящимся на пути между и (рис.4.4).
Рис. 4.4.
Построение графа автомата Мили по ГСА микропрограммы рассмотрим на примере ГСА, представленной на рис.4.5.
На первом этапе выполним разметку согласно указанным выше правилам. Получаем пять меток, выделенных красными крестиками на рис.4.5.
Рис. 4.5.
На втором этапе строим граф автомата Мура. Имеем пять вершин графа соответствующих пяти состояниям.
По ГСА находим все пути между соседними метками. Так из метки в метку 
существует путь третьего типа, то естьбезусловный переход. Этот путь проходит через операторную вершину, отмеченную сигналом 
, который выносится на дугу перехода из состояния в состояние .
Рассмотрим пути, идущие от метки . Всего их три. Первый путь из в 
проходит через условную вершину 
и операторную вершину 
, то есть это путь первого вида, соответствующий переходу из состояния в состояние поусловию с выработкой выходного сигнала . Второй путь из в 
проходит через условные вершины и 
и операторную вершину 
, то есть это путь первого вида, соответствующий переходу из состояния в состояние по условию 
с выработкой выходного сигнала .
Третий путь из в проходит через условные вершины и , и не проходит ни через какую операторную вершину, то есть это путь второго вида, соответствующий переходу из состояния в состояние по условию 
без выходного сигнала.
Рассмотрим пути, идущие от метки . Всего их два. Первый путь из в 
проходит через условную вершину 
и операторную вершину 
, то есть это путь первого вида, соответствующий переходу автомата из состояния в состояние по условию с выработкой выходного сигнала . Второй путь из в проходит через ту же условную вершины и не проходит ни через какую операторную вершину, то есть это путь второго вида, соответствующий переходу из состояния в состояние по условию без выходного сигнала.
Из метки также существует два пути и оба второго типа без выходного сигнала: из в соответствующий переходу из состояния в состояние по условию 
; из 
в 
соответствующий переходу из состояния в состояние поусловию .
Из существует один путь в третьего вида, проходящий через операторную вершину 
.
Результат построенного абстрактного автомата Мили показан на рис.4.6.
Рис. 4.6.
Если мы переобозначим сигналы на дугах, например заменив на 
, на 
и т.д., а 
на 
, 
на 
, и т.п., то получим абстрактный автомат Мили в привычном виде.
Переход осуществляется так же в два этапа.
На первом этапе производится определение числа состояний путем разметки и отметкиграф-схемы;
на втором - определение графа автомата.
Правила разметки:
помечаем начальную и конечную вершины ГСА микропрограммы.
помечаем операторные вершины, (рис.4.7,б).
На втором этапе проводим построение графа автомата Мура, причем метки соответствуют вершинам графа, внутри которых записывается выходной сигнал, так как в автомате Мура выходной сигнал зависит только от состояния и не зависит от входного сигнала.
В результате анализа разметки видим, что между парами меток имеем пути второго и третьего вида. Каждому пути ставим соответствующий переход.
Построение автомата Мура рассмотрим на примере ГСА МП, представленной на рис.4.8.
Рис. 4.8.
На первом этапе выполним разметку согласно указанным выше правилам. Получаем шесть меток (рис.4.8).
На втором этапе строим граф автомата Мили.
Имеем шесть вершин графа соответствующих шести состояниям.
Внутри каждой вершины записываем соответствующий выходной сигнал.
По ГСА находим все пути между соседними метками. Так из метки в метку существует один путь третьего типа, то естьбезусловный переход. Этот путь изображается дугой перехода из состояния в состояние .
Рассмотрим пути, идущие от метки . Всего их три.
Первый путь из в проходит через условную вершину 
то есть этопуть второго вида, соответствующий переходу из состояния в состояние по условию .
Второй путь проходит через условные вершины и , то есть это тоже путь второго вида, соответствующий переходу из состояния 
в состояние по условию 
.
Третий путь из в проходит через условные вершины и , то есть это путь второго вида, соответствующий переходу из состояния в состояние по условию 
.
Результат построенного абстрактного автомата Мили показан на рис. рис.4.9
Рис. 4.9.
Очень часто в управляющих устройствах нужны сигналы обоих типов: первого рода как в абстрактном автомате Мили и второго рода как в абстрактном автомате Мура. В автомате Мили выходной сигнал зависит как от состояния, так и от входного сигнала и формируется в тот же дискретный интервал времени, в котором поступает входной сигнал (рис.4.10,а).
Рис. 4.10.
В автомате Мура выходной сигнал зависит только от состояния, и выдается все то время, когда автомат находится в этом состоянии (рис.4.10,б):
Совмещенный автомат или 
- автомат таким образом содержит сигналы как первого рода, так и второго и описывается восьмеркой вида:
При графическом задании 
- автомата на переходах указываются выходные сигналы 1 рода 
, а в вершинах выходные сигналы 2 рода 
(рис.4.11).
Рис. 4.11.
Явное задание - автомата требует описание всех составляющих и выполняется так же как и для автоматов Мили и Мура.
Табличное задание - автомата состоит в представлении работы автомата двумя таблицами: таблицей переходов (табл.4.1) и таблицей выходов (табл.4.2), в которой в отличие от автомата Мили в верхней строке добавляются сигналы второго рода.
| z\a | a1 | a2 | a3 |
|---|---|---|---|
| z1 | a 3 | a 1 | a 1 |
| z2 | a1 | a3 | a2 |
| \uh | u1 | u3 | u2 |
|---|---|---|---|
| z\a | a1 | a2 | a3 |
| z1 | w1 | w1 | w2 |
| z2 | w1 | w2 | w1 |
Матричное задание - автомата состоит в описании двумя матрицами аналогично матричному представлению автоматов Мили и Мура.
1. Получите у преподавателя вариант индивидуального задания.
|
Вариант |
1 |
2 |
3 |
4 |
5 |
6 |
|
Микропрограмма автомата (рис. 4-5) |
4 |
5 |
6 |
7 |
8 |
9 |
2. От микропрограммы перейдите к графу интерпретирующего автомата Мили.
3. По графу микропрограммы синтезируйте схему технической реализации.
4. Проверьте правильность функционирования автомата. Для этого:
- подайте кратковременно на вход R сигнал со значением логического "0". При этом произойдет сброс их триггеров в "0",
- определите множество входных сигналов, определяющих переход автомата из одного состояния в другое.
Надеюсь, эта статья про построение абстрактных автоматов по граф-схеме микропрограммы, была вам полезна, счастья и удачи в ваших начинаниях! Надеюсь, что теперь ты понял что такое построение абстрактных автоматов по граф-схеме микропрограммы и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Теория цифровых автоматов
Ответы на вопросы для самопроверки пишите в комментариях, мы проверим, или же задавайте свой вопрос по данной теме.
Комментарии
Оставить комментарий
Теория цифровых автоматов
Термины: Теория цифровых автоматов