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

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

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

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

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

Определение

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

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

{ displaystyle x_ {i} = sum _ {j = 0} ^ {n} a_ {ij} x_ {j}, ; ; ; 1 leq i leq n,}

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

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

{ displaystyle x_ {m} = Tx_ {0},}

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

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

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

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

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

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

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

В j-го путь продукта является (злоупотреблением обозначениями) кортежем k_j краевые грузы вдоль него:

{ displaystyle p_ {j} = (w_ {k_ {j}} ^ {(j)}, ldots, w_ {2} ^ {(j)}, w_ {1} ^ {(j)}).}

^{[требуется разъяснение ]}

К расколоть вершина v состоит в том, чтобы заменить его источником и стоком с учетом исходной инцидентности и весов (это обратный морфизму графа, принимающий источник и сток в v).
В усиление контура вершины v w.r.t. подграф ЧАС - это усиление от источника к приемнику графа потока сигналов, разделенного на v после удаления всех вершин не в ЧАС.
Каждый путь определяет порядок вершин вдоль него. По пути j, то я-го Фактор узла FRL (BRL) это (1-S_я^(j))⁻¹ куда S_я^(j) - усиление контура я-я вершина вдоль j-й w.r.t. подграф, полученный удалением v₀ и все вершины впереди (позади).

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

{ displaystyle T_ {j} = prod _ {i = k_ {j}} ^ {1} (1-S_ {i} ^ {(j)}) ^ {- 1} w_ {i} ^ {(j )},}

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

{ displaystyle T = sum _ {j in J} T_ {j}.}

Пример

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

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

{ displaystyle f + e (1-b) ^ {- 1} c,}

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

{ displaystyle T_ {d} = left [1-f-e (1-b) ^ {- 1} c right] ^ {- 1} d.}

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

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

{ Displaystyle T ^ {(FRL)} = left [1-fe (1-b) ^ {- 1} c right] ^ {- 1} d + left [1-fe (1-b) ^ { -1} c right] ^ {- 1} e (1-b) ^ {- 1} a,}

и

{ Displaystyle T ^ {(BRL)} = left [1-fe (1-b) ^ {- 1} c right] ^ {- 1} d + (1-f) ^ {- 1} e left [1-bc (1-f) ^ {e} right] ^ {- 1} a,}

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

Приложения

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

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

{ displaystyle y_ {i} = sum _ {j = 1} ^ {2} a_ {ij} x_ {j} + sum _ {j = 1} ^ {2} b_ {ij} y_ {j}}

и

{ displaystyle z_ {i} = sum _ {j = 1} ^ {2} c_ {ij} y_ {j},}

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

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

{ Displaystyle T = C (1-B) ^ {- 1} A.}

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

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

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

Последовательные соединения соответствуют конкатенации слов, которые могут быть расширены до подмножеств свободный моноид ${ Displaystyle Sigma ^ {*}}$ . За А, B ${ Displaystyle substeq Sigma ^ {*}}$

{ Displaystyle A cdot B = {ab mid a in A, b in B }.}

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

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

{ displaystyle A ^ {*} = { lambda } + A + AA + AAA + cdots,}

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

{ Displaystyle (1-х) ^ {- 1} = 1 + х + х ^ {2} + х ^ {3} cdots,}

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

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

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

дорожка ab, имеет узловые факторы (c^*, ${ displaystyle lambda}$ ), что дает вклад

{ displaystyle ac ^ {*} b,}

дорожка Ада, имеет узловые факторы (c^*, c^*, ${ displaystyle lambda}$ ), что дает вклад

{ displaystyle ac ^ {*} dc ^ {*} a,}

дорожка ба, имеет узловые факторы (c^*, ${ displaystyle lambda}$ ), что дает вклад

{ displaystyle bc ^ {*} а.}

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

{ displaystyle L = ac ^ {*} b + ac ^ {*} dc ^ {*} a + bc ^ {*} a.}

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

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

Примечания

^ Лоренс 1964.
^ ^а ^б ^c Ригл и Лин 1972.
^ ^а ^б Бжозовский и Маккласки, 1963 г..
^ ^а ^б Book et al. 1971 г..
^ ^а ^б Плиам и Ли 1995.
^ Андалуси, Чал и Сьюер, 2006 г., с. 2962.
^ Куич и Саломаа 1985.