Kody internetowe

W informatyce kody online są przykładem kodów kasowania bez współczynnika . Kody te mogą zakodować wiadomość w wielu symbolach, tak że znajomość dowolnej ich części pozwala odzyskać oryginalną wiadomość (z dużym prawdopodobieństwem). Bezstopniowe kody wytwarzają dowolnie dużą liczbę symboli, które mogą być nadawane, dopóki odbiorniki nie będą miały wystarczającej liczby symboli.

Widok wysokiego poziomu wykorzystania kodów online

Algorytm kodowania online składa się z kilku faz. Najpierw wiadomość jest dzielona na n bloków wiadomości o stałym rozmiarze. Następnie zewnętrzne kodowanie jest kodem wymazywania , który tworzy bloki pomocnicze, które są dołączane do bloków wiadomości w celu utworzenia wiadomości złożonej.

Na tej podstawie wewnętrzne kodowanie generuje bloki kontrolne. Po odebraniu określonej liczby bloków kontrolnych można odzyskać pewną część wiadomości złożonej. Po odzyskaniu wystarczającej liczby zewnętrznych dekodowań można użyć do odzyskania oryginalnej wiadomości.

Szczegółowa dyskusja

Kody online są parametryzowane przez rozmiar bloku i dwa skalary q i ε . Autorzy proponują q = 3 i ε = 0,01. Te parametry określają równowagę między złożonością a wydajnością kodowania. Z dużym prawdopodobieństwem można odzyskać wiadomość zawierającą n bloków z (1+3ε) n bloków kontrolnych. Prawdopodobieństwo niepowodzenia wynosi (ε/2) ^q+1 .

Kodowanie zewnętrzne

Jako zewnętrzne kodowanie można użyć dowolnego kodu kasującego, ale autor kodów online sugeruje, co następuje.

Dla każdego bloku wiadomości wybierz pseudolosowo q bloków pomocniczych (z łącznej liczby 0,55 q ε n bloków pomocniczych), do których zostanie dołączony. Każdy blok pomocniczy jest zatem XORem wszystkich bloków komunikatów, które zostały do ​​niego dołączone.

Kodowanie wewnętrzne

Wykres otrzymanych bloków kontrolnych w stosunku do liczby bloków komunikatów ustalonych dla komunikatu blokowego 10000.

Wewnętrzne kodowanie pobiera złożoną wiadomość i generuje strumień bloków kontrolnych. Blok kontrolny to XOR wszystkich bloków z wiadomości złożonej, do której jest dołączony.

Stopień bloku kontrolnego to liczba bloków, do których jest on dołączony . Stopień jest określany poprzez próbkowanie rozkładu losowego, p , który jest zdefiniowany jako:

${\ Displaystyle F = \ lewo \ lceil {\ Frac {\ ln (\ epsilon ^ {2}/4)} {\ ln (1- \ epsilon / 2)}} \ prawo \ rceil}$

${\ Displaystyle p_ {1} = 1 - {\ Frac {1 + 1 / F} {1 +\epsilon }}}$

${\ Displaystyle p_ {i} = {\ Frac {(1-p_ {1}) fa} {(F-1) i (i-1)} }}$ dla ${\ Displaystyle 2 \ równoważnik ja \ równoważnik F}$

Gdy znany jest stopień bloku kontrolnego, bloki z komunikatu złożonego, do którego jest on dołączony, są wybierane jednolicie.

Rozszyfrowanie

Oczywiście dekoder stopnia wewnętrznego musi zawierać bloki kontrolne, których nie może obecnie zdekodować . Blok kontrolny można zdekodować tylko wtedy, gdy znane są wszystkie bloki, do których jest dołączony, z wyjątkiem jednego. Wykres po lewej pokazuje postęp wewnętrznego dekodera. Oś x przedstawia liczbę otrzymanych bloków kontrolnych, a linia przerywana pokazuje liczbę bloków kontrolnych, których nie można aktualnie użyć. Na początku rośnie to prawie liniowo, ponieważ odbieranych jest wiele bloków kontrolnych o stopniu > 1, ale bezużytecznych. W pewnym momencie niektóre bloki kontrolne nagle stają się użyteczne, rozwiązując więcej bloków, co z kolei powoduje, że więcej bloków kontrolnych jest użytecznych. Bardzo szybko można rozszyfrować cały plik.

Jak pokazuje wykres, wewnętrzny dekoder po prostu nie chce dekodować wszystkiego przez chwilę po otrzymaniu n bloków kontrolnych. Zewnętrzne kodowanie zapewnia, że ​​kilka nieuchwytnych bloków z wewnętrznego dekodera nie stanowi problemu, ponieważ plik można odzyskać bez nich.

Linki zewnętrzne

• Oryginalny papier
• Rateless Codes and Big Downloads (bardziej przystępny artykuł tego samego autora)
• Artykuły Petara Maymounkova
• Projekt Ruby hostowany w RubyForge zawierający bibliotekę Ruby do kodowania online