Cтраница 2
Рассмотрим характеризационную задачу преобразования модели, задающей выходные функции автомата, в модель, определяющую его функции возбуждения. Соответствующую выходной функции fj автомата модель / Л представим взвешенным графом Gfj, множество вершин и дуг которого взаимно однозначно соответствует вершинам и дугам графа переходов автомата Gn, причем дуги графа Gfj взвешены переменной, принимающей значения у - й выходной функции на соответствующих переходах автомата из одного состояния в другое. Дуги графа Gfj ориентированы. Если структура запрещенных фигур не зависит от ориентации дуг, будем рассматривать соответствующий неориентированный граф, обозначая его Gfj. [16]
Каждой компоненте соответствует подавтомат. Графы переходов подавтоматов, соответствующих полученному варианту многокомпонентной раскраски вершин графа сцепления, приведены на рис. 4.5. Частичное декартово произведение этих трех графов переходов определяет граф переходов исходного автомата с шестью внутренними состояниями. На рис. 4.6 приведена его реализация с учетом разложения на функционально несвязные сомножители. [17]
Задача соседнего кодирования внутренних состояний автомата в многозначном структурном алфавите сводится к вложению графа переходов автомата в ( К, и) - куб, где К - мощность используемого структурного алфавита; и - число кодирующих разрядов. При этом переходы из одного состояния в другое осуществляются только по ребрам ( К, и) - куба и коды соответствующих его вершин сопоставляются с вершинами графа переходов. Знание структуры запрещенных фигур вложения графа в ( К, и) - куб позволяет осуществлять соседнее кодирование внутренних состояний в заданном структурном алфавите преобразованием графа переходов автомата к ЛГ-кубируемому виду путем введения минимального числа дополнительных ( неустойчивых) состояний. Для этого с помощью покрытия семантических таблиц определяется множество ребер исходного графа, введение дополнительных состояний на которые переводит его в класс графов, вложимых в ( К, ) - куб. [18]
Рассмотрим микропроцессорную реализацию асинхронного автомата. Наиболее простая реализация получается, если длины входного и выходного векторов не превышают разрядности используемого микропроцессора. При нарушении этого условия увеличивается время обработки входного вектора, что приводит к снижению верхней граничной частоты спектра входного сигнала. Прочерк в выходном векторе графа переходов автомата будет означать сохранение предыдущего значения соответствующей выходной логической переменной. [19]
Граф переходов автомата Gn содержит в себе информацию о значениях выходных функций на всех переходах до размещения внутренних состояний. Эти значения определяются распределением вектора Y на дугах графа переходов. Каждую выходную функцию fj до размещения внутренних состояний представим в виде модели tyf. S ( U, jj), где 5-носитель модели, совпадающий с множеством вершин графа переходов автомата; U-множество дуг графа переходов; у - распределение значений у - й компоненты вектора Y по дугам графа переходов. [20]