|
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
|
|
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
Структурный синтез управляющего автомата
При заданных типах элементов памяти структурный синтез управляющего автомата сводится к выполнению следующих проектных операций: - кодирование внутренних состояний; - формирование структурной таблицы или таблицы функционирования автомата; - формирование и минимизация функций возбуждения элементов памяти и функций выходов; - построение комбинационной схемы автомата в выбранном базисе логических элементов и функциональной схемы автомата.
3.2.1 Кодирование внутренних состояний
Структурный синтез начинается с двоичного кодирования внутренних состояний автомата - установления взаимно-однозначного соответствия между состояниями автомата и комбинациями состояний элементов памяти. Анализ структурного синтеза автоматов показывает, что различные варианты кодирования состояний автомата приводят к различным выражениям функций возбуждения и функций выходов, в результате чего оказывается, что сложность комбинационной схемы автомата существенно зависит от выбранного кодирования. Как правило, нахождения вариантов кодирования состояний, которые обеспечивают ослабленную функциональную зависимость для функций возбуждения, дает более экономичную схему, чем при других типах кодирования. При кодировании состояний каждому состоянию устройства должна быть поставлена в соответствие некоторая кодовая комбинация. Число разрядов кода выбирается из следующих соображений: если число состояний равно S, то для обеспечения s кодовых комбинаций требуется k-разрядный код, где k-минимальное целое число, при котором выполняется неравенство s ≤ 2 k. При двоичном кодировании состояний автомата число триггеров в его схеме равно числу разрядов кода и вычисляется по формуле:
n = k = ù log2 S é, где
S – число состояний автомата; ù é - округление в большую сторону.
Обычно выполняют экономичное кодирование состояний, которое обеспечивает наиболее простую реализацию комбинационной схемы (КС) автомата. Используется метод соседнего кодирования, основанный на поиске соседних состояний и назначении им соседних кодов.
3.2.2 Формирование структурной таблицы автомата
Структурную таблицу или таблицу функционирования автомата можно получить непосредственно из таблицы переходов-выходов и таблицы кодов состояний. Для этого символы состояний необходимо заменить соответствующими кодами и установить порядок следования строк и столбцов. Структурная таблица автомата содержит графы, в которые заносятся данные текущего состояния, значения входных условий, данные следующего состояния, в которое должно перейти устройство, и выходные сигналы комбинационного узла. Для наглядности выполняемых преобразований структурная таблица автомата заполняется с учетом функционирования заданного элемента памяти.
Таблица 1 – Таблица переходов триггеров
3.2.3 Формирование функций возбуждения и выходов
В структурной таблице автомата отображаются значения функций возбуждения и выходов для всех рабочих наборов. С целью упрощения их аналитического представления используют карты Карно и выполняют их минимизацию. Минимизацию функций целесообразно выполнять по критериям оптимальности совместной минимизации: минимум числа различных термов (конъюнкций или дизъюнкций), используемых для покрытия всех функций системы и минимум рангов этих термов. При этом один и тот же терм может входить в покрытие нескольких функций.
3.2.4 Построение функциональной схемы управляющего автомата На основе полученных функций возбуждения и функций выходов можно построить функциональную схему микропрограммного автомата. На практике чаще всего используют базисы Буля (элементы И, ИЛИ, НЕ), Шеффера (элементы И-НЕ) и Пирса (элементы ИЛИ-НЕ). Качество решения задачи синтеза КС оценивают по затратам оборудования и быстродействию. При разработке схем на основе конкретной элементной базы количество оборудования обычно измеряется числом корпусов (модулей), используемых в схеме. В теоретических разработках ориентируются на произвольную элементную базу и поэтому для оценки затрат оборудования используется оценка сложности схем по Квайну. Сложность (цена) схемы по Квайну определяется суммарным числом входов логических элементов в составе схемы. При такой оценке единица сложности, т. е. единица оборудования - один вход логического элемента. При этом цена инверсного входа обычно принимается равной двум. Такой подход к оценке сложности схем является результативным по следующим причинам. Во-первых, сложность схемы легко вычисляется по булевым функциям, на основе которых строится схема: сложность схемы равна сумме числа букв в дизъюнктивной нормальной форме, причем букве со знаком отрицания соответствует цена два, и числа знаков дизъюнкции, увеличенного на единицу для каждого дизъюнктивного выражения. Во-вторых, все классические методы минимизации булевых функций обеспечивают минимальность схемы именно в смысле цены схемы по Квайну. И наконец, практика показывает, что схема, минимальная в смысле цены по Квайну, обычно реализуется наименьшим числом конструктивных элементов - корпусов. Быстродействие схемы оценивается максимальной задержкой сигнала при прохождении его от входа схемы к выходу, т. е. определяется промежутком времени от момента поступления входных сигналов до момента установления соответствующих значений выходных сигналов. Задержка сигнала кратна числу элементов, через которые проходит сигнал от входа к выходу схемы. Поэтому быстродействие схемы характеризуется значением dτ, где τ - задержка сигнала на одном логическом элементе. Значение d определяется количеством уровней комбинационной схемы, которое рассчитывается следующим образом. Входам комбинационной схемы присваивается уровень 0. Элементы, связанные только с входами схемы, относятся к уровню 1. Элемент относится к уровню d, если он связан по входам с элементами уровней d-1, d-2, ..., 0. Максимальный уровень элементов определяет количество уровней комбинационной схемы.
Пример синтеза управляющего автомата для заданного алгоритма
По заданной содержательной схеме алгоритма в микрооперациях разработать функциональную схему управляющего автомата Мура (Мили) (рисунок 9), в качестве элементов памяти использовать D-триггеры, комбинационную схему реализовать на логических элементах. Дать оценку конструктивной сложности ЦА.
Рисунок 9 – Схема алгоритма в микрооперациях
1) Заменим наборы микроопераций О1, О2, О3, О4 на коды микрокоманд Y1, Y2, Y3, Y4. В результате получим кодированную ГСА в микрокомандах. 2) Построим отмеченную граф-схему алгоритма (ГСА) управляющего автомата Мура (Мили) В соответствии с требованиями предъявляемыми к разметке состояний цифрового автомата Мура (Мили) получаем отмеченную ГСА цифрового автомата (рисунок 10, а), б)).
а) б)
а - для автомата Мура, б - для автомата Мили.
Рисунок 10 – Отмеченные граф-схемы
3) Построение графа функционирования автомата Согласно отмеченной граф-схеме алгоритма управляющего автомата Мура (Мили) строим граф функционирования автомата (рисунок 11, а), б)).
а)
б) а - для автомата Мура, б - для автомата Мили.
Рисунок 11 – Графы функционирования автоматов 4) Кодирование состояний устройства Число разрядов кода состояния соответствует числу элементов памяти и определяется по формуле: k = ù log2 S é , где k – число разрядов (число элементов памяти) S – число внутренних состояний; ù é - округление в большую сторону. В нашем случае для автомата Мура число состояний S = 6. Количество разрядов кода состояния (число элементов памяти): K = ]log2S[ = ]log26[ = 3. Для автомата Мили число состояний S = 5. Количество разрядов кода состояния (число элементов памяти): k = ]log2S[ = ]log25[ = 3. Таблицы кодировки состояний для автомата Мура и автомата Мили приведены на рисунке 12, а) и б) соответственно.
а) б)
а - для автомата Мура, б - для автомата Мили.
Рисунок 12 - Таблицы кодировки состояний
5) Построение структурной таблицы автомата По отмеченной ГСА или графу функционирования автомата, таблицы кодировки состояний автомата и таблицы переходов триггеров строим структурную таблицу автомата.
Таблица 2 – Таблица переходов D-триггера
Таблица 3 – Структурная таблица автомата Мура
Таблица 4 - Структурная таблица автомата Мили
6) Минимизация функций возбуждения элементов памяти и функций выходов Из структурной таблицы автомата Мура (Мили) получаем систему логических уравнений для цифрового автомата Мура (Мили).
Система логических уравнений для цифрового автомата Мура:
Система логических уравнений для цифрового автомата Мили:
Из системы логических уравнений для цифрового автомата Мура получаем полное множество конъюнкций для данного автомата:
Из системы логических уравнений для цифрового автомата Мили получаем полное множество конъюнкций для данного автомата:
Из полного множества конъюнкций получаем таблицу покрытия конъюнкциями системы логических уравнений.
Таблица 5 - Таблица покрытия конъюнкциями для цифрового автомата Мура
Таблица 6 - Таблица покрытия конъюнкциями для цифрового автомата Мили
7) Построение функциональной схемы управляющего автомата Мура (Мили) На основе полученных функций возбуждения и функций выходов строим функциональную схему управляющего автомата Мура (Мили).
Рисунок 13 - Функциональная схема управляющего автомата Мура
Рисунок 14 - Функциональная схема управляющего автомата Мили
8) Оценка конструктивной сложности управляющего автомата Мура (Мили): - определение конструктивной сложности автомата Мура методом Квайна - число входов логических элементов: 59. - число ярусов сигнала на самом длинном пути от входа к выходу: 4. - количество элементов необходимых для построения функциональной схемы:
Таблица 7 – Оборудование для реализации автомата Мура
- определение конструктивной сложности автомата Мили методом Квайна - число входов логических элементов: 51. - число ярусов сигнала на самом длинном пути от входа к выходу: 4. - количество логических элементов необходимых для построения функциональной схемы:
Таблица 8 – Оборудование для реализации автомата Мили
Популярное:
|
Последнее изменение этой страницы: 2016-08-31; Просмотров: 776; Нарушение авторского права страницы
