МИНИМИЗАЦИЯ СОСТОЯНИЙ АВТОМАТА
Минимизация числа состояний выполняется в два этапа. На этапе первичной минимизации необходимо найти и объединить в одно все состояния, имеющие одинаковые выходные символы и при переходе вырабатывающие одинаковые состояния. Второй этап минимизации проводится с помощью треугольной таблицы. ПЕРВИЧНАЯ МИНИМИЗАЦИЯ Как видно из таблицы 1.3.1 состояния а31, а32, а50, а57 под воздействием α переходят в а0 и вырабатывают 0, следовательно, их можно объединить в одну группу. Рассуждения аналогичны и для остальных состояний. Обозначим получившиеся состояния буквой "в" и перепишем таблицу переходов-выходов.
Таблица 1.4.1 – Таблица переходов-выходов
Как видно таблица 1.4.1 не является окончательной, и минимизацию можно продолжить. Обозначим получившиеся состояния буквой "с" и перепишем таблицу переходов-выходов.
Таблица 1.4.2 – Таблица переходов-выходов
Как видно таблица 1.4.2 не является окончательной, и минимизацию можно продолжить. Обозначим получившиеся состояния буквой "d" и перепишем таблицу переходов-выходов.
Таблица 1.4.3 – Таблица переходов-выходов
Как видно таблица 1.4.3 является окончательной на данном этапе минимизации. Теперь можно перйти к следующему этапу – минимизации с помощью треугольной таблицы.
МИНИМИЗАЦИЯ С ПОМОЩЬЮ ТРЕУГОЛЬНОЙ ТАБЛИЦЫ Составим треугольную таблицу (рисунок 1.4.2), руководствуясь следующими правилами: 1) строки таблицы обзначаются состояниями d1, d2, …, dn-1, а столбцы d0, d1, …, dn-2, где n – число состояний абстрактного автомата; 2) на пересечении i-той строки и j-того столбца записываются условия, при которых возможно объединение состояний di и dj; если состояния нельзя объединить ни при каких условиях, ставится знак "х"; если они объединяются безусловно, то ставится знак "v"; окончательное объединение состояний определяется на основе непротиворечивости условий.
Выпишем из таблицы пары эквивалентных состояний:
Так как любое di состояние из промежутка от d0 до d14 нельзя объединить ни с каким состоянием dj из этого промежутка (в треугольной таблице на пересечении di и dj стоит знак "x" ), то при любом варианте укрупнения получим число состояний не менее 15. Исходя из этого получим следующие пары эквивалентных состояний, обозначенные буквой "е": е0 = (0, 15) е1 = (1, 16) е2 = (2, 17) е3 = (3, 18) е4 = (4, 19) е5 = (5, 20) е6 = (6, 21) е7 = (7, 22) е8 = (8, 23) е9 = (9, 24) е10 = (10, 25) е11 = (11, 26) е12 = (12, 15) е13 = (13, 16) е14 = (14, 17) Полученные пары полностью удовлетворяют условиям замкнутости и полноты. На основе полученных пар получаем таблицу переходов-выходов минимального автомата (таблица 1.4.2.1).
Таблица 1.4.2.1 – Таблица переходов-выходов минимального автомата
СТРУКТУРНЫЙ СИНТЕЗ КОНЕЧНОГО АВТОМАТА УСТРАНЕНИЕ КРИТИЧЕСКИХ СОСТЯЗАНИЙ В СХЕМЕ Для устранения критических состязаний в схеме применяют: 1) Генератор тактовых импульсов. Недостатки: жесткие требования к стабильности длительности импульсов генератора, относительно низкое быстродействие. Достоинства: небольшие аппаратурные затраты. 2) Вспомогательную память. Недостатки: большие аппаратурные затраты, низкое быстродействие. Достоинства: высокая стабильность работы автомата. 3) Специальное кодирование состояний. Недостатки: большие аппаратурные затраты, низкое быстродействие. Достоинства: высокая стабильность работы автомата.
Наиболее оптимальным в данном случае является первый способ.
КОДИРОВАНИЕ СОСТОЯНИЙ, ВХОДНЫХ И ВЫХОДНЫХ СИГНАЛОВ Закодируем состояния (таблица 2.2.1), входные (таблица 2.2.2) и выходные (таблица 2.2.3) сигналы.
Таблица 2.2.1 – Кодированные состояния
Таблица 2.2.2 – Кодированные входные сигналы
Таблица 2.2.3– Кодированные выходные сигналы
СОСТАВЛЕНИЕ КОДИРОВАННОЙ ТАБЛИЦЫ ПЕРЕХОДОВ На основе таблиц 2.2.1, 2.2.2 и 1.4.2.1 построим кодированную таблицу переходов (таблица 2.3.1).
Таблица 2.3.1 – Кодированная таблица переходов
Популярное: Как распознать напряжение: Говоря о мышечном напряжении, мы в первую очередь имеем в виду мускулы, прикрепленные к костям ... Как выбрать специалиста по управлению гостиницей: Понятно, что управление гостиницей невозможно без специальных знаний. Соответственно, важна квалификация... Почему человек чувствует себя несчастным?: Для начала определим, что такое несчастье. Несчастьем мы будем считать психологическое состояние... Почему люди поддаются рекламе?: Только не надо искать ответы в качестве или количестве рекламы... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (713)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |