Материал: Tdu_5
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ЖЕЛЕЗНОДОРОЖНОГО ТРАНСПОРТА
Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования
«ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПУТЕЙ СООБЩЕНИЯ»
Кафедра «Автоматика и телемеханика на железных дорогах»
МЕТОД КОДИРОВАНИЯ СОСТОЯНИЙ АСИНХРОННЫХ КОНЕЧНЫХ АВТОМАТОВ
Методические указания
к практическому занятию № 5
по дисциплине
«Теория дискретных устройств»
САНКТ-ПЕТЕРБУРГ
ПГУПС
2013
1
Цель работы
Изучение метода синтеза асинхронных автоматов с исключением критических состязаний.
1 Основные понятия
Асинхронные автоматы в отличие от синхронных [1] не требуют синхронизации внешних и внутренних воздействий, а исключение критических состязаний при их работе достигается с использованием избыточного кодирования.
Для построения асинхронных конечных автоматов, свободных от критических состязаний, может быть применен метод кодирования состояний по столбцам таблицы переходов. При его использовании не требуется анализ всех допустимых случаев состязаний.
Пусть дана таблица переходов (табл. 1). В каждой ее клетке записаны номера состояний асинхронного автомата, устойчивые состояния обозначены цифрами в скобках, а через запятую указано значение выхода асинхронного автомата при данном устойчивом состоянии.
Таблица 1
Совмещенная таблица переходов и выходов
S |
|
x |
|
|
|
|
|
0 |
|
1 |
|
|
|
||
|
|
|
|
|
|
|
|
1 |
(1), 0 |
|
7 |
|
|
|
|
2 |
3 |
|
(2), 0 |
|
|
|
|
3 |
(3), 1 |
|
5 |
|
|
|
|
4 |
(4), 1 |
|
7 |
|
|
|
|
5 |
4 |
|
(5), 1 |
|
|
|
|
6 |
(6), 0 |
|
2 |
|
|
|
|
7 |
6 |
|
(7), 0 |
|
|
|
|
Шаг 1. Формирование разделяющих переменных по каждому столбцу и определение -классов.
Переходы в таблице осуществляются по столбцам x = 0 и x = 1. Переход осуществляется в то состояние, номер которого указан в рассматриваемой клетке таблицы переходов, например, из клетки x, S 0,7 будет
реализован переход в клетку столбца x = 0 с номером состояния S = 6. Объединяя все возможные переходы по каждому столбцу рассматриваемой таблицы переходов, получаем систему λ-классов каждого столбца. Каждый такой класс будет содержать одно устойчивое и все неустойчивые состоя-
2
ния, из которых задан переход в данное устойчивое состояние. Другими словами, каждый λ-класс будет содержать номера тех состояний, которым соответствуют одинаковые цифры по каждому столбцу таблицы переходов. Рис. 1 поясняет методику выделения λ-классов.
λ-классы столбца х = 0 |
λ-классы столбца х = 1 |
|||||
λ1 |
(1) |
|
|
1 |
1→7 |
|
|
|
|
||||
|
|
2→3 |
λ5 |
4 |
|
|
|
2 |
|
|
|||
|
2→4 Недопустимый |
|
|
4→7 |
||
λ2 |
(3) |
|
(7) |
|||
|
переход |
|
|
|
||
|
|
|
|
|
||
λ3 |
(4) |
|
λ6 |
(2) |
|
|
5 |
5→4 |
6 |
6→2 |
|||
|
|
|||||
|
(6) |
|
|
3 |
|
|
λ4 |
7 |
7→6 |
λ7 |
(5) |
3→5 |
|
|
|
|||||
Рис. 1 Определение λ-классов в заданной таблице переходов
В столбце x = 0 сформировано 1 = 4 λ-класса, а в столбце x = 1 – 2 = 3 λ-класса. Каждый обозначенный в табл. 1 переход осуществляется внутри одного из семи λ-классов (рис. 1). Если в результате состязаний реле в работе автомата возникает переход из одного λ-класса в другой (например, как это показано на рис. 1: ложный переход 2 → 4 вместо 2 → 3), то нарушается алгоритм работы автомата – возникает так называемое критическое состязание [1], поэтому необходимо исключить такие ложные переходы между λ-классами. С этой целью в каждом столбце x = 0 и x = 1 вводятся разделяющие внутренние переменные, кодирующие λ-классы. Разделяющие переменные обладают следующими свойствами.
Свойство 1. Для состояний, принадлежащих одному λ-классу, разделяющие переменные имеют одинаковые значения.
Свойство 2. Для состояний, принадлежащих разным λ-классам, разделяющие переменные имеют разные значения.
Свойство 3. При любом переходе внутри столбца x = 0 или x = 1 разделяющие переменные не меняют своих значений.
Свойство 4. Поведение асинхронного конечного автомата в столбце x = 0 или x = 1 зависит только от разделяющих переменных.
Таким образом, условием отсутствия критических состязаний является разделение любой пары λ-классов в каждом столбце таблицы переходов.
3
Осуществим кодирование каждого λ-класса.
Шаг 2. Кодирование -классов.
Для каждого столбца на основании числа λ-классов в нем определяется минимально необходимое число разделяющих переменных yi:
N log |
2 |
|
|
, |
(1) |
|
|
j |
|
|
где j – число λ-классов в столбце j;
N – число разделяющих переменных в столбце j;
a – ближайшее целое, превосходящее a (целое сверху от a). Пользуясь формулой (1), находим:
1 log2 4 2 2;
2 log2 3 1, 585 2.
Втабл. 2 приведен результат кодирования λ-классов. Видно, что каждый λ-класс по столбцам x = 0 и x = 1 разделен.
|
|
|
|
|
Таблица 2 |
||
|
Кодирование λ-классов |
|
|
|
|||
|
|
|
|
|
|
|
|
|
x = 0 |
|
|
x = 1 |
|
|
|
|
|
|
|
|
|
|
|
λ-класс |
S |
y1y2 |
λ-класс |
S |
|
y3y4 |
|
|
|
|
|
|
|
|
|
λ1 |
(1) |
00 |
|
1 |
|
00 |
|
λ2 |
2 |
01 |
λ5 |
4 |
|
00 |
|
(3) |
01 |
|
(7) |
|
00 |
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
λ3 |
(4) |
10 |
λ6 |
(2) |
|
01 |
|
|
|
|
|
|
|
||
5 |
10 |
6 |
|
01 |
|
||
|
|
|
|
||||
|
|
|
|
|
|
|
|
λ4 |
(6) |
11 |
λ7 |
3 |
|
10 |
|
|
|
|
|
|
|
||
7 |
11 |
(5) |
|
10 |
|
||
|
|
|
|
||||
|
|
|
|
|
|
|
|
Шаг 3. Кодирование исходной таблицы переходов.
Используя табл. 2, кодируем исходную таблицу переходов. Для осуществления кодирования в соответствующие клетки таблицы переходов проставляем код λ-класса, которому принадлежит рассматриваемое состояние (табл. 3).
Таблица 3
Кодирование строк таблицы переходов
S |
x = 0 |
x = 1 |
|
|
|
|
|
|
4
|
y1y2 |
y3y4 |
|
|
|
1 |
00 |
00 |
|
|
|
2 |
01 |
01 |
|
|
|
3 |
01 |
10 |
|
|
|
4 |
10 |
00 |
|
|
|
5 |
10 |
10 |
|
|
|
6 |
11 |
01 |
|
|
|
7 |
11 |
00 |
|
|
|
Шаг 4. Составление кодированной таблицы переходов.
Таблицу условно можно разделить на две части – содержащую переходы внутри основных состояний (они соответствуют исходной таблице переходов) и содержащую неосновные состояния (см. рис. 1). Таким образом, первые семь строк кодированной таблицы переходов соответствуют строкам табл. 1, где десятичные номера состояний заменены на их коды из табл. 3.
Таблица 4
Кодированная таблица переходов
Разделяющие |
y1y2 |
y3y4 |
||
переменные |
||||
|
|
|||
S |
y1y2y3y4 |
x = 0 |
x = 1 |
|
|
|
|
|
|
1 |
0000 |
(0000) |
1100 |
|
2 |
0101 |
0110 |
(0101) |
|
3 |
0110 |
(0110) |
1010 |
|
|
|
|
|
|
4 |
1000 |
(1000) |
1100 |
|
|
|
|
|
|
5 |
1010 |
1000 |
(1010) |
|
|
|
|
|
|
6 |
1101 |
(1101) |
0101 |
|
7 |
1100 |
1101 |
(1100) |
|
|
|
|
|
|
8 |
0001 |
0000 |
0101 |
|
9 |
0010 |
0000 |
1010 |
|
10 |
0011 |
0000 |
0011 |
|
11 |
0100 |
0110 |
1100 |
|
|
|
|
|
|
12 |
0111 |
0110 |
0011 |
|
|
|
|
|
|
13 |
1001 |
1000 |
0101 |
|
14 |
1011 |
1000 |
0011 |
|
15 |
1110 |
1101 |
1010 |
|
16 |
1111 |
1101 |
0011 |
|
В табл. 4 состояния 1–7 – основные, а состояния 8–16 – неосновные. Для заполнения первых семи строк таблицы (основных состояний) применяется следующее правило.
Правило получения основных состояний. Если в клетке таблицы переходов (см. табл. 1) на пересечении строки, соответствующей основ-
5