Упрощение условий перехода в МПА

 

 

Учет недоопределенности условий пере-

хода в МПА позволяет сильнее миними-

зировать число состояний.

Если минимизация не делается или уже

сделана, условия переходов доопределя-

ют , что приводит к их упрощению.

 

 

Для каждого состояния выписывается совокупность всех условий переходов, описываемых конъюнкциями, совмест-
но с реакцией автомата: формируемым
в такте сигналом и состоянием перехода.

Эту совокупность удобно брать из ПТП.

 

Затем каждое условие упрощается путем вычеркивания тех переменных, удаление которых не приводит к возникновению неоднозначности в описании реакции ав-

томата.

 

 

В результате конъюнкции будут макси- мально сокращены при сохранении ор- тогональности условий для различных реакций.

 

 

Поиск удаляемых переменных выполня-

ется путем пробных вычеркиваний и

проверок их результатов.

После вычеркиваний могут возникать

повторяющиеся выражения, которые

удаляются.

 

 

Примеры

 

 

 

 

 

 

Для автоматов Мура описание реакции можно брать без выходных сигналов, так

как все они одинаковы для S_i.

 

 

Пример

 

 

Выбор способа

Построения МПА.

 

 

Разобранные выше различные процеду-

ры применяются при построении МПА

избирательно - в зависимости от рассмат- риваемых МПА. Зафиксируем наиболее употребимые последовательности дейст-

вий при переходе от микропрограмм к

МПА.

 

 

I.МПА для работы по одному алгоритму с небольшим числом микрокоманд.

1. Получить и проверить содержательную ГСА.

2. Получить кодированную ГСА.

3. Перейти к МСА.

4. Уточнить МСА.

 

 

 

5. Перейти от МСА к ГСА.

6. Построить по ГСА автомат.

 

п.п 3¸5 можно не выполнять при уверенности, что в алгоритме нет фиктивных (лишних) ветвей.

 

 

II.МПА Мура для работы по нескольким частным алгоритмам.

1. Получить и проверить част-

ные содержательные ГСА.

2. Получить кодированные ГСА.

3. Построить частные МСА.

4. Получить объединенную МСА.

5. Уточнить ОМСА.

 

6. Перейти к объединенной ГСА.

7. Построить по ОГСА автомат.

 

п. 5 можно опустить при уверенности, что в алгоритмах нет фиктивных (лишних) ветвей.

 

Если ОГСА слишком громоздка, автомат можно строить по МСА.

 

 

Тогда вместо п.п 6,7 выполняются:

 

6¢.Доопределить формулы пере- ходов ОМСА так же, как для перехода к ОГСА.

7¢.Построить по доопределенной МСА автомат.

 

III.МПА Мили для работы по несколь- ким частным алгоритмам.

1. Получить и проверить частные содержательные ГСА.

2. Получить частные МСА.

3. Построить ОМСА.

4. Уточнить ОМСА.

5. Построить по ОМСА автомат.

6. Минимизировать МПА.

7. Упростить условия переходов.