У вас вопросы?
У нас ответы:) SamZan.net

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

Работа добавлена на сайт samzan.net: 2016-06-20

Поможем написать учебную работу

Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.

Предоплата всего

от 25%

Подписываем

договор

Выберите тип работы:

Скидка 25% при заказе до 3.4.2025

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

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

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

) Ф=Х

) 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}

Ø

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

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

Состояния

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

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

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

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 с.

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




1. . Функция. Основные понятия.
2. Содержательное и формальное в теории познания
3. История Франкского Королевства эпохи Меровингов
4. ТЕМАТИЧНА МОДЕЛЬ ТА МЕТОД ПРОГНОЗУ ГАЗОСПОЖИВАННЯ З УРАХУВАННЯМ ЦИКЛІЧНОСТІ 01
5. Большой бонус
6. Доклад- Исследование электрической цепи переменного тока при последовательном соединении
7. .2014 Маршрут работает по расписанию на воскресные дни в полном объеме транспортной ра
8. з курсу основ картографії втім деякі суттєві поняття та властивості картографічних зображень заслуговують.html
9. Уильям Джеймс Многообразие религиозного опыта
10. Рисуночный тест-как метод психоанализа

Материалы собраны группой SamZan и находятся в свободном доступе