Абстрактный автомат Мили
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
но, ветвь, выходящая из вершины Yi, помечается символом zi. Наконец, если клетка YiYi пустая, то непосредственно за микрокомандой Yi, должна отрабатываться следующая микрокоманда, определяемая информацией, записанной в другие клетки строки Yi. (При этом на ГСА вслед за операторной вершиной Yj ждущая вершина уже не включается).
). Если в строке Yi некоторая клетка YiYj не пуста и в ней записано некоторое условие zi, то на ГФ проводится ветвь из вершины Yi в вершину Yj, эта ветвь помечается символом zi и т. д.
Рис. 2.1. Граф функционирования МПА.
. Составление граф-схемы алгоритма ГСА по графу функционирования.
Если на ГСА отметить некоторыми символами состояния автомата, то будет получена так называемая отмеченная ГСА. Отметка осуществляется согласно следующим правилам:
) Вход вершины, следующей за начальной операторной вершиной, обозначается некоторым символом, например а0.
) Этим же символом отмечается вход конечной вершины, если она существует (в данном случае такой вершины нет, так как заданный граф циклический, т. е. замкнутый).
3) Входы всех вершин, следующих за операторными, помечаются различными символами, например а1, а2, а3 ...
Рис. 2.2. Граф-схема алгоритма ГСА.
3. Построение абстрактной таблицы переходов.
В абстрактной таблице переходов пять столбцов: номер строки N, текущее аn и будущее аn+1 состояния, входные {Z} и выходные {Y} сигналы. Каждая строка таблицы соответствует одному пути перехода автомата. Если необходимо сохранить некоторое состояние МПА неизменным, то аn и аn+1 принимаются равными.
Таблица. 2.1.
Nanan+1{Z}{Y}1a0a0y02a0a1z0y3(t3)3a1a21y1(t1)4a2a31y6(t6)5a3a41y4 (t4,z4)6a4a4z4y4 (t4,z4)7a4a5y118a5a31y6(t6)
Структурный синтез МПА
1. Рациональное кодирование состояний автомата.
Максимальный индекс аi равен 5, следовательно, необходимо не менее трех двоичных разрядов (Q4, Q2, Q1) для кодирования всех аi.
Правило кодирования состояний аi с целью минимизации величины ? К: чем чаще встречается ai в столбце аn+1 абстрактной таблицы переходов, тем с меньшим числом единиц должна использоваться комбинация для кодирования этого состояния.
Таблица. 2.2.
Состояние aiЧисло повторенийK(an+1)Q4Q2Q1a01011a11001a21010a32000a42100a51101
. Построение структурной таблицы переходов (табл. 2.3.).
Сравнивая текущее значение Qi в кодовой комбинации k(an) с будущим значением Qi в комбинации k(an+1), находим сигналы переходов ?.
Таблица. 2.3.
Nanan+1{Z}{Y}K(an)K(an+1)?Q4Q2Q1Q4Q2Q1Q4Q2Q11a0a0y00110110112a0a1z0y3(t3)0110010-13a1a21y1(t1)0010100+-4a2a31y6(t6)0100000-05a3a41y4 (t4,z4)000100+006a4a4z4y4 (t4,z4)1001001007a4a5y1110010110+8a5a31y6(t6)101000-0-
. Вывод логических выражений для функций выходов и переходов.
Для нахождения перечисленных функций целесообразно составить промежуточные контермы КN, где индекс N соответствует номеру строки. Контермы составляются по абстрактной и структурной таблицам переходов следующим образом: для N-й строки образуется конъюнкция из сигналов Qi (в текущий момент времени) и входных сигналов zi, взятых со знаками инверсии либо без них.
Функции возбуждения будем искать для D - триггеров, объединяя контермы, для которых операторы ? помечены знаками 1 и +.
Таблица. 2.4.
KnКонтермыФункции выходовK1y0=K1; y1= K3 ;y3 =K2 ;= K5 v K6 ;y6= K4 v K8 ;
y11= K7 ;K2K3K4K5Функции возбужденияK6D4= K5 v K6 v K7;
D2= K1 v K3;
D1= K1 v K2 v K7;K7K8
Схемная реализация МПА
Обратимся к табл.2.4, где приведены функции выходов МПА и функции возбуждения триггеров. Из этой таблицы видно, что произвольная функция уi, Tj может быть представлена как дизъюнкция ряда контермов. Таким образом, матричная схема МПА должна содержать две матрицы (рис.2.3): M1 - для формирования контермов и M2 - для выработки выходных величин в виде дизтермов.
Кроме того, структурная схема на рис.2.3 содержит триггерный регистр Рг, объект управления ОУ, цифровую линию задержки ЦЛЗ (таймер), генератор прямоугольных импульсов ГПИ и счетчик числа микрокоманд СТМ.
Матрица M2 вырабатывает микрокоманды {У}, управляющие ОУ, и функции возбуждения {А} - триггерами Рг. Совокупность сигналов {Z} характеризует состояние ОУ, а совокупность сигналов {Q} - состояние элементов памяти МП А. Из перечисленных сигналов матрица М1 формирует контермы {К}. ЦЛЗ управляется кодами {В}, соответствующими отрабатываемой в данный момент микрокоманде, так что импульсы f от ГПИ проходят на вход синхронизации С регистра с требуемой задержкой ti.
Рис. 2.3. Структурная схема МПА.
Функциональная схема МПА представлена на рис.2.4. В любом рабочем состоянии МПА лишь на одном выходе матрицы M1, и, следовательно, на одном входе матрицы M2 может действовать единичный сигнал. Поэтому первую из них назовем матрицей-дешифратором, а вторую - матрицей-шифратором. Регистр образован из трех D-триггеров. ЦЛЗ формирует временные интервалы заданной длительности ti, требуемой для отработки микрокоманд yi. ЦЛЗ управляется непосредственно сигналами у1, y3, y4, y6.
Совокупность сигналов {Z} оповещает о состоянии ОУ и поступает по цепи обратной связи, как и совокупность сигналов {Q} на входные (вертикальные) шины M1; из перечисленных сигналов {Q}, {Z} образуются контермы Ki на горизонтальных шинах матриц.
Рис. 2.4. Функциональная схема МПА на базе ПЛМ.
.3 Синтез счётчика числа микрокоманд
Абстрактный синтез счётчика
. Выбор количества триггеров. Т.к. N=10, то требуется y=]log210[=4 триггера. Обозначим их А, Б, В, Г.
. Кодирование внутренних состояний.
Рис. 2.5. Граф переходов счетчика
С помощью четырёх триггеров можно получить Nmax=2q=16 внутренних состояний КА. В данном случае 6 из них являются л