Декомпозиция автоматов

Реальный МПА выполняет законченную функцию управления операционным устройством (управление движением, контролем, декодированием и др.) даже при 10–15 состояниях. Для управления объектами, состоящими из не­скольких устройств, используются более сложные автоматы.

В ряде случаев сложные автоматы можно разделить (декомпозиро­вать) на несколько взаимодействующих автоматов. И если число состояний в МПА1, МПА2, МПАЗ определяется показателями степени числа 2, равными m l, m 2, m 3, то общее число состояний трех взаимодейст­вующих автоматов составит

.

Если М 1 = М 2 = М З = 3, то М = 512, т.е. три взаимодействующих авто­мата по 8 состояний каждый эквивалентны одному сложному автомату с 512 состояниями. При m = 4, M = 2¹² = 4096.

Выделение счетчика в качестве памяти МПА – это и есть один из ва­риантов декомпозиции автоматов. Другим вариантом является система формирова­ния синхросигналов в полисинхронном автомате, т.е. в автома­те, исполь­зующем несколько сигналов синхронизации с разными периода­ми следова­ния во времени.

В этом случае система подключения в нужное время синхротактов с другим периодом следования является самостоятельным автоматом.

Декомпозиция автоматов основана на разложении графа переходов авто­мата в частичное декартово произведение более простых графов [7].

Рассмотрим граф переходов автомата Мура, состояния которого соответст­вуют выходным сигналам. Для автоматов графы переходов – 2-инци­дентные графы, т.к. из любой вершины возможны лишь две исходящие ду­ги (по условию α_i и условию ). Поэтому целесообразно декомпозиро­вать граф G на два подграфа G_b и G_d в соответствии с проекциями графа G на перпендикулярные оси B и D (рис. 71). Проекция на ось В соответствует автомату на счетчике или на регистре сдвига с обратными связями. Проекция на ось D – специальный автомат, но в нем небольшое число состоя­ний, следовательно, он окажется простым при реализации как схем F 1 и F 2, так и блока памяти с унитарным кодированием. Для пояснения принципа

Рис. 71

Рис. 72. Алгоритм управления

декомпозиции сигналы переходов в графе рис. 71 не обозначены, т.к. они не имеют принципиального значения для уяснения существа дела.

Предлагаемый метод декомпозиции за счет «проекции» на две оси осуществим лишь тогда, когда в ГСА после каждой функциональной вершины () возможен переход только к двум другим и по условию или , т.е. нет переходов через несколько логических условий, как в ГСА рис. 72. Однако в этом случае для такой декомпозиции алгоритм может быть преобразован за счет введения после некоторых или пустых операторов.