_WELCOMETO Radioland

Главная Схемы Документация Студентам Программы Поиск Top50  
Поиск по сайту



Навигация
Главная
Схемы
Автоэлектроника
Акустика
Аудио
Измерения
Компьютеры
Питание
Прог. устройства
Радио
Радиошпионаж
Телевидение
Телефония
Цифр. электроника
Другие
Добавить
Документация
Микросхемы
Транзисторы
Прочее
Файлы
Утилиты
Радиолюб. расчеты
Программирование
Другое
Студентам
Рефераты
Курсовые
Дипломы
Информация
Поиск по сайту
Самое популярное
Карта сайта
Обратная связь

Студентам


Студентам > Курсовые > Синтез комбинацонных схем и конечных автоматов

Синтез комбинацонных схем и конечных автоматов

Страница: 5/10

 

Таблица 2.3.3 – Общая таблица переходов и выходов автомата

 

Перейдём непосредственно к минимизации полученного автомата по числу состояний. Для этого воспользуемся алгоритмом, известным в литературе как метод Гриса - Хопкрофта. Его достоинство в том, что он даёт гарантированно минимальную форму автомата. Однако в общем случае он является довольно трудоёмким и применяется, как правило, для автоматов с небольшим количеством состояний. Он основан на свойстве транзитивности эквивалентности

 

                                  (si ~ sj) ∩ (sj ~ sk)  (si ~ sk)                              (2.3.1)

 

Пара эквивалентных состояний переходит при всех возможных значениях входа в пары также эквивалентных состояний.

Алгоритм состоит из следующих шагов.

Сначала разбиваем все состояния автомата на множества по признаку совпадения выходных сигналов. В нашем случае получаем 2 множества:       S1 = {0, 2, 4, 6}  и  S2 = {1, 3, 5, 7}.

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

 

пары

0

1

2

3

0;2

0;4

1;5

2;6

3;7

0;4

0;0

1;1

2;2

3;3

0;6

0;4

1;5

2;6

3;7

2;4

4;0

5;1

6;2

3;7

2;6

4;4

5;5

6;6

7;7

4;6

0;4

1;5

2;6

3;7

1;3

2;6

3;7

4;0

5;1

1;5

2;2

3;3

4;4

5;5

1;7

2;6

3;7

4;0

5;1

3;5

6;2

7;3

0;4

1;5

3;7

6;6

7;7

0;0

1;1

5;7

2;6

3;7

4;0

5;1