Tornádo kód - Tornado code

v teorie kódování, Tornádo kódy jsou třídou mazací kódy ta podpora oprava chyb. Kódy Tornado vyžadují konstantní C redundantnější bloky než datově efektivnější Kódy mazání Reed-Solomon, ale generují se mnohem rychleji a mohou rychleji mazat. Softwarové implementace tornádo kódů jsou asi 100krát rychlejší na malých délkách a asi 10 000krát rychlejší na větších délkách než mazací kódy Reed-Solomon.[1] Od zavedení kódů Tornado se objevilo mnoho dalších podobných kódů pro vymazání Online kódy, Kódy LT a Kódy Raptor.

Tornado kódy používají vrstvený přístup. Všechny vrstvy kromě posledního použití LDPC kód opravy chyb, který je rychlý, ale má šanci na selhání. Poslední vrstva používá opravný kód Reed – Solomon, který je pomalejší, ale je optimální z hlediska zotavení po selhání. Kódy Tornado diktují, kolik úrovní, kolik bloků obnovy v každé úrovni a distribuce použitá ke generování bloků pro jiné než konečné vrstvy.

Přehled

Vstupní data jsou rozdělena do bloků. Bloky jsou sekvence bitů, které mají stejnou velikost. Data pro obnovení používají stejnou velikost bloku jako vstupní data. Vymazání bloku (vstupu nebo obnovení) je detekováno jinými prostředky. (Například blok z disku neprošel kontrolou CRC nebo nikdy nedorazil síťový paket s daným pořadovým číslem.)

Počet bloků obnovy je dán uživatelem. Poté se určí počet úrovní spolu s počtem bloků v každé úrovni. Počet v každé úrovni je určen faktorem B, který je menší než jedna. Pokud existuje N vstupních bloků, má první úroveň obnovy bloky B * N, druhá má B * B * N, třetí má B * B * B * N atd.

Všechny úrovně obnovy kromě konečné úrovně používají LDPC, který funguje pomocí xor (exclusive-or). Xor pracuje na binárních hodnotách, 1 s a 0 s. A xor B je 1, pokud A a B mají různé hodnoty a 0, pokud A a B mají stejné hodnoty. Pokud dostanete výsledek (A xor B) a A, můžete určit hodnotu pro B. (A xor B xor A = B) Podobně, pokud vám bude dán výsledek (A xor B) a B, můžete určit hodnota pro A. To se vztahuje na více hodnot, takže vzhledem k výsledku (A xor B xor C xor D) a kterékoli 3 z hodnot lze chybějící hodnotu obnovit.

Bloky obnovy na první úrovni jsou tedy jen xor nějaké sady vstupních bloků. Podobně jsou bloky obnovy na úrovni dva xor nějaké sady bloků na úrovni jedna. Bloky použité v xoru jsou vybrány náhodně, bez opakování. Nicméně číslo bloků xor'ed, aby se obnovovací blok vybere z velmi specifické distribuce pro každou úroveň.

Protože xor je rychlá operace a bloky obnovy jsou xor pouze podmnožiny bloků na vstupu (nebo na nižší úrovni obnovy), lze bloky obnovy generovat rychle.

Konečnou úrovní je kód Reed-Solomon. Kódy Reed-Solomon jsou optimální, pokud jde o zotavení z poruch, ale pomalu se generují a obnovují. Protože každá úroveň má méně bloků než ta předchozí, má kód Reed-Solomon malý počet bloků pro obnovení, které lze generovat a použít při obnově. Přestože je Reed-Solomon pomalý, má k dispozici jen malé množství dat.

Během obnovy je nejdříve obnoven kód Reed-Solomon. Je zaručeno, že to bude fungovat, pokud je počet chybějících bloků na úrovni předposlední nižší než počet současných bloků ve finální úrovni.

Když půjdete níže, úroveň obnovení LDPC (xor) lze použít k obnovení úrovně pod ní s vysokou pravděpodobností pokud jsou k dispozici všechny bloky obnovy a úroveň pod chybí maximálně o C 'méně bloků než úroveň obnovy. Algoritmus pro obnovení je najít nějaký blok obnovy, který má na nižší úrovni pouze jednu ze své generující sady. Pak se xor bloku obnovy se všemi přítomnými bloky rovná chybějícímu bloku.

Patentové záležitosti

Kódy Tornado byly dříve patentovány ve Spojených státech amerických.[2] Patenty US6163870 A (podané 6. listopadu 1997) a US 6081909 A (podané 6. listopadu 1997) popisují kódy Tornado a jejich platnost vypršela 6. listopadu 2017. Patenty US6307487 B1 (podané 5. února 1999) a US6320520 B1 (podané 17. září 1999) také zmiňují kódy Tornado a jejich platnost vypršela 5. února 2019, respektive 17. září 2019.

Citace

Michael Luby vytvořil kódy Tornado.[3][4]

externí odkazy

Čitelný popis z CMU (PostScript) [1] a další od Luby v International Computer Science Institute (PostScript) [2].

Viz také

Poznámky

  1. ^ Přístup digitální fontány ke spolehlivé distribuci hromadných dat. http://portal.acm.org/citation.cfm?id=285243.285258
  2. ^ (Mitzenmacher 2004 )
  3. ^ (Luby 1997 )
  4. ^ (Luby 1998 )

Reference

  • M. Mitzenmacher (2004). „Digital Fountains: A Survey and Look Forward“. Proc. 2004 IEEE Workshop informační teorie (ITW).
  • M. Luby, M. Mitzenmacher, A. Shokrollahi, D. Spielman , V. Stemann (1997). „Praktické kódy odolné vůči ztrátám“. Sborník dvacátého devátého ročníku ACM sympozium o teorii práce na počítači (STOC ): 150–159.CS1 maint: více jmen: seznam autorů (odkaz)
  • M. Luby, M. Mitzenmacher, A. Shokrollahi (1998). "Analýza náhodných procesů pomocí vyhodnocení typu stromu." Proc 9. ročníku ACM -SyAM Symposium on Discrete Algorithms: 364–373.CS1 maint: více jmen: seznam autorů (odkaz)