3.2. Асинхронные потенциальные автоматы

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

Из основной модели асинхронного потенциального автомата следует, что и

где входные информационные сигналы ЭП. Функция (3.4) называется функцией переходов ЭП типа а функцию

принято называть функцией возбуждения ЭП типа

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

Автомат находится в устойчивом состоянии, если для всех т. е., если все ЭП находятся в устойчивом состоянии. В векторной форме условие устойчивости состояния автомата можно записать так:

Автомат находится в неустойчивом состоянии, если хотя бы один ЭП находится в неустойчивом состоянии, т. е., если

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

Пусть автомат при некотором состоянии входа находится в устойчивом состоянии что будем символически записывать в виде Затем состояние входа изменяется на некоторое состояние при котором изменяются входные сигналы одного или нескольких ЭП. Автомат в этом случае переходит в неустойчивое состояние Через время на входах КС появятся новые значения выходных сигналов некоторых ЭП При этом оказываются возможными три варианта дальнейшего поведения автомата.

1. Новые значения сигналов не изменяют входных сигна-лов ни одного ЭП, а значит, в этом случае переходный процесс заканчивается через время устойчивое состояние изменяется на некоторое новое устойчивое состояние Символически такие переходы можно представить в виде

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

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

(круглыми скобками отмечены устойчивые полные состояния автомата). В первом случае длительность переходного процесса равна во втором - (задержками сигналов в КС пренебрегли). Автоматы, в которых хотя бы при одном изменении состояния входа возможно неоднократное изменение внутренних состояний, будем называть автоматами со сложными переходами. Внутреннее состояние будем называть переходным, если

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

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

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

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

переходных процессов в КС. Эти же условия с учетом величины будут приведены ниже. Очевидно, что быстродействие автоматов со сложными переходами значительно ниже быстродействия автоматов с простыми переходами.

В § 2.2 было показано, что в результате состязаний ЛЭ на выходах КС могут появляться ложные сигналы малой длительности. Так как в автомате имеются обратные связи, то ложные сигналы, поступив через ЭП на входы КС, могут привести к неправильному срабатыванию других ЭП, что может вызвать переход автомата в непредусмотренное функцией переходов внутреннее состояние — возникают состязания устойчивых состояний. Из этого следует, что КС необходимо синтезировать свободной от состязаний и что нельзя допускать несоседние изменения состояний входа.

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

Таким образом, основным назначением ЭП является задержка сигналов, задающая время, отводимое в автомате на переходные процессы в КС. Чем большее требуется время тем меньшее быстродействие будет иметь автомат. Точные значения величины времени протекания в КС переходных процессов неизвестны, но всегда можно указать некоторые пределы, в которых они заключены:

Тогда для гарантии правильной работы автомата должно выполняться соотношение

Если положить, что то необходимо выполнение условия

С учетом этих соотношений для автоматов с простыми переходами необходимо соблюдать условие

а для автоматов со сложными переходами — условие

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

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

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

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

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

Если бы даже величины задержек сигналов во всех ЭП были одинаковы, то и тогда нельзя было бы допускать одновременного изменения выходных сигналов двух или большего числа ЭП. Это объясняется тем, что при одновременном изменении нескольких входных сигналов КС в ней могли бы возникнуть критические состязания ЛЭ, вызывающие появление ложных сигналов на выходах КС.

Итак, чтобы иметь полную уверенность в том, что полученный в результате синтеза автомат будет выполнять заданные функции, следует потребовать выполнения шести условий:

1. При переходах не должны возникать автоколебательные процессы.

2. КС должна синтезироваться свободной от состязаний.

3. Состояния входа должны изменяться только на соседние.

4. Величина задержки сигналов в ЭП должна быть больше максимальной длительности переходных процессов в КС.

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

6. Должны отсутствовать критические состязания ЭП.

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

В качестве ЭП могут быть использованы линии задержки любого типа. При синтезе автоматов на интегральных микросхемах требуемую величину задержки можно получить с помощью некоторого числа последовательно включенных ЛЭ.

Будем считать, что сигналы или или изменяются одновременно, если моменты их изменения разделены интервалом, меньшим чем где — максимально возможное время переходных процессов в КС. Если никакие два сигнала из не изменяются одновременно, то для КС можно использовать модель, показанную на рис. 2.14. В этом случае основную модель автомата можно преобразовать к виду, приведенному на рис. 3.2,a ( - паразитные элементы задержки с виртуальной и постоянной задержками соответственно). Паразитные элементы задержки на входах и выходах не показаны, так как они, находясь вне цепей обратных связей, не могут оказать сколько-нибудь существенного влияния на работу автомата.

Рис. 3.2

Комбинационная схема в данной модели автомата является безынерционной, а значит, можно исключить из рассмотрения протекающие в ней переходные процессы. На этом основании часть КС, реализующую функции можно рассматривать как совокупность гипотетических безинерционных ЛЭ, на выходах которых включены элементы задержки. Из этого следует, что все понятия, введенные в §§ 2.2 - 2.4, можно использовать и для асинхронных потенциальных автоматов с той лишь разницей, что внутреннее состояние автомата определяется как набор значений выходных сигналов ЭП, а не набор значений выходных сигналов всех ЛЭ, входящих в состав ЛС. В частности, таблицы и графы переходов автоматов по своей структуре должны быть аналогичны таблицам и графам переходов ЛС.

Для анализа автоматов, так же как и для анализа ЛС, можно использовать решение функции переходов относительно устойчивых состояний. Отсутствие решения будет означать, что функция переходов задает некоторый генератор сигналов. Значит, не любая система функций (3.1) является функцией переходов асинхронного потенциального автомата.

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