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.
Odpověď na názor
Odpovídáte na názor k článku Network coding v peer-to-peer sieťach.
Pravidla pro diskutující
Přidáním čtenářského příspěvku do diskusí či fóra souhlasíte s tím, že budete dodržovat následující pravidla. Při jejich hrubém porušení se vystavujete riziku smazání příspěvku, jeho modifikaci, v krajním případě i zablokování přístupu do diskusí.
Redakce ze zásady nezasahuje do čtenářských diskusí a zavazuje se, že nebude mazat ani modifikovat příspěvky, kromě případů, kdy tyto porušují některé z následujících pravidel. V takové situaci je na zvážení redakce, zda příspěvek modifikuje s viditelným upozorněním, či přímo smaže. Redakce nikdy nemaže „nesouhlasné komentáře“ jen proto, že jsou nesouhlasné. Vítáme střet názorů, ale vždy v rámci slušné a kultivované debaty.
Příspěvky nesmí obsahovat:
- Vulgární či hrubé výrazy.
- Urážlivé výroky na adresu druhé osoby či skupiny osob.
- Texty, které mají za cíl jen vyprovokovat emotivní reakci (trolling).
- Rasové útoky či útoky na jakoukoliv jinou menšinu či skupinu obyvatel.
- Komerční nabídky a affiliate odkazy.
- Odkazy na warez, sériová čísla, licenční kódy, pornografii a další nevhodný materiál stejně jako žádosti o poskytnutí tohoto obsahu.
- Prokazatelně protiprávní obsah.
Informace o soukromí: U všech přidaných komentářů provozovatel ukládá IP adresu a hostname odesílatele. U neregistrovaných uživatelů se na webu zobrazuje část hostname, případně IP adresy, neumožňující identifikovat konkrétní počítač.
Povolené značky XHTML: a, br, code, em, li, ol, p, pre, strong, sub, sup, ul
