Online kódy - Online codes
v počítačová věda, online kódy jsou příkladem kódy bez mazání. Tyto kódy mohou zakódovat zprávu do řady symbolů, takže znalost jakéhokoli jejich zlomku umožňuje obnovit původní zprávu (s vysokou pravděpodobností). Rateless kódy vytvářejí libovolně velké množství symbolů, které lze vysílat, dokud přijímače nemají dostatek symbolů.
Online kódování algoritmus sestává z několika fází. Nejprve je zpráva rozdělena na n bloky zpráv pevné velikosti. Pak vnější kódování je mazací kód který produkuje pomocné bloky, které jsou připojeny k blokům zpráv za účelem vytvoření složené zprávy.
Z toho vnitřní kódování generuje kontrolní bloky. Po obdržení určitého počtu kontrolních bloků může být obnovena část zlomku složené zprávy. Jakmile bylo získáno dost, lze vnější dekódování použít k obnovení původní zprávy.
Podrobná diskuse
Online kódy jsou parametrizovány velikostí bloku a dvěma skaláry, q a ε. Autoři naznačují q= 3 a ε = 0,01. Tyto parametry nastavují rovnováhu mezi složitostí a výkonem kódování. Zpráva o n bloky lze obnovit, s vysokou pravděpodobností, od (1 + 3ε)n zkontrolujte bloky. Pravděpodobnost poruchy je (ε / 2)q + 1.
Vnější kódování
Jako vnější kódování lze použít jakýkoli mazací kód, ale autor online kódů navrhuje následující.
Pro každý blok zpráv si vyberte pseudonáhodně q pomocné bloky (z celkem 0,55qεn pomocné bloky). Každý pomocný blok je pak XOR všech bloků zpráv, které jsou k němu připojeny.
Vnitřní kódování
Vnitřní kódování přijímá kompozitní zprávu a generuje proud kontrolních bloků. Kontrolní blok je XOR všech bloků ze složené zprávy, ke které je připojen.
The stupeň kontrolního bloku je počet bloků, ke kterým je připojen. Stupeň je určen vzorkováním náhodného rozdělení, p, který je definován jako:
- pro
Jakmile je znám stupeň kontrolního bloku, jsou bloky ze složené zprávy, ke které je připojen, vybrány jednotně.
Dekódování
Je zřejmé, že dekodér vnitřního stupně musí obsahovat kontrolní bloky, které aktuálně nemůže dekódovat. Kontrolní blok lze dekódovat, pouze pokud jsou známy všechny bloky kromě jednoho, ke kterým je připojen. Graf vlevo ukazuje průběh vnitřního dekodéru. Osa x vykresluje počet přijatých kontrolních bloků a přerušovaná čára zobrazuje počet kontrolních bloků, které nelze aktuálně použít. To nejprve stoupá téměř lineárně, protože je přijato mnoho kontrolních bloků se stupněm> 1, ale nepoužitelných. V určitém okamžiku jsou některé kontrolní bloky najednou použitelné, což vyřeší více bloků, což způsobí, že bude použitelné více kontrolních bloků. Celý soubor lze velmi rychle dekódovat.
Jak graf také ukazuje, že vnitřní dekodér se po obdržení na chvíli stydí dekódovat vše n zkontrolujte bloky. Vnější kódování zajišťuje, že pár nepolapitelných bloků z vnitřního dekodéru nepředstavuje problém, protože soubor lze obnovit i bez nich.
externí odkazy
- Originální papír
- Kódy bez státní příslušnosti a velká stahování (Přístupnější příspěvek od stejného autora)
- Články od Petara Maymounkova
- Projekt Ruby hostovaný na RubyForge obsahující knihovnu Ruby pro online kódování