Cтраница 1
Асинхронный автомат представляется таблицей переходов. Она имеет строку, соответствующую каждому внутреннему состоянию Qt, и столбец X /, соответствующий каждому состоянию входа. Для каждой пары внутреннего состояния и входного символа таблица переходов указывает следующее внутреннее сотояние и выходной символ. Считается, что если f ( Qi, Xj) - Qi, то Qi является установившимся состоянием при входе X / и в табл 4.11 заключается в окружность. Все другие состояния неустойчивы. Переход из одного состояния в другое вызывается изменением символа на входе автомата. [1]
Для асинхронных автоматов, то есть таких автоматов, у i оторых время такта определяется скоростью переброса различных его запоминающих элементов, существенным ( для обеспечения правильной работы автомата) являе ся также согласование изменения ( потенциальных) входных сигналов с переходами автомата из одного состояния в другое. [2]
В асинхронных автоматах длительность интервала времени Т - величина переменная, определяемая только моментами изменения состояния входа. При этом, обычно, принимается, что состояние входа асинхронного автомата может измениться лишь после того, как автомат перейдет в определенное внутреннее состояние. [3]
В асинхронных автоматах должны быть исключены ошибки, связанные с состязаниями, и [ - logjr ] позиций уже не являются достаточными. Если кодирование внутренних состояний осуществляется произвольным образом, то может оказаться, что двум состояниям Q и Q /, между которыми должен быть переход ( соседние внутренние состояния), будут приписаны кодовые комбинации, отличающиеся значениями нескольких переменных внутреннего состояния. Тогда возникают условия для состязаний элементов памяти. [4]
Рассмотрим микропроцессорную реализацию асинхронного автомата. Наиболее простая реализация получается, если длины входного и выходного векторов не превышают разрядности используемого микропроцессора. При нарушении этого условия увеличивается время обработки входного вектора, что приводит к снижению верхней граничной частоты спектра входного сигнала. Прочерк в выходном векторе графа переходов автомата будет означать сохранение предыдущего значения соответствующей выходной логической переменной. [5]
Первоочередной задачей при кодировании асинхронных автоматов является исключение критических состязаний. Методы решения этой задачи разделяются на две группы. К первой относятся методы кодирования, позволяющие устранить вообще все состязания элементов памяти. Например, кодовые комбинации 01101 и 01001 являются соседними. Состязания не возникают, если всем соседним внутренним состояниям приписать соседние кодовые комбинации. Методы второй группы осуществляют такое кодирование, при котором допускаются некритические состязания элементов памяти. [6]
При таком допущении теория асинхронных автоматов в ряде случаев может быть сведена к синхронному случаю, поскольку фактические длины интервалов между последовательными моментами автоматного времени в идеализированной теории автоматов ( без учета переходных процессов) не имеют никакого значения. [7]
В противоположность синхронным автоматам, в асинхронных автоматах моменты переходов из одного состояния в другое заранее не определены и могут совершаться через неравные между собой промежутки времени. Для асинхронных автоматов можно ввести дискретное время, определяемое исключительно лишь одними моментами фактических переходов автомата из одного состояния в другое. Однако при этом теория асинхронных автоматов становится существенно отличной от соответствующей теории для синхронного случая. Поэтому мы в качестве мо-ментов дискретного автоматного времени для асинхронных автоматов будем рассматривать не только моменты фактически имевших место переходов, но также и такие моменты, в которые переходы были возможны, но фактически не произошли. Разумеется, при этом необходимо считать, что интервал дискретности автомата ограничивает минимально возможное расстояние между лополнительно вводимыми моментами автоматного времени. [8]
Цифровые апериодические системы, которые также называют асинхронными автоматами. Состояние счетчика числа посылок, которые пересекли контролирующий луч света, можно характеризовать вектором состояния, принимающим дискретные значения, которые фиксируются индикатором счетчика. Состояние же счетчика может быть изменено перемещающейся посылкой в любой момент времени. Вектор состояния может состоять из непрерывно и дискретно изменяющихся компонент ( непрерывных и дискретных переменных состояния), в этом случае системы называются гибридными. [9]
Более общий класс кодирований сообщений образуют автоматные кодирования, реализуемые инициальными асинхронными автоматами, выдающими в каждый момент времени нек-рое ( быть может, пустое) слово в алфавите В. Содержательный смысл этого обобщения заключается в том, что автомат в разных состояниях реализует различные кодирования букв алфавита сообщений. Побуквенное кодирование - это автоматное кодирование, реализуемое автоматом с одним состоянием. [10]
Приведенный метод реализации автоматов в ВС подразумевал, строго говоря, реализацию в среде асинхронных автоматов. [11]
Заметим, что введение общего автоматного времени для системы автоматов не означает, вообще говоря, отказ от рассмотрения асинхронных автоматов. Речь идет здесь о том, что совместная работа автоматов в системе определяет общее дискретное время для всех входящих в нее автоматов, отличное, вообще говоря, от того автоматного времени, в котором эти автоматы работали бы вне данной системы. [12]
К числу наиболее известных интерпретаций Р - задачи относятся ставшие классическими задачи о минимизации булевых функций в классе дизъюнктивных нормальных форм ( ДНФ) и о минимизации длины кода внутренних состояний асинхронного автомата. Проведенный в [10] анализ рассматриваемых в работе [21] оптимизационных задач проектирования дискретных устройств в базисе ПЛМ показал, что кроме упомянутых выше задач минимизации ДНФ булевых функций и минимизации длины кода внутренних состояний асинхронного автомата интерпретациями Р - задачи являются также разнообразные оптимизационные задачи, возникающие при синтезе одноярусных сетей из ПЛМ, минимизации секвенциальных автоматов, нахождении минимального дизъюнктивного базиса для заданного множества булевых векторов, построении проверяющего теста для транзисторной матрицы, реализующей систему элементарных конъюнкций, а также при построении диагностического теста для дизъюнктивной матричной схемы, если в ней возможны любые кратные неисправности типа исчезновения транзисторов. [13]
В силу того что в этом случае автомат переходит из одного состояния в другое через время, определяемое только быстродействием ПЗУ, и не зависит ни от каких других разрешающих ( синхронизирующих) сигналов, получается реализация асинхронного автомата. [14]
Еще одна особенность графа переходов, полученного по лингвистическому описанию, заключается в том, что он, как правило, содержит петли, дублирующие входящие в вершину дуги ( это условие должно быть выполнено всегда при описании асинхронного автомата); при условии реализации устройства в виде синхронного автомата эти петли могут быть исключены из графа переходов без нарушения правильности функционирования. [15]