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

На пересечении i-й строки и j-го столбца ТП указывается то внутреннее состояние, в которое автомат перейдет из внутреннего состояния Si (i-ая строка) под действием входных сигналов, соответствующих состоянию входа  Хj (j-ый столбец).

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

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

ТП содержит 4 состояния, поэтому потребуется две внутренние переменные у₁ и у₂ (два ЭП), так как из двух переменных можно получить 2²=4 комбинаций: 00, 01, 10, 11.

В общем случае п элементов памяти имеют 2ⁿ состояний. Если ТП имеет z строк, то минимально необходимое число внутренних переменных определяется по формуле:

Q=] log₂ z [, где р>=z – ближайшее к z число, которое является степенью числа 2.

(р=2^Q>=z)

Кодирование состояний заключается в сопоставлении каждой строке ТП одной из комбинаций (двоичных наборов) внутренних переменных. Пусть внутреннему состоянию 1 соответствует двоичный набор 00 (у₁=у₂=0), внутреннему состоянию 2 - 01; 3 - 10; 4 - 11. Затем строится кодированная ТП. Для этого цифра в каждой клетке ТП заменяется двоичным набором соответствующей строки (табл. 4).

Например, в клетке на пересечении 1 и 4 столбца  проставлено внутреннее состояние 1, которому соответствует код 10.

Кодированная ТП дает возможность определить поведение АКА при смене входных сигналов и переходе его из одного состояния в другое.

Рассмотрим клетку ТП с ко

ординатами (). В ней записано состояние 01. Это означает, что при наличие на входе сигнала 01 реле У₁ должно остаться в выключенном состоянии а реле У₂ – во

включенном , т. е. состояние ЭП сохраняется, что соответствует устойчивому состоянию 2 схемы. Чтобы осуществить переход из состояния 2 в состояние 3 необходимо изменить значение входных сигналов на 00. В клетке с координатами (00,01) записано состояние 10. Это означает, что если реле У₁ было без тока, а реле У₂ под током и на вход поступил сигнал 00, то реле У₁ должно включиться, а реле У₂  - выключиться. Следовательно, в данной клетке проставлено состояние 3, которое является неустойчивым.

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

1.  У₁ включается раньше чем выключится реле У₂.  В этом случае схема окажется в состоянии 4 (У₁=У₂=1), а затем выключается У₂ и схема перейдет в состояние 3.

2.    У₂ выключается раньше, чем включается реле У_1. В этом случае схема окажется в состоянии 1 (У₁=У₂=0). Но это полное состояние (00,00) является устойчивым и для реле У₂ здесь записано условие его включения. По этой причине У₂ не включится и схема останется в состоянии 1 вместо того, чтобы перейти в состояние 3.

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