АСИНХРОННЫХ АВТОМАТОВ ТЕОРИЯ

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

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

Т. о., в А. а. т. рассматриваются модели устр-в, обладающих более сложным поведением, чем конечные автоматы. Однако эта сложность в реальных АА считается нежелательной помехой, поскольку она проявляется в зависимости переходных процессов от соотношения временных характеристик элементов, а такая зависимость ввиду неизбежного разброса этих характеристик может оказаться недетерминированной. Такие недетерминированные переходные процессы (называемые состязаниями или гонками) могут приводить к ошибкам и сбоям в работе автомата. Поэтому важной практической задачей А. а. т. является устранение состязаний, т. е. синтез АА, в которых переходы из одного устойчивого состояния в другое под действием данного входного сигнала происходят однозначно и не зависят от величин задержек элементов и длительностей входных тактов. Такие АА функционируют как обычные конечные автоматы. Состязания устраняют с помощью спец. «противого-ночных» методов кодирования состояний абстрактных автоматов, введения дополнительных задержек в некоторых цепях обратной связи и построения схем с заранее заданными свойствами, гарантирующими отсутствие состязаний. Лит.: Кузнецов О. П. Об асинхронных логических сетях. «Проблемы передачи информации», 1961, в. 9; Лазарев В. Г., Пийль Е. И. Синтез асинхронных конечных автоматов. М., 1964; Рогинский В. Н. Динамика работы дискретных автоматов с линейными задержками. «Проблемы передачи информации», 1967, т. 3, в. 1; Якубайтис 3. А. Синтез асинхронных конечных автоматов. Рига, 1970; Колдуэлл С. Логический синтез релейных устройств. Пер. с англ. М., 1962; Миллер Р. Теория переключательных схем. Пер. с англ., т. 2. М., 1971. О. П. Кузнецов.