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

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

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

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

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

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

от 25%

Подписываем

договор

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

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

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. 6 Характеристика ФАП- небольшое преобладание правого полушария оценка 8 Психоэмоциональное состояние
4. Психологический диагноз
5. тематика Д. искусство география биология верны все ответы
6. Египет в ближневосточной политике США (1952-1981 гг.)
7. Московские музеи
8. Тема- Вводный инструктаж
9. Курс лекций по анализу экономической деятельности
10. Тема 4 Мировой рынок капиталаВопросы1
11. докладов до 50 баллов ~ индивидуально
12. Ясно что исходным материалом для разработки психических фактов должны служить как простейшие психические
13. ФИНАНСОВЫЙ УНИВЕРСИТЕТ ПРИ ПРАВИТЕЛЬСТВЕ РОССИЙСКОЙ ФЕДЕРАЦИИ Финансовый университет Уфимский филиал
14. Экологическое состояние бассейна реки Западная Двина в пределах Смоленской области
15. реферат дисертації на здобуття наукового ступеня кандидата фармацевтичних наук Х
16. Фашизм истоки сущность роль в современном обществе
17. Северный Арктический федеральный университет имени М
18. Анализ порядка расчета уплаты налогов на доходы физических лиц на современном этапе в Беларуси
19. ОК как фактор эффективности деятельности
20.  Оценка привлекательности и выбор международных рынков Рынком называют сферу обмена и по этой причине р

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