рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Граф - схемы микропрограммных автоматов

Граф - схемы микропрограммных автоматов - раздел Транспорт, ТЕОРИЯ ЦИФРОВЫХ АВТОМАТОВ   Для Описания Микропрограмм Необходимо Знать И Задавать Послед...

 

Для описания микропрограмм необходимо знать и задавать последовательности микрокоманд и функции перехода, определяющие порядок выполнения микрокоманд. Для описание микропрограмм обычно используется язык граф-схем алгоритмов (ГСА).

Граф-схема алгоритма (ГСА) - ориентированный связный граф, содержащий одну начальную вершину (А0), одну конечную (Ак) и произвольное количество условных (P={p1, ..., pF}) и операторных (А={A1, ..., AG}) вершин.

Конечная, операторная и условная вершины имеют по одному входу, начальная вершина входов не имеет. Начальная и операторная вершины имеют по одному выходу, а условная - два выхода, помеченных символами 0 и 1. Конечная вершина выходов не имеет.

ГСА удовлетворяет следующим условиям:

1 Входы и выходы вершин соединяются друг с другом с помощью дуг направленных всегда от выхода ко входу.

2 Каждый выход соединён точно с одним входом.

3 Любой вход соединяется по крайней мере с одним выходом.

4 Любая вершина графа лежит по крайней мере на одном пути из начальной вершины к конечной вершине.

5 Один из выходов условной вершины может соединяться с её входом, что недопустимо для операторной вершины. Такие условные вершины называются возвратными вершинами.

6 В каждой условной вершине записывается один из элементов множества X={x1, ..., xl, ..., xL}, называемого множеством логических условий. Разрешается в различных условных вершинах запись одинаковых элементов множества X.

7 В каждой операторной вершине записывается оператор ( микрокоманда) Yt - подмножество множества Y={y1, ..., yn, ..., yN}, называемого множеством микроопераций Yt=(yt1, ..., ytu, ..., ytU); ytnÎY, u=1, ..., U.

При U=0, Yt=Æ (пусто), что допустимо. Разрешается также запись в различных операторных вершинах одинаковых подмножеств множества микроопераций.

При большом количестве дуг, приходящих на один вход вершины, ГСА выглядит неаккуратно, поэтому разрешается изображать дуги, входящие в вершины, так, как показано на рис.69.

Пример ГСА, содержащего 6 условных и 7 операторных вершин приведён на рис.70.

Предположим, что в операторных вершинах ГСА записаны операторы Yt, ... , YT - все разные, так что операторную вершину можно отождествить с записанным в ней оператором (в вершине Ai записан оператор Yi. В таком случае вместо обозначения Ai для операторной вершины можно использовать символы Yi).

Начальной вершине поставим в соответствие оператор Y0, а конечной - оператор Yk=YT+1. Пусть в ГСА имеется путь из вершины Yi (i=0, 1, ... , T) в вершину Yj (j=1, ... , T, T+1) вида

, (A)

проходящий только через условные вершины pi1, ... , piR; где lir Î {0,1} - символ, приписанный выходу условной вершины pir, через который проходит путь (A). Каждому такому пути соответствует элементарная конъюнкция , где xir - логическое условие, записанное в условной вершине pir; .

Если между вершинам Yi и Yj имеется несколько (например H) путей, проходящих через условные вершины, то aij равно дизъюнкции элементарных конъюнкций, соответствующих всем путям, то есть

- конъюнкция, соответствующая h - му пути из Yi в Yj.

Таким образом, aij - функция перехода от оператора (микрокоманды) Yi к оператору (микрокоманде) Yj.

Всевозможные наборы значений переменных обозначим через . Определим процесс выполнения ГСА, начиная с оператора Y0 (начальный оператор), на произвольной бесконечной последовательности наборов Dm1, ..., Dmg, ... следующим образом:

Выписываем оператор Y0.

ШАГ 1 Придаём переменным значения из набора Dm1. Из множества функций перехода a01, ... , a выбираем функцию a0i1 (i1Î{1, ... , T}), такую, что a0i1(Dm1) = 1. В строчку рядом с Y0 записываем Yi1

Y0 Yi1.

ШАГ 2 Придаём переменным значения из набора Dm2. Из множества функций перехода ai11, ... , ai выбираем функцию ai1i2 (i2Î{1, ... , T}), такую, что ai1i2(Dm2) = 1. В сточку рядом с Yi1 записываем Yi2

Y0 Yi1 Yi2 и т. д.

Пусть перед некоторым q - м шагом имеем строчку операторов

Y0 Yi1 Yi2 ... .

Если на наборе Dmq некоторая функция перехода равна единице (iqÎ{1, ... , T}), то в выписанную строчку операторов добавляем . Если оказывается, что () = 1, то в сточку вслед за записываем YT+1(конечный оператор), и процесс выполнения ГСА завершается.

Строчка Y0 Yi1 Yi2 ... называется значением ГСА на последовательности наборов Dm1, Dm2, ... , , . Процедура выполнения ГСА на заданной последовательности наборов переменных может прекратиться в двух случаях:

- исчерпаны все наборы (заключительным в значении ГСА стоит оператор );

- достигнута конечная вершина (заключительным в значении ГСА стоит конечный оператор YT+1).

Например, значение ГСА на по рис.70 на последовательности наборов

Рассмотрим процедуру выполнения ГСА на произвольной последовательности наборов при наличии возвратных условных вершин на примере фрагмента ГСА, приведенного на рис. 71.

Между операторами Y1 и Y3 имеется бесчисленное множество путей, в связи с чем :

Так как логические условия, соответствующие всем путям, начиная со второго, равны нулю, a13 фактически определяется первым путём.

В связи с этим в дальнейшем учитываются лишь те пути через возвратные вершины, которые проходят через выход, не соединённый с её входом. Таким образом, на рис.71 имеется лишь один путь вида

из вершины Y1 в вершину Y3. Тогда,

Пусть в процессе выполнения ГСА на некоторой последовательности наборов выполнился оператор Y1, после чего в этой последовательности стоят наборы значений переменных xi

101,

111.

Из выражений (С) видно, что ни одна функция перехода из оператора Y1 на наборе 101 не равна единице, поэтому в строку рядом с Y1 записывается пустой оператор Y0 :

...Y1Y0 и

выполняется переход к следующему набору (111), на котором проверяется значение функции перехода из того же оператора Y1. На наборе 111 a13=1, а поэтому рядом с Y0 записывается оператор Y3:

... Y1Y0Y3...

Если бы и на этом наборе ни одна из функций перехода не была бы равна единице, то рядом с Y0 был бы записан ещё один пустой оператор Y0 и так до тех пор, пока на каком-то наборе не появилось значение некоторой функции перехода, равной единице.

Такое выполнение ГСА соответствует тому, что при значениях переменных, при которых ни одна функция перехода из последнего выполненного оператора не равна единице, управляющее устройство не выдаёт сигналов на выполнение микроопераций в операционном блоке (выполняется микрокоманда Y0) и тем самым реализуется ожидание в работе устройства.

 

– Конец работы –

Эта тема принадлежит разделу:

ТЕОРИЯ ЦИФРОВЫХ АВТОМАТОВ

ЮЖНО УРАЛЬСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Граф - схемы микропрограммных автоматов

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Базис И, ИЛИ, НЕ. Свойства элементарных функций алгебры логики
  Пусть x - некоторая логическая переменная. Тогда: 1. , что означает возможность исключения из логического вы

Табличное описание булевых функций
  Вследствие конечности множества наборов заданного количества логических переменных, простейшим и самым естественным способом описания ФАЛ является табличный. Пример описания трёх ФА

Аналитическое описание булевых функций
На примерах описания ФАЛ, приведенных в таблице 3, видно, что конституента 1 может быть описана в виде элементарной конъюнкции переменных:

Геометрическое представление булевых функций
  В геометрическом представлении ФАЛ значения входных переменных n - местного набора интерпретируются как координаты в n - мерной декартовой системе координат. Координат

Минимизация с помощью минимизирующих карт
  Как было отмечено выше, одним из способов представления ФАЛ от небольшого числа переменных (обычно не больше 5) являются диаграммы Карно или Вейча, которые строятся на развёртках мн

Минимизация функций алгебры логики по методу Квайна
  При минимизации по методу Квайна в базисе И, ИЛИ, НЕ исходная ФАЛ задаётся в СДНФ. Целью минимизации является нахождение всех первичных импликант и выбор некоторых из них для

По методу Квайна - Мак-Класки
  Недостаток метода Квайна - необходимость исчерпывающего попарного сравнения или сопоставления всех минтермов на этапе нахождения первичных импликант. С ростом числа минтермов увелич

Логические элементы И и И-НЕ
(Позитивная логика) Схема логического элемента И, построенного на полупроводниковых диодах и резисторе, приведена на рис.10а).

Логические элементы ИЛИ, ИЛИ-НЕ
  Схема логического элемента ИЛИ, построенного на полупроводниковых диодах и резисторе, приведена на рис.12а).

Программируемые логические матрицы (ПЛМ)
  Программируемая логическая матрица [2] представляет собой функциональный блок, созданный на базе интегральной полупроводниковой технологии и предназначенный для реализации логически

Процедуры программирования ПЛМ
Физическим принципом программирования ПЛМ является пережигание (испарение) выбранных перемычек. В процессе эксплуатации ПЛМ могут возникнуть следующие задачи: - начальное программ

Определение абстрактного цифрового автомата
Обобщённая структура системы обработки цифровой информации, приведённая на рис.1, соответствует описанию абстрактного цифрового автомата. Для целей технического проектирования в каноническую структ

Методы описания цифровых автоматов
  Чтобы задать цифровой автомат S, необходимо описать все элементы множества S = { A, X ,Y, d, l, a1}, то есть входной и выходной алфавиты и алфавит состояний, а также функ

Синхронные и асинхронные цифровые автоматы
Состояние as автомата S называется устойчивым состоянием, если для любого входа zfÎX, такого, что d(am, zf) = as, имеет место d(as

Цифровых автоматов Мили и Мура
Абстрактный цифровой автомат работает как преобразователь слов входного алфавита в слово в выходном алфавите [5]. Рассмотрим это положение, взяв в качестве примера автомат Мили S1.

Минимизация абстрактного автомата Мили
  Для табличного описания процедура минимизации цифровых автоматов алгоритмизирована и выполняется в несколько шагов.   Шаг 1 Распространение неопределённости т

Минимизация абстрактного автомата Мура
Минимизация автоматов Мура основана на тех же принципах, что и минимизация автоматов Мили. Для табличного описания эта процедура алгоритмизирована и состоит из трёх шагов.  

Элементарные автоматы памяти
  Комбинационная схема с обратными связями, имеющая два устойчивых состояния и предназначенная для хранения одного бита информации, называется элементарным автоматом или триггером. Со

Синхронизация в цифровых автоматах
  Смена состояний в синхронизированных автоматах происходит в определённые моменты времени, задаваемые по цепям синхронизации внешним тактовым генератором. Изменение состояний в реаль

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

Декомпозиция устройств обработки цифровой информации
  В любом устройстве или системе обработки цифровой информации можно выделить два существенно различающихся блока (рис.63): - операционный блок (или операционный автомат);

Управляющие автоматы
Любая команда, операция или процедура, выполняемая в операционном блоке, описывается некоторой микропрограммой и реализуется за несколько тактов, в каждом из которых выполняется шаг микропрограммы

Принцип действия управляющего автомата с хранимой в памяти логикой и микропрограммное управление
  Хранимая в памяти микропрограмма должна содержать информацию о функциях переходов и выходов управляющего микропрограммного автомата. Рассматривая управляющий автомат (УА) в терминах

Горизонтальное микропрограммирование
  При горизонтальном микропрограммировании каждому биту операционной части микрокоманды ставится в соответствие определённый управляющий функциональный сигнал, то есть определённая ми

Вертикальное микропрограммирование
  При вертикальном микропрограммировании микрооперация определяется не состоянием одного из бит микрокоманды, а двоичным кодом, содержащимся в операционной части микрокоманды (

Горизонтально - вертикальное микропрограммирование
  В этом случае подмножества VL представляются горизонтальным способом , а микрооперации внутри каждого из подмножеств - вертикальным способом (рис.66). Для каждого подмнож

Синтез микропрограммного автомата Мили
  Конечный автомат, реализующий микропрограмму работы дискретного устройства, называется микропрограммным автоматом. Синтез микропрограммного автомата Мили по граф - схеме ал

Синтез микропрограммного автомата Мура
Синтез автомата Мура по граф - схеме алгоритма также состоит из двух этапов: - получение отмеченной ГСА; - построение графа автомата. На первом из этих этапов начальная,

Минимизация микропрограммных автоматов
  Изложенный ранее метод минимизации абстрактных автоматов применяется и для минимизации полностью определённых микропрограммных автоматов. Если два состояния автоматы Мили с

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги