Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Лекции - Теория дискретных устройств - файл Лекция8.doc


Лекции - Теория дискретных устройств
скачать (1179.2 kb.)

Доступные файлы (11):

Лекция10.doc522kb.17.11.2010 17:46скачать
Лекция11.doc1221kb.17.11.2010 17:49скачать
Лекция1.doc211kb.07.12.2010 15:54скачать
Лекция2.doc98kb.06.12.2010 21:27скачать
лекция3.doc120kb.06.12.2010 22:25скачать
лекция4.doc173kb.09.03.2011 17:18скачать
Лекция5.docx176kb.10.03.2011 16:09скачать
лекция6.doc82kb.07.12.2010 01:39скачать
Лекция7.doc81kb.18.11.2010 15:16скачать
Лекция8.doc133kb.18.11.2010 19:07скачать
Лекция9.doc141kb.01.12.2010 18:09скачать

Лекция8.doc

Лекция №8

Абстрактный синтез автоматов
Пусть алгоритм управления ОУ задан рис. 57.


Рис. 57

При составлении ГСА проек­тировщик глубоко изучил структуру ОУ с учетом смысла сигналов и логических условий α1, α2, α3).

Для проектирования автомата управ­ления можно абстрагироваться от смысла (семантики) элементов множеств {c} и {α} и переходить к построению формального описания работы авто­мата.
Общая схема системы будет иметь вид рис. 58, где обо­значено:

Рис 58
X, Y – множества входных и выходных переменных ОУ;

с1, с2, …, ск – сигналы управления для ОУ (выходы схемы СА);

СА – схема автомата;

Z(t)=Z1, Z2, …, Zp – внутренние значения переменных автомата, формируемые схемой СА в момент t,;

Z(t + 1) – значения переменных после подачи очередного импульса синхронизации, т.е. в момент времени t + 1;

ПА – память автомата;

СС – схема синхронизации;

τ – сигнал синхронизации;

– сигнал синхронизации, действующий после сигнала τ, т.е. Ø.
Рассмотрим вначале так называемый автомат Мура.

В автоматах Мура следующее состояние а(t + 1) определяется как система булевых функций F1, зависящая от номера (или кода) состояния автомата а(t) и множества логических сигналов {α},

а выходные сигналы A(t) задаются системой булевых функций F2, зависящих только от состояния а(t) и не зависящих от {α}.
Для формального описания функционирования автомата в виде графа переходов и набора булевых функций, определяющих выходные сигналы {c}. Произведем разметку ГСА, выполнив несколько этапов формальных дейст­вий.

Этап 1.

      1. Отметим все операторы действия (кроме логических) с помощью последова­тельно занумерованных меток аi (i = 0, 1, 2, …). Справа рядом с отмеченным опе­ратором на рис. 57 поставлен номер аi в кружочке.

      2. Будем расставлять метки ai от оператора а0 (начало) до конца ак по наиболее длинному пути. Оператор окончания в ГСА также помечается меткой а0. В данной схеме оба пути (как при α2 = 0, так и при α2 = 1) одинаковы по длине. Поэтому предпочтем путь α2 = 0.

      3. Далее так же отметим все не помеченные по пункту 2 операторы. На рис. 57 это метка а9 при α2 = 1.

Этап 2.

  1. Отмеченные операторы соответствуют внутренним состояниям автомата αi (здесь i = ), через которые в дальнейшем определяются переменные Zj (j = 1, 2, …, p) в зависимости от выбранного проектировщиком способа кодирования множества состояний автомата {a}.

  2. Выпишем систему булевых функций F2, соответствующих правилу формирова­ния выходных сигналов {c} как функций состояний. Для данного примера получим:





  1. Обозначим каждое состояние аi в виде вершины графа. (граф алгоритма переходов автомата из одно состояния в другое)




Рис. 59


  1. Соединим i и j вершины графа направленной стрелкой в том случае, если на ГСА есть путь от ai к aj (i, j = ). Для данного примера получим граф переходов автомата из состояния ai в другое aj в виде рис. 59. Переход из состояния ai в лю­бое другое aj согласно графу рис. 59 происходит в момент t после поступления импульса синхронизации (обозначим τ), т.е. состояние а(t) сменится на a(t+1).

  2. Выпишем систему булевых функций F1, определяющих переходы a(t)→a(t + 1). Тогда получим следующую запись по графу переходов:



Сигнал τ не принято опускать как признак наличия «автоматного времени».
Формальный «закон» функционирования автомата Мура может быть задан не только графом переходов и системами F1 и F2.

Зная граф пе­реходов, можно составить таблицу переходов с одновременным отображением в ней как переходов, так и выходных сигналов. Нетрудно видеть, что графу рис. 59 соответствует таблица 24.
Таблица 24

a(t + 1)

a(t)

0

1

2

3

4

5

6

7

8

9

0




1

























1







1






















2









α1



















3



























α2

4
















1













5



















1










6





















α3







7

























1




8

1




























9
















1













Иногда в такой таблице (напоминающей МСА) в каждой клетке при наличии перехода по условию (без условия ставится 1) через черточку ставится обозначе­ния сигналов управления. Впрочем, для автоматов Мура в таком обозначении нет необходимости, т.к. функции выходов F1 не зависят от α.

Можно записать обобщенно правило функционирования автомата Мура в виде:

A(t) = F1(a(t)); а(t + 1) = F2(a(t), {α}).
Таблица переходов автомата иногда задается в другом виде (табл. 25)
Таблица 25

a(t)

Условие перехода

a(t + 1)

c(t)

A(t)

0

1

1



a0

1

1

2

C1

a1

2





1

3

C2

a2

3





4

9

C3C4

a3

4

1

5

C1C5

a4

5

1

6

C7

a5

6





3

7

C8

a6

7

1

8

C5C6

a7

8

1

0

C7C9

a8

9

1

5

C2C6

a9


Абстрактный синтез автомата Мура завершается получением графа перехо­дов или таблицы переходов с выпиской функций F1 и F2.


Скачать файл (1179.2 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации