|
| |
 |
Электронные компоненты Мануалы § 5.2. ПОСТРОЕНИЕ УА С ЖЕСТКОЙ ЛОГИКОЙ При использовании жесткой логики УА строится из разрозненных комбинационных логических схем и элементов памяти, так что изменение закона функционирования автомата возможно только путем переделки его схемы. Процедура построения УА заключается в выполнении следующих шагов: 1) осуществляют разметку ГСА для определения набора состояний автомата; 2) находят множество путей на ГСА для определения переходов автомата; 3) строят граф переходов автомата и его структурную таблицу; 4) осуществляют кодирование состояний автомата двоичными наборами с учетом типов используемых триггеров; 5) производят синтез и минимизацию комбинационной схемы автомата в выбранном базисе логических элементов; 6) составляют структурную схему УА. Перед выполнением описанной процедуры необходимо решить, по какой модели будет строиться автомат: по модели Мили, когда выходные сигналы y{t) автомата вырабатываются в зависимости от его внутренних состояний a{t) и от значений входных сигналов x{t): y{t) = flciit), x{t)]. (5.1) или по модели Мура, когда выходные сигналы в каждом такте зависят только от его тёкущего состояния y{t)flait)]. (5.2) Автомат Мили имеет число состояний, меньшее, чем автомат Мура, однако его комбинационная схема может оказаться сложнее. При сравнении моделей необходимо также учитывать, что у автомата Мили выходной сигнал формируется одновременно с переходом автомата в. новое состояние, что может затруднить сопряжение работы УА и OA во времени. Рассмотрим выполнение отдельных шагов процедуры построения УА. Если выбрана модель автомата Мили, то разметка ГСА осуществляется по следующим правилам: символом Ci отмечается вход вершины, следующей за начальной, а гакже вход конечной вершины; вход каждой вершины, следующей за операторной, отмечается символом а,,, причем разным вершинам присваиваются разные символы; если вход вершины отмечается, то только одним символом. Пример 5.2. Осуществим разметку ГСА (см. рис. 5.2) по указанным правилам. Всего требуется четыре символа af, Og, % и а, каждому из которых ставится в соответстние внутреннее состояние автомата, причем начальным состоянием будет являться aj. Поскольку для реализации автомата с N состояниями требуется п > logg/ триггеров, то в данном примере достаточно использовать два триггера. Для удобства перехода от размеченной ГСА к графу автомата вводится понятие пути от отметки к отметке как пути в направлении дуги ГСА, проходящего не более чем через одну операторную вершину. Путь обозначается следующим образом: Om(«m. аз)/(с, а,) Us, (5.3)  Рис. 5.4. Графы переходов управляющих автоматов, построенных по модели Мили (а) и модели Мура (б) где Х(ат, Gs) - конъюнкция логических условий Xt, соотвегствую-щих условным вершинам на этом пути, причем Xt берут в-прямой форме, если из данной вершины путь выходит по стрелке «да» (1), и в инверсной форме, если путь выходит по стрелке «нет» (0); у{ат, о») - содержимое операторной вершины, расположенной между отметками Qrn и Og. Допустимы пути, не содержащие условных вершин, а также пути, не содержащие операторной вершины. Рассматриваются все пути, кроме тех, в которых некоторое условие Xj входит как в прямой, так и в инверсной формах. Граф переходов автомата строят следующим образом. Каждой отметке а- на ГСА ставят в соответствие вершину графа, а каждому пути типа (5.3) ставят в соответствие переход из вершины От в вершину а. Переход помечают конъюнкцией логических условий Х(ат, а) и выходными сигналами у{ат, а-Если в рассматриваемом пути отсутствуют логические вершины, то полагают Х(ат, ««) = 1 (т. е. осуществляют безусловный переход); если же отсутствует операторная вершина, то полагают г/(а„, = у, где уо - пустой оператор. Пример 5.3. По ГСА (см. рис. 5.2) в соответствии с изложенной методикой построим граф переходов автомата Мили (рис. 5.4, а). Синтез автомата Мура аналогичен синтезу автомата Мили, но правила разметки ГСА заключаются в следующем: символом щ отмечаются начальная и конечная вершины ГСА; каждая операторная вершина отмечается единственным и отличным от других символом а. Пример такой разметки ГСА приведен на рис. 5.2, где соответствующие символы Ci, Сг, cze заключены в скобки. При построении графа переходов автомата Мура (рис. 5.4, б) каждому пути вида GX(c„, а,) а, (5.4) на ГСА ставят в соответствие переход автомата из состояния в состояние под действием входного сигнала Х{ат., а. При этом в каждом состоянии at автомат вырабатывает выходной сигнал У), записанный в операторной вершине ГСА, отмеченной символом а,-. Далее, исходя из имеющегося графа переходов, осуществляют шаги по построению УА в соответствии с общими правилами структурного синтеза автоматов. Особенностью УА является то, что он обычно является частичным автоматом, поскольку многие сочетания входных сигналов оказываются невозможными; это упрощает как дальнейшую процедуру синтеза УА, так и структурную схему автомата. Существенное значение имеет рациональное кодирование состояний автомата, поскольку от выбранного варианта кодирования зависит число обязательных членов в записи функций возбуждения триггеров автомата, что определяет сложность комбинационной схемы. Принципы рационального кодирования зависят от типа используемых триггеров. Так, при реализации автомата на D-триггерах используют прежде всего двоичные наборы, имеющие возможно меньшее число единиц (меньший вес), причем стремятся сопоставить наборы с наименьшим весом тем состояниям, в которых имеется наибольшее число переходов. При реализации автомата на основе J-К, Т или У?-5-триггеров принцип рационального кодирования состоит в минимизации суммарного числа изменений состояний триггеров на всех переходах автоматов. С этой целью связанные переходом состояния стремятся кодировать такими двоичными наборами, расстояние между которыми минимально. В несложных случаях задача отыскания кодирования, близкого к оптимальному, решается перебором, в более сложных - с помощью специальных алгоритмов поиска такого кодирования [8]. Задание автомата с помощью графа перехода обеспечивает наглядность (особенно при небольшом числе вершин), но запись аналитических выражений для функций возбуждения триггеров и функций выходов более удобно производить с помощью структурных таблиц (т. е. кодированных таблиц переходов и выходов). Каждая строка таблицы определяет один переход автомата. В ней указываются: исходное состояние а„, его код К{ат), состояние перехода а, его код К{а, входные сигналы Х(с„, oj, выходные сигналы F(a„, и обязательные функции возбуждения Да, Х{а,п, о., обеспечивающие изменение состояния триггеров автомата. Пример 5.4. По графу переходов автомата Мили (см. рис. 5.4, а) построим структурную табл. 5.1. В качестве элементов памяти использованы D-триггеры и при кодировании состояний - все наборы, образуемые двумя триггерами Qi и Qa. По таблице записывают уравнения сигналов возбуждения Di и выходных сигналов yj. Для этого рассматривают все строки таблицы, в которых содержится данная функция возбуждения (или данный выходной сигнал), и выписывают-конъюнкции Х(а„, а) и /С(а„), находящиеся в этих строках. Пример 5.5. По табл. 5.1 записываем следующие переключательные функции: Таблица 5.1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 [ 55 ] 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 |