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

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

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

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

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

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

от 25%

Подписываем

договор

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

Скидка 25% при заказе до 27.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. ЛЕКЦІЯ 10. Всесвітнє господарство та міжнародні економічні відносини
3. по теме Историческая мозаика древнерусский быт
4. реферат дисертації на здобуття наукового ступеня кандидата педагогічних наук
5. .1 Летательные аппараты от древности до наших дней 1
6. 27 лет Требования к мужскому смокингу должны включать- внешний вид; возрастную группу; конструктивные особ
7. драматизаций Принципиально важно ознакомить ребенка с разными типами задач оказать помощь в выявлении сп
8. передано прийнято
9. докладная записка 2 справка докладная записка заявление автобиография резюме
10.  Работа печатается на одной стороне листа белой бумаги формата А4 210х297 мм

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