от параметров элементов, образующих структуру автомата. В ряде случаев автомат работает так, что на протяжении одного и того же интервала времени Т может быть несколько неустойчивых тактов. Поэтому должно выполняться не равенство Ттгпё>Ттах, чтобы при любом конечном числе г неустойчивых ТаКТОВ ГтахГ<Ттгп Функционирование, или поведение автомата при заданных множествах {рг}, {Л}, {лг} и начальном внутреннем состоянии хо, полиостью детерминировано и определяется функциями переходов и выходов. Функция переходов устанавливает зависимость внутреннего состояния автомата в следующий момент времени (t+l) от состояния входа и внутреннего состояния в настоящий момент времени t:

х(<+1)=<р[р(0; и (*)]•(З-П

Функция выходов устанавливает зависимость состояния выхода автомата от состояния входа и внутреннего состояния автомата в один и тот же момент времени t:

М*) = Г[р(/); *(*)]•<3.2)

В выражениях (3.1) и (3.2) p(t)-состояние входа автомата в момент (такт) t, принимающее одно из значений {pi, рл};

Х(Л) -состояние выхода автомата в момент времени t, принимающее одно из значенийКк}, к

(t) -внутреннее состояние автомата в момент времени t, принимающее одно из значений {яо, КБ xs-

i}.

Часто удобно использовать понятие «состояние автомата», которое, в отличие от внутреннего состояния, иногда называют полным. Состояние автомата р. в момент времени t определяется внутренним состоянием и состоянием входа автомата в этот же момент времени. Заметим, что множество состояний {\и\, [iz, [лд} (причем u(t}<={u.m}) конечного автомата всегда конечно, так

как R=NS.

Таким образом, внутреннее состояние автомата в момент времени ;+! и состояние выхода автомата в момент t определяется состоянием автомата в момент времени t:

*(/+1)=<р[ц(*)]; мо=Г[ц(0].С3-3); (З-4)

Задавая для всевозможных пар р(0 и я (0 то или иное значение х(/+1) и то или иное значение K(t), определяем соответственно функции переходов и выходов. Автоматы, для которых функции переходов и выходов определены на всех парах [p(it); я (О], называют полностью определенными или полными. Автоматы, для которых функции выходов или переходов определены не на всех этих парах, называют недоопределенными. При этом автоматы, у которых для какой-либо пары [р(0; х(0] функция выходов определена, а функция переходов не определена, обычно не рассматриваются.

Состояние и. (t) недоопределенного автомата, соответствующее паре [(>(t); K(t}], на которой функция переходов не определена, называют неиспользуемым. Остальные состояния будем называть используемыми. Если на каком-либо используемом состоянии автомата функция выходов не определена, то будем говорить, что ему соответствует безразличное состояние выхода *. Поведение асинхронного автомата определяют следующими уравнениями:

x(*+lj=l>[p(f+l); к(01;(3.5)

Ь(/+П=ф[р(* + 1); x(f+i)l.

Первое из этих уравнений показывает, что внутреннее состояние автомата в момент времени t+1 определяется состоянием входа автомата в этот же момент и внутренним его состоянием в предыдущий момент. Заметим, что в синхронных автоматах внутреннее состояние определялось состоянием входа в предшествующий момент времени [см. выражение 3.1)].

В классе асинхронных автоматов также рассматриваются полные и недоопределенные автоматы.

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

Заметим, что в частном случае может быть безразличным те состояние выхода, а лишь один или несколько выходных сигналов, набор значении которых определяет данное состояние выхода.

Время t при этом часто опускается.

Следует отметить еще один частный тип автоматов, а именно таких автоматов, для которых {pi}, т. е. множество состояний входа, состоит лишь из одного элемента pi. Этот случай возможен тогда, когда автомат не имеет входов или, что то же самое, состояние его входа имеет неизменное значение pi. Такие автоматы называют автономными. Все остальные автоматы относятся к неавтономным. Поскольку далее рассматриваются только эти автоматы, слово «неавтономный» опускается.

Все автоматы можно разделить на автоматы общего вида (универсальные) и автоматы того или

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

Микропрограммный автомат (МА) может рассматриваться в качестве формальной модели ЦБУ дискретного устройства с концентрированными функциональными связями (см. рис. 1.4,6). Общая структура микропрограммного автомата изображена на рис. 3.3.

Микропрограммный автомат вырабатывает последовательность воздействий 2л; и Zp/ для включения операторных функциональных блоков (ОФБг) и логических функциональных блоков (ЛФБд) соответственно.

При воздействии на ЛФБ, вырабатывается одно из двух возможных значений проверяемого параметра р„ которое поступает на вход pj микропрограммного автомата. Следовательно, на вход pj воздействие может поступить лишь в том случае, если имеется воздействие на выходе 2р/. Поэтому все входы МА разделяются на две группы: внешние /-i, Гп и внутренние pi, рт- Выходы лрг ZPm иззовем внутренними, a zaa, •••> ZAtt-внешними.

Зависимость поступления воздействий на внутренние входы микропрограммного автомата от его выходных воздействии - одна из основных особенностей микропрограммного автомата. Второй основной особенностью МА является то, что при неизменном состоянии внешнего входа автомат вырабатывает последовательность сигналов на основных выходах.

Следует заметить, что в частном случае в микропрограммном автомате могут отсутствовать ЛФБ. Тогда микропрограммный автомат при неизменном состоянии внешнего входа вырабатывает «жесткую» последовательность воздействий на ОФБ, а при отсутствии внешних входов - лишь одну из таких «жестких» последовательностей.

Набор значений сигналов на входах т-i, Гп образует состояние внешнего входа Ri<=:{Ri, Ri}, а на входах pi, pm - состояние внутреннего входа p]a{n, Pi, Рм}, где N - состояние внутреннего входа при отсутствии воздействий на всех внутренних выходах Zp, грл. Пара [Ri; Pj] образует состояние (полное) входа микропрограммного автомата - pv- При L=l микропрограммный автомат называется автономным.

Состоянием внешнего выхода является набор значений сигналов на выходах гд, внутреннего выхода - набор значений сигналов на выходах 2р,,.., ZpA.

Микропрограммный автомат может иметь S внутренних состояний (SЛsl). При 5=1 микропрограммный автомат, очевидно, становится комбинационным. При 5>1 среди внутренних состояний МА кроме начального состояния х(0)=хо выделяют некоторое число конечных состояний.

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

Если класс МА определяется особенностью его алгоритма функционирования при взаимодействии с функциональными блоками, то класс автоматов с распределенной задержкой - особенностью применяемого элементного базиса. В автомате с распределенной задержкой каждый элемент логического преобразователя (ЛП) кроме реализации логической функции / обеспечивает также задержку т (рис. 3.4,а). Из модели данного элемента, изображенной на рис. 0.4,6, видно, что сигнал на входе элемента задержки т формируется только одним логическим элементом /, который иногда называют модулем. Таким образом, при представлении автомата с распределенной задержкой в виде модели с ЛП и элементом памяти (ЭП) в виде задержки т получим схему, изображенную на рис. 3.5. Таким образом, характерной особенностью ЛП модели автомата с распределенной задержкой является то, что в нем имеется только один каскад логических элементов, а объем памяти автомата определяется совокупностью задержек всех логических элементов ЛП. Автоматы с распределенной задержкой получают все большее распространение в связи с применением интегральных схем для по строения быстродействующих дискретных устройств.

, zaa, а состоянием

3.2. Автоматные языки описания условий работы проектируемого дискретного устройства

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

Для того чтобы задать алгоритм функционирования автомата необходимо задать его функции переходов и выходов. Задание функции переходов означает задание определенного перехода из внутреннего состояния -Лг во внутреннее состояние щ (не исключается случай 1=/) при воздействии состояния входа ру. Задание функции выходов означает, что каждой паре (ру; к<) сопоставлено состояние выхода Ki автомата.

Часто говорят, что задание функций переходов и выходов означает задание однозначных отображений множества пар {[р„; Кг]} в множества {к,} и {Хг}. Языки, позволяющие таким образом задать функции переходов и выходов автомата, будем называть стандартными. К стандартным языкам относятся, например, таблицы переходов, матрицы переходов, диаграммы переходов, таблицы включений и т. д. Из всех известных стандартных языков в последнее время в качестве языка задания автомата общего вида основное применение нашли таблицы переходов.

Наряду со стандартными существуют и другие языки задания алгоритма функционирования релейного устройства, с помощью которых могут быть заданы отображения последовательностей состояний входа (входных последовательностей) в последовательности состояний выхода (в выходные последовательности), т. е. отображения множества слов во входном алфавите в множестве слов в выходном алфавите. Функция же переходов с помощью таких языков в явном виде не задается.

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

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

Все известные начальные языки предназначены для описания в каком-либо виде условий работы автомата, заданных множеством пар последовательностей (в том числе и бесконечных) состояний входа и выхода автомата, т. е. множеством последовательностей «вход - выход». Каждая пара такого множества включает входную последовательность, т. е. входное слово, буквами которого являются состояния входа автомата, и однозначно сопоставленную ей выходную последовательность, т. е. выходное слово, буквами которого являются состояния выхода автомата. Например, условиями работы задана следующая последовательность «вход-выход»:

P"Ki, р.2л2> И~> рзлз-

Тогда если множеством состояний выхода автомата является множество {Ki, Кч, U, то построенный по этим условиям автомат будет реализовать одну из следующих трех последовательностей:

КГ Р2Л2> PK1, РзЛз;

Р1Л.1,

Р2Л2 Р1Л2> рзл-з PKli ?2Л2» Р1Л3> рзлз-

При задании условий работы автомата, служащего моделью реального устройства, часто удобно говорить не о состояниях входа и выхода, а о последовательности смены значения сигналов на входах и выходах автомата. Тогда вместо последовательности «вход - выход» будет задаваться последовательность значений сигналов на входах и выходах автомата. Для задания такой последовательности значений обычно используются первоначальные таблицы включений [I].

Пример первоначальной таблицы включений для счетчика на пять импульсов приведен на рис. 3.6.