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

Например, код строки 1, т. е. состояние 1 будет иметь код 0000, так как в столбце а₁ состояние 1 принадлежит классу l₁ и кодируется значением У₁У₂=00, а в столбце а₂ – состояние 1 принадлежит классу l₅ и кодируется значением У₃У₄=00. Поэтому общий код строки 1 равен 0000.

Результат кодирования строк приведен в табл. 6.

Рассмотрим переход из состояния 2 (0101) в состояние 4 (1001). Так как переход осуществляется в столбце а₂ (внутри класса l₆), то разделяющими переменными являются у₃, у₄ и они не меняют своего значения во время данного перехода, которое будет определяться только значением разделяющих переменных, т. е. Конъюнкцией  (свойство 4).

Переменные у₁ и у₂ являются не разделяющими и дают возможность различить состояния, входящие в один l - класс. (В данном примере различить состояния 2 и 4). Видно, что во время данного перехода не разделяющие переменные у₁ и у₂ меняют свое значение , т. е. между ними возможны состязания, но ни одна из этих переменных не входит в конъюнкцию f и, следовательно, состязания между ними не повлияют на работу схемы.

Обеспечение свойства 4 достигается на этапе до определения внутренних состояний, что будет показано ниже. На данной идее основан метод кодирования состояний по столбцам ТП. Он состоит из следующих этапов.

I.   Для каждого столбца а_j выделяются разделяющие переменные. Их число равно ] log₂ n j [. Общее число элементов памяти, необходимое для построения схемы, равно:

q=>] log₂ n j [ ,

jЄR

где R –  множество индексов столбцов ТП.

В нашем примере q=N₁+N₂=4. Разделяющие переменные для столбца а₁ – у₁, у₂, а для столбца а₂ – у₃ и у₄.

II.  l - классы столбца а_j кодируются произвольно кодовыми словами, длиной   ] log₂ n j [.

Для столбца а₁ приведен вариант кодирования на рис. 3, для а₂ на рис. 4.

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

III.  Составляется таблица кодирования строк ТП. В качестве исходной используется таблица 6.

IV.  Составляется кодированная ТП (табл.7). Общее число состояний в

кодированной ТП равно 2^q .Строки, соответствующие заданной ТП (см. табл. 5), являются основными и кодируются кодовыми словами на основании таблицы кодирования (см. табл. 6). Остальные строки кодируются неиспользованными кодовыми словами.

В табл. 7 состояния 1-7 считаются основными, а состояние 8–16 -  неосновными. Кодированная ТП заполняется следующим образом. Если в клетке ТП на пересечении строки, соответствующей основному состоянию S₁,  и столбца аj проставлено состояние S_j, то в нее заносится код состояния S_j (i и j – индексы основных состояний). Например, в клетке (а₁,0000) должен быть проставлен код состояния   1 – 0000; в клетке (а₂,0101) – код состояния 4 – 1001 и т. д.

Не основные состояния доопределяются с учетом обеспечения свойства 4.

Рассмотрим задачу до определения на следующем примере. Пусть задан переход из состояния 2 в состояние 4 . Он может произойти двумя путями (рис. 5, а, б ). Разделяющие переменные у₃ и у₄ не изменяются, поэтому в клетках (а₂,0001) и (а₂,1101) надо проставить код устойчивого состояния 4 – 1001, в котором значения разделяющих переменных совпадают с их значением в кодах строк этих состояний.

Таким образом, до определение в клетке (а_j,S_i) зависит от значений разделяющих переменных в коде строки S_i.

Будем использовать два правила до определения.

Правило 1. Если в коде строки S_i значение разделяющих переменных по столбцу а_j совпадает с их значением в коде одного из устойчивых состояний этого столбца, то в клетке (а_j,S_i) записывается код этого устойчивого состояния.