Вам бонус- начислено 1 монета за дневную активность. Сейчас у вас 1 монета

4. Построение абстрактных автоматов по граф-схеме микропрограммы

Лекция



Привет, сегодня поговорим про построение абстрактных автоматов по граф-схеме микропрограммы, обещаю рассказать все что знаю. Для того чтобы лучше понимать что такое построение абстрактных автоматов по граф-схеме микропрограммы , настоятельно рекомендую прочитать все из категории Теория автоматов.

Управляющие автоматы: изучение принципов построения управляющих автоматов с "жесткой" логикой, приобретение навыков синтеза и анализа их работы.

Любое цифровое устройство можно рассматривать как устройство, состоящее из двух частей: операционного и управляющего блоков. Операционный блок, например АЛУ, характеризуется совокупностью определенных в нем микроопераций, каждая из которых представляет собой некоторый выполняемый в данном операционном блоке акт передачи или преобразования информации. Часть цифрового вычислительного устройства, предназначенного для выработки последовательности управляющих функциональных сигналов, называется управляющим блоком или управляющим устройством (УУ). 545i86cf

Формально УУ можно рассматривать как конечный автомат, определяемый:

1) множеством двоичных выходных сигналов,

2) множеством входных сигналов,

3) множеством подлежащих реализации программ,

4) множеством внутренних состояний.

Управляющие блоки называются управляющими автоматами. Поскольку эти автоматы задаются микропрограммами, они часто именуются микропрограммными автоматами.

Существуют два метода построения логики управляющих автоматов:

  • - с жесткой логикой,
  • - с хранимой в памяти логикой.

Управляющие автоматы с "жесткой" логикой представляют собой логические схемы, вырабатывающие распределенные во времени управляющие функциональные сигналы. В отличие от управляющих устройств, с хранимой в памяти логикой, у этих автоматов можно изменить логику работы только путем переделок схем автомата.

ЭВМ высокой производительности управляются автоматами с "жесткой" логикой. Типичным применением такого автомата является устройство управления АЛУ.

Произведем синтез цифрового автомата, заданного микропрограммой (рис. 1). По микропрограмме строится соответствующий управляющий автомат Мили или Мура. Синтезируем автомат Мили, так как он имеет число состояний, как правило, меньше, чем число состояний эквивалентного ему автомата Мура. С этой точки зрения автомат Мили предпочтительнее.

4. Построение абстрактных автоматов по граф-схеме микропрограммы

4. Построение абстрактных автоматов по граф-схеме микропрограммы

Переход от микропрограммы к автомату Мили иллюстрируется рис. 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

4. Построение абстрактных автоматов по граф-схеме микропрограммы

На элементах D1.3, D4 собрана схема, вырабатывающая управляющие сигналы состояний Q0, Q1, Q2 и множество входных сигналов . Схема функционирует так, что на ее выходах только одно логическое значение "0", все остальные - "1". Зная этот выход (в разные моменты времени он разный) и граф микропрограммы, можно точно определить текущие и следующие состояния автомата, выходные управляющие сигналы.

Поэтому тем, на какие элементы D1.1 или D1.2 заведен этот вывод (провод), и определяются следующие состояния автомата.

Объединение по "п" некоторых выводов этих элементов (D1.3, D4) согласно графу функционирования автомата дает множество управляющих выходных сигналов.

Элементы D1.1, D1.2 служат для формирования функций возбуждения триггеров.


4.1 Переход от Граф-схема алгоритма МП к графу абстрактного автомата Мили

Переход осуществляется в два этапа.

На первом этапе производится определение числа состояний путем разметки и отметки граф-схемы;

на втором - определение графа автомата.

Правила разметки:

  1. Символом 4. Построение абстрактных автоматов по граф-схеме микропрограммы помечаем вход вершины следующей за начальным оператором в ГСА и вход конечной вершины. (рис.4.1,а).
  2. Символами 4. Построение абстрактных автоматов по граф-схеме микропрограммы - входы вершин, следующих за операторными вершинами (рис.4.1,б).

4. Построение абстрактных автоматов по граф-схеме микропрограммы


Рис. 4.1.

Если в результате разметки оказалось, что в одну и ту же вершину граф-схемы входит несколько размеченных стрелок, то им присваивается один и тот же символ. В дальнейшем символ 4. Построение абстрактных автоматов по граф-схеме микропрограммы рассматривается как начальное состояние автомата, а символы 4. Построение абстрактных автоматов по граф-схеме микропрограммы- как промежуточные состояния автомата. Таким образом, число состояний автомата определяется числом различающихся символов 4. Построение абстрактных автоматов по граф-схеме микропрограммы

Переход от отмеченных граф-схем к графу автомата осуществ-ляется в следующем порядке.

Вершинами графа изображаются все состояния автомата и внутри кружков записываются символы 4. Построение абстрактных автоматов по граф-схеме микропрограммы, то есть существующие метки на ГСА.

На граф-схеме микропрограммы отыскивается путь между двумя соседними состояниями 4. Построение абстрактных автоматов по граф-схеме микропрограммы и 4. Построение абстрактных автоматов по граф-схеме микропрограммы. Пути отображаются дугами. Возможно существование путей трех видов:

  1. Если этот путь содержит логические условия, то дуга, связывающая вершины 4. Построение абстрактных автоматов по граф-схеме микропрограммы и 4. Построение абстрактных автоматов по граф-схеме микропрограммы графа автомата, отмечаетсялогической функцией 4. Построение абстрактных автоматов по граф-схеме микропрограммы, значение которой определяет переход автомата из состояния 4. Построение абстрактных автоматов по граф-схеме микропрограммы в состояние 4. Построение абстрактных автоматов по граф-схеме микропрограммы и оператором 4. Построение абстрактных автоматов по граф-схеме микропрограммы находящимся на пути между 4. Построение абстрактных автоматов по граф-схеме микропрограммы и 4. Построение абстрактных автоматов по граф-схеме микропрограммы (рис.4.2).

    4. Построение абстрактных автоматов по граф-схеме микропрограммы


    Рис. Об этом говорит сайт https://intellect.icu . 4.2.

  2. Если этот путь содержит логические условия, то дуга, связывающая вершины 4. Построение абстрактных автоматов по граф-схеме микропрограммы и 4. Построение абстрактных автоматов по граф-схеме микропрограммы графа автомата, отмечаетсялогической функцией, значение которой определяет переход автомата из состояния 4. Построение абстрактных автоматов по граф-схеме микропрограммы в состояние as и если на пути между 4. Построение абстрактных автоматов по граф-схеме микропрограммы и 4. Построение абстрактных автоматов по граф-схеме микропрограммы отсутствует операторная вершина, то этот факт отмечается символом '-' или символом 4. Построение абстрактных автоматов по граф-схеме микропрограммы ( пустой оператор, пропуск такта) (рис.4.3);

    4. Построение абстрактных автоматов по граф-схеме микропрограммы


    Рис. 4.3.

  3. Если этот путь не содержит логические условия, то есть существует безусловный переход, то это путь третьего вида. Такой переход обозначается "1" вместо логической функции и оператором 4. Построение абстрактных автоматов по граф-схеме микропрограммы находящимся на пути между 4. Построение абстрактных автоматов по граф-схеме микропрограммы и 4. Построение абстрактных автоматов по граф-схеме микропрограммы (рис.4.4).

4. Построение абстрактных автоматов по граф-схеме микропрограммы


Рис. 4.4.

Построение графа автомата Мили по ГСА микропрограммы рассмотрим на примере ГСА, представленной на рис.4.5.

На первом этапе выполним разметку согласно указанным выше правилам. Получаем пять меток, выделенных красными крестиками на рис.4.5.

4. Построение абстрактных автоматов по граф-схеме микропрограммы


Рис. 4.5.

На втором этапе строим граф автомата Мура. Имеем пять вершин графа соответствующих пяти состояниям.

По ГСА находим все пути между соседними метками. Так из метки 4. Построение абстрактных автоматов по граф-схеме микропрограммы в метку 4. Построение абстрактных автоматов по граф-схеме микропрограммы существует путь третьего типа, то естьбезусловный переход. Этот путь проходит через операторную вершину, отмеченную сигналом 4. Построение абстрактных автоматов по граф-схеме микропрограммы, который выносится на дугу перехода из состояния 4. Построение абстрактных автоматов по граф-схеме микропрограммы в состояние 4. Построение абстрактных автоматов по граф-схеме микропрограммы.

Рассмотрим пути, идущие от метки 4. Построение абстрактных автоматов по граф-схеме микропрограммы. Всего их три. Первый путь из 4. Построение абстрактных автоматов по граф-схеме микропрограммы в 4. Построение абстрактных автоматов по граф-схеме микропрограммы проходит через условную вершину 4. Построение абстрактных автоматов по граф-схеме микропрограммы и операторную вершину 4. Построение абстрактных автоматов по граф-схеме микропрограммы, то есть это путь первого вида, соответствующий переходу из состояния 4. Построение абстрактных автоматов по граф-схеме микропрограммы в состояние 4. Построение абстрактных автоматов по граф-схеме микропрограммы поусловию 4. Построение абстрактных автоматов по граф-схеме микропрограммы с выработкой выходного сигнала 4. Построение абстрактных автоматов по граф-схеме микропрограммы. Второй путь из 4. Построение абстрактных автоматов по граф-схеме микропрограммы в 4. Построение абстрактных автоматов по граф-схеме микропрограммы проходит через условные вершины 4. Построение абстрактных автоматов по граф-схеме микропрограммы и 4. Построение абстрактных автоматов по граф-схеме микропрограммы и операторную вершину 4. Построение абстрактных автоматов по граф-схеме микропрограммы, то есть это путь первого вида, соответствующий переходу из состояния 4. Построение абстрактных автоматов по граф-схеме микропрограммы в состояние 4. Построение абстрактных автоматов по граф-схеме микропрограммы по условию 4. Построение абстрактных автоматов по граф-схеме микропрограммы с выработкой выходного сигнала 4. Построение абстрактных автоматов по граф-схеме микропрограммы.

Третий путь из 4. Построение абстрактных автоматов по граф-схеме микропрограммы в 4. Построение абстрактных автоматов по граф-схеме микропрограммы проходит через условные вершины 4. Построение абстрактных автоматов по граф-схеме микропрограммы и 4. Построение абстрактных автоматов по граф-схеме микропрограммы, и не проходит ни через какую операторную вершину, то есть это путь второго вида, соответствующий переходу из состояния 4. Построение абстрактных автоматов по граф-схеме микропрограммы в состояние 4. Построение абстрактных автоматов по граф-схеме микропрограммы по условию 4. Построение абстрактных автоматов по граф-схеме микропрограммы без выходного сигнала.

Рассмотрим пути, идущие от метки 4. Построение абстрактных автоматов по граф-схеме микропрограммы. Всего их два. Первый путь из 4. Построение абстрактных автоматов по граф-схеме микропрограммы в 4. Построение абстрактных автоматов по граф-схеме микропрограммы проходит через условную вершину 4. Построение абстрактных автоматов по граф-схеме микропрограммы и операторную вершину 4. Построение абстрактных автоматов по граф-схеме микропрограммы, то есть это путь первого вида, соответствующий переходу автомата из состояния 4. Построение абстрактных автоматов по граф-схеме микропрограммы в состояние 4. Построение абстрактных автоматов по граф-схеме микропрограммыпо условию 4. Построение абстрактных автоматов по граф-схеме микропрограммы с выработкой выходного сигнала 4. Построение абстрактных автоматов по граф-схеме микропрограммы. Второй путь из 4. Построение абстрактных автоматов по граф-схеме микропрограммы в 4. Построение абстрактных автоматов по граф-схеме микропрограммы проходит через ту же условную вершины 4. Построение абстрактных автоматов по граф-схеме микропрограммы и не проходит ни через какую операторную вершину, то есть это путь второго вида, соответствующий переходу из состояния 4. Построение абстрактных автоматов по граф-схеме микропрограммы в состояние 4. Построение абстрактных автоматов по граф-схеме микропрограммы по условию 4. Построение абстрактных автоматов по граф-схеме микропрограммы без выходного сигнала.

Из метки 4. Построение абстрактных автоматов по граф-схеме микропрограммы также существует два пути и оба второго типа без выходного сигнала: из 4. Построение абстрактных автоматов по граф-схеме микропрограммы в 4. Построение абстрактных автоматов по граф-схеме микропрограммы соответствующий переходу из состояния 4. Построение абстрактных автоматов по граф-схеме микропрограммы в состояние 4. Построение абстрактных автоматов по граф-схеме микропрограммы по условию 4. Построение абстрактных автоматов по граф-схеме микропрограммы ; из 4. Построение абстрактных автоматов по граф-схеме микропрограммы в 4. Построение абстрактных автоматов по граф-схеме микропрограммы соответствующий переходу из состояния 4. Построение абстрактных автоматов по граф-схеме микропрограммы в состояние 4. Построение абстрактных автоматов по граф-схеме микропрограммы поусловию 4. Построение абстрактных автоматов по граф-схеме микропрограммы.

Из 4. Построение абстрактных автоматов по граф-схеме микропрограммы существует один путь в 4. Построение абстрактных автоматов по граф-схеме микропрограммы третьего вида, проходящий через операторную вершину 4. Построение абстрактных автоматов по граф-схеме микропрограммы.

Результат построенного абстрактного автомата Мили показан на рис.4.6.

4. Построение абстрактных автоматов по граф-схеме микропрограммы


Рис. 4.6.

Если мы переобозначим сигналы на дугах, например заменив 4. Построение абстрактных автоматов по граф-схеме микропрограммы на 4. Построение абстрактных автоматов по граф-схеме микропрограммы, 4. Построение абстрактных автоматов по граф-схеме микропрограммы на 4. Построение абстрактных автоматов по граф-схеме микропрограммы и т.д., а 4. Построение абстрактных автоматов по граф-схеме микропрограммы на 4. Построение абстрактных автоматов по граф-схеме микропрограммы, 4. Построение абстрактных автоматов по граф-схеме микропрограммы на 4. Построение абстрактных автоматов по граф-схеме микропрограммы, и т.п., то получим абстрактный автомат Мили в привычном виде.

4.2 Переход от ГСА МП к графу абстрактного автомата Мура

Переход осуществляется так же в два этапа.

На первом этапе производится определение числа состояний путем разметки и отметкиграф-схемы;

на втором - определение графа автомата.

Правила разметки:

  1. Символом 4. Построение абстрактных автоматов по граф-схеме микропрограммы помечаем начальную и конечную вершины ГСА микропрограммы.
  2. Символами 4. Построение абстрактных автоматов по граф-схеме микропрограммы помечаем операторные вершины, (рис.4.7,б).

    4. Построение абстрактных автоматов по граф-схеме микропрограммы


    Рис. 4.7.

  3. Разные вершины ГСА должны быть помечены разными метками.

На втором этапе проводим построение графа автомата Мура, причем метки соответствуют вершинам графа, внутри которых записывается выходной сигнал, так как в автомате Мура выходной сигнал зависит только от состояния и не зависит от входного сигнала.

В результате анализа разметки видим, что между парами меток имеем пути второго и третьего вида. Каждому пути ставим соответствующий переход.

Построение автомата Мура рассмотрим на примере ГСА МП, представленной на рис.4.8.

4. Построение абстрактных автоматов по граф-схеме микропрограммы


Рис. 4.8.

На первом этапе выполним разметку согласно указанным выше правилам. Получаем шесть меток (рис.4.8).

На втором этапе строим граф автомата Мили.

Имеем шесть вершин графа соответствующих шести состояниям.

Внутри каждой вершины записываем соответствующий выходной сигнал.

По ГСА находим все пути между соседними метками. Так из метки 4. Построение абстрактных автоматов по граф-схеме микропрограммы в метку 4. Построение абстрактных автоматов по граф-схеме микропрограммы существует один путь третьего типа, то естьбезусловный переход. Этот путь изображается дугой перехода из состояния 4. Построение абстрактных автоматов по граф-схеме микропрограммы в состояние 4. Построение абстрактных автоматов по граф-схеме микропрограммы.

Рассмотрим пути, идущие от метки 4. Построение абстрактных автоматов по граф-схеме микропрограммы. Всего их три.

Первый путь из 4. Построение абстрактных автоматов по граф-схеме микропрограммы в 4. Построение абстрактных автоматов по граф-схеме микропрограммы проходит через условную вершину 4. Построение абстрактных автоматов по граф-схеме микропрограммы то есть этопуть второго вида, соответствующий переходу из состояния 4. Построение абстрактных автоматов по граф-схеме микропрограммы в состояние 4. Построение абстрактных автоматов по граф-схеме микропрограммы по условию 4. Построение абстрактных автоматов по граф-схеме микропрограммы.

Второй путь проходит через условные вершины 4. Построение абстрактных автоматов по граф-схеме микропрограммы и 4. Построение абстрактных автоматов по граф-схеме микропрограммы, то есть это тоже путь второго вида, соответствующий переходу из состояния 4. Построение абстрактных автоматов по граф-схеме микропрограммы в состояние 4. Построение абстрактных автоматов по граф-схеме микропрограммы по условию 4. Построение абстрактных автоматов по граф-схеме микропрограммы.

Третий путь из 4. Построение абстрактных автоматов по граф-схеме микропрограммы в 4. Построение абстрактных автоматов по граф-схеме микропрограммы проходит через условные вершины 4. Построение абстрактных автоматов по граф-схеме микропрограммы и 4. Построение абстрактных автоматов по граф-схеме микропрограммы, то есть это путь второго вида, соответствующий переходу из состояния 4. Построение абстрактных автоматов по граф-схеме микропрограммы в состояние 4. Построение абстрактных автоматов по граф-схеме микропрограммы по условию 4. Построение абстрактных автоматов по граф-схеме микропрограммы.

Результат построенного абстрактного автомата Мили показан на рис. рис.4.9

4. Построение абстрактных автоматов по граф-схеме микропрограммы


Рис. 4.9.

4.3 Абстрактный С-автомат (совмещенный автомат)

Очень часто в управляющих устройствах нужны сигналы обоих типов: первого рода как в абстрактном автомате Мили и второго рода как в абстрактном автомате Мура. В автомате Мили выходной сигнал зависит как от состояния, так и от входного сигнала и формируется в тот же дискретный интервал времени, в котором поступает входной сигнал (рис.4.10,а).

4. Построение абстрактных автоматов по граф-схеме микропрограммы


Рис. 4.10.

4. Построение абстрактных автоматов по граф-схеме микропрограммы

В автомате Мура выходной сигнал зависит только от состояния, и выдается все то время, когда автомат находится в этом состоянии (рис.4.10,б):

4. Построение абстрактных автоматов по граф-схеме микропрограммы

Совмещенный автомат или 4. Построение абстрактных автоматов по граф-схеме микропрограммы - автомат таким образом содержит сигналы как первого рода, так и второго и описывается восьмеркой вида:

4. Построение абстрактных автоматов по граф-схеме микропрограммы

При графическом задании 4. Построение абстрактных автоматов по граф-схеме микропрограммы - автомата на переходах указываются выходные сигналы 1 рода 4. Построение абстрактных автоматов по граф-схеме микропрограммы, а в вершинах выходные сигналы 2 рода 4. Построение абстрактных автоматов по граф-схеме микропрограммы (рис.4.11).

4. Построение абстрактных автоматов по граф-схеме микропрограммы


Рис. 4.11.

Явное задание 4. Построение абстрактных автоматов по граф-схеме микропрограммы - автомата требует описание всех составляющих и выполняется так же как и для автоматов Мили и Мура.

Табличное задание 4. Построение абстрактных автоматов по граф-схеме микропрограммы - автомата состоит в представлении работы автомата двумя таблицами: таблицей переходов (табл.4.1) и таблицей выходов (табл.4.2), в которой в отличие от автомата Мили в верхней строке добавляются сигналы второго рода.

Таблица 4.1.
z\a a1 a2 a3
z1 a 3 a 1 a 1
z2 a1 a3 a2

Таблица 4.2.
\uh u1 u3 u2
z\a a1 a2 a3
z1 w1 w1 w2
z2 w1 w2 w1

Матричное задание 4. Построение абстрактных автоматов по граф-схеме микропрограммы - автомата состоит в описании двумя матрицами аналогично матричному представлению автоматов Мили и Мура.

4. Построение абстрактных автоматов по граф-схеме микропрограммы

2. Порядок выполнения работы

1. Получите у преподавателя вариант индивидуального задания.

Вариант

1

2

3

4

5

6

Микропрограмма

автомата (рис. 4-5)

4

5

6

7

8

9

2. От микропрограммы перейдите к графу интерпретирующего автомата Мили.

3. По графу микропрограммы синтезируйте схему технической реализации.

4. Проверьте правильность функционирования автомата. Для этого:

- подайте кратковременно на вход R сигнал со значением логического "0". При этом произойдет сброс их триггеров в "0",

- определите множество входных сигналов, определяющих переход автомата из одного состояния в другое.

3. Вопросы для самостоятельной работы

  • 1) Чем определяется конечный автомат?
  • 2) Что представляет собой автомат с "жесткой " логикой?
  • 3) Как перейти от микропрограммы к графу интерпретирующему автомат Мили?
  • 4) В чем различие автомата Мили и Мура?
  • 5) Объясните работу схемы технической реализации автомата Мили.

4. Построение абстрактных автоматов по граф-схеме микропрограммы

Вау!! 😲 Ты еще не читал? Это зря!

Надеюсь, эта статья про построение абстрактных автоматов по граф-схеме микропрограммы, была вам полезна, счастья и удачи в ваших начинаниях! Надеюсь, что теперь ты понял что такое построение абстрактных автоматов по граф-схеме микропрограммы и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Теория автоматов

Ответы на вопросы для самопроверки пишите в комментариях, мы проверим, или же задавайте свой вопрос по данной теме.

создано: 2015-05-17
обновлено: 2021-12-16
132837



Рейтиг 9 of 10. count vote: 2
Вы довольны ?:


Найди готовое или заработай

С нашими удобными сервисами без комиссии*

Как это работает? | Узнать цену?

Найти исполнителя
$0 / весь год.
  • У вас есть задание, но нет времени его делать
  • Вы хотите найти профессионала для выплнения задания
  • Возможно примерение функции гаранта на сделку
  • Приорететная поддержка
  • идеально подходит для студентов, у которых нет времени для решения заданий
Готовое решение
$0 / весь год.
  • Вы можите продать(исполнителем) или купить(заказчиком) готовое решение
  • Вам предоставят готовое решение
  • Будет предоставлено в минимальные сроки т.к. задание уже готовое
  • Вы получите базовую гарантию 8 дней
  • Вы можете заработать на материалах
  • подходит как для студентов так и для преподавателей
Я исполнитель
$0 / весь год.
  • Вы профессионал своего дела
  • У вас есть опыт и желание зарабатывать
  • Вы хотите помочь в решении задач или написании работ
  • Возможно примерение функции гаранта на сделку
  • подходит для опытных студентов так и для преподавателей



Комментарии


Оставить комментарий
Если у вас есть какое-либо предложение, идея, благодарность или комментарий, не стесняйтесь писать. Мы очень ценим отзывы и рады услышать ваше мнение.
To reply

Теория автоматов

Термины: Теория автоматов