Nätverkskodning

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 22 oktober 2016; kontroller kräver 2 redigeringar .

Nätverkskodning  är en gren av informationsteori som studerar frågan om att optimera dataöverföring över ett nätverk med hjälp av tekniker för att ändra datapaket vid mellanliggande noder.

Grunderna för nätverkskodning

För att förklara principerna för nätverkskodning, använd exemplet på ett fjärilsnätverk, som föreslagits i det första arbetet med nätverkskodning "Nätverksinformationsflöde" [1] . Betrakta nätverket som visas i figuren, där det finns en eller två källor som genererar paket A och B, som kommer till ingången till fjärilsnätverket. De första noderna som ansvarar för att överföra information sänder ett paket vardera (A till vänster och B till höger) vid ingången till mottagarnas slutnod. De skickar också dessa paket till en mellannod, som istället för att skicka två paket i tur och ordning (och slösa tid), kombinerar dessa paket, till exempel med hjälp av XOR- operationen och sänder vidare.

Destinationsnoder har förmågan att återställa originalpaketen från information om ett enstaka mottaget paket och en kombination av dem. Som ett resultat ökar nätverksgenomströmningen - två paket kan sändas till två mottagare samtidigt (för varje cykel), även om den minsta nätverkssektionen endast innehåller tre dataöverföringskanaler.

Slumpmässig nätverkskodning

I motsats till statisk nätverkskodning, när mottagaren känner till alla manipulationer som utförs med paketet, övervägs frågan om slumpmässig nätverkskodning också när denna information är okänd. Författarskapet till de första verken om detta ämne tillhör Kötter, Krzyszang och Silva [2] . Detta tillvägagångssätt kallas också nätverkskodning med slumpmässiga koefficienter - när koefficienterna under vilka de initiala paketen som sänds av källan kommer att inkluderas i de resulterande paketen som tas emot av mottagaren, med okända koefficienter som kan bero på den aktuella nätverksstrukturen och till och med på slumpmässigt beslut fattade vid mellanliggande noder.

Huvudmetoden är införandet i det överförda paketet av ytterligare information som identifierar paketet inom en viss session (det antas att paket som tillhör endast en session kan kombineras). Det kan till exempel vara ett enkelt bitfält. För fjärilsnätverket som diskuterats ovan kan detta bitfält bestå av två bitar för varje paket:

Paket bitfält
tio
0 1
elva

Den första mottagaren kommer att få två paket med bitfält "1 0" och "1 1", den andra mottagaren kommer att få "0 1" och "1 1". Genom att använda detta fält som information om koefficienterna för den linjära ekvationen för paketen, kan mottagaren återställa originalpaketen om de sändes utan fel.

Skydd av information från förvrängning

För icke-slumpmässig nätverkskodning kan standardtekniker för anti-jamming och kantutjämning som används för enkel överföring av information över ett nätverk användas. Men som noterats i artikeln "LDPC-kodningsscheman för fel" [3] har paket som återställs från linjära kombinationer en högre sannolikhet att tas emot med ett fel, eftersom de påverkas som en felsannolikhet i två paket som används för informationsåterställning vid en gång.

Med tanke på "fjärilsnätverket" kan det visas att för den första mottagaren är sannolikheten att ta emot ett paket utan fel större än för paketet , även om vi antar samma, men icke-noll, felsannolikheter i de mottagna paketen och .

För att minska denna effekt föreslår författarna att metoden för iterativ avkodning av paket A och B (till exempel med LDPC- kodning) ändras när paketavkodningsiterationer utförs samtidigt och avkodare utbyter information om felsannolikheterna i ett specifikt paket bitar. För att helt bli av med denna effekt föreslår författarna också att dela upp källkodspaketen i flera delar och överföra dem på olika sätt. Som det numeriska experimentet visade, utjämnar detta verkligen sannolikheterna för paketavkodning.

Metoderna som används för avkodning i slumpmässig nätverkskodning betraktar alla mottagna paket som ett enda objekt (ofta en matris) byggt från de mottagna radpaketen. Om den första delen av paketet är ett bitfält, reduceras operationer med matrisen, för det första, till att föra dess vänstra sida till en diagonal form (med Gauss-metoden ), och sedan till att korrigera fel på höger sida av matrisen . För att korrigera fel kan rangkoder användas , som inte bara kan korrigera fel i matrisens kolumner (på grund av felaktigt mottagna databitar), utan även fel i matrisens rader (på grund av överföringsfel i bitfältet) .

Anteckningar

  1. ↑ Ahlswede, R.; Ning Cai; Li, S.-YR; Yeung, RW, " Network information flow ", Information Theory, IEEE Transactions on, vol.46, nr.4, s.1204-1216, juli 2000
  2. ↑ Artiklar
    • Koetter R., Kschischang FR Kodning för fel och raderingar i slumpmässig nätverkskodning// IEEE International Symposium on Information Theory. Proc.ISIT-07.-2007.- S. 791-795.
    • Silva D., Kschischang FR Användning av rankmetriska koder för felkorrigering i slumpmässig nätverkskodning // IEEE International Symposium on Information Theory. Proc. ISIT-07. – 2007.
    • Koetter R., Kschischang FR Kodning för fel och raderingar i slumpmässig nätverkskodning // IEEE Transactions on Information Theory. - 2008 - V. IT-54, N.8. - P. 3579-3591.
    • Silva D., Kschischang FR, Koetter R. A Rank-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-kodningsscheman för felkontroll i ett multicast-nätverk

Se även