3.4. Задание асинхронных потенциальных автоматов таблицами и графами переходов

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

Рис. 3.17

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

Для задания автомата с помощью таблицы переходов необходимо определить его функции переходов и выхода (3.3.):

каждой паре следует поставить в соответствие некоторые знамения функций

Данное соответствие довольно просто задается табличным методом.

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

Таблица 3.7. (см. скан) Табличное задание функций переходов и выхода автомата

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

Интервал времени, в течение которого автомат находится

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

при переходных процессах (в неустойчивых состояниях) на выходах не должны появляться ложные сигналы малой длительности;

реакция выходных сигналов на изменение состояний входа должна иметь минимальное запаздывание.

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

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

где при простых переходах и при сложных переходах. Крайним парам соответствуют устойчивые состояния, т.е.

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

с одним переходным состоянием и сложный переход

с двумя переходными состояниями.

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

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

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

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

У автомата, задаваемого табл. 3.7, должно быть не менее двух физических входов и не менее двух физических выходов так как имеются четыре состояния входа и три состояния выхода 27, т.е. для данного автомата можно положить, что

где или или 1.

Таблица 3.8. (см. скан) Упрощенный вариант табл. 3.7

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

Для простоты в таблицах переходов вместо состояний и будем указывать значения кодирующих сигналов а внутренние состояния автомата будем обозначать только одним индексом (табл. 3.8).

После задания автомата таблицей переходов следует решить еще две важные задачи: произвести минимизацию числа его

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

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

Рис. 3.18

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

(переходные состояния 3 и 2 неустойчивы для состояния входа 00). По графу переходов, показанному на рис. 3.18,б, полезно самостоятельно составить временные диаграммы для входного и трех внутренних сигналов (ответ см. на рис. 3.20).

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

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

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