Практические занятия Прикладная теория цифровых автоматов
  • Регистрация
1 1 1 1 1 1 1 1 1 1 Рейтинг 5.00 (1 Голос)

Занятие 14. Граф автомата, таблица переходов и выходов

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

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

Работа последовательностного автомата определяется не только входным набором, но и собственным состоянием автомата. В свою очередь состояние Si автомата зависит от начального S0 его состояния и последовательности входных наборов, приведших его в это состояние(рис. 1).

Описание: R9

Рисунок 58. Дискретное устройство с памятью (yi = F(x1,…,xn, Si)

Si {S0,S1,…,SL}, 2< L < m).

Мы рассматриваем дискретные устройства с конечным числом L состояний S. Рассмотрим представление автомата с памятью графом автомата. Начнем с представления триггера – автомата с 2 состояниями. Состояния представим вершинами, а связи между ними – стрелками. Стрелки снабдим условиями переходов.

 D - триггер (задержка – сигнал х задерживается на один такт T)

Рисунок 59. D - триггер (задержка – сигнал х задерживается на один такт T).

Описание: R11

Рисунок 60. Изображение D-триггера на схемах

Описание: R12

Рисунок 61. С синхросигнал с периодом Т.

Сигнал D запоминается в момент, когда С=1 и хранится весь оставшийся период Т.

Теперь выполним проектирование так называемого “Секретного замка” – последовательного автомата запирающего дверь и открывающего ее, или поднимающего сигнал тревоги в зависимости от последовательностей входных воздействий.

Описание: C:\Documents and Settings\Tatiyana\Мои документы\Ded\1.bmp

Рисунок 62. “х1, х2”- входные переменные, “y1,y2” – выходные переменные.

1,дверь открывается,

y1=

0, дверь закрывается;

1, тревога звучит,

y2=

0, тревога не звучит.

Задана всего одна открывающая последовательность входных наборов. Еще один набор - нейтральный (х1х2 = 00), автомат остается в том же состоянии. На всех остальных последовательностях звучит сигнал тревоги.

Для нашего автомата открывающая входная последовательность пусть будет такой – х1х2= 01 11 10. Последовательности, например, начинающиеся с наборов 11 иди 10, вызовут сигнал тревоги автомата. Если дверь открыта, то она остается в этом состоянии при нейтральном входном наборе(00), любое нажатие входных кнопок вызовет закрытие двери. Наконец, если нечаянно сам владелец замка нажал неверную входную последовательность, то он может вывести автомат из тревоги, набрав единственную верную последовательность выхода из тревоги, например, х1х2 = 11 10.

Построим граф автомата “секретный замок” для уже сформулированных данных. Вначале автомат находится в некотором начальном состоянии( S0, x1x2=00, y1y2 = 00). Набираем первый набор открывающей последовательности. Автомат переходит в следующее состояние(S1, y1y2=00), но в этом состоянии автомат ждет уже второй набор открывающей последовательности. Поучив его (х1х2 =11), автомат переходит в следующее состояние(S2, y1y2 =00), в котором автомат ждет третий правильный входной набор. Получив его автомат переходит в состояние S3. Но в этом состоянии автомат, уже получив всю правильную открывающую входную последовательность, должен открыть дверь (S3, y1y2= 10). При входном нейтральном наборе (00) дверь остается открытой, после нажатия любого набора (01, или 11, или 10), дверь закрывается (S0, y1y2 =00).

Описание: C:\Documents and Settings\Tatiyana\Мои документы\Ded\1.bmp

Рисунок 63. Описание работы по открытию замка.

Остается реализовать режимы входа в тревогу и выхода из нее. В состоянии S1 наборы 00 и 01 уже задействованы, остаются наборы 10 и 11, при них нужно реализовать переход в тревогу - состояние (S4 y1y2 =01). В состоянии S1 нейтральный набор возвращает в то же состояние S1, наборы 01 и 10 переводят автомат в состояние тревоги S4. Аналогично в состоянии S2 нейтральный набор 00 возвращает автомат в состояние S2, наборы 11 и 01 – в состояние тревоги S4.

Описание: C:\Documents and Settings\Tatiyana\Мои документы\Ded\1.bmp

Рисунок 64. Описание работы по правильной последовательности и формированию сигнала тревоги.

Остается реализовать поведение автомата при выходе из тревоги. В состоянии S4 набор 11 переводит автомат в состояние S5 (y! y2 = 01). Из состояния S5 набор 10 сбрасывает тревогу (S0, y1y2 =00). При остальных наборах – возврат в состояние тревоги.

Описание: C:\Documents and Settings\Tatiyana\Мои документы\Ded\1.bmp

Рисунок 65. Полное описание графа автомата ”Секретный замок”.

Граф автомата полностью описывает его повеление. Но в некоторых случаях (когда число входных переменных не велико) используют другую форму задания алгоритма работы последовательностного автомата - таблица переходов и выходов автомата (ТПиВ). Таблица переходов и выходов автомата является прямоугольной матрицей, строки которой сопоставлены входным наборам и столбцы – состояниям.

Описание: C:\Documents and Settings\Tatiyana\Мои документы\Ded\1.bmp

Рисунок 66. Таблица переходов и выходов автомата “Секретный замок”.

Полученная таблица переходов и выходов еще представлена на так называемом абстрактном уровне. Чтобы перейти к комбинационным схемам необходимо заменить абстрактные символы состояний комбинациями наборов двоичных переменных, т. е. произвести кодирование состояний автомата. Необходимое условие правильного кодирования состояний – каждому состоянию нужно поставить свой, отличный от других состояний код. Отсюда число к внутренних переменных z1z2…zk, кодирующих состояния, вычисляется по следующей формуле k=]log2(L +1)[.Состояния переменных zi представляются состояниями памяти автомата, отсюда схема последовательностного автомата выглядит следующим образом.

Первоначально проведем так называемое тривиальное кодирование состояний, состояние Si закодируем k-разрядным двоичным кодом числа i. k=]log2(5+1)[=3.

 

z3

z2

z1

S0

0

0

0

S1

0

0

1

S2

0

1

0

S3

0

1

1

S4

1

0

0

S5

1

0

1

Описание: C:\Documents and Settings\Tatiyana\Мои документы\Ded\1.bmp

Рисунок 67. Кодированная таблица переходов и выходов.

Прежде всего обратим внимание на расстановку состояний по столбцам кодированной таблицы переходов и выходов. Они расставлены согласно их кодированию. Состояния Sx обозначают не использованные коды 110 и 111.

Итак, мы перешли от абстрактного представления автомата к системе булевых функций: первый столбец кодированной таблицы переходов и выходов представляет булеву функцию z1(t+1), второй столбец – булеву функцию z2(t+1), третий столбец – булеву функцию z3(t+1).

Чтобы построить выходные функции автомата, поступим следующим образом. Разместим состояния автомата на матрице трех переменных – z1z2z3:

Описание: C:\Documents and Settings\Tatiyana\Мои документы\Ded\1.bmp

Рисунок 68. Размещение состояний автомата “Секретный замок” на матричной форме переменных z1, z2, z3.

Функция у1 принимает единичное значение на единственном наборе, соответствующему состоянию S3 – это набор 011. И кроме того она не определена на наборах, соответствующих состояниям Sx. Функция у2 Принимает единичное значение на наборах, соответствующих состояниям S4, S5 и не определена на наборах для состояний Sx.

Рисунок 69. Выходные функции автомата “Секретного замка”.

Домашнее задание. Построить граф автомата “Секретный замок” по заданию[3, стр. 12], номер варианта определяется по i, младшая цифра задает открывающую последовательность, старшая - последовательность сброса тревоги. Построить таблицу переходов и выходов автомата, провести кодирование состояний и построить кодированную таблицу переходов и выходов. Построить функции z1,z2,z3,у1 и y2.

Граф автомата, таблица переходов и выходов - 5.0 out of 5 based on 1 vote

Добавить комментарий


Защитный код
Обновить

По темам:

История Украины

Культурология

Высшая математика

Информатика

Охотоведение

Статистика

География

Военная наука

Английский язык

Генетика

Разное

Технологиеские темы

Украинский язык

Филология

Философия

Химия

Экология

Социология

Физическое воспитание

Растениевосдство

Педагогика

История

Психология

Религиоведение

Плодоводство

Экономические темы

Бухгалтерские темы

Маркетинг

Иностранные языки

Ветеринарная медицина

Технические темы

Землеустройство

Медицинские темы

Творчество

Лесное и парковое хозяйство