Минимизация конечных автоматов

Тип работы:
Контрольная
Предмет:
Коммуникации, связь, цифровые приборы и радиоэлектроника


Узнать стоимость

Детальная информация о работе

Выдержка из работы

http: ///

http: ///

Государственное Образовательное Учреждение Высшего Профессионального Образования

Московский Государственный Технологический Университет «СТАНКИН»

Кафедра «Компьютерные системы управления»

Учебный курс «Теория дискретных систем управления»

Контрольная работа

по теме: «Минимизация конечных автоматов»

Выполнила: студентка Богачев Д. С.

Принял: к.т.н., преп. Нежметдинов Р. А.

Москва, 2012 г.

Содержание

  • 1. Исходные данные
  • 2. Составление треугольной таблицы
  • 3. Нахождение списка максимальных классов совместимости
  • 4. Составление списка простых классов совместимости
  • 5. Нахождение минимального замкнутого покрытия
  • 6. Таблица переходов и выходов минимального автомата
  • 7. Синтез конечного автомата
  • 8. Получение логических функций выходов конечного автомата
  • 9. Минимизация логических функций
  • 10. Синтез функциональной схемы
  • 11. Принципиальная электрическая схема
  • Список литературы

1. Исходные данные

Конечный автомат задан совмещенной таблицей переходов и выходов

а1

a2

a3

a4

a5

a6

a7

a8

a9

z1

а5/-

-/-

а5/-

а5/w2

a2/-

a1/ w1

a6/-

-/-

а2/-

z2

a1/ w1

a6/-

-/ w1

-/-

a1/-

-/ w2

-/-

а8/-

а5/-

z3

-/-

-/-

-/-

-/-

-/-

a2/-

-/-

а7/-

a6/-

z4

-/-

-/-

a1/-

a2/-

а4/-

-/-

а1/-

-/-

a1/-

Тип элемента памяти — D-триггер.

2. Составление треугольной таблицы

2

х

3

V

V

4

V

V

х

5

х

х

х

х

6

х

V

х

х

х

7

х

V

х

х

2,6

1,4

х

8

1,8

6,8

V

V

1,8

2,7

V

9

х

х

х

х

х

х

2,6

х

1

2

3

4

5

6

7

8

3. Нахождение списка максимальных классов совместимости

Используя треугольную таблицу, составляем список максимальных классов совместимости:

1) Ф=Х

2) 7~8,9 Ф={7,8}{7,9}

3) 6~8 Ф={6,8}{7,8}{7,9}

4) 5~7,8 Ф={5,7,8}{6,8}{7,9}

5) 4~8 Ф={4,8}{5,7,8}{6,8}{7,9}

6) 3~8 Ф={3,8}{4,8}{5,7,8}{6,8}{7,9}

7) 2~8,7,6,4,3 Ф={2,3,8}{2,4,8}{5,7,8}{2,6,8}{7,9}{2,7}

8) 1~8,4,3 Ф={2,3,8}{2,4,8}{5,7,8}{2,6,8}{7,9}{2,7}{1,8,4}{1,8,3}

Ф={2,3,8}{2,4,8}{5,7,8}{2,6,8}{7,9}{2,7}{1,8,4}{1,8,3}

4. Составление списка простых классов совместимости

{5,7,8}

2,6; 1,4; 1,8

{2,6,8}

2,7; 6,8

{2,4,6}

6,8

{2,3,8}

6,8

{1,3,8}

1,8

{1,4,8}

1,8

{2,7}

O

{7,9}

2,6

{5,7}

2,6; 1,4

{7,8}

O

{5,8}

1,8

{2,6}

O

{2,8}

6,8

{6,8}

2,7

{2,4}

O

{4,8}

O

{2,3}

O

{3,8}

O

{1,4}

O

{1,8}

1,8

{1,3}

O

{1}

O

{2}

O

{3}

O

{4}

O

{5}

O

{6}

O

{7}

O

{8}

O

{9}

O

5. Нахождение минимального замкнутого покрытия

Простые классы

Состояния

Порожденные множества

1

2

3

4

5

6

7

8

9

1,4

1,8

2,6

2,7

6,8

5,6

5,7,8

x

x

x

o

o

o

0

2,6,8

x

x

x

x

o

x

0

2,4,8

x

x

x

o

х

2,3,8

x

x

x

o

0

1,4,8

x

x

x

x

x

1,3,8

x

x

x

x

0

2,7

x

x

x

7,9

x

x

o

0

7,8

x

x

2,6

x

x

x

0

2,4

x

x

0

4,8

x

x

2,3

x

x

3,8

x

x

1,4

x

x

x

1,3

x

x

5

x

9

x

Выбираем новые состояния:

{5,7,8} - b1

{1,4,8} -- b2

{2,6} -- b3

{1,3} -- b4

{9} -- b5

6. Таблица переходов и выходов минимального автомата

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

b1

b2

b3

b4

b5

Z1

b3/-

b1/w2

b2(b4)/w1

b1/-

b3/-

Z2

b2/-

b2/w1

b3/w2

b2(b4)/w1

b1/-

Z3

b1/-

b1/-

b3/-

-/-

b3/-

Z4

b2/-

b3/-

-/-

b2(b4)/-

b2/-

7. Синтез конечного автомата

Производим кодирование входов, выходов и состояний:

Входы:

Х1

Х2

Z1

0

0

Z2

0

1

Z3

1

0

Z4

1

1

Состояния:

t1

t2

t3

b1

0

0

0

b2

0

0

1

b3

0

1

0

b4

0

1

1

b5

1

0

0

Выходы:

y

w1

0

w2

1

Функции возбуждения памяти

D-триггера

Переходы:

000

001

010

011

100

00

010

000

011

000

010

01

001

001

010

001

000

10

000

000

010

-

010

11

001

010

-

011

001

Выходы:

000

001

010

011

100

00

-

1

0

-

-

01

-

0

1

0

-

10

-

-

-

-

-

11

-

-

-

-

-

Таблицу переходов автомата соответствует таблице возбуждения памяти синтезируемого автомата для D-триггера:

000

001

010

011

100

00

010

000

011

000

010

01

001

001

010

001

000

10

000

000

010

-

010

11

001

010

-

011

001

8. Получение логических функций выходов конечного автомата

0= ;

1=0

;

Используя таблицу функции возбуждения памяти D-триггера, получим следующие логические функции переходов конечного автомата:

ц10= ---------- ц 20=

;

ц30=

;

ц 11= ц10 ;

ц 21 = ц 20

ц 31= ц 30

Минимизация логических функций

Для минимизации логических функций будем использовать карты Карно. Y1()

*

*

*

*

*

*

*

1

*

*

*

*

*

1

*

*

*

y= ;

1

1

*

1

1

1

1

*

1

1

ц 2 = ;

1

1

1

*

1

1

1

1

*

ц 3= ;

10. Синтез функциональной схемы

  • совместимость автомат логический конечный
  • 11. Принципиальная электрическая схема
  • Список литературы
  • 1. Никишечкин А. П. Теория дискретных систем управления. Учебное пособие. — М.: ИЦ ГОУ МГТУ «Станкин», 2006 — 242 с.
  • 2. Интегральные микросхемы: Справочник / Б. В. Тарабрин, Л. Ф. Лунин, Ю. Н. Смирнов и др.; Под ред. Б. В. Тарабрина. — М.: Радио и связь, 1983 — 528 с., ил.
ПоказатьСвернуть
Заполнить форму текущей работой