Главная База знаний "Allbest" Программирование, компьютеры и кибернетика Минимизация конечных автоматов

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

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

Рубрика Программирование, компьютеры и кибернетика
Вид контрольная работа
Язык русский
Дата добавления 22.06.2012
Размер файла 215,8 K

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

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

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

????????? ?? http://www.allbest.ru/

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}

Ш

{7,9}

2,6

{5,7}

2,6; 1,4

{7,8}

Ш

{5,8}

1,8

{2,6}

Ш

{2,8}

6,8

{6,8}

2,7

{2,4}

Ш

{4,8}

Ш

{2,3}

Ш

{3,8}

Ш

{1,4}

Ш

{1,8}

1,8

{1,3}

Ш

{1}

Ш

{2}

Ш

{3}

Ш

{4}

Ш

{5}

Ш

{6}

Ш

{7}

Ш

{8}

Ш

{9}

Ш

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

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

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

*

*

*

*

*

*

*

1

*

*

*

*

*

1

*

*

*

y= ;

1

1

*

1

1

1

1

*

1

1

ц 2 = ;

1

1

1

*

1

1

1

1

*

ц 3= ;

Список литературы

автомат совместимость конечный электрический

1. Никишечкин А.П. Теория дискретных систем управления. Учебное пособие. - М.: ИЦ ГОУ МГТУ «Станкин», 2006 - 242 с.

2. Интегральные микросхемы: Справочник / Б.В. Тарабрин, Л.Ф. Лунин, Ю.Н. Смирнов и др.; Под ред. Б.В. Тарабрина. - М.: Радио и связь, 1983 - 528 с., ил.

Размещено на Allbest.ru


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

  • Минимизация абстрактного автомата

    Методика минимизации абстрактного автомата. Порядок построения графа полученного минимизированного автомата. Синтез на элементах ИЛИ-НЕ и Т-тригерах. Составление таблицы переходов. Разработка микропрограммного автомата, реализующего микропрограмму.

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

  • Абстрактный автомат Мили

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

    курсовая работа [823,8 K], добавлен 19.07.2012

  • Табличный метод структурного синтеза конечных автоматов

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

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

  • Синтез управляющего автомата с жесткой логикой, реализующего функцию умножения, начиная с младших разрядов множителя

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

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

  • Разработка конечного цифрового аппарата

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

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

  • Алгоритм синтеза автомата

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

    контрольная работа [141,5 K], добавлен 14.10.2012

  • Моделирование дискретного автомата

    Содержание и особенности этапов синтеза дискретного автомата. Граф переходов-выходов автомата Мура, кодирование входных и выходных сигналов. Построение функциональной схемы автомата Мура на RS–триггерах и элементах И-НЕ в программе Electronic WorkBench.

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

  • Синтез распознающего автомата

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

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

  • Проектирование управляющего автомата в САПР Quartus II

    Разработка управляющего автомата процессора с жесткой логикой в САПР Quartus II. Построение схемы функциональной микропрограммы команды "Исключающее ИЛИ" в размеченном виде. Унитарное кодирование состояний автомата. Запись функций переходов и выходов.

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

  • Синтез конечного распознающего автомата

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

    дипломная работа [1,8 M], добавлен 18.08.2013

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

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