Hálózati kódolás

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt hozzászólók, és jelentősen eltérhet a 2016. október 22-én felülvizsgált verziótól ; az ellenőrzések 2 szerkesztést igényelnek .

A hálózati kódolás az információelmélet  egyik ága , amely a hálózaton keresztüli adatátvitel optimalizálásának kérdését vizsgálja a közbenső csomópontokon lévő adatcsomagok megváltoztatására szolgáló technikák segítségével.

A hálózati kódolás alapjai

A hálózati kódolás elveinek elmagyarázásához használja a pillangóhálózat példáját, amelyet a hálózati kódolásról szóló első munkában javasoltak "Hálózati információáramlás" [1] . Tekintsük az ábrán látható hálózatot, amelyben van egy vagy két forrás, amely A és B csomagokat generál, amelyek a pillangóhálózat bemenetére érkeznek. Az információ továbbításáért felelős első csomópontok egy-egy csomagot továbbítanak (A bal oldalon és B a jobb oldalon) a bemeneten a címzettek végcsomópontjaihoz. Ezeket a csomagokat egy közbenső csomópontnak is továbbítják, amely ahelyett, hogy egymás után két csomagot küldene (és időt veszítene), kombinálja ezeket a csomagokat, például az XOR művelettel , és továbbítja.

A célcsomópontok képesek visszaállítani az eredeti csomagokat egyetlen fogadott csomagra és ezek kombinációjára vonatkozó információkból. Ennek eredményeként nő a hálózati átviteli sebesség - két csomag egyidejűleg két címzettnek továbbítható (minden ciklusban), bár a minimális hálózati szakasz csak három adatátviteli csatornát tartalmaz.

Véletlenszerű hálózati kódolás

Ellentétben a statikus hálózati kódolással, amikor a fogadó ismeri a csomaggal végzett összes manipulációt, akkor a véletlenszerű hálózati kódolás kérdését is figyelembe veszik, ha ez az információ ismeretlen. Az első ilyen témájú művek szerzői Kötter, Krzyszang és Silva [2] nevéhez fűződik . Ezt a megközelítést véletlen együtthatós hálózati kódolásnak is nevezik – amikor azok az együtthatók, amelyek alatt a forrás által továbbított kezdeti csomagok bekerülnek a fogadó által kapott csomagokba, ismeretlen együtthatókkal, amelyek az aktuális hálózati struktúrától, sőt a véletlenszerűségtől is függhetnek. köztes csomópontokon hozott döntések .

A fő módszer az, hogy a továbbított csomagba további információkat foglalnak, amelyek azonosítják a csomagot egy bizonyos munkameneten belül (úgy gondolják, hogy csak egy munkamenethez tartozó csomagok kombinálhatók). Ez lehet például egy egyszerű bitmező. A fent tárgyalt pillangóhálózat esetében ez a bitmező minden csomaghoz két bitből állhat:

Csomag bit mező
tíz
0 1
tizenegy

Az első címzett két "1 0" és "1 1" bitmezővel rendelkező csomagot kap, a második címzett pedig "0 1" és "1 1" bitmezőt. Ezt a mezőt a csomagok lineáris egyenletének együtthatóira vonatkozó információként használva a vevő visszaállíthatja az eredeti csomagokat, ha azokat hiba nélkül továbbították.

Az információ védelme a torzítás ellen

A nem véletlenszerű hálózati kódoláshoz szabványos zavarás- és élsimítási technikák használhatók, amelyek az információk hálózaton keresztüli egyszerű továbbítására szolgálnak. Azonban, amint az „LDPC kódolási sémák hibához” [3] cikkben megjegyeztük, a lineáris kombinációkból helyreállított csomagok nagyobb valószínűséggel kapnak hibával, mivel két, információ-helyreállításra használt csomagban hibavalószínűségként érintik őket. egyszer.

A "pillangó" hálózatot figyelembe véve kimutatható, hogy az első címzettnél nagyobb a valószínűsége annak, hogy egy csomagot hibamentesen fogad, mint a csomag esetében, még akkor is, ha a kapott csomagokban azonos, de nem nulla hibavalószínűséget feltételezünk és .

Ennek a hatásnak a csökkentése érdekében a szerzők az A és B csomagok iteratív dekódolásának módszerének módosítását javasolják (például LDPC kódolással), amikor a csomagdekódolási iterációkat egyidejűleg hajtják végre, és a dekóderek információt cserélnek az adott csomag hibavalószínűségéről. bitek. Ennek a hatásnak a teljes megszabadulása érdekében a szerzők azt is javasolják, hogy a forráscsomagokat több részre bontsák, és különféle módokon vigyék át őket. Ahogy a numerikus kísérlet megmutatta, ez valóban kiegyenlíti a csomagdekódolás valószínűségét.

A véletlenszerű hálózati kódolásban a dekódoláshoz használt módszerek az összes vett csomagot egyetlen objektumnak (gyakran mátrixnak) tekintik, amely a fogadott sorcsomagokból épül fel. Ha a csomag első része bitmező, akkor a mátrixszal végzett műveletek először a bal oldalát átlós alakra hozzuk ( Gauss módszerrel ), majd a mátrix jobb oldalán lévő hibák javítására. . A hibák kijavítására rangkódok használhatók , amelyek nem csak a mátrix oszlopaiban lévő hibákat (a hibásan vett adatbitek miatt), hanem a mátrix soraiban (a bitmezőben előforduló átviteli hibák miatt) is javíthatják. .

Jegyzetek

  1. ↑ Ahlswede, R.; Ning Cai; Li, S.-YR; Yeung, RW, " Network information flow ", Information Theory, IEEE Transactions on, 46. kötet, 4. sz., 1204-1216. o., 2000. július
  2. ↑ Cikkek
    • Koetter R., Kschischang FR Hibák és törlések kódolása véletlenszerű hálózati kódolásban// IEEE International Symposium on Information Theory. Proc.ISIT-07.-2007.- P. 791-795.
    • Silva D., Kschischang FR Rang-metrikus kódok használata hibajavításhoz véletlenszerű hálózati kódolásban // IEEE International Symposium on Information Theory. Proc. ISIT-07. – 2007.
    • Koetter R., Kschischang FR Hibák és törlések kódolása véletlenszerű hálózati kódolásban // IEEE Transactions on Information Theory. - 2008 - V. IT-54, N.8. - P. 3579-3591.
    • Silva D., Kschischang FR, Koetter R. A Random-Metric Approach to Error Control in Random Network Coding // IEEE Transactions on Information Theory.- 2008- V. IT-54, N. 9.- P.3951-3967.
  3. ↑ Kang J., Zhou B., Ding Z., Lin S. LDPC kódolási sémák hibakezeléshez multicast hálózatban

Lásd még