Структурный синтез управляющего автомата

При заданных типах элементов памяти структурный синтез управляющего автомата сводится к выполнению следующих проектных операций:

- кодирование внутренних состояний;

- формирование функций внешнего перехода;

- формирование и минимизация функций возбуждения элементов памяти и функций выходов;

- построение комбинационной схемы автомата в выбранном базисе логических элементов и функциональной схемы автомата.

3.2.1 Кодирование внутренних состояний

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

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

При кодировании состояний каждому состоянию устройства должна быть поставлена в соответствие некоторая кодовая комбинация. Число разрядов кода выбирается из следующих соображений: если число состояний равно S, то для обеспечения s кодовых комбинаций требуется k-разрядный код, где k-минимальное целое число, при котором выполняется неравенство s ≤ 2 ^k.

При двоичном кодировании состояний автомата число триггеров в его схеме равно числу разрядов кода и вычисляется по формуле:

n = k = ù log₂ S é, где

S – число состояний автомата;

ù é - округление в большую сторону.

Обычно выполняют экономичное кодирование состояний, которое обеспечивает наиболее простую реализацию комбинационной схемы (КС) автомата. Используется метод соседнего кодирования, основанный на поиске соседних состояний и назначении им соседних кодов.

3.2.2 Формирование функций внешнего перехода или построение графа автомата

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

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

3.2.3 Формирование функций возбуждения и выходов

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

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

Таблица 1 – Таблица переходов триггеров

Q(t)®Q(t+1)	D	T	S	R	J	K
0 → 0				x		x
0 → 1						x
1 → 0					x
1 → 1			x		x

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

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

3.2.4 Построение функциональной схемы управляющего автомата

На основе полученных функций возбуждения и функций выходов можно построить функциональную схему микропрограммного автомата. На практике чаще всего используют базисы Буля (элементы И, ИЛИ, НЕ), Шеффера (элементы И-НЕ) и Пирса (элементы ИЛИ-НЕ). Качество решения задачи синтеза КС оценивают по затратам оборудования и быстродействию.

При разработке схем на основе конкретной эле­ментной базы количество оборудования обычно измеряется числом корпусов (модулей), используемых в схеме. В теоретических разработках ориентируются на произвольную элементную базу и поэтому для оценки затрат оборудования используется оценка сложности схем по Квайну. Сложность (цена) схемы по Квайну определяется суммарным числом входов логических элементов в составе схемы. При такой оценке единица сложности, т. е. единица оборудования - один вход логического элемента. При этом цена инверсного входа обычно принимается равной двум.

Такой подход к оценке сложности схем является результативным по следующим причи­нам. Во-первых, сложность схемы легко вычисляется по булевым функциям, на основе которых строится схема: сложность схемы равна сумме числа букв в дизъюнктивной нормальной форме, причем букве со знаком отрицания соответствует цена два, и числа знаков дизъюнкции, увеличенного на единицу для каждого дизъ­юнктивного выражения. Во-вторых, все классические методы мини­мизации булевых функций обеспечивают минимальность схемы именно в смысле цены схемы по Квайну.

И наконец, практика показывает, что схема, минимальная в смысле цены по Квайну, обычно реализуется наименьшим числом конструктивных элемен­тов - корпусов.

Быстродействие схемы оценивается максимальной задержкой сигнала при прохождении его от входа схемы к выходу, т. е. определяется промежутком времени от момента поступления вход­ных сигналов до момента установления соответствующих значений выходных сигналов. Задержка сигнала кратна числу элементов, через которые проходит сигнал от входа к выходу схемы. Поэтому быстродействие схемы характеризуется значением dτ, где τ - задержка сигнала на одном логическом элементе. Значение d определяется количеством уровней комбинационной схемы, кото­рое рассчитывается следующим образом. Входам комбинационной схемы присваивается уровень 0. Элементы, связанные только с входами схемы, относятся к уровню 1. Элемент относится к уровню d, если он связан по входам с элементами уровней d-1, d-2,..., 0. Максимальный уровень элементов определяет коли­чество уровней комбинационной схемы.

Дата добавления: 2015-05-09