Главная База знаний "Allbest" Коммуникации, связь, цифровые приборы и радиоэлектроника Минимизация конечных автоматов

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

Нахождение списка максимальных классов совместимости, минимального замкнутого покрытия. Составление списка простых классов совместимости, таблицы переходов и выходов минимального автомата. Обзор получения логических функций выходов конечного автомата.

Рубрика Коммуникации, связь, цифровые приборы и радиоэлектроника
Вид контрольная работа
Язык русский
Дата добавления 23.06.2012
Размер файла 1,2 M

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://allbest.ru/

Размещено на http://allbest.ru/

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

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

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

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

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

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

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

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

Москва, 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 с., ил.
  • Размещено на Allbest.ru

Подобные документы

  • Синтез цифрового автомата с памятью

    Проектирование цифровых автоматов Мили и Мура с памятью в булевом базисе по заданной ГСА. Составление частично структурированной таблицы переходов-выходов. Построение функций выходов, логической схемы автомата. Особенности его экспериментальной проверки.

    курсовая работа [628,7 K], добавлен 14.07.2012

  • Проектирование элементов ЭВУ

    Построение графа синтезируемого автомата. Определение количества элементов памяти. Составление таблицы переходов, выходов и возбуждения конечного автомата. Переход от исходного автомата Мили к эквивалентному автомату Мура. Алгоритмы вычисления функций.

    курсовая работа [714,7 K], добавлен 21.05.2013

  • Разработка функциональной схемы конечного автомата

    Алгоритм работы автомата Мили в табличном виде. Графический способ задания автомата. Синтез автомата Мили на Т-триггерах. Кодирование состояний автомата. Таблицы кодирования входных и выходных сигналов. Таблица переходов и выходов абстрактного автомата.

    курсовая работа [24,7 K], добавлен 01.04.2010

  • Разработка структуры операционной части автомата

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

    курсовая работа [868,4 K], добавлен 07.04.2012

  • Теория автоматов

    Управляющий автомат и его связь с операционным автоматом. Разработка алгоритма работы управляющего автомата. Построение кодированной ПТП, синтез функций возбуждения и выходов. Реализация управляющего автомата с жесткой логикой на заданной элементной базе.

    курсовая работа [57,9 K], добавлен 29.12.2011

  • Синтез цифрового конечного автомата Мура

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

    курсовая работа [2,8 M], добавлен 04.02.2013

  • Синтез цифрового автомата

    Расчет схемы цифрового автомата, функционирующего в соответствии с заданным алгоритмом. Кодирование состояний. Составление таблицы функционирования комбинационного узла автомата. Запись логических выражений. Описание выбранного дешифратора и триггера.

    курсовая работа [423,4 K], добавлен 18.04.2011

  • Синтез многофункционального конечного автомата

    Составление структурной схемы автомата. Выбор элементной базы. Функциональная схема автомата. Задающий генератор и делитель частоты. Преобразователь параллельного кода в последовательный. Формирователь стартовых импульсов. Кодирование и минимизация.

    курсовая работа [3,0 M], добавлен 07.02.2013

  • Проектирование управляющего автомата

    Управляющий цифрового автомат типа Мура. Абстрактный и структурный синтез автомата, построена функциональная схема. Функции выходов и возбуждения элементов памяти. Моделирование на ПК с использованием симулятора ModelSim. Описание автомата на языке VHD.

    курсовая работа [214,2 K], добавлен 07.11.2010

  • Абстрактный синтез конечного автомата

    Формирование алфавитного оператора. Приведение оператора к автоматному виду. Построение графа переходов абстрактного автомата. Кодирование состояний, входных и выходных сигналов. Формирование функций возбуждения и выходных сигналов структурного автомата.

    курсовая работа [66,3 K], добавлен 10.11.2010

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.

© 2000 — 2023, ООО «Олбест» Все права защищены