Некоммутативный граф потока сигналов - Noncommutative signal-flow graph

Система с множеством входов и выходов, представленная в виде некоммутативного матричного графа потока сигналов.

В теория автоматов и теория управления, филиалы математика, теоретическая информатика и системная инженерия, а некоммутативный граф потока сигналов инструмент для моделирования[1] взаимосвязанных систем и конечных автоматов путем сопоставления краев ориентированный граф к звенеть или же полукольцо.

Единственный край масса может представлять собой массив импульсные реакции сложной системы (см. рисунок справа),[2] или персонаж из алфавит снял входная лента конечного автомата,[3] в то время как граф может представлять поток информации или переходы между состояниями.

Какими бы разнообразными ни были эти приложения, они во многом основаны на одной и той же теории.[4][5]

Определение

Фрагмент сигнально-поточного графа.

Учитывать п уравнения с участием п+1 переменные {Икс0, Икс1,...,Иксп}.

с аij элементы в кольце или полукольце р. Бесплатная переменная Икс0 соответствует исходной вершине v0, таким образом, не имея определяющего уравнения. Каждому уравнению соответствует фрагмент ориентированный граф грамм=(V,E) как показано на рисунке.

Веса ребер определяют функцию ж из E к р. Наконец исправьте выходную вершину vм. График потока сигналов - это сбор этих данных. S = (грамм=(V,E), v0,vм V, ж : Eр). Уравнения могут не иметь решения, но когда оно есть,

с Т элемент р называется прирост.

Последовательное устранение

Метод обратной петли

Есть несколько[2] некоммутативные обобщения Правило масона.[требуется разъяснение ] Самым распространенным является метод цикла возврата (иногда называют метод прямого возврата (FRL), имея двойную метод обратного возврата (BRL)). Первое строгое доказательство[требуется разъяснение ] приписывается Риглу,[2] так это иногда называют Правило Ригла.[6]

Как и в случае с правилом Мейсона, эти[требуется разъяснение ] Выражения усиления объединяют термины теоретико-графическим способом (коэффициенты усиления петли, произведения путей и т. д.). Как известно, они справедливы над произвольным некоммутативным кольцом и над полукольцом регулярных выражений.[5]

Официальное описание

Метод[требуется разъяснение ] начинается с перечисления всех путей от ввода до вывода,[требуется разъяснение ] проиндексировано j J. Мы используем следующие определения:

  • В j-го путь продукта является (злоупотреблением обозначениями) кортежем kj краевые грузы вдоль него:
[требуется разъяснение ]
  • К расколоть вершина v состоит в том, чтобы заменить его источником и стоком с учетом исходной инцидентности и весов (это обратный морфизму графа, принимающий источник и сток в v).
  • В усиление контура вершины v w.r.t. подграф ЧАС - это усиление от источника к приемнику графа потока сигналов, разделенного на v после удаления всех вершин не в ЧАС.
  • Каждый путь определяет порядок вершин вдоль него. По пути j, то я-го Фактор узла FRL (BRL) это (1-Sя(j))−1 куда Sя(j) - усиление контура я-я вершина вдоль j-й w.r.t. подграф, полученный удалением v0 и все вершины впереди (позади).

Вклад j-й путь к выигрышу - это произведение вдоль пути, чередующееся между весами произведения пути и коэффициентами узлов:

так что общий выигрыш

Пример

Некоммутативный граф потока сигналов из Икс к z

Рассмотрим показанный график потока сигналов. Из Икс к z, есть два произведения пути: (d) и (е, а). Вдоль (d), вклады FRL и BRL совпадают, поскольку оба имеют одно и то же усиление контура (разделение которого снова появляется в правом верхнем углу таблицы ниже):

Если умножить его коэффициент узла и вес пути, то его вклад в усиление составит

По пути (е, а), FRL и BRL немного отличаются, каждая из которых имеет отдельные разбиения вершин. у и z как показано в следующей таблице.

Return Loop Split Table.png

Добавление к Тd, чередующегося произведения узловых факторов и весов путей, мы получаем два выражения усиления:

и

Эти значения легко увидеть, если использовать тождества (ab)−1 = б−1а−1 и а(1-ба)−1=(1-ab)−1а.

Приложения

Матричные графики потока сигналов

Рассмотрим уравнения

и

Эта система может быть смоделирована как скалярный граф потока сигналов с множеством входов и выходов. Но переменные естественным образом распадаются на слои, которые можно собрать в векторы. Икс=(Икс1,Икс2)ту=(у1,у2)т иz=(z1,z2)т. Это значительно упрощает матричный график потока сигналов как показано на рисунке вверху статьи.

Применение метода цикла прямого возврата тривиально, поскольку существует продукт с одним путем (C,А) с одним контурным усилением B в у. Таким образом, в виде матрицы эта система имеет очень компактное представление карты ввода-вывода.

Конечные автоматы

Представление конечного автомата в виде (некоммутативного) графа потоков сигналов над полукольцом.

Важным видом некоммутативного графа потока сигналов является конечное состояние автомат над алфавитом .[3][4]

Последовательные соединения соответствуют конкатенации слов, которые могут быть расширены до подмножеств свободный моноид . За А, B

Параллельные соединения соответствуют установить союз, который в этом контексте часто пишут А+B.

Наконец, петли естественно соответствуют Клини закрытие

куда это пустое слово. Подобие бесконечному геометрическому ряду

является более чем поверхностным, поскольку выражения этой формы служат «инверсией» в этом полукольцо.[7]

Таким образом, подмножества построенный из конечного числа этих трех операций, можно отождествить с полукольцо из обычные выражения. Аналогично, конечные графы, ребра которых взвешены подмножествами можно отождествить с конечными автоматами, хотя обычно эта теория начинается с одиночка устанавливает как на рисунке.

Этот автомат детерминирован, поэтому мы можем однозначно перечислять пути с помощью слов. При использовании метода цикла возврата вклады пути:

  • дорожка ab, имеет узловые факторы (c*, ), что дает вклад
  • дорожка Ада, имеет узловые факторы (c*, c*, ), что дает вклад
  • дорожка ба, имеет узловые факторы (c*, ), что дает вклад

Таким образом язык принимаемый этим автоматом (коэффициент усиления его графа потока сигналов) является суммой этих членов

Исторические заметки

Смотрите также

Примечания

Рекомендации

  • Андалуси, С .; Chalh, Z .; Сьюер, К. (2006). "Бесконечный ноль линейных моделей графа облигаций, меняющихся во времени: Графические правила". Разработка компьютерных систем управления, Международная конференция IEEE по приложениям управления, 2006 г.. С. 2962–2967. Дои:10.1109 / CACSD-CCA-ISIC.2006.4777109.CS1 maint: ref = harv (связь)
  • Книга, Рональд; Даже, Шимон; Грейбах, Шейла; Отт, Джин (1971). «Неоднозначность графиков и выражений» (PDF). Транзакции IEEE на компьютерах. IEEE. 100 (2): 149–153. Дои:10.1109 / т-с.1971.223204.CS1 maint: ref = harv (связь)
  • Brzozowski, J.A .; Маккласки-младший, Э.Дж. (1963). «Методы графа потока сигналов для диаграмм состояний последовательных цепей». Транзакции IEEE на электронных компьютерах. IEEE (2): 67–76. Дои:10.1109 / PGEC.1963.263416.CS1 maint: ref = harv (связь)
  • Грейбах, Шейла (1965). «Новая теорема о нормальной форме для грамматик контекстно-свободной структуры фраз». Журнал ACM. ACM. 12 (1): 42–52. Дои:10.1145/321250.321254.CS1 maint: ref = harv (связь)
  • Куич, Вернер; Саломаа, Арто (1985). Полукольца, автоматы и языки. Springer-Verlag.CS1 maint: ref = harv (связь)
  • Лоренс, Чарльз С. (1964). Графы: для моделирования и анализа линейных систем. Макгроу-Хилл.CS1 maint: ref = harv (связь)
  • Плиам, Джон; Ли, Э. Брюс (1995). «О глобальных свойствах взаимосвязанных систем». IEEE Transactions on Circuits and Systems I: Fund. Теория и приложения. IEEE. 42 (12): 1013–1017. Дои:10.1109/81.481196.CS1 maint: ref = harv (связь)
  • Ригл, Дэрил; Лин, П. (1972). «Матричные графы потоков сигналов и оптимальный топологический метод оценки их усиления». IEEE Transactions по теории цепей. IEEE. 19 (5): 427–435. Дои:10.1109 / tct.1972.1083542.CS1 maint: ref = harv (связь)