1. Абстрактный синтез автомата



Скачать 465.04 Kb.
Дата26.07.2014
Размер465.04 Kb.
ТипДокументы
1. Абстрактный синтез автомата

1.1. Абстрактный автомат синтезируется по алфавитному оператору, который описывает работу оператора (входные слова и соответствующие им выходные слова). Таблица 1



Входной алфавит

Выходной алфавит

0000

0011

0001

0111

0010

1011

0011

0001

0100

1111

0101

1111

0110

0111

0111

0001

1000

1001

1001

1111

1010

0010

1011

0010

1100

0001

1101

0000

1110

1110

1111

0000

Для того чтобы по алфавитному оператору можно было синтезировать, он должен соответствовать двум условиям автоматности:

  1. длины входных и выходных слов должны быть одинаковыми;

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


Алфавитный оператор, приведённый к автоматному виду:

Таблица 2



Входной алфавитный оператор

Выходной алфавитный оператор

000011

110011

000111

110111

00101

11011

001111

110001

0100

1111

0101

1111

011011

110111

011111

110001

100011

111001

1001

1111

101011

110010

101111

110010

110011

110001

110111

110000

1110

1110

1111111

1110000

1.2. Построение графов переходов

  1. Перед приходом первого символа любого входного слова, автомат находится в начальном состоянии.

  2. После прихода последнего входного символа входного слова, автомат приходит в начальное состояние.

Минимизация абстрактного автомата заключается в том, что из его графа можно удалить эквивалентные состояния.

На первом этапе определили данное множество эквивалентных пар (обозначены на рис.1 одним цветом):



рис1. Граф-переходов автомата Мили по алфавитному оператору.


М
инимизированный граф-переходов

рис.2 Минимизированный граф-переходов.

После минимизации осталось 20 состояний автомата.

По графу минимального автомата составляем таблицы переходов и выходов:



Таблица переходов Таблица 3

а

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

Z1

2

3

4

11

-

8

13

1

8

11

-

1

-

15

16

13

18

-

-

7

Z2

14

9

6

11

1

13

19

1

10

13

8

7

8

20

17

1

18

5

5

12

Таблица выходов Таблица 4

а

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

W1

1

1

0

0

-

1

0

1

1

1

-

0

-

1

1

0

0

-

-

0

W2

1

1

0

1

0

0

0

1

0

0

1

0

0

1

0

1

0

1

0

1


2.Структурный синтез автомата

Переходим к структурному синтезу автомата Мили по алфавитному оператору.



    1. Кодируем абстрактные входные и выходные сигналы символами структурного алфавита:

X – входной структурный алфавит, Х = {0,1}

Y – выходной структурный алфавит, Y = {0,1}







y







x

W1

0




Z1

0

W2

1




Z2

1




    1. Кодируем состояния абстрактного автомата символами структурного алфавита состояний:

Q = {0,1}

По заданию метод кодирования состояний случайный.

Таблица 5


a

Q0 Q1 Q2 Q3 Q4

1

00001

2

00010

3

00011

4

00100

5

00101

6

00110

7

00111

8

01000

9

01001

10

01010

11

01011

12

01100

13

01101

14

01110

15

01111

16

11000

17

11001

18

11010

19

11011

20

11100

Определяем количество элементарных автоматов (триггеров):

T = ] logz a [ = 5



    1. Составляем кодированную таблицу переходов и выходов структурного автомата (в таблицу 4 и 5 вставляем коды):

Таблица переходов Таблица 6

a


00001

00010

00011


00100


00101


00110


00111


01000


01001


01010


01011


01100


01101


01110


01111


11000


11001


11010


11011


11100

x

0


00010

00011

00100

01011

-

01000

01101

00001

01000

01011

-

00001

-

01111

11000

01101

11010

-

-

00111

1


01110

01001

00110

01011

00001

01101

11011

00001

01010

01101

01000

00111

01000

11100

11001

00001

11010

00101

00101

01100

Кодированная таблица выходов структурного автомата Таблица 7



a


00001

00010

00011


00100


00101


00110


00111


01000


01001


01010


01011


01100


01101


01110


01111


11000


11001


11010


11011


11100

Х

0

1

1

0

0

-

1

0

1

1

1

-

0

-

1

1

0

0

-

-

0

1

1

1

0

1

0

0

0

1

0

0

1

0

0

1

0

1

0

1

0

1




    1. Формируем логические выражения выходных сигналов в соответствии с таблицей 7 в виде одномерной таблицы истинности:

Таблица 8

A

Х

Q0 Q1 Q2 Q3 Q4

Y

1

0

00001

1

2

0

00010

1

3

0

00011

0

4

0

00100

0

5

0

00101

-

6

0

00110

1

7

0

00111

0

8

0

01000

1

9

0

01001

1

10

0

01010

1

11

0

01011

-

12

0

01100

0

13

0

01101

-

14

0

01110

1

15

0

01111

1

16

0

11000

0

17

0

11001

0

18

0

11010

-

19

0

11011

-

20

0

11100

0

1

1

00001

1

2

1

00010

1

3

1

00011

0

4

1

00100

1

5

1

00101

0

6

1

00110

0

7

1

00111

0

8

1

01000

1

9

1

01001

0

10

1

01010

0

11

1

01011

1

12

1

01100

0

13

1

01101

0

14

1

01110

1

15

1

01111

0

16

1

11000

1

17

1

11001

0

18

1

11010

1

19

1

11011

0

20

1

11100

1

2.5. Формируем таблицу функции возбуждения элементарного автомата на основании таблиц 6 и 7. В каждой клетке записывается значение входного сигнала, который нужно подать на вход элементарного автомата, чтобы осуществить переход указанный в таблице 7.

Таблица 9



X

Q0Q1Q2Q3Q4

T0

T1

T2

R1

S1

R2

S2

0

00001

0

0

0

0

1

1

0

1

0

1

1

0

1

1

0

0

00010

0

0

0

0

-

0

1

1

0

1

0

1

0

0

1

0

00011

0

0

1

1

0

1

0

1

0

0

1

0

-

1

0

0

00100

0

1

1

0

1

0

1

1

0

1

1

0

1

0

1

0

00101

-

-

-

-

-

-

-

1

0

0

1

-

0

0

-

0

00110

0

1

1

1

0

-

0

1

0

1

0

1

0

0

1

0

00111

0

1

1

1

0

0

-

1

1

0

1

0

-

0

-

0

01000

0

1

0

-

0

0

1

1

0

1

0

-

0

0

1

0

01001

0

0

0

-

0

1

0

1

0

0

0

0

1

1

0

0

01010

0

0

0

0

-

0

1

1

0

0

1

1

0

0

1

0

01011

-

-

-

-

-

-

-

1

0

0

0

1

0

1

0

0

01100

0

1

1

-

0

0

1

1

0

1

0

0

1

0

1

0

01101

-

-

-

-

-

-

-

1

0

0

1

-

0

1

0

0

01110

0

0

0

0

-

0

1

1

1

0

0

1

0

-

0

0

01111

1

0

1

1

0

1

0

1

1

0

1

1

0

0

-

0

11000

1

0

1

-

0

0

1

1

1

1

0

-

0

0

1

0

11001

0

0

0

0

1

1

0

1

0

0

0

0

1

1

0

0

11010

-

-

-

-

-

-

-

1

1

1

1

1

0

0

1

0

11011

-

-

-

-

-

-

-

1

1

1

1

1

0

0

-

0

11100

1

1

0

0

1

0

1

1

1

0

0

-

0

-

0




    1. На основании таблиц 8 и 9 строим диаграммы Вейча, которые необходимо минимизировать:

Диаграмма Вейча для выходного сигнала:

























Q3











































Q4































x














































Q0




-

-

-

-

-

-

-

-

Q2










-

-

-

-

-

-

-

-




Q1







-

-

-

-

1

-

-

0













-

-

0

1

1

0

0

0













1

-

1

0

1

0

1

1













1

1

0

1

0

0

-

0













1

0

0

0

1

0

-

0













1

0

0

1

-

1

1

-

Диаграммы Вейча для триггеров:

























Q3













Т0




























Q4































X














































Q0




-

-

-

-

-

-

-

-

Q2










-

-

-

-

-

-

-

-




Q1







-

-

-

-

1

-

-

1













-

-

1

1

1

0

0

1













0

-

0

0

0

0

0

0













0

1

1

1

0

0

-

0













0

0

1

0

0

0

-

0













0

0

0

0

-

0

0

-




























Q3













Т1




























Q4































x














































Q0




-

-

-

-

-

-

-

-

Q2










-

-

-

-

-

-

-

-




Q1







-

-

-

-

0

-

-

1













-

-

1

1

1

0

0

0













0

-

0

0

1

0

0

1













0

0

0

0

1

0

-

1













1

1

0

1

1

0

-

1













0

0

0

1

-

1

0

-


























Q3













Т2




























Q4































x














































Q0




-

-

-

-

-

-

-

-

Q2










-

-

-

-

-

-

-

-




Q1







-

-

-

-

0

-

-

0













-

-

1

1

0

0

0

1













0

-

0

1

0

0

0

0













0

1

1

0

0

1

-

1













1

1

1

0

1

1

-

1













0

1

1

0

-

1

0

-




























Q3













R1




























Q4































x














































Q0




-

-

-

-

-

-

-

-

Q2










-

-

-

-

-

-

-

-




Q1







-

-

-

-

-

-

-

0













-

-

1

1

-

0

0

-













0

-

1

1

-

0

-

-













0

1

1

1

0

-

-

-













1

1

0

1

0

-

-

0













0

-

0

1

-

0

0

-




























Q3













S1




























Q4































x














































Q0




-

-

-

-

-

-

-

-

Q2










-

-

-

-

-

-

-

-




Q1







-

-

-

-

0

-

-

0













-

-

0

0

0

1

1

0













-

-

0

0

0

1

0

0













-

0

0

0

1

0

-

0













0

0

-

0

1

0

-

1













-

0

-

0

-

1

1

-



























Q3













R2




























Q4































x














































Q0




-

-

-

-

-

-

-

-

Q2










-

-

-

-

-

-

-

-




Q1







-

-

-

-

-

-

-

0













-

-

0

0

0

1

1

0













0

-

1

0

0

1

1

0













0

1

0

-

0

1

-

0













-

0

0

0

0

0

-

0













0

0

1

0

-

1

1

-




























Q3













S2




























Q4































x














































Q0




-

-

-

-

-

-

-

-

Q2










-

-

-

-

-

-

-

-




Q1







-

-

-

-

0

-

-

1













-

-

-

1

1

0

0

1













1

-

0

1

1

0

0

1













1

0

-

0

1

0

-

1













0

-

-

1

1

-

-

1













1

1

0

1

-

0

-

-

Логические выражения для функций возбуждения триггеров, полученные с помощью диаграмм Вейча:

а).



б).

2.7. По полученным минимизированным Булевым функциям, строим электрическую принципиальную схему автомата. Все микросхемы, использованные построение схемы, относятся к серии К155 (см Приложение). Всего в схеме задействована 41 микросхема, из них:

К155ЛИ1 – 26 шт.

К155ЛА3 – 1 шт.

К155ЛЕ1 – 1шт.

К155ЛЕ7 – 8 шт.

К155ТВ1 – 5 шт.

Т-триггеры и RS-триггеры построены на базе микросхемы К155ТВ1

3.Учебно-исследовательская работа студента
Анализ полученных функций возбуждения выходных сигналов на возможность их факторизации и на упрощение функциональной схемы.

Функции после их факторизации:








После факторизации функций

Похожие:

1. Абстрактный синтез автомата iconАбстрактный синтаксис Рефала
Предлагаю более абстрактный синтаксис. Он несколько шире прежнего, но не намного. Примерно настолько, чтобы объять как Рефал Плюс...
1. Абстрактный синтез автомата iconМинимизация абстрактных автоматов
Два автомата называются эквивалентными [12, 14], если они реализуют один и тот же алфавитный оператор. Задача минимизации числа состояний...
1. Абстрактный синтез автомата iconТехническое задание на разработку автомата выдачи жетонов авж санкт-Петербург 2012 г. Общие сведения
Цель разработки: создание изделия (автомата продажи жетонов), входящего в комплекс станционного оборудования аскопм
1. Абстрактный синтез автомата iconДоговор на установку и обслуживание торгового автомата
Оператор торгового автомата, с одной стороны, и, в лице, действующего на основании, именуемое в дальнейшем Учреждение, с другой стороны,...
1. Абстрактный синтез автомата iconСформулировать определение конечного автомата как размеченного орграфа. Понятие допускаемой цепочки и языка автомата (в терминах орграфов). Сформулировать теорему Клини
С использованием карты Карно перечислить все тупиковые и указать минимальные днф булевой функции
1. Абстрактный синтез автомата iconИнструкция по сервисному обслуживанию и настройке автомата 5 Оперативная (длинная) статистика
Это нужно для предварительной диагностики неисправностей платы. В случае успешного тестирования на экране автомата появится надпись...
1. Абстрактный синтез автомата iconЛекции Практические занятия Лабораторные работы ирс срс 3 5 3
Исследование характеристик конечных автоматов. Описание функционирования вероятностного конечного автомата, конечных автоматов Мили...
1. Абстрактный синтез автомата iconПрименение модели клеточного автомата для моделирования пешеходного движения с гетерогенными участниками
Приводятся модель пешеходного движения на основе клеточного автомата и методы их интеграции в системы реального времени, на примере...
1. Абстрактный синтез автомата iconПрямой синтез диметилового эфира из синтез-газа и его превращение в углеводороды (бензин)

1. Абстрактный синтез автомата iconОтображение языка синтез в rdfs
В данной статье1 рассматривается вопрос отображения языка синтез в rdfs. Определяются принципы отображения и расширения rdfs для...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org