Lubyho transformační kód - Luby transform code

V informatice jsou Lubyovy transformační kódy ( LT kódy ) první třídou praktických fontánových kódů, které jsou téměř optimálními kódy opravujícími mazání . Byly vynalezeny Michaelem Lubym v roce 1998 a publikovány v roce 2002. Stejně jako některé jiné fontánové kódy , LT kódy závisejí na řídkých bipartitních grafech, aby vyměnily režii příjmu za rychlost kódování a dekódování. Rozlišující charakteristikou LT kódů je použití obzvláště jednoduchého algoritmu založeného na exclusive nebo operation ( ) ke kódování a dekódování zprávy.

LT kódy jsou bez ratelů, protože kódovací algoritmus může v zásadě produkovat nekonečný počet paketů zpráv (tj. Procento paketů, které musí být přijaty k dekódování zprávy, může být libovolně malé). Jsou to kódy opravující mazání, protože je lze použít ke spolehlivému přenosu digitálních dat na mazacím kanálu .

Další generací kódů LT jsou kódy Raptor (viz například IETF RFC 5053 nebo IETF RFC 6330), které mají lineární časové kódování a dekódování. Kódy Raptor jsou v zásadě založeny na kódech LT, tj. Kódování kódů Raptor používá dvě fáze kódování, kde druhou fází je kódování LT. Podobně dekódování pomocí kódů Raptor primárně závisí na dekódování LT, ale dekódování LT je smícháno s pokročilejšími technikami dekódování. Kód RaptorQ specifikovaný v IETF RFC 6330, který je nejpokročilejším fontánovým kódem, má ve srovnání s použitím pouze LT kódu výrazně vyšší pravděpodobnost dekódování a výkon.

Proč používat LT kód?

Tradiční schéma přenosu dat přes mazací kanál závisí na nepřetržité obousměrné komunikaci.

  • Odesílatel kóduje a odešle balíček informací.
  • Přijímač se pokusí dekódovat přijatý paket. Pokud to lze dekódovat, přijímač odešle potvrzení zpět do vysílače. Jinak přijímač požádá vysílač o opětovné odeslání paketu.
  • Tento obousměrný proces pokračuje, dokud nebudou úspěšně přeneseny všechny pakety ve zprávě.

Některé sítě, například sítě používané pro mobilní bezdrátové vysílání, nemají kanál zpětné vazby. Aplikace v těchto sítích stále vyžadují spolehlivost. Fontánové kódy obecně a zvláště LT kódy tento problém obcházejí přijetím v podstatě jednosměrného komunikačního protokolu.

  • Odesílatel kóduje a odesílá paket za paketem informací.
  • Přijímač vyhodnotí každý přijatý paket. Pokud dojde k chybě, chybný paket bude zahozen. Jinak je paket uložen jako část zprávy.
  • Nakonec má příjemce dostatek platných paketů k rekonstrukci celé zprávy. Když byla celá zpráva úspěšně přijata, přijímač signalizuje, že přenos je dokončen.

Jak bylo uvedeno výše, kód RaptorQ specifikovaný v IETF RFC 6330 v praxi překonává kód LT.

LT kódování

Proces kódování začíná rozdělením nekódované zprávy do n bloků zhruba stejné délky. Zakódované pakety jsou pak produkovány pomocí generátoru pseudonáhodných čísel .

  • Stupeň d , 1 ≤  d  ≤  n , dalšího paketu je vybrán náhodně.
  • Přesně d bloky ze zprávy jsou vybrány náhodně.
  • Pokud M i je i tý blok zprávy, datová část dalšího paketu se vypočte
kde { i 1 ,  i 2 ,…,  i d } jsou náhodně zvolené indexy pro bloky d zahrnuté v tomto paketu.
  • Ke kódovanému paketu je připojena předpona, která definuje, kolik bloků n je ve zprávě, kolik bloků d bylo exkluzivně uloženo do datové části tohoto paketu a seznam indexů { i 1 ,  i 2 ,…,  i d }.
  • Nakonec je na paket aplikována nějaká forma kódu pro detekci chyb (snad stejně jednoduchá jako kontrola cyklické redundance ) a paket je přenášen.

Tento proces pokračuje, dokud přijímač neoznámí, že zpráva byla přijata a úspěšně dekódována.

LT dekódování

Proces dekódování používá k načtení kódované zprávy operaci „ exclusive “ nebo „ exclusive “.

  • Pokud aktuální paket není čistý nebo replikuje paket, který již byl zpracován, aktuální paket bude zahozen.
  • Pokud má aktuální čistě přijatý paket stupeň d  > 1, je nejprve zpracován proti všem plně dekódovaným blokům v oblasti pro frontu zpráv (jak je podrobněji popsáno v dalším kroku), poté je uložen v oblasti vyrovnávací paměti, pokud je jeho snížený stupeň větší než 1.
  • Když je přijat nový čistý paket stupně d  = 1 (blok M i ) (nebo je stupeň aktuálního paketu snížen na 1 podle předchozího kroku), je přesunut do oblasti pro frontu zpráv a poté porovnán se všemi pakety stupně d  > 1 sídlící v pufru. To je exkluzivní-ORed do datové části jakékoliv pufrovaného paketu, který byl zakódován pomocí M i , stupeň tohoto odpovídajícího paketu je zmenšena, a seznam indexů pro tento paket je upravena tak, aby odrážela použití M i .
  • Když tento proces odemkne blok stupně d  = 2 ve vyrovnávací paměti, tento blok se zmenší na stupeň 1 a je zase přesunut do oblasti pro frontu zpráv a poté zpracován proti paketům zbývajícím ve vyrovnávací paměti.
  • Když bylo všech n bloků zprávy přesunuto do oblasti fronty zpráv, přijímač signalizuje vysílači, že zpráva byla úspěšně dekódována.

Toto dekódování postup funguje, protože A  A  = 0 pro každou bitového řetězce A . Poté,  co bylo do balíčku stupně d exkluzivně uloženo d -1 odlišných bloků, zbývá pouze původní nekódovaný obsah bezkonkurenčního bloku. V symbolech máme  

Variace

Je možné několik variací výše popsaných kódovacích a dekódovacích procesů. Například namísto předpony každého paketu seznamem skutečných indexů bloku zpráv { i 1 ,  i 2 ,…,  i d } může kodér jednoduše poslat krátký „klíč“, který sloužil jako zárodek generátoru pseudonáhodných čísel (PRNG) nebo indexová tabulka použitá ke konstrukci seznamu indexů. Protože přijímač vybavený stejnou RNG nebo indexovou tabulkou může spolehlivě znovu vytvořit "náhodný" seznam indexů z tohoto semene, lze dekódovací proces úspěšně dokončit. Alternativně lze kombinací jednoduchého LT kódu nízkého průměrného stupně s robustním kódem opravujícím chyby vytvořit raptorový kód, který v praxi překoná optimalizovaný LT kód.

Optimalizace LT kódů

K optimalizaci přímého LT kódu lze použít pouze jeden parametr: funkci distribuce stupňů (popsanou jako generátor pseudonáhodných čísel pro stupeň d v sekci kódování LT výše). V praxi jsou ostatní „náhodná“ čísla (seznam indexů {  i 1 ,  i 2 ,…,  i d  }) vždy převzata z rovnoměrného rozdělení na [0, n ), kde n je počet bloků, do kterých zpráva byla rozdělena.

Sám Luby diskutoval o „ideální solitonové distribuci “ definované

Tato distribuce stupňů teoreticky minimalizuje očekávaný počet nadbytečných kódových slov, která budou odeslána před dokončením procesu dekódování. Ideální distribuce solitonů však v praxi nefunguje dobře, protože jakákoli fluktuace kolem očekávaného chování způsobuje, že v určitém kroku dekódovacího procesu nebude k dispozici žádný paket (sníženého) stupně 1, takže dekódování selže. Navíc některé z původních bloků nebudou xorovány do žádného z přenosových paketů. V praxi je tedy za ideální distribuci nahrazena modifikovaná distribuce, „robustní solitonová distribuce “. Účelem modifikace je obecně produkovat více paketů velmi malého stupně (přibližně 1) a méně paketů stupně větších než 1, s výjimkou špičky paketů v poměrně velkém množství zvoleném tak, aby bylo zajištěno, že všechny původní bloky budou součástí nějakého balíčku.

Viz také

Poznámky a reference

  1. ^ a b M.Luby, „LT Codes“, 43. výroční sympozium IEEE o základech informatiky, 2002.
  2. ^ Exkluzivní nebo (XOR) operace, symbolizované ⊕, má velmi užitečnou vlastnost, že A  ⊕  A  = 0, kdeje libovolný řetězec bitů .
  3. ^ Fontánní kódy od DJC MacKay, poprvé publikováno v IEEE Proc.-Commun., Sv. 152, č. 6, prosinec 2005.
  4. ^ a b Optimalizace distribuce titulů LT kódů pomocí přístupu důležitého vzorkování , Esa Hyytiä, Tuomas Tirronen a Jorma Virtamo (2006).

externí odkazy