Vlákno názorů k článku Network coding v peer-to-peer sieťach od anonym - Pro pochopeni staci jeden rok linearni algebry na...
-
anonymníPro pochopeni staci jeden rok linearni algebry na FJFI :) Clanek je velmi zajimavy a kvalitni, diky za nej! Jen me tak napada, jestli by sla odesilana linearni kombinace (koeficienty) komprimovat, pak by se mohlo usetrit par zajimavych byte... ale asi to nepujde, kdyz musi byt vsechny koeficienty uplne ruzne...
-
Na pochopenie myšlienky zrejme stačí matematika základnej školy. Ale veľa vecí je tam skrytých. Napr. pri násobení n-bitového čísla (blok) koeficientom (16-bitové číslo) normálne potrebujete k*n bitových operácií, kde k je počet jednotkových bitov v koeficiente. Ale to násobenie sa dá robiť v 2 bytových operáciách použitím modulárnej reprezentácie.
Každý blok je prvkom telesa GF(2^(2^m)), pre predstavu si za m dosaďte napr. 23 pre 1 MB bloky (2^23=1MB*8 bitov/byte). Teleso GF(2^(2^m)) je izomorfné vektorovému priestoru dimenzie d nad telesom GF(2^(2^m/d)). Inak povedané, každý prvok (blok) sa dá vyjadriť ako vektor dĺžky d, každý prvok je 2^m/d bitové číslo. 1MB blok sa dá vyjadriť napr. ako vektor 1024*1024 bajtov. To je zrejme celkom jasné.
Trik je, že modulárna reprezentácia je homomorfizmus (alebo izomorfizmus v tomto prípade). To znamená, že násobenie môžme robiť po zložkách. Napr. použijeme vektorový priestor nad GF(2^8), každý blok sa dá zobraziť na vektor bytov. Násobenie obrovského čísla koeficientom s vektorovou reprezentáciou (0, 0, 0, ..., 0, 0, a, b) nám zabere len 2 bytové operácie.
Prevod z "normálnej" do modulárnej reprezentácie ale trvá d*log(d) (Fast Fourier Transform). Lenže my si môžme predstaviť, že bloky súboru už v modulárnej reprezentácii sú, takže žiadny prevod nás zaťažovať nebude. Nakoniec je sčítanie paradoxne pomalšie než násobenie malým koeficientom :-)
Násobenie a invertovanie v GF(2^8) sa dá jednoducho implementovať predpočítanými tabuľkami, 16kB tabuľka pre násobenie (matica 256x256) a pole 256 bytov pre invertovanie. Sčítanie je xor.
