Graf přechodného signálu

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 23. října 2020; kontroly vyžadují 4 úpravy .

Přechodový graf signálů ( lineární přechodový graf , lineární graf signálů ; anglicky signál-flow graph, SFG ), navržený Claudem Shannonem , ale často nazývaný Masonův graf kvůli jeho práci na tomto termínu - specializovaný graf toku , ve kterém vrcholy odpovídají některým proměnným a hrany spojují incidentní vrcholy s některými funkcemi. Formálněji: orientovaný graf , jehož každý vrchol odpovídá signálu ( váhová funkce ) , závisí nějakým způsobem na signálech ( váhové funkce ) v jiných vrcholech. $i$ $a_{i}$

Grafy přechodných signálů se nejčastěji používají k reprezentaci toku signálů ve fyzickém systému a jeho ovladačích, které tvoří jeden kybernetický fyzický systém . Používá se také v různých elektronických sítích a zesilovačích, digitálních filtrech , filtrech stavových proměnných a některých typech analogových filtrů. V literatuře je běžné, že grafy přechodu signálu jsou spojeny se systémem lineárních rovnic .

Historie

Wai-Kai Chen napsal: „Koncept grafu přechodového signálu vyvinul Shannon [1] při práci s analogovými počítači. Největší podíl na vývoji grafu přechodového signálu má Mason [2] [3] . Ukázal, jak relativně jednoduchým způsobem použít graf přechodového signálu k řešení některých složitých elektronických problémů. Termín signálový přechodový graf byl použit kvůli jeho původní aplikaci v elektronice a jeho podobnosti s elektronickými signály a blokovými diagramy studovaných systémů. [čtyři]

Lawrence napsal: „Před Masonovou prací identifikoval Shannon [1] řadu vlastností toho, co je nyní známé jako průtokové grafy. Bohužel, dokument byl původně velmi omezený ve své klasifikaci a k materiálu mělo přístup jen velmi málo lidí.“ [5]

„Pravidla pro výpočet determinantu Masonova grafu poprvé uvedl a dokázal Shannon pomocí matematické indukce. Jeho dílo zůstalo prakticky neznámé i poté, co Mason v roce 1953 publikoval své klasické dílo. O tři roky později Mason pravidla znovu objevil a dokázal je tím, že se podíval na hodnotu determinantu a na to, jak se mění, když jsou do grafu přidány proměnné. [...]"

Rozsah

Robichaux et al. definují rozsah grafu přechodového signálu takto:

„Rozsahem vyvinutých metod jsou všechny fyzické systémy podobné těmto sítím [postavené z ideálních transformátorů, aktivních prvků a gyrátorů]. Trent [6] ukázal, že do této kategorie spadají všechny fyzikální systémy, které splňují následující podmínky.

Výsledný soustředěný systém se skládá z řady jednoduchých částí, z nichž každá má známé dynamické vlastnosti, které lze definovat rovnicemi pomocí dvou typů skalárních proměnných a parametrů systému. Proměnné prvního typu jsou veličiny, které lze měřit, alespoň teoreticky, připojením měřicího zařízení ke dvěma spojovacím bodům prvku. Proměnné druhého typu charakterizují veličiny, které lze měřit zapojením měřidla do série s prvkem. Relativní rychlosti a polohy, tlakové ztráty a napětí jsou typické veličiny prvního typu, zatímco elektrické proudy, síly, tepelné toky jsou veličiny druhého typu. [...]
Proměnné prvního typu se musí řídit zákonem podobným pravidlu Kirchhoffova napětí, zatímco proměnné druhého typu musí dodržovat zákon podobný pravidlu Kirchhoffova uzlu.
Fyzické rozměry odpovídajících výsledků výpočtů proměnných obou typů musí být konzistentní. Pro systémy, ve kterých jsou tyto podmínky splněny, je možné sestrojit spojnicový graf izomorfní k dynamickým vlastnostem systému popsaným zvolenými proměnnými. Tyto metody [...] lze aplikovat přímo na tyto spojnicové grafy, stejně jako na elektrické sítě, a získat tak přechodový graf signálů systému.“

Základy teorie průtokových grafů

V grafu na obrázku je funkční závislost uzlu označena šipkou, která do něj vstupuje, uzel, který tuto závislost způsobuje, je začátek této šipky a v nejobecnější podobě je graf toku signálu označen pouze příchozími šipkami. ty uzly, které ovlivňují zpracování v přijímacím uzlu, a na každém i -tém uzlu jsou příchozí proměnné zpracovány podle funkce spojené s tímto uzlem , například Fj . (a) tedy představuje množinu explicitních vztahů:

{\begin{aligned}x_{1}&={\text{nezávislá proměnná}}\\x_{2}&=F_{2}(x_{1},x_{3})\\x_{ 3}&=F_{3}(x_{1},x_{2},x_{3})\\\end{aligned}}

Uzel x 1 je izolovaný uzel, protože do něj nevstupuje žádná šipka; rovnice pro x 2 a x 3 odpovídají grafům uvedeným v položkách (b) a (c) obrázku.

Tyto vztahy definují pro každý uzel funkci, která zpracovává vstupy přijaté uzlem. Každý nezdrojový uzel nějakým způsobem kombinuje vstupní signály a vysílá výsledný signál na každé odchozí větvi. "Graf toku, jak byl původně definován Masonem, implikuje soubor funkčních vztahů, ať už lineárních nebo ne" [7] .

Masonovy grafy jsou však obvykle přísnější, což znamená, že každý uzel pouze sčítá zadané šipky a že každá hrana je pouze funkcí uzlu, ze kterého pochází. Za těchto podmínek bude systém napsán následovně:

{\begin{aligned}x_{1}&={\text{nezávislá proměnná}}\\x_{2}&=f_{21}(x_{1})+f_{23}(x_{3 })\\x_{3}&=f_{31}(x_{1})+f_{32}(x_{2})+f_{33}(x_{3})\\\end{aligned}}

Nyní mohou být funkce spojeny s okrajem grafu signálů spojujících pár uzlů , , namísto definování společných funkcí pro každý uzel. Příspěvek uzlu k sobě samému, například pro , se nazývá smyčka. Často jsou tyto funkce jednoduše multiplikativní koeficienty (často nazývané transmitance nebo zisky), například kde - může být nejen skalární, ale také funkcí nějakého parametru, jako je Laplaceova transformační proměnná . Grafy toku signálu se velmi často používají u signálů transformovaných Laplaceem, protože se jedná o systémy lineárních diferenciálních rovnic. V tomto případě se propustnost často označuje jako přenosová funkce. $f_{ij}$ $ij$ $x_{i}$ $x_{j}$ ${\displaystyle f_{33))$ $x_{3}$ ${\displaystyle f_{ij}(x_{j})=c_{ij}x_{j))$ $C$ $s$ $c(s)$

Výběr proměnných

Existuje několik způsobů, jak vybrat proměnné v komplexním systému, a pro každou z nich lze napsat systém rovnic, který lze znázornit jako graf. Psaní rovnic je značně usnadněno, pokud existuje metoda, která umožňuje vykreslovat přímo ze schematického diagramu studovaného systému. Struktura takto získaných grafů zjevně souvisí s topologií schematického diagramu a dokonce i implicitní zohlednění rovnic se stává zbytečným. V některých případech stačí jednoduše znázornit průtokový graf na schematickém diagramu a dojít k řešení problému i bez obrázku.

Nejedinečnost

Graf toku signálu obsahuje stejné množství informací jako rovnice, ze kterých je odvozen; ale mezi grafem a soustavou rovnic neexistuje žádná korespondence jedna ku jedné. Jeden systém vytvoří různé grafy v závislosti na pořadí, ve kterém jsou rovnice použity k nalezení proměnné zapsané na levé straně. [7] Pokud se například každá rovnice týká všech závislých proměnných, pak existují možné grafy. [osm] $n$ $n!$

Lineární přechodový graf signálů

Metody křivkového grafu toku signálu jsou použitelné pouze pro lineární časově invariantní systémy . Při modelování zájmového systému je obvykle prvním krokem stanovení rovnic, které reprezentují fungování systému bez ohledu na jejich povahu. Poté se na základě tohoto systému rovnic sestaví samotný graf.

Graf lineárního přechodového signálu se skládá z uzlů a vážených směrovaných větví. Uzly jsou proměnné rovnic a váhy větví jsou koeficienty. Signály mohou proudit pouze podél větve ve směru označeném šipkou. Graf může představovat pouze operace násobení koeficientem a sčítáním, které jsou dostatečné pro znázornění rovnic spojení. Když signál překročí větev v určeném směru, signál se vynásobí váhou větve. Když dvě nebo více větví jdou do stejného uzlu, jejich výstupy se sečtou.

Pro systémy popsané lineárními algebraickými nebo diferenciálními rovnicemi je graf toku signálu matematicky ekvivalentní soustavě rovnic popisujících systém. V tomto případě lze rovnice definující graf nalézt pro každý uzel sečtením větví zahrnutých v tomto uzlu. Samotné větve zprostředkovávají příspěvky ostatních uzlů, vyjádřené jako hodnota zdrojového uzlu vynásobená váhou spojovací větve, obvykle reálné číslo nebo funkce nějakého parametru (např. proměnná Laplaceova transformace). $s$

Choma, člen IEEE , napsal o lineárních aktivních sítích následující:

„Znázorněním toku signálu (nebo „grafem“, jak se tomu běžně říká) rozumíme diagram, který zobrazením algebraických vztahů mezi relevantními proměnnými a větvemi sítě jednoznačně představuje, jak přivedený vstupní signál „teče“ ze vstupních portů do porty.závěr [...]“ [9] .

Užitečnost analýzy grafu toku signálu také popsal počítačový vědec Chen:

„Analýza lineárního systému nakonec vede k řešení systému lineárních algebraických rovnic. Jako alternativu k obvyklým algebraickým metodám řešení systému lze získat řešení zvážením vlastností určitých orientovaných grafů spojených se systémem. [...] Neznámé rovnice odpovídají uzlům grafu, zatímco lineární vztahy mezi nimi se jeví jako směrované hrany spojující uzly. [...] Souvislé orientované grafy lze v mnoha případech konstruovat přímo pohledem na fyzikální systém, aniž by bylo nutné nejprve formulovat odpovídající rovnice“ [10] .

Poznámky

↑ 12 n . l . Shannon. Teorie a návrh strojů s lineárními diferenciálními rovnicemi (anglicky) : journal. - Řízení palby Výboru pro výzkum národní obrany USA: Zpráva 411, sekce D-2, 1942. - Leden. Přetištěno v Claude E. Shannon: Collected Papers / NJA Sloane; Aaron D. Wyner. - Wiley IEEE Press, 1993. - S. 514. - ISBN 978-0-7803-0434-5 .
↑ SJ Mason. Teorie zpětné vazby – některé vlastnosti grafů toku signálu // Sborník IRE. - 1953-09. - T. 41 , č.p. 9 . — S. 1144–1156 . — ISSN 2162-6634 . - doi : 10.1109/JRPROC.1953.274449 . Archivováno 29. října 2020.
↑ SJ Mason. Teorie zpětné vazby - Další vlastnosti grafů toku signálu // Sborník IRE. - 1956-07. - T. 44 , č.p. 7 . — S. 920–926 . — ISSN 2162-6634 . - doi : 10.1109/JRPROC.1956.275147 . Archivováno z originálu 17. února 2022.
↑ Chen, Wai-Kai, 1936-. Aplikovaná teorie grafů: grafy a elektrické sítě . — 2d rev. vyd. Amsterdam: North-Holland Pub. Co., 1976. - 1 online zdroj (xvi, 542 stran) str. - ISBN 978-0-7204-2371-6 , 0-7204-2371-6, 978-1-4831-6415-1, 1-4831-6415-2.
↑ Lorens, Charles Stanton, Vogel, Dan. Technická zpráva 317 - Teorie a aplikace průtokových grafů // Research Laboratory of Electronics, MIT. Archivováno z originálu 6. března 2021.
↑ Horace M. Trent. Izomorfismy mezi orientovanými lineárními grafy a soustředěnými fyzikálními systémy // Acoutical Society of America Journal. - 1955. - Sv. 27 , iss. 3 . — P. 500 . — ISSN 0001-4966 . - doi : 10.1121/1.1907949 . Archivováno z originálu 24. října 2019.
↑ 1 2 Louis PA Robichaud, Maurice Boisvert, Jean Robert. Grafy toku signálu a aplikace . — 1962.
↑ Narsingh Deo. Teorie grafů s aplikacemi ve strojírenství a informatice . - 2004. - ISBN 9788120301450 .
↑ J. Choma. Analýza toku signálu zpětnovazebních sítí // IEEE Transactions on Circuits and Systems. — 1990-04. - T. 37 , č.p. 4 . — S. 455–463 . — ISSN 1558-1276 . - doi : 10.1109/31.52748 . Archivováno 30. října 2020.
↑ Wai-Kai Chen. Aplikovaná teorie grafů . - 1971. - ISBN 978-0444101051 . Archivováno 27. října 2020 na Wayback Machine

Literatura

Karelin V. P., Kureichik V. M. Základní pojmy teorie lineárních přechodových grafů // Orientované grafy a konečné automaty / A. N. Melikhov. - M .: Nauka, 1971. - S. 196-211. — 416 s. — (Teoretické základy technické kybernetiky). (str. 196-211 napsali V. P. Karelin a V. M. Kureichik na přání autora knihy A. N. Melikhova, viz str. 196 knihy)