13.2 Структурный синтез ца по методу графа автомата

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

Триггер с раздельными входами имеет два входа. Два входа представляют четыре различные комбинации входных кодов. Код 11 считается запрещенной при нормальной работе комбинацией, поэтому в таблице переходов рисунка 13.4б его нет. Входы R и S называются соответственно нулевым и сигнальным. Несмотря на то, что триггер имеет два выхода прямой Q и обратный , состояние триггера определяется всегда по состоянию прямого выхода. Поэтому, в таблице переходов приведен только прямой выход. Из таблицы видно, что при поступлении 1 на нулевой R вход, триггер переходит в состояние 0 независимо от того, в каком состоянии он до этого находился. Переходы Q показаны для двух его состояний, из 0 и из 1.

Аналогично, при поступлении 1 на вход S, триггер переходит в состояние 1. В качестве примера, рассмотрим граф автомата заданный рисунком 13.5.

Каждой дуге графа приписывается набор сигналов переключения, элементов памяти Rt и St, где t =1,2,3…, t - длина кодов состояний. Каждый разряд кода состояния представляется одним элементом памяти - RS триггером.

Если триггер памяти t меняет свое состояние с 0 на 1, то соответствующая дуга графа автомата отмечается символом St.

Если триггер меняет свое состояние с 1 на 0, то дуга отмечается символом Rt.

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

Систему логических функций сигналов R₁,R₂,S₁,S₂ переключения состояний и выходов y₁,y₂ получаем по заданному графу автомата следующим образом.

Функция Rt (или St) получается как дизъюнкция минтермов, состоящих из переменных состояния исходящего узла и входных переменных, приписанных к исходящей дуге этого узла.

Аналогичным образом получается функция выхода у_і, где і=1,2,..n.

Тогда, система логических функций определяется в виде:

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

13.3 Метод синтеза ца по граф–схеме алгоритма

Рассмотренные методы структурного синтеза автоматов, особенно с использованием таблиц переходов и выходов, являются универсальными, но они пригодны для сравнительно небольших автоматов. Развитие систем автоматизированного проектирования требует новых подходов и методов синтеза цифровых автоматов.

Важнейшим аспектом формализации синтеза цифровых устройств является создание языка, для описания алгоритмов функционирования ЦУ, допускающего переход к математической модели автомата. С этих точек зрения наиболее приемлемым языком является язык граф - схемы алгоритмов (ГСА).

Возможность использования граф - схемы алгоритма для описания работы автомата поясним на примере рисунка 13.6.

В этом графе множество входных переменных Х составляет пять условных логических переходов Х1…Х5 и множество выходных функций Y определяет четыре микрооперации У1…У4. Кроме того, работа автомата производится по тактовым импульсам (ТИ) машинного дискретного времени (на схеме не показанны).

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

Для рассмотрения алгоритма работы автомата, будем двигаться от начального операторного блока по путям направления дуг графа, учитывая равенства 1 или 0 выходов условных операторов. Так путь Х1, Х2 ведет к операторной вершине У2, путь Х1,Х2 –к вершине У1,У4 и путь Х1-к вершине У1,У2,У3. Это определяет работу автомата следующим образом.

Если в начальный момент на входы поступят переменные Х1=Х2=1, то по приходу ТИ устройство перейдет, независимо от остальных входных переменных, в состояние, при котором на выходе У2 появится сигнал равный 1. На остальных выходах сигналы будут равны 0, т.е. на выходах У1, У2, У3, У4 будет код 0100 тогда, когда на вход автомата поступит код 11ххх, где х может принимать безразличное значение 0 или 1.

Аналогично, при подаче в начальный момент на вход кода 0хххх, на выходе появится код 1110, а при входной комбинации 10ххх-код1001. Таким образом, можно проследить работу всего автомата. Так, например, входной сигнал 0хх11 приводит автомат в конечное состояние по пути Х1У1,У2,У3Х4Х5Конец.

Интересными в этой граф-схеме алгоритма являются следующие ситуации:

-после оператора У1 следует оператор У4 без всяких условий. Это означает, что после выходного кода 1000 на следующем такте появится выходной код с сигналами У1=У4=1;

-после операторной вершины У2 идет условная вершина Х3 с логическим условием цикла по 0 значению. На выходе устройства сигнал У2 не появится пока Х2 не примет значение 1.

-если в операторной вершине записи нет, то это означает 0 выходной сигнал.

Синтез цифрового автомата по методу граф - схемы алгоритма выполняется в следующей последовательности:

-составление содержательного графа – схемы алгоритма с записью логических условий и микроопераций в содержательных терминах;

-кодирование содержательного графа -схемы алгоритма символами условий Хі и микроопераций Уі;

-построение отмеченного графа -схемы алгоритма;

-построение графа автомата;

-получение системы логических функций;

-построение логической схемы.

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

Отмеченный граф - схемы алгоритма получаем по следующим правилам:

-символом а₁ отмечаем вход вершины, следующей за начальной, а также вход конечной вершины;

-символом а_і отмечаются все вершины следующие за операторными, где і =2,3,4….k;

-входы всех вершин, следующих за операторными, должны быть отмечены;

-вход вершины отмечается только один раз.

Отмеченный граф - схемы алгоритма служит основой для перехода к графу автомата.

После получения отмеченного графа алгоритма, строим граф частичного автомата А с состояниями а₁,….,а_r, где а₁ начальное и конечное состояние. Переходы и выходные сигналы в этом автомате определяются как пути переходов из отмеченных состояний, например аm в состояние аs. Каждому пути перехода вида а_mY(a_m, a_s) - a_s (a_m, a_s a₁,…,a_M) ставим в соответствие переход автомата А из состояния а_m в состояние a_s.

Приписав каждой дуге графа операторы условий Хі и выходы Yi, получим частичный граф автомата. Дальнейшие этапы синтеза рассматривались ранее.

В последующем изложении мы рассмотрим примеры применения на практике канонических методов структурного синтеза цифровых устройств в системах автоматизированного проектирования (САПР)