Kod transformacji Luby

W informatyce kody transformacji Luby'ego ( kody LT ) są pierwszą klasą praktycznych kodów fontannowych , które są prawie optymalnymi kodami korygującymi wymazywanie . Zostały wynalezione przez Michaela Luby'ego w 1998 roku i opublikowane w 2002 roku. Podobnie jak niektóre inne kody fontannowe , kody LT zależą od rzadkich grafów dwudzielnych , aby wymienić narzut odbioru na szybkość kodowania i dekodowania. Cechą wyróżniającą kody LT jest zastosowanie szczególnie prostego algorytmu opartego na wyłącznym lub operacja ( $zakodowania$ i odkodowania wiadomości.

Kody LT są bezszybkościowe , ponieważ algorytm kodowania może w zasadzie wygenerować nieskończoną liczbę pakietów wiadomości (tj. odsetek pakietów, które muszą zostać odebrane, aby zdekodować wiadomość, może być dowolnie mały). Są to kody korygujące wymazywanie , ponieważ można ich używać do niezawodnego przesyłania danych cyfrowych w kanale wymazywania .

Następną generacją poza kodami LT są kody Raptor (patrz na przykład IETF RFC 5053 lub IETF RFC 6330), które mają kodowanie i dekodowanie w czasie liniowym. Kody Raptor są zasadniczo oparte na kodach LT, tj. kodowanie dla kodów Raptor wykorzystuje dwa etapy kodowania, z których drugim etapem jest kodowanie LT. Podobnie, dekodowanie za pomocą kodów Raptor opiera się głównie na dekodowaniu LT, ale dekodowanie LT jest mieszane z bardziej zaawansowanymi technikami dekodowania. Kod RaptorQ określony w IETF RFC 6330, który jest najbardziej zaawansowanym kodem źródłowym, ma znacznie lepsze prawdopodobieństwo dekodowania i wydajność w porównaniu z użyciem samego kodu LT.

Dlaczego warto używać kodu LT?

Tradycyjny schemat przesyłania danych przez kanał kasowania zależy od ciągłej komunikacji dwukierunkowej.

Nadawca koduje i wysyła pakiet informacji.
Odbiorca próbuje zdekodować odebrany pakiet. Jeśli można go odkodować, odbiornik wysyła potwierdzenie z powrotem do nadajnika. W przeciwnym razie odbiornik prosi nadajnik o ponowne wysłanie pakietu.
Ten dwukierunkowy proces trwa do momentu pomyślnego przesłania wszystkich pakietów w wiadomości.

Niektóre sieci, na przykład używane do bezprzewodowego nadawania przez sieć komórkową, nie mają kanału zwrotnego. Aplikacje w tych sieciach nadal wymagają niezawodności. Kody Fountain ogólnie, a kody LT w szczególności, pozwalają obejść ten problem, przyjmując zasadniczo jednokierunkowy protokół komunikacyjny.

Nadawca koduje i wysyła pakiet po pakiecie informacji.
Odbiorca ocenia każdy pakiet w miarę jego odbierania. Jeśli wystąpi błąd, błędny pakiet jest odrzucany. W przeciwnym razie pakiet jest zapisywany jako fragment wiadomości.
W końcu odbiorca ma wystarczającą liczbę ważnych pakietów, aby zrekonstruować całą wiadomość. Po pomyślnym odebraniu całej wiadomości odbiornik sygnalizuje, że transmisja została zakończona.

Jak wspomniano powyżej, kod RaptorQ określony w IETF RFC 6330 przewyższa w praktyce kod LT.

kodowanie LT

Proces kodowania rozpoczyna się od podzielenia niezaszyfrowanej wiadomości na n bloków o mniej więcej równej długości. Zakodowane pakiety są następnie tworzone za pomocą generatora liczb pseudolosowych .

Stopień d , 1 ≤ d ≤ n następnego pakietu jest wybierany losowo.
dokładnie d bloków z wiadomości.
Jeżeli Mi _jest i - tym blokiem wiadomości, część danych następnego pakietu jest obliczana jako

{\ Displaystyle M_ {i_ {1}} \ oplus M_ {i_ {2}} \ oplus \ cdots \ oplus M_ {i_ {d}} \,} gdzie

{ i ₁ , i ₂ , …, i _d } to losowo wybrane indeksy dla d bloków zawartych w tym pakiecie.

Do zakodowanego pakietu dodawany jest przedrostek określający, ile bloków n znajduje się w wiadomości, ile bloków d zostało włączonych na wyłączność do części danych tego pakietu oraz listę indeksów { i ₁ , i ₂ , …, ja _d }.
Na koniec do pakietu stosowana jest pewna forma kodu wykrywającego błędy (być może tak prosta, jak cykliczna kontrola redundancji ) i pakiet jest przesyłany.

Proces ten trwa do momentu, gdy odbiorca zasygnalizuje, że wiadomość została odebrana i pomyślnie zdekodowana.

dekodowanie LT

Proces dekodowania wykorzystuje operację „ exclusive or ” do pobrania zakodowanej wiadomości.

Jeśli bieżący pakiet nie jest czysty lub replikuje pakiet, który został już przetworzony, bieżący pakiet jest odrzucany.
Jeśli aktualnie prawidłowo odebrany pakiet ma stopień d > 1, jest on najpierw przetwarzany względem wszystkich w pełni zdekodowanych bloków w obszarze kolejkowania komunikatów (jak opisano dokładniej w następnym kroku), a następnie przechowywany w obszarze bufora, jeśli jego zredukowany stopień jest równy większy niż 1.
Gdy otrzymany zostanie nowy, czysty pakiet o stopniu d = 1 (blok M _i ) (lub stopień aktualnego pakietu zostanie zmniejszony do 1 w poprzednim kroku), jest on przenoszony do obszaru kolejkowania wiadomości, a następnie dopasowywany do wszystkich pakiety stopnia d > 1 rezydujące w buforze. Jest on wczytywany na zasadzie wyłączności do części danych dowolnego buforowanego pakietu, który został zakodowany przy użyciu _Mi , stopień tego pasującego pakietu jest zmniejszany, a lista indeksów dla tego pakietu jest dostosowywana, aby _{odzwierciedlić} zastosowanie Mi.
Kiedy ten proces odblokowuje blok stopnia d = 2 w buforze, blok ten jest redukowany do stopnia 1 i z kolei jest przenoszony do obszaru kolejkowania wiadomości, a następnie przetwarzany względem pakietów pozostających w buforze.
Gdy wszystkie n bloków wiadomości zostanie przeniesionych do obszaru kolejkowania wiadomości, odbiornik sygnalizuje nadajnikowi, że wiadomość została pomyślnie zdekodowana.

Ta procedura dekodowania działa, ponieważ ZA = 0 dla dowolnego ciągu bitów A ⊕ $\ oplus}$ displaystyle Po tym, jak d - 1 odrębnych bloków zostało przekształconych na wyłączność w pakiet stopnia d , pozostaje tylko oryginalna niezakodowana zawartość niedopasowanego bloku. W symbolach mamy

{\ Displaystyle {\ rozpocząć {wyrównane} & {} \ qquad (M_ {i_ {1}} \ oplus \ kropki \ oplus M_ {i_ {d}}) \ oplus (M_ {i_ {1}} \ oplus \ kropki \oplus M_{i_{k-1}}\oplus M_{i_{k+1}}\oplus \dots \oplus M_{i_{d}})\\&=M_{i_{1}}\oplus M_ {i_{1}}\oplus \dots \oplus M_{i_{k-1}}\oplus M_{i_{k-1}}\oplus M_{i_{k}}\oplus M_{i_{k+1 }}\oplus M_{i_{k+1}}\oplus \dots \oplus M_{i_{d}}\oplus M_{i_{d}}\\&=0\oplus \dots \oplus 0\oplus M_ {i_{k}}\oplus 0\oplus \dots \oplus 0\\&=M_{i_{k}}\,\end{wyrównane}}}

Wariacje

Możliwych jest kilka wariantów procesów kodowania i dekodowania opisanych powyżej. Na przykład, zamiast poprzedzać każdy pakiet listą rzeczywistych indeksów bloków wiadomości { _{i 1 , i 2 , …, id} } _, koder może _po prostu wysłać krótki „klucz”, który służył jako ziarno dla generatora liczb pseudolosowych (PRNG) lub tabela indeksów używana do konstruowania listy indeksów. Ponieważ odbiornik wyposażony w ten sam RNG lub tablicę indeksów może niezawodnie odtworzyć „losową” listę indeksów z tego materiału siewnego, proces dekodowania może zakończyć się pomyślnie. Alternatywnie, łącząc prosty kod LT o niskim średnim stopniu z solidnym kodem korygującym błędy, można skonstruować kod raptora , który w praktyce będzie przewyższał zoptymalizowany kod LT.

Optymalizacja kodów LT

Jest tylko jeden parametr, którego można użyć do optymalizacji prostego kodu LT: funkcja rozkładu stopni (opisana jako generator liczb pseudolosowych dla stopnia d w sekcji kodowania LT powyżej). W praktyce pozostałe liczby „losowe” (lista indeksów { i ₁ , i ₂ , …, i _d } ) są niezmiennie brane z rozkładu jednostajnego na [0, n ), gdzie n jest liczbą bloków, na które wiadomość została podzielona.

Luby sam omówił „idealny rozkład solitonów ” zdefiniowany przez

{\ Displaystyle {\ rozpocząć {wyrównane} \ operatorname {P} \ {d = 1 \} & = {\ Frac {1} {n}} \\ [2pt] \ operatorname {P} \ {d = k \} &={\frac {1}{k(k-1)}}\qquad (k=2,3,\kropki ,n).\,\end{wyrównane}}}

Ten rozkład stopni teoretycznie minimalizuje oczekiwaną liczbę nadmiarowych słów kodowych, które zostaną wysłane przed zakończeniem procesu dekodowania. Jednak idealny rozkład solitonów nie działa dobrze w praktyce, ponieważ wszelkie wahania wokół oczekiwanego zachowania powodują, że na pewnym etapie procesu dekodowania nie będzie dostępnego pakietu o (zmniejszonym) stopniu 1, więc dekodowanie zakończy się niepowodzeniem. Co więcej, niektóre z oryginalnych bloków nie będą umieszczane w żadnym z pakietów transmisyjnych. Dlatego w praktyce zmodyfikowany rozkład, „odporny rozkład solitonów”. ", zastępuje idealny rozkład. Efektem modyfikacji jest generalnie wytworzenie większej liczby pakietów o bardzo małym stopniu (około 1) i mniejszej liczby pakietów o stopniu większym niż 1, z wyjątkiem nagłego wzrostu liczby pakietów w dość dużej ilości wybrany w celu zapewnienia, że wszystkie oryginalne bloki zostaną uwzględnione w jakimś pakiecie.

Zobacz też

Uwagi i odniesienia

^ ^a ^b M.Luby, „LT Codes”, 43. doroczne sympozjum IEEE na temat podstaw informatyki, 2002.
^ Operacja wyłączności lub (XOR), symbolizowana przez ⊕, ma bardzo użyteczną właściwość, że A ⊕ A = 0, gdzie A jest dowolnym ciągiem bitów .
^ Kody fontann , autorstwa DJC MacKay, po raz pierwszy opublikowane w IEEE Proc.-Commun., Cz. 152, nr 6, grudzień 2005.
^ ^a ^b Optimising the Degree Distribution of LT Codes with a Importance Sampling Approach , Esa Hyytiä, Tuomas Tirronen i Jorma Virtamo (2006).

Linki zewnętrzne

[Luby-1] M.Luby, „LT Codes”, 43. doroczne sympozjum IEEE na temat podstaw informatyki, 2002.

[2] ^ Operacja wyłączności lub (XOR), symbolizowana przez ⊕, ma bardzo użyteczną właściwość, że A ⊕ A = 0, gdzie A jest dowolnym ciągiem bitów .

[MacKay-3] Kody fontann , autorstwa DJC MacKay, po raz pierwszy opublikowane w IEEE Proc.-Commun., Cz. 152, nr 6, grudzień 2005.

[Tirronen-4] Optimising the Degree Distribution of LT Codes with a Importance Sampling Approach , Esa Hyytiä, Tuomas Tirronen i Jorma Virtamo (2006).