Kod tornada

W teorii kodowania kody Tornado są klasą kodów wymazywania , które obsługują korekcję błędów . Kody Tornado wymagają stałego C więcej nadmiarowych bloków niż bardziej efektywne pod względem danych kody wymazywania Reeda-Solomona , ale są znacznie szybsze w generowaniu i mogą szybciej naprawiać wymazywania. Oparte na oprogramowaniu implementacje kodów tornada są około 100 razy szybsze na małych długościach i około 10 000 razy szybsze na większych długościach niż kody kasowania Reeda-Solomona. Od czasu wprowadzenia kodów Tornado pojawiło się wiele innych podobnych kodów kasowania, w szczególności kody online , kody LT i kody Raptor .

Kody Tornado wykorzystują podejście warstwowe. Wszystkie warstwy z wyjątkiem ostatniej używają LDPC , który jest szybki, ale ma szansę na niepowodzenie. Ostatnia warstwa wykorzystuje kod korekcji Reeda-Solomona, który jest wolniejszy, ale optymalny pod względem odzyskiwania po awarii. Kody Tornado określają liczbę poziomów, liczbę bloków odzyskiwania na każdym poziomie oraz rozkład używany do generowania bloków dla warstw niekońcowych.

Przegląd

Dane wejściowe są podzielone na bloki. Bloki to sekwencje bitów o tym samym rozmiarze. Dane odzyskiwania używają tego samego rozmiaru bloku co dane wejściowe. Wymazanie bloku (wejścia lub odzyskania) jest wykrywane w inny sposób. (Na przykład blok z dysku nie przechodzi kontroli CRC lub pakiet sieciowy o danym numerze sekwencyjnym nigdy nie dotarł).

Liczbę bloków naprawczych podaje użytkownik. Następnie określa się liczbę poziomów wraz z liczbą bloków na każdym poziomie. Liczba na każdym poziomie jest określana przez współczynnik B, który jest mniejszy niż jeden. Jeśli jest N bloków wejściowych, pierwszy poziom odzyskiwania ma B*N bloków, drugi ma B*B*N, trzeci ma B*B*B*N i tak dalej.

Wszystkie poziomy odzyskiwania z wyjątkiem ostatniego używają LDPC, który działa na zasadzie xor (exclusive-or). Xor działa na wartościach binarnych, 1s i 0s. Axor B wynosi 1, jeśli A i B mają różne wartości, a 0, jeśli A i B mają te same wartości. Jeśli otrzymałeś wynik (A xor B) i A, możesz określić wartość dla B. (A xor B xor A = B) Podobnie, jeśli masz wynik (A xor B) i B, możesz określić wartość dla A. To rozciąga się na wiele wartości, więc biorąc pod uwagę wynik (A xor B xor C xor D) i dowolne 3 wartości, brakującą wartość można odzyskać.

Tak więc bloki odzyskiwania na poziomie pierwszym to po prostu xor pewnego zestawu bloków wejściowych. Podobnie, każdy z bloków odzyskiwania na poziomie drugim jest xorem jakiegoś zestawu bloków na poziomie pierwszym. Bloki używane w xor są wybierane losowo, bez powtórzeń. Jednak liczba bloków xorowanych w celu utworzenia bloku odzyskiwania jest wybierana z bardzo specyficznego rozkładu dla każdego poziomu.

Ponieważ operacja xor jest operacją szybką, a bloki naprawcze są operacjami xor tylko podzbioru bloków na wejściu (lub na niższym poziomie odzyskiwania), bloki naprawcze można generować szybko.

Ostatnim poziomem jest kod Reeda-Solomona. Kody Reeda-Solomona są optymalne pod względem odzyskiwania po awariach, ale powolne w generowaniu i odzyskiwaniu. Ponieważ każdy poziom ma mniej bloków niż poprzedni, kod Reeda-Solomona ma niewielką liczbę bloków odzyskiwania do wygenerowania i wykorzystania w odzyskiwaniu. Tak więc, mimo że Reed-Solomon jest powolny, ma tylko niewielką ilość danych do przetworzenia.

Podczas odzyskiwania kod Reeda-Solomona jest odzyskiwany jako pierwszy. Gwarantuje to, że zadziała, jeśli liczba brakujących bloków na poziomie przedostatnim jest mniejsza niż liczba bloków obecnych na poziomie końcowym.

Idąc niżej, poziom odzyskiwania LDPC (xor) może być użyty do odzyskania poziomu poniżej niego z dużym prawdopodobieństwem , jeśli wszystkie bloki przywracania są obecne, a na niższym poziomie brakuje co najwyżej C' mniej bloków niż poziom przywracania. Algorytm odzyskiwania polega na znalezieniu bloku przywracania, w którym brakuje tylko jednego zespołu prądotwórczego z niższego poziomu. Wtedy xor bloku odzyskiwania ze wszystkimi obecnymi blokami jest równy brakującemu blokowi.

Kwestie patentowe

Kody Tornado były wcześniej opatentowane w Stanach Zjednoczonych Ameryki. Patenty US6163870 A (złożone 6 listopada 1997) i US 6081909 A (złożone 6 listopada 1997) opisują kody Tornado i wygasły 6 listopada 2017. Patenty US6307487 B1 (złożone 5 lutego 1999) i US6320520 B1 (złożone 17 września 1999 r.) również wspominają o kodach Tornado i wygasły odpowiednio 5 lutego 2019 r. i 17 września 2019 r.

Cytaty

Michael Luby stworzył kody Tornado.

Linki zewnętrzne

Czytelny opis z CMU (PostScript) [1] i inny z Luby w International Computer Science Institute (PostScript) [2] .

Zobacz też

Notatki

M. Mitzenmacher (2004). „Cyfrowe fontanny: ankieta i perspektywa” . proc. 2004 Warsztaty teorii informacji IEEE (ITW) .
M. Luby , M. Mitzenmacher , A. Shokrollahi , D. Spielman , V. Stemann (1997). „Praktyczne kody odporne na straty”. Materiały z dwudziestego dziewiątego dorocznego sympozjum ACM poświęconego teorii informatyki : 150–159. {{ cite journal }} : CS1 maint: wiele nazwisk: lista autorów ( link )
M. Luby , M. Mitzenmacher , A. Shokrollahi (1998). „Analiza procesów losowych za pomocą oceny drzewa i-lub”. Materiały z 9. dorocznego sympozjum ACM-SIAM na temat algorytmów dyskretnych : 364–373. {{ cite journal }} : CS1 maint: wiele nazwisk: lista autorów ( link )